3.2 Iterative elimination of dominated strategies
3 min read•august 7, 2024
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 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 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
- 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
- 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 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
- : 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
- : 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
- : 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
Key Terms to Review (16)
Dominant Strategy Equilibrium: Dominant strategy equilibrium occurs when each player's strategy is optimal, given the strategies chosen by other players. In this situation, players have a dominant strategy that yields the best outcome regardless of what opponents do. This equilibrium concept is vital in understanding how players make decisions, particularly in contexts involving strictly and weakly dominant strategies as well as the iterative elimination of dominated strategies.
Dominated Strategy: A dominated strategy is a choice in game theory that is worse than another strategy available to a player, regardless of what the other players do. This means that there exists at least one other strategy that always provides a higher payoff, making the dominated strategy less appealing. Identifying dominated strategies helps in simplifying games by allowing players to discard inferior options and focus on more optimal choices.
Extensive form game: An extensive form game is a representation of a strategic situation that allows players to make decisions at various points in time, depicted through a tree-like structure that illustrates the sequence of moves, choices, and potential outcomes. This format helps analyze strategies in situations where timing and order of moves matter, connecting key concepts like backward induction, sequential rationality, and subgame perfect equilibrium, while also illustrating credible threats and promises as well as the iterative elimination of dominated strategies.
Game simplification: Game simplification is the process of reducing the complexity of a strategic game by eliminating unnecessary elements, such as dominated strategies, to make analysis and decision-making easier. This process helps players focus on the most relevant strategies, ultimately leading to clearer insights and more efficient outcomes in strategic interactions.
Iterative Elimination: Iterative elimination is a method used in game theory to systematically remove dominated strategies from consideration in a game. This process helps simplify the analysis of strategic interactions by focusing on strategies that are more likely to be played, thus narrowing down the possible outcomes and aiding in finding equilibrium points in games.
Nash Equilibrium: Nash Equilibrium is a concept in game theory where no player can benefit by unilaterally changing their strategy if the strategies of the other players remain unchanged. This means that each player's strategy is optimal given the strategies of all other players, resulting in a stable outcome where players have no incentive to deviate from their chosen strategies.
Normal Form Game: A normal form game is a representation of a strategic interaction between players, where each player's strategies and corresponding payoffs are displayed in a matrix format. This setup allows players to analyze their choices and anticipate the decisions of others, leading to various outcomes based on the players' strategies. Understanding this concept is crucial as it forms the basis for analyzing credible threats and promises, as well as determining optimal strategies through processes like iterative elimination of dominated strategies.
Pareto Optimality: Pareto optimality is a state in which resources are allocated in a way that no individual can be made better off without making someone else worse off. It represents an efficient distribution of resources where any change to improve one person's situation would detriment another's, highlighting the balance of benefits among all participants involved. This concept plays a vital role in analyzing strategic interactions, especially when considering dominated strategies and potential outcomes.
Payoff Matrix: A payoff matrix is a table that shows the payoffs or outcomes for each player in a game, given all possible combinations of strategies chosen by the players. It visually represents the choices available to players and their potential results, making it essential for analyzing strategic interactions in various types of games.
Rationalizability: Rationalizability is a concept in game theory that refers to the idea that players make decisions based on their beliefs about other players' strategies, assuming that everyone is rational and has common knowledge of rationality. This concept emphasizes that a player's choice can be justified by a belief that others are also making rational choices, leading to the formation of an equilibrium. It connects to several important ideas in strategic interactions, including the implications of strategy choices, the cognitive processes behind decision-making, and the iterative reasoning involved in eliminating non-viable options.
Reduced Normal Form: Reduced normal form is a simplified representation of a game in normal form, where dominated strategies have been eliminated from consideration. This approach allows players to focus on the strategies that remain relevant and likely to influence the outcome of the game, making it easier to analyze strategic interactions. By reducing the normal form, players can identify equilibrium points more efficiently, leading to better strategic decision-making.
Sequential Elimination: Sequential elimination is a method used in game theory where dominated strategies are removed step-by-step from consideration, refining the strategy set for players. This process helps to simplify complex strategic interactions by focusing on the remaining strategies that could potentially be optimal, ensuring that only viable choices are considered in decision-making.
Strategy Profile: A strategy profile is a complete description of the strategies chosen by each player in a game, detailing what action each player will take in every possible situation they may encounter. This concept is crucial as it helps analyze the overall outcome of strategic interactions and assists in determining the equilibrium points within various game formats. Understanding strategy profiles is essential for evaluating decision-making processes, especially when converting between different game representations or analyzing equilibria in games with incomplete information.
Strictly Dominated: A strategy is strictly dominated when there exists another strategy that always provides a better payoff, regardless of what the opponents choose. Understanding strictly dominated strategies is key in simplifying strategic interactions, as they can be eliminated from consideration in decision-making processes, leading to more efficient outcomes.
Utility Maximization: Utility maximization is the principle that individuals or players aim to achieve the highest level of satisfaction or benefit from their choices, given their preferences and constraints. This concept ties closely to the idea of players making strategic decisions based on available options, the anticipated payoffs of these options, and a rational assessment of their preferences.
Weakly dominated: A strategy is considered weakly dominated if there exists another strategy that performs at least as well in all possible scenarios and strictly better in at least one scenario. This concept helps to identify strategies that are never the best choice, which is essential for simplifying decision-making processes in games.