IMG_0707.jpeg

# Algorithmic Game Theory ## What is Game Theory? * **Standard definition:** the study of mathematical models of strategic interactions among rational agents. * **My definition:** the study of interactions in multi-agent systems. * Each agent has their own agenda. * Outcome depends...

# Algorithmic Game Theory ## What is Game Theory? * **Standard definition:** the study of mathematical models of strategic interactions among rational agents. * **My definition:** the study of interactions in multi-agent systems. * Each agent has their own agenda. * Outcome depends on the actions of all agents. ## Example: The Hotelling Game ### Setting * A street of length 1. * A population of consumers evenly distributed on the street. * Two vendors choose where to locate. * Each consumer goes to the closer vendor. * **Goal:** Each vendor wants to maximize the number of consumers who come to them. ### Questions * If the vendors choose locations simultaneously, where will they locate? * Both locate in the middle * If vendor 1 chooses first, and then vendor 2, where will they locate? * Vendor 1 in the middle, vendor 2 next to vendor 1 * What if there are 3 vendors? * No equilibrium * What if consumers are not evenly distributed? ## Example: The Braess Paradox ### Setting * A traffic network. * Each edge has a cost that depends on the amount of traffic on the edge. * Goal: Send 1 unit of traffic from s to t, minimizing the total cost. ### Instance 1 * $c_1(x) = x$, $c_2(x) = x$, $c_3(x) = 1$, $c_4(x) = 1$ * Cost: 2 ### Instance 2 * Add a free edge from the middle of the top path to the middle of the bottom path. * All traffic goes $s \rightarrow a \rightarrow b \rightarrow t$. * Cost: 2 ## What is Algorithmic Game Theory? * **Definition:** the study of the intersection of game theory and algorithm design. * **Two directions:** * Use algorithm design to improve game-theoretic solutions. * Use game theory to address problems in algorithm design. ## Examples of AGT * **Mechanism design:** * How should we design the rules of an auction to maximize revenue? * How should we design a voting system to get "good" outcomes? * **Price of anarchy:** * How much efficiency is lost due to selfish behavior? * How can we quantify the cost of not having a central authority? * **Fair division:** * How can we divide a set of resources among a set of agents in a fair way? * Each agent has different preferences. * **Learning in games:** * How do agents learn to play games in a repeated setting? * Do they converge to an equilibrium? * **Computing equilibria:** * How hard is it to compute a Nash equilibrium? * Can we do it in polynomial time? ## Resources * **AGT book:** [https://agtbook.org/](https://agtbook.org/) * **Noam Nisan's course:** [https://courses.cs.washington.edu/courses/cse599d/06wi/](https://courses.cs.washington.edu/courses/cse599d/06wi/) * **Tim Roughgarden's course:** [http://theory.stanford.edu/~tim/f16/f16.html](http://theory.stanford.edu/~tim/f16/f16.html) * **Constantinos Daskalakis' course:** [http://people.csail.mit.edu/costis/6896sp11/](http://people.csail.mit.edu/costis/6896sp11/) * **AVIAD RUBINSTEIN's course:** [https://users.cs.duke.edu/~aviad/](https://users.cs.duke.edu/~aviad/)