Distributed computing: each computer is strategic.

Algorithmic Game Theory = Theory of Algorithms + Game Theory

Intersection of: Math, Computer Science, Economics

Basics of Game Theory

Games

A game consists of

A set of players
A set of strategies
A payoff specification
A set of outcomes

Game theory tries to predict the outcome of the game by taking into account the individual behavior of the players.

Types of Games

Cooperative VS non-cooperative

Symmetric VS asymmetric

Zero-sum VS non-zero-sum

Simultaneous VS sequential

Perfect information VS imperfect information

One-shot VS repeated

Normal-Form Games

$n$ rational players, for each player $i$, there is a strategy set $\Sigma_i$

Payoff: state or strategy profile $(s_1,\cdots,s_n)$, where $s_i\in\Sigma_i$, gives payoff $(p_1,\cdots,p_n)$ to the $n$ players.

Payoff matrix: $\Sigma_1\times\Sigma_2\times\cdots\times\Sigma_n$.

Equilibrium

An equilibria is a strategy combination in which individual are not willing to change their state.

"STABLE"

The ISP Dilemma

Equivalent to the prisoner dilemma

~~Omitted~~

Dominant Strategy Equilibrium

A strategy profile $s^*=(s_1^*,\cdots,s_n^*)$ is DSE if $s_i^*$ is dominant strategy for each player $i$. $$ \forall i,\forall s_{-i}=(s_1,\cdots,s_{i-1},s_{i+1},\cdots,s_n): p_i(s_i^*,s_{-i})\geq p_i(s_i,s_{-i}) $$

for any possible alternative strategy $s_i$.

Dominant strategy is the best response to any strategy of the other players.

But not all games have a dominant strategy equilibrium.

Nash Equilibrium

A strategy profile $s^*=(s_1^*,\cdots,s_n^*)$ is NE if for each $i,s_i^*$ is a best response to $s_{-i}^*$.

For any possible alternative strategy $s_i$: $$ p_i(s_i^*,s_{-i})\geq p_i(s_i,s_{-i}^). $$ In a NE, no agent can unilaterally deviate from her strategy given others' strategies as fixed.

Agent has to deliberate about the strategies of the other agents.

If the game is played as a sequence of improving moves of single players and players converge to a solution, then it has to be NE.

DSE implies NE, reverse is not true.

Example: The Battle of the Sexes

~~Omitted~~

Typical game which has two Nash Equilibrium.

Computation of Equilibrium

Computational Issues

Does a NE always exist? Pure VS Mixed strategies

Can a NE be efficiently computed? Hardness

What about the "quality" of a NE? PoA and PoS

How long does it take to converge to a NE if any? Speed of convergence

Existence of NE

For pure strategies games, there maybe no, one, or many NE.

Any game with a finite set of players and a finite set of strategies always has a NE of mixed strategy.

(In this lecture, we focus on PNE)

Finding NE

Trivial idea: Brute-force

Polynomial in the size of explicit normal-form (payoff-matrix)
Exponential in $n$

Worth to think about polynomial time (w.r.t. $n$) solution

Quality of NE

~~Omitted~~

PoA: pessimistic estimation

PoS: optimistic estimation

Speed of Convergence

How many moves after will they reach NE?

What is the social value achieved after a bounded number of selfish moves?

It may take exponential time to converge.