Patrizio Angelini
Dipartimento di Informatica e Automazione
Università degli Studi Roma Tre


Scegliete un numero intero tra 0 e 100
Vince chi si avvicina di più ai 2/3 della
media dei numeri scelti
◦ Chi vince prende un +!




Non ha senso scegliere un numero superiore a 66,
perché non potrà mai essere i 2/3 della media
Se tutti fanno questo ragionamento, e nessuno
sceglie un numero maggiore di 66, non ha senso
scegliere un numero maggiore di 44
…
Se tutti ragionassero bene, il numero migliore da
scegliere sarebbe 0
Game theory attempts to mathematically capture
behavior in strategic situations, or games, in
which an individual's success in making choices
depends on the choices of others
Myerson, 1991

Zero-sum / Non-zero-sum games
◦ Un giocatore guadagna a spese dell’altro
◦ Le somme dei guadagni e delle perdite dei giocatori
potrebbero essere differenti

Cooperative / Non-cooperative games
◦ I giocatori possono cooperare oppure no

Strategic Game:
◦ A set of players
◦ For each player, a set of strategies
◦ For each player, preferences over the set of
action profiles (the list of all the player’s
actions)
 Preferences are ordinal (Player 1 prefers a to b)

Time is absent from the model
◦ All the players choose simultaneously

Rationality assumption
◦ Each player makes her best choice

Non-zero sum game

Non-cooperative game





Two suspects are held in separate cells.
There is enough evidence to convict each of them
of a minor offense, but not enough to convict
either of them of the major crime, unless one of
them finks.
If they both stay quiet, each will be convicted of
the minor offense and spend 1 year in prison.
If one and only one of them finks, she will be
freed and used as a witness against the other, who
will spend 4 years in prison.
If they both fink, each will spend 3 years in prison.

Players: the two suspects S1 and S2

Strategies: Either Quiet or Fink, for both players

Preferences:
◦ S1: {F,Q} (payoff 3) – {Q,Q} (2) – {F,F} (1) – {Q,F} (0)
◦ S2: {Q,F} (3) – {Q,Q} (2) – {F,F} (1) – {F,Q} (0)
Q
F
Q
(2,2)
(0,3)
F
(3,0)
(1,1)
S2
S1
Q
F
Q
(2,2)
(0,3)
F
(3,0)
(1,1)

How would you act if you were suspect S1?

How would you act if you were suspect S2?

What is the best global solution?

A set of strategies, one for each player, such that no
player has incentive to unilaterally change her action
◦ each player is assumed to know the strategies of the other
players

A group of players is in Nash equilibrium if each one
is making her best decision, taking into account the
decisions of the others.

Nash equilibria are used to analyze the outcome of
the strategic interaction of several decision makers.
◦ predicting what will happen if several players are making
decisions at the same time.
◦ there could be more than one Nash Equilibrium
 if it is only one, then the outcome is certain

We cannot predict the result of the choices of
multiple decision makers if we analyze those
decisions in isolation
◦ we must ask what each player would do, taking into account
the decision-making of the others.




Non è detto che l'equilibrio di Nash sia la
soluzione migliore per tutti.
In un EN il singolo giocatore non può aumentare il
proprio guadagno modificando solo la propria
strategia, ma un insieme di giocatori può farlo
allontanandosi congiuntamente dall'equilibrio.
L'equilibrio di Nash può non essere un ottimo di
Pareto.
Analogamente, l’ottimo di Pareto può non essere
un equilibrio.
A
B
A
(1,-1)
(-1,1)
B
(-1,1)
(1,-1)

How many Nash Equilibria?

What is the best global solution?
◦ Is it a Nash Equilibrium?
A
B
A
(2,2)
(0,0)
B
(0,0)
(1,1)

How many Nash Equilibria?

What is the best global solution?
◦ Is it a Nash Equilibrium?


Instead of simply choosing an action, players
choose probability distributions over the set of
available actions.
Such distributions can be represented by a
function that assigns a real number to each
action profile
◦ von Neumann-Morgenstern utility function

One lottery is preferred to another if it results in
a higher expected value of this utility function.
Ogni gioco finito con strategie miste
ammette almeno un equilibrio di Nash
◦ Gioco finito: numero finito di giocatori e strategie

A
B
A
(1,-1)
(-1,1)
B
(-1,1)
(1,-1)
A mixed strategy in which both players choose A
with probability ½ and B with probability ½ is a
Nash Equlibrium

Come scegli la mattina la strada da fare per
andare a lavoro?
◦ La più corta?
◦ La più veloce?
◦ Quella con meno semafori?
◦ Quella che passa davanti al bar o al tabaccaio?
◦ Quella con meno traffico?
◦ Tenendo in considerazione quanto traffico aggiuntivo puoi
causare agli altri?
 Sei non lo fai, sei egoista (selfish)



In una rete, spesso è difficile (impossibile)
imporre strategie centralizzate
Gli utenti fanno le proprie scelte in modo selfish
In generale, il risultato di una ottimizzazione
locale degli utenti selfish è peggiore dell’ottimo
globale quando gli utenti cooperano
l(x) = x
s
t
l(x) = 1

Una strada corta ma stretta

Una strada larga ma lunga

x è la percentuale di traffico che passa in una strada
l(x) = x
s
t
l(x) = 1


Se tutti fanno la strada corta, ci mettono tutti 1 ora
Se la metà fa la strada corta, quelli ci mettono ½ ora e
gli altri 1 ora, quindi tempo medio ¾ d’ora
Price of Anarchy = 4/3
l(x) = x
l(x) = 1
s
t
l(x) = 1
l(x) = x

Metà del traffico passa sopra e metà sotto

Tempo medio pari a 1 ora e mezza
l(x) = x
s
l(x) = 1
l(x) = 0
l(x) = 1

t
l(x) = x
Viene costruita una strada di raccordo larghissima e
cortissima, con costo 0
Che succede?
l(x) = x
s
l(x) = 1
l(x) = 0
l(x) = 1
t
l(x) = x
Passano tutti per quella strada e…
Ci mettono 2 ore!
Price of Anarchy = 4/3

Non è detto che avere più alternative sia meglio
◦ Chiudiamo qualche strada per diminuire il traffico?

Una decisione centralizzata può portare ad un
migliore outcome per tutti i giocatori
◦ Nel caso di Pigou solo la metà dei giocatori andava
meglio, per gli altri era uguale


Grafo diretto con tante coppie (sorgentedestinazione), ognuna delle quali deve trasportare
una certa quantità di flusso
Ad ogni arco è associata una funzione di latenza che
dipende dal flusso totale che passa su quell’arco

Si sceglie il cammino con latenza totale minima

Ogni utente controlla una parte minima del traffico
◦ Per questo si modella con il flusso

Quale è il rapporto nel caso peggiore tra la
latenza totale/media di un Equilibrio di Nash
e la latenza ottima di un flusso sulla rete?
◦ The Price of Anarchy

Se le funzioni di latenza sugli archi sono lineari,
allora il prezzo dell’anarchia è al massimo 4/3
◦ Pigou e Braess matchano il caso peggiore

Se le funzioni di latenza sono polinomi di grado d,
allora il prezzo dell’anarchia è
[1 − d・(d+1)−(d+1)/d]
◦ d -> ∞ implica PoA -> ∞
−1
d -> ∞ implica PoA -> ∞
l(x) = x
s
d
1-ε
ε
l(x) = 1
t

Se le funzioni di latenza sono continue e
non decrescenti, la latenza totale di un EN è
al massimo pari alla latenza totale ottima
nel caso in cui ogni coppia sorgentedestinazione trasporti il doppio del traffico
◦ In mancanza di controllo centralizzato, è
sufficiente aumentare la banda di un fattore
costante


Il prezzo dell’anarchia non cambia al variare
della complessità della topologia della rete
Esempi worst-case si ottengono sempre anche su
reti con 2 nodi e archi paralleli tra loro
◦ Pigou

Quello che conta sono solo le funzioni di latenza
E’ possibile progettare reti su cui un
atteggiamento selfish da parte dei router induca
un’efficienza del routing vicina a quella ottima?
Il paradosso di Braess suggerisce di partire da
una rete e togliere archi

Risultati di inapprossimabilità
◦ Con latenze non decrescenti e continue, non esiste
un’approssimazione migliore di n/2, anche con solo una
sorgente e una destinazione
◦ Con latenze lineari, non esiste un’approssimazione migliore
di 4/3, anche con solo una sorgente e una destinazione
Le approssimazioni ottime sono quelle triviali
Non rimuovere nessun arco