NETS 4120: Algorithmic Game Theory #1

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, 11, -1
1, -10, 0-1, 1
-1, 11, -10, 0
Rock-paper scissors

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?


How does computational complexity affect our predictions?
How does computational complexity limit our design choices?

An Easy Game (Prisoner’s Dilemma)

Stay SilentTestify
Stay Silent5 Years, 5 Years50 Years, 3 Years
Testify3 Years, 50 Years40 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



Leave a Comment