{"id":3482,"date":"2024-01-20T00:04:44","date_gmt":"2024-01-19T15:04:44","guid":{"rendered":"https:\/\/saraheee.com\/?p=3482"},"modified":"2024-01-20T00:06:59","modified_gmt":"2024-01-19T15:06:59","slug":"nets-4120-algorithmic-game-theory-1","status":"publish","type":"post","link":"https:\/\/saraheee.com\/ko\/2024\/01\/nets-4120-algorithmic-game-theory-1\/","title":{"rendered":"NETS 4120: Algorithmic Game Theory #1"},"content":{"rendered":"

Algorithmic Game Theory<\/h2>\n\n\n\n

Incentives and Computation<\/p>\n\n\n\n

Algorithm Design vs. Mechanism Design<\/p>\n\n\n\n

Algorithms vs. Games<\/h4>\n\n\n\n

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.<\/p>\n\n\n\n

And once the rules are in place, predict what will happen.<\/p>\n\n\n\n

This comes up all the time.<\/h4>\n\n\n\n

Google, Blockchain<\/p>\n\n\n\n

Game Theory Basics<\/h4>\n\n\n\n

What is a game? A set of Players actions, and payoffs<\/p>\n\n\n\n

two-player game \u2192 much larger games (like end-player games)<\/p>\n\n\n\n

Game Theory<\/h4>\n\n\n\n
0, 0<\/td>-1, 1<\/td>1, -1<\/td><\/tr>
1, -1<\/td>0, 0<\/td>-1, 1<\/td><\/tr>
-1, 1<\/td>1, -1<\/td>0, 0<\/td><\/tr><\/tbody><\/table>
Rock-paper scissors<\/figcaption><\/figure>\n\n\n\n

<\/p>\n\n\n\n

Can we predict outcomes?<\/h4>\n\n\n\n

What happens if everyone plays “rationally”?
What if some people don’t?<\/p>\n\n\n\n

Traffic Routing<\/h4>\n\n\n\n

Town A – x\/100 hours – 1 hour – Town B
Town A – 1 hour – x\/100 hours – Town B<\/p>\n\n\n

\n
\"\"<\/figure><\/div>\n\n\n

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.<\/p>\n\n\n\n

\ud1b5\uadfc \uc2dc\uac04\uc774 x\/100\uc2dc\uac04 \uc774\uc0c1, A \ub9c8\uc744\uc5d0\uc11c B \ub9c8\uc744\ub85c \uc774\ub3d9\ud568
50\uba85\uc740 \uc704\uc758 \uacbd\ub85c\ub85c, 50\uba85\uc740 \uc544\ub798\uc758 \uacbd\ub85c\ub85c \uc774\ub3d9\ud558\uba74 \ubaa8\ub450 1\uc2dc\uac04 30\ubd84\uc774 \uc18c\uc694\ub428.<\/mark><\/p>\n\n\n\n

The delay is 1.5 hours for everybody at the unique Nash equilibrium<\/p>\n\n\n

\n
\"\"<\/figure><\/div>\n\n\n

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.<\/p>\n\n\n\n

\ubaa8\ub4e0 \uc0ac\ub78c\ub4e4\uc774 x\/100 hours \uacbd\ub85c\ub97c \ud0dd\ud560 \uac83<\/mark><\/p>\n\n\n\n

Delay is 2 hours for everybody at the unique Nash equilibrium<\/p>\n\n\n\n

<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

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<\/p>\n\n\n\n

<\/p>\n\n\n\n

Can we influence outcomes?<\/h4>\n\n\n\n

Can we change the rules of the game to encourage “rational” players to do what we want?<\/p>\n\n\n\n

Computation?<\/h4>\n\n\n\n

How does computational complexity affect our predictions?
How does computational complexity limit our design choices?<\/p>\n\n\n\n

An Easy Game (Prisoner’s Dilemma)<\/h4>\n\n\n\n
<\/td>Stay Silent<\/td>Testify<\/td><\/tr>
Stay Silent<\/td>5 Years, 5 Years<\/td>50 Years, 3 Years<\/td><\/tr>
Testify<\/td>3 Years, 50 Years<\/td>40 Years, 40 Years<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Guess Two-Thirds of the Average<\/h4>\n\n\n\n

– 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\\)<\/p>\n\n\n\n

– compute \\(\\bar{x} := \\frac{1}{k}\\sum_{i=1}^{k}x_i\\)<\/p>\n\n\n\n

– find \\(x_j\\), closest to \\(\\frac{2}{3}\\bar{x}\\)<\/p>\n\n\n\n

Player \\(p_j\\) wins $5; all other players win nothing<\/p>\n\n\n\n

<\/p>\n\n\n\n

IS COMMON KNOWLEDGE REASONABLE?
THE PARABLE OF THE ISLANDERS<\/h4>\n\n\n\n

<\/p>\n\n\n\n

Reference<\/h4>\n\n\n\n