WhatsApp Image 2025-04-06 at 15.28.07.jpeg

# Algorithmic Game Theory ## What is Game Theory? Game theory is the study of mathematical models of strategic interactions among rational agents. It has applications in many fields, including: * Economics * Political Science * Biology * Computer Science ### Key Concepts * **Players**...

# Algorithmic Game Theory ## What is Game Theory? Game theory is the study of mathematical models of strategic interactions among rational agents. It has applications in many fields, including: * Economics * Political Science * Biology * Computer Science ### Key Concepts * **Players**: Individuals or entities making decisions. * **Strategies**: A plan of action that a player takes. * **Payoffs**: The outcome a player receives after all players have executed their strategies. * **Rationality**: Players act in their best interest to maximize their payoffs. ## Normal-Form Games A normal-form game, also known as a strategic game, is a representation of a game where the players simultaneously choose their actions. ### Definition A normal-form game is defined by: * A set of players: $N = {1, 2,..., n}$ * For each player $i$, a set of strategies: $S_i$ * For each player $i$, a payoff function: $u_i: S_1 \times S_2 \times... \times S_n \rightarrow \mathbb{R}$ ### Example: Prisoner's Dilemma | | Player 2: Cooperate | Player 2: Defect | | :---------- | :------------------ | :--------------- | | Player 1: Cooperate | -1, -1 | -3, 0 | | Player 1: Defect | 0, -3 | -2, -2 | ## Solution Concepts A solution concept is a prediction of how the game will be played. ### Dominant Strategy A strategy $s_i \in S_i$ is a dominant strategy if it yields the highest payoff for player $i$ regardless of the other players' strategies. ### Nash Equilibrium A Nash Equilibrium is a set of strategies, one for each player, such that no player can improve their payoff by unilaterally changing their strategy. Formally, $(s_1, s_2,..., s_n)$ is a Nash Equilibrium if for all players $i$ and for all strategies $s'_i \in S_i$: $u_i(s_i, s_{-i}) \geq u_i(s'_i, s_{-i})$ Where $s_{-i}$ denotes the strategies of all players except player $i$. ### Example: Finding Nash Equilibrium Consider the following game: | | Player 2: A | Player 2: B | | :---------- | :---------- | :---------- | | Player 1: A | 2, 1 | 0, 0 | | Player 1: B | 1, 2 | 3, 1 | Nash Equilibria: (B, A) and (A, B) ## Algorithmic Considerations * **Computational Complexity**: Finding Nash Equilibria in complex games can be computationally hard (e.g., PPAD-complete). * **Algorithms**: Develop algorithms to find or approximate Nash Equilibria. * **Mechanism Design**: Designing games to achieve desired outcomes. ## Extensive-Form Games An extensive-form game specifies the order of moves, the players' choices at each move, the information they have, and the payoffs. ### Definition An extensive-form game includes: * A set of players * A game tree * Information sets * Payoffs ### Example: Ultimatum game Player 1 proposes how to divide a sum of money. Player 2 can accept or reject. If Player 2 accepts, the money is divided as proposed. If Player 2 rejects, both players get nothing. ## Coalitional Game Theory Focuses on the behavior of groups of players (coalitions) and how they can achieve better outcomes by cooperating. ### Key Concepts * **Coalition**: A subset of players. * **Characteristic Function**: Defines the value a coalition can achieve. * **Core**: A stable set of payoff distributions that no coalition can improve upon by acting on its own. ## Mechanism Design Designing the rules of a game to achieve a specific outcome, even when players act strategically. ### Key Concepts * **Social Choice Function**: A function that maps player preferences to a collective decision. * **Incentive Compatibility**: Ensuring that players have an incentive to reveal their true preferences. * **Vickrey Auction**: A sealed-bid auction where the highest bidder wins but pays the second-highest bid, which is an example of incentive-compatible mechanism.