IMG_2081.HEIC

# Algorithmic Game Theory ## What is Game Theory? * **Strategic Decisions:** A way to mathematically formalize strategic decision making. * **Multi-Agent Interactions:** Situations where multiple agents interact, and the actions of one agent affects the others. * **Rationality Assumption:**...

# Algorithmic Game Theory ## What is Game Theory? * **Strategic Decisions:** A way to mathematically formalize strategic decision making. * **Multi-Agent Interactions:** Situations where multiple agents interact, and the actions of one agent affects the others. * **Rationality Assumption:** Agents are assumed to be rational and act in their own best interests. * **Applications:** Economics, political science, computer science, biology, etc. ## Example: The Prisoner's Dilemma Two suspects are arrested for a crime. They are held in separate cells and cannot communicate. The police offer each of them a deal: * If one confesses and the other does not, the confessor goes free, and the other gets 10 years in prison. * If both confess, they each get 5 years in prison. * If neither confesses, they each get 1 year in prison. ### Payoff Matrix | | Suspect B Confesses | Suspect B Stays Silent | | :---------- | :------------------ | :--------------------- | | **A Confesses** | (-5, -5) | (0, -10) | | **A Stays Silent** | (-10, 0) | (-1, -1) | ### The Dilemma * **Individual Rationality:** Each suspect is better off confessing, regardless of what the other does. * **Collective Irrationality:** If both confess, they are both worse off than if they had both stayed silent. ## Algorithmic Game Theory * **Intersection:** The intersection of game theory and algorithm design. * **Computational Issues:** Addresses the computational issues that arise in game theory. * **Algorithm Design:** Uses game-theoretic ideas to design better algorithms. ### Key Topics * **Computing Equilibria:** Developing algorithms to find Nash equilibria and other solution concepts. * **Mechanism Design:** Designing games or protocols to achieve desired outcomes. * **Price of Anarchy:** Quantifying the inefficiency that results from selfish behavior. ## Nash Equilibrium * **Definition:** A set of strategies, one for each player, such that no player has an incentive to unilaterally deviate. * **Formal Definition:** A strategy profile $s = (s_1, s_2,..., s_n)$ is a Nash equilibrium if for every player $i$ and every alternative strategy $s'_i$, $u_i(s_i, s_{-i}) \geq u_i(s'_i, s_{-i})$ where: * $s_i$ is the strategy of player i. * $s_{-i}$ is the vector of strategies of all players except i. * $u_i$ is the utility function of player i. ### Example: Rock-Paper-Scissors * **Mixed Strategy:** Players randomize their actions. * **Nash Equilibrium:** Each player plays each action with equal probability (1/3). ## Mechanism Design * **Goal:** Designing the rules of a game to achieve a desired outcome, even when players act selfishly. * **Examples:** * Auctions: Design an auction to maximize revenue or allocate resources efficiently. * Voting Systems: Design a voting system to elect the candidate that best represents the preferences of the voters. ### VCG (Vickrey-Clarke-Groves) Mechanism * **Truthfulness:** Players are incentivized to reveal their true preferences. * **Social Welfare Maximization:** The mechanism selects the outcome that maximizes the sum of the players' utilities. ## Price of Anarchy (PoA) * **Definition:** A measure of how much the social welfare degrades due to selfish behavior. * **Formula:** $PoA = \frac{\text{Social Welfare in the Worst Nash Equilibrium}}{\text{Optimal Social Welfare}}$ * **Interpretation:** The higher the PoA, the greater the inefficiency. ### Example: Braess's Paradox * **Adding a road:** Adding a road to a network can sometimes increase the travel time for everyone. * **Selfish Routing:** If drivers choose their routes selfishly, the resulting equilibrium can be worse than if some roads were closed.