Multi-Agent Systems

Static Games

1. Rationalizable Strategies

• Multi-agent decision problems differ from single-agent problems as the utility for an agent depends on the strategies of other agents. These settings are termed as games, starting with two-player games.
  • Each player selects a strategy and receives a payoff based on both players' strategies.

1.1 Examples

• Prisoner's Dilemma
  • Two criminals are offered a bargain to testify against each other. Various outcomes based on confessions:
    • Both confess: 2 years in prison each.
    • One confesses: Confessor goes free, the other receives 10 years.
    • Neither confesses: 1 year each.
• Battle of the Sexes
  • A couple prefers different events but wants to attend the same one.
• Chicken (Hawk-Dove)
  • Two drivers head towards each other; the first to swerve is termed chicken.
• Matching Pennies
  • Players reveal penny positions; if they match, player 1 wins, otherwise player 2 wins.

1.2 Modeling Strategic Games

• Definition of Strategic Game:
  • Described by a tuple ( \mathscr{G} = \langle N, (\ALPHABET S_i){i \in N}, (u_i){i \in N} \rangle )
  • (N) is a set of players, (\ALPHABET S_i) is a set of strategies for player (i), and (u_i) is the utility function of player (i).
• Finite games
  • Games with finite strategy sets can be represented with a matrix.

1.3 Dominated Strategies

• Dominance Definition:
  • Strategy (s_i) strictly dominates (t_i) if it yields a higher utility for all opposing strategies.
  • A dominant strategy is one that dominates all others.
• Assumption:
  • Rational players will not choose strictly dominated strategies.

1.4 Dominant Strategy Equilibrium

• Dominant Strategy Equilibrium:
  • A strategy profile where each player plays a dominant strategy.
  • Example: In the Prisoner's Dilemma, both choose to confess as it's a dominant strategy.

1.5 Rationalizable Equilibrium

• Common Knowledge of Rationality:
  • All players are assumed to be rational, and this is common knowledge.
• Iterative Elimination of Dominated Strategies (IEDS):
  • Eliminate strictly dominated strategies iteratively.

1.6 Iterative Elimination of Weakly Dominated Strategies

• IEWDS (Iterative Elimination of Weakly Dominated Strategies):
  • Similar to IEDS but for weakly dominated strategies.
  • Order of elimination can affect the outcome.

1.7 Second Price Auction

• Rationalizable Strategy in Auctions:
  • In sealed bid second-price auctions, bidding truthfully is rationalizable as it weakly dominates other strategies.

1.8 Dominance by Mixed Strategies

• Mixed Strategy:
  • A probability distribution over pure strategies.
  • Can be used to extend elimination concepts.

1.9 Cournot Competition

• Oligopoly Market Model:
  • Firms choose production levels; prices depend on total production.
  • Use elimination of never-best response strategies to find equilibrium.

1.10 Beyond Rationalizable Strategies: Maxmin Strategies

• Maxmin Strategies:
  • Determine the minimum payoff a player can guarantee and choose a strategy to maximize this minimum.

1.11 Relation Between Maxmin Strategies and Dominant Strategies

• Theorems:
  • Dominant strategies are also maxmin strategies.
  • Strictly dominant strategy equilibrium is the unique vector of maxmin strategies.

Exercises

• Practice finding solutions using iterative elimination and identifying maxmin strategies.

Note: This summary provides a high-level overview of strategic games and the theories surrounding rationalizable and dominant strategies, using examples to illustrate key concepts.