44613284-5677-47FE-8F2C-F58B877B15A9.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. * Began with Émile Borel a...

# 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. * Began with Émile Borel and John von Neumann. * Major advances by John Nash. * Substantial activity in the 1950s. ### Basic Model * A set of players *N* = {$1, 2,..., n$}. * Each player *i* has a set of available strategies $S_i$. * Let $S = S_1 \times S_2 \times... \times S_n$ be the set of strategy profiles. * Each player *i* has a utility function $u_i : S \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 | ### Nash Equilibrium * A strategy profile $s = (s_1, s_2,..., s_n)$ is a **Nash Equilibrium** if no player can unilaterally deviate and improve its utility. * $\forall i \in N$, $\forall s'_i \in S_i$, $u_i(s_i, s_{-i}) \ge u_i(s'_i, s_{-i})$. * Every game has a Nash Equilibrium (in mixed strategies). * John Nash, 1950. ## What is Algorithmic Game Theory? * **Algorithmic Game Theory (AGT)** is an area that interfaces between Game Theory and Algorithm Design. * It uses algorithm design and analysis to understand and reason about behavior in strategic settings. * It uses game theory to design systems and algorithms for strategic users. ### Typical Questions in AGT * **Computation of Equilibria:** What is the complexity of finding Nash Equilibria in various games? * **Mechanism Design:** How can we design games so that selfish players are motivated to produce good social outcomes? * **Price of Anarchy:** How inefficient are Nash Equilibria in a given game? ### Example: Network Routing * **The Model:** * A network with *n* players. * Each player wants to route traffic from a source to a destination. * The cost of an edge *e* is $l_e(x)$, where *x* is the congestion on *e*. * Each player wants to minimize its cost. * **Nash Equilibrium:** * No player can improve its cost by unilaterally changing its route. * **Price of Anarchy:** * How much worse is the cost of a Nash Equilibrium compared to the optimal routing? ### Example: Sponsored Search Auctions * **The setting:** * *m* slots for ads. * *n* bidders. * Each bidder *i* has a value $v_i$ for a click. * Bidders bid for slots. * The auction determines who gets which slot and at what price. * **Goals:** * Maximize revenue. * Achieve good social welfare (allocate slots to those who value them the most). * **Challenges:** * Bidders are strategic. * The auction mechanism influences bidding behavior. ## Course Topics * Basics of Game Theory * Mechanism Design * Price of Anarchy * Fair Division * Social Networks * Auctions * Voting * Matching ## Reading * **"Algorithmic Game Theory"** edited by Nisan, Roughgarden, Tardos, Vazirani. * **"Twenty Lectures on Algorithmic Game Theory"** by Tim Roughgarden. * **"Multiagent Systems"** by Shoham and Leyton-Brown. * Recent research papers.