Immune Disorders Unit Jeneral Hospital.jpeg

# Algorithmic Game Theory ## What is Algorithmic Game Theory? * **Game Theory**: studies strategic interactions between rational players. * **Algorithm Design**: How to design efficient algorithms that compute solutions. ### **Challenges** * **Game Theory**: Assumes players can compute opt...

# Algorithmic Game Theory ## What is Algorithmic Game Theory? * **Game Theory**: studies strategic interactions between rational players. * **Algorithm Design**: How to design efficient algorithms that compute solutions. ### **Challenges** * **Game Theory**: Assumes players can compute optimal strategies but does not consider the computational complexity of doing so. * **Algorithm Design**: Ignores the strategic behavior of participants. ### **Algorithmic Game Theory** * Lying at the intersection of computer science and game theory, algorithmic game theory (AGT) uses algorithm design and analysis to predict behavior in strategic settings. * It Designs strategy-proof mechanisms so that selfish behavior yields desirable outcomes. ## **Topics** ### **Solution Concepts** * **Nash Equilibrium**: A set of strategies (one for each player) in which no player can improve their payoff by unilaterally changing their strategy. * How hard is it to compute a Nash Equilibrium? ### **Mechanism Design** * How should we design the rules of a game to ensure that, when each player acts in their best interest, the outcome is socially desirable? * **Auctions**: Google and Yahoo! sell advertisement slots via auctions. * How should they design the auction to maximize revenue? * **Social Choice**: When is it possible to design a voting rule that accurately reflects the preferences of the voters? ### **Price of Anarchy** * How inefficient is selfish behavior? * **Braess's Paradox**: Adding a road to a network can increase the average travel time for all users due to selfish routing. ### **Fair Division** * How to fairly divide resources among multiple players with different preferences. * **Cake Cutting**: How to divide a cake among several people such that everyone feels they have received a fair share. ## **Selfish Routing (Price of Anarchy)** ### **The Model** * A network of $n$ players who want to travel from a source $s$ to a destination $t$. * Each edge $e$ has a cost/latency function $l_e(x)$ that depends on the amount of traffic $x$ on that edge. * Each player wants to minimize their travel time. ### **The Question** * How much does selfish routing increase the total travel time compared to the optimal (centrally enforced) routing? ### **Braess's Paradox** * Adding a road to a network can increase the total travel time for all players.  * **Left**: 100 players want to travel from S to E. The total cost is 1.5 for everyone. * **Right**: A new road with cost 0 is added from A to B. Everyone will use the path S $\rightarrow$ A $\rightarrow$ B $\rightarrow$ E, with a total cost of 2. ### **The Price of Anarchy (PoA)** * The Price of Anarchy is the ratio between the cost of the worst-case Nash Equilibrium and the cost of the optimal solution. $$ PoA = \frac{\text{Cost of worst-case Nash Equilibrium}}{\text{Cost of optimal solution}} $$ ### **Theorem** * If all latency functions are linear, the Price of Anarchy is at most $\frac{4}{3}$. ### **Proof Idea** * Let $f$ be a flow at Nash Equilibrium, and $f^*$ be the optimal flow. * Consider a flow that is a mixture of $f$ and $f^*$: $f_t = (1-t)f + tf^*$, for $t \in [0,1]$. * Show that the cost of $f_t$ is a convex function of $t$, and its derivative at $t = 0$ is non-negative. * Use this to bound the cost of $f$ in terms of the cost of $f^*$. ## **Mechanism Design** ### **Mechanism Design** * How to design the rules of a game to ensure that, when each player acts in their best interest, the outcome is socially desirable? ### **Auctions** * **Goal**: Sell an item to one of $n$ bidders. * Each bidder $i$ has a private value $v_i$ for the item. * The auctioneer wants to maximize revenue. ### **Desiderata** * **Efficiency**: The item should be allocated to the bidder with the highest value. * **Individual Rationality**: Each bidder should be guaranteed non-negative utility. * **Truthfulness**: Each bidder should maximize their utility by bidding their true value. ### **Vickrey-Clarke-Groves (VCG) Mechanism** * Allocate the item to the bidder with the highest bid. * Charge each bidder the "externality" they impose on the other bidders. * Specifically, the winner $i$ pays the second highest bid. * This is a truthful mechanism that maximizes social welfare. ### **Theorem** * The VCG mechanism is truthful: bidding your true value is a dominant strategy. ### **Proof Idea** * Consider bidder $i$. Let $b_{-i}$ be the highest bid among the other bidders. * If $v_i > b_{-i}$, then bidder $i$ wants to win the item and pay $b_{-i}$. Bidding $v_i$ ensures this. * If $v_i < b_{-i}$, then bidder $i$ does not want to win the item. Bidding $v_i$ ensures this. ## **Cake Cutting (Fair Division)** ### **Cake Cutting** * How to divide a cake among $n$ players such that everyone feels they have received a fair share, where each player may have a different idea of what constitutes a fair share. ### **The Model** * The cake is represented by the interval $[0,1]$. * Each player $i$ has a valuation function $V_i$ that assigns a value to each subinterval of the cake. * We assume that $V_i([0,1]) = 1$ for all players $i$. ### **Fairness Notions** * **Proportionality**: Each player receives a piece of the cake that they value at least $\frac{1}{n}$. * **Envy-freeness**: No player prefers another player's piece of the cake to their own. * **Pareto Optimality**: It is impossible to make one player better off without making another player worse off. ### **Challenges** * How to design algorithms that compute fair allocations, especially when the number of players is large. ### **The Dubins-Spanier Algorithm** * For two players, the Dubins-Spanier algorithm guarantees a proportional division. * One player cuts the cake in half according to their valuation, and the other player chooses which piece they want. ### **The Selfridge-Conway Algorithm** * For three players, the Selfridge-Conway algorithm guarantees an envy-free division. * The algorithm is more complex but guarantees that no player envies another player's piece. ### **Open Problems** * Can we design efficient algorithms that compute envy-free divisions for $n$ players? * What other fairness notions are possible and desirable?