IMG_3379.jpeg

# Algorithmic Game Theory - Lecture 1 Instructor: Anna Karlin TA: Nicolò Gatti ## What is Game Theory? - Study of interactions between **rational**, **self-interested** agents. - Each agent (player) has a set of possible actions. - Each agent has a **utility** (or payoff) function t...

# Algorithmic Game Theory - Lecture 1 Instructor: Anna Karlin TA: Nicolò Gatti ## What is Game Theory? - Study of interactions between **rational**, **self-interested** agents. - Each agent (player) has a set of possible actions. - Each agent has a **utility** (or payoff) function that depends on the actions of all agents. - Agents are rational and act to maximize their own utility. ## Example: Prisoner's Dilemma | | Cooperate | Defect | | :---------- | :-------- | :------ | | **Cooperate** | $-1, -1$ | $-3, 0$ | | **Defect** | $0, -3$ | $-2, -2$ | - 2 suspects are arrested for a crime. - If both cooperate (remain silent), they each get a light sentence. - If both defect (betray the other), they each get a moderate sentence. - If one cooperates and the other defects, the defector goes free and the cooperator gets a heavy sentence. - **Dominant strategy:** Defect (always better, regardless of what the other player does). - **Nash equilibrium:** (Defect, Defect) - both players play their dominant strategy. - **Socially optimal outcome:** (Cooperate, Cooperate) - maximizes the sum of the players' utilities. - Note the difference between **optimality** and **equilibrium**. ## What is Algorithmic Game Theory? - Brings together game theory and algorithm design & analysis. - **Game theory** provides the models. - **Algorithm design & analysis** provides the tools. We are concerned with: 1. **Computational efficiency** of game-theoretic solution concepts. 2. Design of games so that the **outcomes** are good. 3. **Descriptive** rather than **prescriptive** game theory. ## Examples of Topics 1. **Mechanism design:** How to design games so that the socially optimal outcome is achieved, even when players act in their own self-interest. 2. **Price of anarchy:** How much does the social welfare degrade due to selfish behavior? 3. **Learning in games:** How do agents learn to play well in repeated games? 4. **Computational social choice:** How to aggregate preferences of multiple agents to make a collective decision. ## Example: Selfish Routing - Network with source $s$ and destination $t$. - Rate of traffic is 1. - Each edge has a cost function that depends on the amount of traffic on the edge. - $c_e(x)$ is the cost to each agent of using edge $e$ when the total traffic on $e$ is $x$. - Agents want to minimize their own cost. - **Nash equilibrium:** Traffic is routed so that no agent can decrease their cost by changing their route. - What is the cost of the Nash equilibrium? - How does it compare to the socially optimal routing? ## Example: Sponsored Search Auctions - Google auctions off ad slots to advertisers. - Advertisers bid on keywords. - Google ranks ads based on bids and quality score. - Advertisers pay Google when their ad is clicked. - How should Google design the auction to maximize revenue? - How should advertisers bid to maximize their profit?