3.2 Iterative elimination of dominated strategies

Iterative elimination of dominated strategies is a powerful tool for simplifying complex games. By removing strategies that are always worse than others, players can focus on the most promising options. This process helps narrow down the game's possibilities.

The technique involves repeatedly identifying and eliminating dominated strategies for each player. As strategies are removed, new domination relationships may emerge. This iterative process continues until no more dominated strategies remain, simplifying the game's analysis.

Dominance and Elimination

Identifying Dominated Strategies

Top images from around the web for Identifying Dominated Strategies

• 

  The Shape of Rational Choices in Game Theory - Dr Tarun Sabarwal, University of Kansas • scipod ... View original

  Is this image relevant?

• 

  The Shape of Rational Choices in Game Theory - Dr Tarun Sabarwal, University of Kansas • scipod ... View original

  Is this image relevant?

1 of 1

Top images from around the web for Identifying Dominated Strategies

• 

  The Shape of Rational Choices in Game Theory - Dr Tarun Sabarwal, University of Kansas • scipod ... View original

  Is this image relevant?

• 

  The Shape of Rational Choices in Game Theory - Dr Tarun Sabarwal, University of Kansas • scipod ... View original

  Is this image relevant?

1 of 1

• Dominated strategies are strategies that always yield lower payoffs than another strategy, regardless of the other player's actions
• Strict dominance occurs when a strategy yields strictly lower payoffs than another strategy for all possible actions of the other player(s)
  • Example: In a game where Player 1 chooses between strategies A and B, if the payoff for A is always higher than B no matter what Player 2 does, then B is strictly dominated by A
• Weak dominance occurs when a strategy yields payoffs that are no higher than another strategy for all possible actions of the other player(s), and strictly lower for at least one action
  • Example: If the payoff for strategy C is always equal to or lower than strategy D, and strictly lower for at least one of Player 2's actions, then C is weakly dominated by D

Iterative Elimination Process

• Iterative elimination is a process of simplifying a game by removing dominated strategies
• Involves sequentially eliminating strictly dominated strategies for each player until no more dominated strategies remain
  • Start by identifying and eliminating any strictly dominated strategies for Player 1
  • Then, identify and eliminate any strictly dominated strategies for Player 2, considering the reduced set of strategies for Player 1
  • Continue this process back and forth until no more strictly dominated strategies can be eliminated
• Sequential elimination refers to performing the iterative elimination process in a specific order, considering each player's strategies one at a time

Game Simplification

Reducing Game Complexity

• Game simplification involves reducing the complexity of a game while preserving its essential strategic structure
• Aims to make the game more manageable and easier to analyze without changing the underlying strategic considerations
• Simplification techniques include eliminating dominated strategies, combining equivalent strategies, and removing redundant players or actions

Reduced Normal Form

• The reduced normal form of a game is a simplified representation obtained by applying game simplification techniques
• Involves removing dominated strategies and combining strategically equivalent strategies
  • Strategically equivalent strategies are those that always yield the same payoffs for all players, regardless of the other players' actions
• The reduced normal form preserves the game's essential strategic structure while presenting it in a more compact and easily analyzable form
  • Example: If two strategies for Player 1 always result in the same payoffs, they can be combined into a single strategy in the reduced normal form

Solution Concepts

Defining Solution Concepts

• A solution concept is a formal rule or criterion used to predict the outcome of a game or to determine the "rational" or "optimal" strategies for players
• Solution concepts provide a framework for analyzing games and determining what strategies players should choose to maximize their payoffs
• Different solution concepts may yield different predictions or recommendations, depending on the assumptions made about player rationality, information, and preferences

Common Solution Concepts

• Nash Equilibrium: A set of strategies, one for each player, such that no player can unilaterally improve their payoff by changing their strategy, given the strategies of the other players
  • Example: In the classic Prisoner's Dilemma game, both players confessing is a Nash Equilibrium, as neither player can improve their outcome by unilaterally changing their strategy
• Dominant Strategy Equilibrium: An equilibrium in which each player plays a dominant strategy (a strategy that yields the highest payoff regardless of other players' actions)
  • Example: In a game where each player has a strictly dominant strategy, the combination of those strategies forms a dominant strategy equilibrium
• Pareto Optimality: A situation in which no player can be made better off without making at least one other player worse off
  • Example: In a coordination game, the outcome where both players choose the highest-payoff action is Pareto optimal, as no other outcome can improve one player's payoff without reducing the other's