Patrizio Angelini

Tecniche Algoritmiche per Grafi e Reti

Dipartimento di Informatica e Automazione Università degli Studi Roma Tre

Equilibri di Nash e Selfish Routing

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 +!

Gioco a premi (come promesso)

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

Gioco a premi

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

Game Theory

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

Game Theory

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)

Our setting

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

Our setting

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.

Prisoner’s Dilemma

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)

Prisoner’s Dilemma

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?

Prisoner’s Dilemma

Q F

Q (2,2) (0,3)

F (3,0) (1,1)S1

S2

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 Equilibrium

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.

Nash Equilibrium

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.

Nash / Pareto Optimum

How many Nash Equilibria?

What is the best global solution?

◦ Is it a Nash Equilibrium?

Matching Pennies

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?

Other examples

A B

A (2,2) (0,0)

B (0,0) (1,1)

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.

Mixed Strategies

Teorema di Nash (J.F. Nash Jr.)

Ogni gioco finito con strategie miste ammette almeno un equilibrio di Nash

◦ Gioco finito: numero finito di giocatori e strategie

A mixed strategy in which both players choose A with probability ½ and B with probability ½ is a Nash Equlibrium

Matching Pennies - Mixed

A B

A (1,-1) (-1,1)

B (-1,1) (1,-1)

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)

Commuting Problem

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

Selfish Routing

Una strada corta ma stretta

Una strada larga ma lunga

x è la percentuale di traffico che passa in una strada

Pigous’s Examplel(x) = x

l(x) = 1

s t

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

Pigous’s Examplel(x) = x

l(x) = 1

s t

Price of Anarchy = 4/3

Metà del traffico passa sopra e metà sotto

Tempo medio pari a 1 ora e mezza

Braess’s Paradox

l(x) = x

l(x) = 1

l(x) = 1

l(x) = x

s t

Viene costruita una strada di raccordo larghissima e cortissima, con costo 0

Che succede?

Braess’s Paradox

l(x) = x

l(x) = 1

l(x) = 1

l(x) = x

s tl(x) = 0

Passano tutti per quella strada e…

Ci mettono 2 ore!

Braess’s Paradox

l(x) = x

l(x) = 1

l(x) = 1

l(x) = x

s tl(x) = 0

Price of Anarchy = 4/3

Braess’s Paradox

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 (sorgente-destinazione), 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

Selfish Routing - Model

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

How bad is Selfish Routing?

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] −1

◦ d -> ∞ implica PoA -> ∞

How bad is Selfish Routing?

d -> ∞ implica PoA -> ∞

How bad is Selfish Routing?

l(x) = xd

l(x) = 1

s t

ε

1-ε

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 sorgente-destinazione trasporti il doppio del traffico

◦ In mancanza di controllo centralizzato, è sufficiente aumentare la banda di un fattore costante

How bad is Selfish Routing?

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

The PoA is independent of the Topology

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

Coping with Selfish Routing

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 trivialiNon rimuovere nessun arco

Coping with Selfish Routing