Algorithmic Game Theory

Course Information

• Instructor: Anna Karlin, email: [email protected]
• TA: Aris Filos-Ratsikas, email: [email protected]
• Class Time: Tuesdays and Thursdays, 1:30 PM - 2:50 PM
• Location: CSE 305
• Course webpage can be found at: https://courses.cs.washington.edu/courses/cse533/23au/

Course Description

• Covers algorithmic game theory with focus on networked systems and markets.
• Topics include solution concepts, mechanism design, price of anarchy, and fair division.

Prerequisites

• Requires knowledge of algorithms and probability.
• Requires mathematical maturity.

Grading Breakdown

• Problem sets: 50%
• Participation: 10%
• Project: 40%

Game Theory Defined

• It is a mathematical framework used to analyze strategic interactions between multiple agents.
• Agents have varied preferences.
• Outcomes for agents are based on the actions of everyone involved.

Game Theory Examples

• Network routing
• Auctions
• Fair division
• Elections
• Social networks

Selfish Routing

• $n$ agents want to travel from vertex $s$ to vertex $t$ in a network.
• Each edge $e$ has a cost function $\mathcal{l}_e(x)$ which represents the cost to each agent using edge $e$ when $x$ agents use that edge.
• The goal is to quantify the drop in network quality due to selfish routing.

Congestion Game

• It comprises a tuple $(N, R, E, {c_e})$.
• $N$ is the number of players.
• $R_i \subseteq 2^E$ represents player $i$'s set of strategies.
• $E$ is the set of resources.
• $c_e$ is the cost function for resource $e$, dependent on the number of players using it.

Congestion Game Example

• Includes a simple network with two vertices, $s$ and $t$, and two edges connecting them.
• Edge 1 has a cost function of $\mathcal{l}_1(x) = x$.
• Edge 2 has a cost function of $\mathcal{l}_2(x) = 1$.

Nash Equilibrium (Definition 1)

• Is a scenario in which no player benefits from unilaterally changing their strategy.

Nash Equilibrium Example

• If all players take edge 1, any player can switch to edge 2 to lower their cost from $n$ to $1$.
• A Nash Equilibrium occurs when one player takes edge 2 while $n-1$ players take edge 1, discouraging any player from switching.
• The cost for the $n-1$ players on edge 1 is $n-1$.
• The cost for the single player on edge 2 is $1$.

Social Cost (Definition 2)

• The total cost incurred by all players in a strategy profile, $SC = \sum_{i \in N} c_i(s)$.
• Social cost is defined as the sum of all players' costs.

Social Cost Example

• In the Nash Equilibrium example above, the social cost is: $SC = (n-1) + 1 = n$
• If all players took edge 2, the social cost would be $SC = n$
• If all players took edge 1, the social cost would be $SC = n \cdot n = n^2$

Price of Anarchy

• Measures the ratio of the worst-case Nash Equilibrium's social cost to the optimal social cost.
• Formula: $PoA = \frac{\text{Social cost of worst-case Nash Equilibrium}}{\text{Optimal social cost}}$

Price of Anarchy Example

• In the example given, the Price of Anarchy is: $PoA = \frac{n}{n} = 1$

Braess's Paradox

• Adding capacity to a network paradoxically increases congestion and travel times.

Braess's Paradox Example

• Network with vertices $A$, $B$, $C$, and $D$.
• Edge from $A$ to $B$ has a cost function of $\mathcal{l}_1(x) = x$.
• Edge from $A$ to $C$ has a cost function of $\mathcal{l}_2(x) = 10$.
• Edge from $B$ to $D$ has a cost function of $\mathcal{l}_3(x) = 10$.
• Edge from $C$ to $D$ has a cost function of $\mathcal{l}_4(x) = x$.
• If one agent travels from $A$ to $D$, the path $A \rightarrow B \rightarrow D$ costs $x + 10$, and the path $A \rightarrow C \rightarrow D$ costs $10 + x$.
• In Nash Equilibrium, players split evenly between the paths, costing each player $\frac{n}{2} + 10$.
• The social cost is: $n \cdot (\frac{n}{2} + 10)$
• When an edge from $B$ to $C$ with cost function $\mathcal{l}_5(x) = 0$ is added, each player takes the path $A \rightarrow B \rightarrow C \rightarrow D$, with cost of $x + 0 + x = 2x$.
• The social cost becomes: $n \cdot 2n = 2n^2$

Non-Atomic Routing Game Example

• $n$ infinitesimal players travel from $s$ to $t$.
• $f_e$ represents flow on edge $e$.
• $\mathcal{l}_e(f_e)$ is the latency on edge $e$.

Wardrop Equilibrium

• Flow pattern $f$ where all flow occurs on paths with minimum latency, denoted as $L(f)$.
• Paths used have equal latency.
• Unused paths have higher latency.