IMG_2961A540046A-1.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 all fields of social science, as well as in logic, systems science and computer science. * Originally, it addresse...

# 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 all fields of social science, as well as in logic, systems science and computer science. * Originally, it addressed zero-sum games, in which one person's gains result in losses for the other participant. * Today, game theory applies to a wide range of behavioral relations, and is now an umbrella term for the science of logical decision making in humans, animals, and computers. ## Cooperative vs. Non-Cooperative * **Cooperative game theory**: players cooperate to optimize their payoff. * **Non-cooperative game theory**: players cannot commit to cooperate. ## What is a Game? A game consists of the following: 1. A set of players 2. A set of rules governing the possible moves 3. A set of outcomes for each possible combination of moves 4. A specification of payoffs for each player for each outcome ### Example: Prisoner's Dilemma * Two suspects are arrested and held in separate cells. * They cannot communicate with each other. * The authorities do not have enough evidence to convict the pair on the principal charge. * They hope to induce both prisoners to betray each other. **Rules:** If they both remain silent, they will both be convicted of a minor charge and sentenced to only one year in prison. If only one betrays the other, he will be freed and used as a witness against the other, who will receive the maximum term of ten years. If both betray each other, they will both be sentenced to five years in prison. **Outcomes:** The number of years in prison **Payoffs:** (Maximize your payoff = minimize the years in prison) can be represented in a matrix (*payoff matrix*) | | **Prisoner B Remains Silent** | **Prisoner B Betrays** | | :---------- | :----------------------------- | :--------------------- | | **Prisoner A Remains Silent** | -1, -1 | -10, 0 | | **Prisoner A Betrays** | 0, -10 | -5, -5 | ## Nash Equilibrium * A **Nash Equilibrium** is a set of strategies, one for each player, such that no player has incentive to unilaterally change his action. Players are in equilibrium if a change in strategy by any one of them would lead that player to earn less than if she remained with her current strategy. * More formally, a set of strategies ${s_1, s_2,..., s_n}$ is a Nash Equilibrium if, for every player $i$, $s_i$ is player $i$'s best response to the strategies specified for all other players. * $s_i$ is player $i$'s best response to the strategies specified for all other players: $s_i \in \mathop{\mathrm{argmax}}_{s \in S_i} u_i(s_i, s_{-i})$ * $s_{-i}$: strategies of all players except player $i$ * $S_i$: set of possible strategies for player $i$ * $u_i$: player $i$'s utility function ### Example: Prisoner's Dilemma | | Prisoner B Remains Silent | Prisoner B Betrays | | :---------- | :------------------------ | :----------------- | | Prisoner A Remains Silent | -1, -1 | -10, 0 | | Prisoner A Betrays | 0, -10 | -5, -5 | * If Prisoner B remains silent, Prisoner A's best response is to betray ($0 > -1$). * If Prisoner B betrays, Prisoner A's best response is to betray ($-5 > -10$). * $\implies$ No matter what Prisoner B does, Prisoner A's best response is to betray. * By symmetry, betray is also Prisoner B's best response, no matter what Prisoner A does * $\implies$ (Betray, Betray) is the only Nash Equilibrium ## Pareto Optimality An outcome of a game is **Pareto Optimal** if there is no other outcome that makes at least one player better off without making any player worse off. ### Example 1: Prisoner's Dilemma | | Prisoner B Remains Silent | Prisoner B Betrays | | :---------- | :------------------------ | :----------------- | | Prisoner A Remains Silent | -1, -1 | -10, 0 | | Prisoner A Betrays | 0, -10 | -5, -5 | * (Remain Silent, Remain silent) is Pareto Optimal. * (Betray, Betray) is not Pareto Optimal. * Nash Equilibrium is not always Pareto Optimal. ### Example 2 | | Option A | Option B | | :---------- | :------- | :------- | | Player A | 1, 2 | 0, 0 | | Player B | 0, 0 | 2, 1 | * All outcomes are Pareto Optimal. * No Nash Equilibrium. ## Mechanism Design * **Mechanism design** is a field in economics and game theory that takes an *objective-first* approach to designing economic mechanisms or incentives, towardsdesired goal, in strategic settings, where players act rationally. * Mechanism design studies how to implement a desired social goal when players have private information. ### Example: Cake Cutting * How do you divide a cake between two people such that each person thinks they received at least half of the cake? * **Solution:** One person cuts the cake into two pieces, and the other person chooses which piece they want. * This mechanism is **strategy-proof**, meaning that it is in each player's best interest to act truthfully. ## Algorithmic Mechanism Design * **Algorithmic mechanism design** is a field that combines algorithm design and mechanism design to design algorithms that are efficient and strategy-proof. * In algorithmic mechanism design, the goal is to design a mechanism that is both computationally efficient and incentivizes players to act truthfully. * The main focus is on settings where the mechanism must be implemented by a computer algorithm, and where the players' strategies may depend on the algorithm used. ### Example: Vickrey Auction * In a **Vickrey auction**, bidders submit sealed bids, and the highest bidder wins but pays the second-highest bid. * Vickrey auction is **truthful**, meaning that it is in each player's best interest to bid their true value. * Vickrey auction is also **efficient**, meaning that it allocates the item to the bidder who values it the most. * Vickrey auction is not always **budget-balanced**, meaning that the auctioneer may have to pay money to the bidders.