Algorithmic Game Theory
Incentives and Computation
Algorithm Design vs. Mechanism Design
Algorithms vs. Games
If we control the whole system, we can just design an algorithm
Otherwise, we have to design the constraints and incentives so that agents in the system work to achieve our goals.
And once the rules are in place, predict what will happen.
This comes up all the time.
Google, Blockchain
Game Theory Basics
What is a game? A set of Players actions, and payoffs
two-player game → much larger games (like end-player games)
Game Theory
| 0, 0 | -1, 1 | 1, -1 |
| 1, -1 | 0, 0 | -1, 1 |
| -1, 1 | 1, -1 | 0, 0 |
Can we predict outcomes?
What happens if everyone plays “rationally”?
What if some people don’t?
Traffic Routing
Town A – x/100 hours – 1 hour – Town B
Town A – 1 hour – x/100 hours – Town B
Suppose 10 drivers leave from town A towards town B.
Every driver wants to minimize her own travel time.
What is the traffic on the network?
In any unbalanced traffic pattern, all drivers on the most loaded path have an incentive to switch their path.
통근 시간이 x/100시간 이상, A 마을에서 B 마을로 이동함
50명은 위의 경로로, 50명은 아래의 경로로 이동하면 모두 1시간 30분이 소요됨.
The delay is 1.5 hours for everybody at the unique Nash equilibrium
A benevolent governor builds a superhighway connecting the short roads of the network.
What is the traffic on the network now?
No matter what the other drivers are doing, it is always better for me to follow the zig-zag path.
모든 사람들이 x/100 hours 경로를 택할 것
Delay is 2 hours for everybody at the unique Nash equilibrium
Adding a fast road to a road network is not always a good idea! Braess’s paradox
In the RHS network, there is a traffic pattern where all players have a delay of 1.5 hours.
PoA = \(\frac{performance of system in worst Nash equilibrium}{optimal performance if drivers did not decide on their own}\) = 4/3
* PoA: (Price of Anarchy) measures the loss in system performance due to free-will
Can we influence outcomes?
Can we change the rules of the game to encourage “rational” players to do what we want?
Computation?
How does computational complexity affect our predictions?
How does computational complexity limit our design choices?
An Easy Game (Prisoner’s Dilemma)
| Stay Silent | Testify | |
| Stay Silent | 5 Years, 5 Years | 50 Years, 3 Years |
| Testify | 3 Years, 50 Years | 40 Years, 40 Years |
Guess Two-Thirds of the Average
– k players \(p_1, p_2, p_3, \cdots, p_k\)
Each player submits a number in [0, 100]: \(x_1, x_2, \cdots, x_k\)
– compute \(\bar{x} := \frac{1}{k}\sum_{i=1}^{k}x_i\)
– find \(x_j\), closest to \(\frac{2}{3}\bar{x}\)
Player \(p_j\) wins $5; all other players win nothing
IS COMMON KNOWLEDGE REASONABLE?
THE PARABLE OF THE ISLANDERS
Reference
- Aaron Roth, (1/25) NETS 4120: Algorithmic Game Theory, Spring 2023, Apr 26, 2023, https://youtu.be/9YIz9jBb2wA?si=0dSSv1muJx6-ASKG