Game Theory and Mechanism Design

Introduction

When multiple agents' goals are not fully aligned, game theory provides a mathematical framework for analyzing their strategic interactions. Mechanism design studies how to craft rules and incentives so that self-interested agents pursuing their own interests also achieve globally optimal outcomes.

Game Theory Fundamentals

Basic Elements of a Game

A game \(G\) consists of the following elements:

• Players: \(N = \{1, 2, ..., n\}\)
• Strategy Space: Each player \(i\)'s strategy set \(S_i\)
• Utility Function: \(u_i: S_1 \times S_2 \times ... \times S_n \rightarrow \mathbb{R}\)

Nash Equilibrium

A Nash Equilibrium is a strategy profile \((s_1^*, s_2^*, ..., s_n^*)\) in which no player can improve their payoff by unilaterally changing their strategy:

\[u_i(s_i^*, s_{-i}^*) \geq u_i(s_i, s_{-i}^*) \quad \forall i \in N, \forall s_i \in S_i\]

where \(s_{-i}^*\) denotes the strategy profile of all players except player \(i\).

Classic Game Examples

Prisoner's Dilemma

	B Cooperate	B Defect
A Cooperate	(-1, -1)	(-3, 0)
A Defect	(0, -3)	(-2, -2)

Nash Equilibrium: (Defect, Defect), but (Cooperate, Cooperate) is Pareto optimal.

Agent scenario: Should two agents share information? Selfishly withholding information (defect) is short-term optimal, but sharing (cooperate) is better for the whole.

Coordination Game

	B Choose Plan A	B Choose Plan B
A Choose Plan A	(2, 2)	(0, 0)
A Choose Plan B	(0, 0)	(1, 1)

Two Nash Equilibria: (A, A) and (B, B). The key challenge is coordination.

Agent scenario: Multiple agents need to choose a consistent tool or standard.

Mixed Strategy Nash Equilibrium

When no pure strategy Nash Equilibrium exists, agents choose strategies according to a probability distribution:

\[\sigma_i: S_i \rightarrow [0, 1] \quad \text{where} \sum_{s_i \in S_i} \sigma_i(s_i) = 1\]

Expected utility:

\[U_i(\sigma_i, \sigma_{-i}) = \sum_{s \in S} \left(\prod_{j} \sigma_j(s_j)\right) u_i(s)\]

Cooperative Games

Shapley Value

In cooperative games, the Shapley value fairly measures each participant's contribution:

\[\phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!(n-|S|-1)!}{n!} \left[ v(S \cup \{i\}) - v(S) \right]\]

where:

• \(v(S)\) is the value function of coalition \(S\)
• \(n\) is the total number of participants
• The summation is over all coalitions not containing \(i\)

Agent scenario: Evaluating each agent's contribution to the final outcome.

from itertools import combinations
import math

def shapley_value(n_agents, value_function):
    """Compute the Shapley value for each agent"""
    shapley = [0.0] * n_agents
    agents = list(range(n_agents))

    for i in agents:
        others = [j for j in agents if j != i]

        for size in range(len(others) + 1):
            for coalition in combinations(others, size):
                coalition_set = set(coalition)

                # Marginal contribution
                marginal = (
                    value_function(coalition_set | {i}) -
                    value_function(coalition_set)
                )

                # Shapley weight
                weight = (
                    math.factorial(size) * 
                    math.factorial(n_agents - size - 1) /
                    math.factorial(n_agents)
                )

                shapley[i] += weight * marginal

    return shapley

# Example: 3 agents cooperating on a task
def value_function(coalition):
    """Coalition value"""
    if len(coalition) == 0: return 0
    if len(coalition) == 1: return 30    # Working alone
    if len(coalition) == 2: return 80    # Two cooperating
    if len(coalition) == 3: return 120   # Three cooperating
    return 0

values = shapley_value(3, value_function)
print(f"Shapley values for each agent: {values}")
# Each agent receives a fair share of the contribution

Mechanism Design

Objectives

Design the rules of the game (mechanism) such that:

1. Incentive Compatible: Truthful reporting is the optimal strategy
2. Individually Rational: Participation is better than non-participation
3. Efficient: Achieves the socially optimal outcome

Auction Mechanisms

English Auction

Open bidding, highest bidder wins:

async def english_auction(item, agents, starting_price=0, increment=1):
    current_price = starting_price
    current_winner = None
    active_bidders = set(agents)

    while len(active_bidders) > 1:
        new_bids = []
        for agent in active_bidders:
            bid = await agent.decide_bid(item, current_price + increment)
            if bid:
                new_bids.append((agent, bid))
            else:
                active_bidders.discard(agent)

        if new_bids:
            best = max(new_bids, key=lambda x: x[1])
            current_winner = best[0]
            current_price = best[1]

    return current_winner, current_price

Vickrey Auction (Second-Price Auction)

Sealed bids; the highest bidder wins but pays only the second-highest price. This encourages truthful bidding.

async def vickrey_auction(item, agents):
    """Vickrey auction: highest bidder wins, pays second-highest price"""
    bids = []
    for agent in agents:
        bid = await agent.private_valuation(item)
        bids.append((agent, bid))

    bids.sort(key=lambda x: x[1], reverse=True)

    winner = bids[0][0]
    price = bids[1][1]  # Pay the second-highest price

    return winner, price

Why the Vickrey auction is incentive compatible: Bidding one's true valuation is a dominant strategy---overbidding may win but at a loss, while underbidding may miss a profitable opportunity.

Dutch Auction

Starts from a high price and decreases; the first to accept wins.

VCG Mechanism (Vickrey-Clarke-Groves)

The VCG mechanism is a generalization of the Vickrey auction. Each participant pays a fee equal to the externality their participation imposes on others:

\[p_i = \sum_{j \neq i} v_j(o_{-i}^*) - \sum_{j \neq i} v_j(o^*)\]

where \(o^*\) is the socially optimal outcome and \(o_{-i}^*\) is the optimal outcome without participant \(i\).

Applications in Agent Systems

Task Allocation via Mechanism Design

class TaskAllocationMechanism:
    """Mechanism design-based task allocation"""

    async def allocate(self, tasks, agents):
        """Allocate tasks using the VCG mechanism"""
        allocations = {}

        for task in tasks:
            # 1. Each agent reports its cost to complete the task
            costs = {}
            for agent in agents:
                costs[agent.id] = await agent.report_cost(task)

            # 2. Select the lowest-cost agent
            winner_id = min(costs, key=costs.get)

            # 3. Compute VCG payment (incentivizes truthful reporting)
            # Payment = second-lowest cost (similar to Vickrey auction)
            sorted_costs = sorted(costs.values())
            payment = sorted_costs[1] if len(sorted_costs) > 1 else sorted_costs[0]

            allocations[task.id] = {
                "agent": winner_id,
                "payment": payment,
                "reported_cost": costs[winner_id],
            }

        return allocations

Multi-Agent Credit Assignment

Using Shapley values to evaluate agent contributions and allocate rewards:

class CreditAssignment:
    def __init__(self, agents):
        self.agents = agents
        self.performance_history = []

    async def evaluate_and_assign(self, task_result, participation):
        """Evaluate each agent's contribution and assign credit"""
        # Record performance of different agent combinations
        overall_score = evaluate_quality(task_result)

        # Compute Shapley values
        def value_fn(coalition):
            if not coalition:
                return 0
            # Estimate coalition value using historical data
            return self.estimate_coalition_value(coalition)

        credits = shapley_value(len(self.agents), value_fn)

        return {
            agent.id: credit 
            for agent, credit in zip(self.agents, credits)
        }

Debate Mechanisms

Using game theory to design debate rules that ensure quality:

class DebateMechanism:
    """Game theory-based debate mechanism"""

    def __init__(self):
        self.reputation = {}  # Agent reputation scores

    async def structured_debate(self, topic, pro_agent, con_agent, judge):
        # Rule design:
        # 1. Word limit per round (prevents information flooding)
        # 2. Must cite evidence (improves quality)
        # 3. Reputation system (long-term incentive for honest argumentation)

        history = []
        for round in range(3):
            pro_arg = await pro_agent.argue(topic, history, max_tokens=500)

            # Verify argument quality
            quality = await judge.evaluate_argument(pro_arg)
            self.update_reputation(pro_agent, quality)

            con_arg = await con_agent.argue(topic, history, max_tokens=500)
            quality = await judge.evaluate_argument(con_arg)
            self.update_reputation(con_agent, quality)

            history.extend([pro_arg, con_arg])

        return await judge.verdict(topic, history)

Social Choice Theory

Arrow's Impossibility Theorem

No voting rule can simultaneously satisfy all of the following conditions:

1. Pareto efficiency: If everyone prefers A > B, then the collective preference is A > B
2. Non-dictatorship: No single person can unilaterally determine the outcome
3. Independence of irrelevant alternatives: The collective ranking of A vs B depends only on individual rankings of A vs B

Implications for agent systems: Multi-agent voting systems cannot simultaneously satisfy all "fairness" conditions; trade-offs among different properties are necessary.

Further Reading

• Tree Search and Monte Carlo - Game search methods
• Nash, J. (1950). "Equilibrium points in n-person games"
• Shapley, L. S. (1953). "A value for n-person games"
• Nisan, N., et al. (2007). "Algorithmic Game Theory"

---

评论