AGT - 01 - Introduzione alla AGT

Per capire meglio il concetto di gioco, andiamo a vedere due classici esempi.

Un dominant strategy equilibrium (DSE) è una combinazione di strategie \(s^* = (s_1^*, s_2^*, \ldots, s_N^*)\) tale che \(s^*\) è una dominant strategy per ogni giocatore \(i\), ovvero tale che per ogni possibile profilo di strategie alternativo \(s = (s_1, s_2, \ldots, s_i, \ldots, s_N)\) si ha che

• Se il payoff \(p_i\) è una utility, allora

  \[p_i(s_1, s_2, \ldots , s_i^*, \ldots, s_N) \geq p_i(s_1, s_2, \ldots, s_i, \ldots, s_N)\]

• Se il payoff \(p_i\) è un costo, allora

  \[p_i(s_1, s_2, \ldots , s_i^*, \ldots, s_N) \leq p_i(s_1, s_2, \ldots, s_i, \ldots, s_N)\]

Detto altrimenti, una dominant strategy è la migliore risposta a qualunque strategia degli altri giocatori. Tipicamente se un gioco ha un DSE, i giocatori convergono quasi immediatamente ad esso. Detto questo, non tutti i giochi hanno un DSE. A tale fine viene risulta fondamentale utilizzare una versione più rilassata di equilibrio, introdotto con la seguente definizione

Un equilibrio di nash (NE) è una combinazione di strategie \(s^* = (s_1^*, s_2^*, \ldots, s_N^*)\) tale che per ogni giocatore \(i\), la strategie \(s_i^*\) è la migliore risposta alle scelte degli altri giocatori \((s_1^*, \ldots, s_{i-1}^*, s_{i+1}^*, \ldots, s_N^*)\), ovvero tale che per ogni altra possibile strategia \(s_i\) per il giocatore \(i\), si ha

• Se il payoff \(p_i\) è una utility, allora

  \[p_i(s_1^*, s_2^*, \ldots , s_i^*, \ldots, s_N^*) \geq p_i(s_1^*, s_2^*, \ldots, s_i, \ldots, s_N^*)\]

• Se il payoff \(p_i\) è un costo, allora

  \[p_i(s_1^*, s_2^*, \ldots , s_i^*, \ldots, s_N^*) \leq p_i(s_1^*, s_2^*, \ldots, s_i, \ldots, s_N^*)\]

Notiamo che se un profilo di strategie è un DES, allora è anche un NE, ma non vale il viceversa. Inoltre, se un gioco viene giocato ripetutamente e i giocatori convergono ad una soluzione, allora la combinazione di strategie finali che rappresenta la soluzione è un NE.

Esempio Consideriamo la seguente situazione, chiamata "The Battle of the Sexes" e descritta dalla seguente matrice di payoffs

Notiamo che i profili di strategie (Stadium, Stadium) e (Cinema, Cinema) sono degli equilibri di Nash, ma non sono DSE.

per i giochi detti pure strategies games, che sono caratterizzati dal fatto che ciascun giocatore sceglie in modo deterministico una strategia, non esiste un risultato generale per l'esistenza di un equilibrio di nash (NE). In altre parole, si potrebbero avere i tre seguenti casi:

• Non esiste nessun NE;

• Ne esiste uno solo;

• Ne esistono più di uno;

Se però consideriamo mixed strategies games, che introducono una variabilità aleatorie alle varie strategie dei giocatori, allora esiste un teorema, dimostrato nel 1951 da Nash per la sua tesi di dottorato, che afferma l'esistenza di un equilibrio in cui ciascun giocatore massimizza il suo valore atteso.

Esempio: Consideriamo la seguente payoff matrix

Notiamo che questo gioco non ammette nessun NE in quanto in ogni profilo di strategie ad almeno uno dei due giocatori conviene cambiare strategia.

Una volta trovato un NE ci possiamo domandare quanto peggiore è il NE trovato rispetto ad una situazione idealizzata in cui i giocatori collaborano tra loro per ottenere il risultato migliore.

Per confrontare outcome diversi necessitiamo di una social-choice function \(C\) che ci permette di associare un numero reale ad ogni proflio di strategie, pertmettendoci così facendo di misurare la qualità complessiva di un outcome \(S\). Un tipico esempio di social-choice function è la seguente

\[C(S) := \text{ sum of all players costs and utilities }\]

Possiamo rappresentare il traffico in una rete tramite un gioco, in cui i giocatori sono gli utenti della rete e le strategie sono i cammini della rete in cui gli utenti possono redirigere il loro traffico.

Per fare un esempio, nel gioco di Pigou [1920], abbiamo la seguente rete

Abbiamo \(1\) unità di traffico che deve passare da \(s\) a \(t\). Notiamo come il costo dell'arco verde dipende dalla congestione dell'arco, ovvero dalla frazione del flusso totale che passa sull'arco, mentre il costo dell'arco rosso è fisso.

L'unico NE di questo gioco è quello in cui tutto il flusso passa sull'arco verde. Il costo di questo equilibrio è

\[1 \cdot 1 + 0 \cdot 1 = 1\]

Per capire il costo minimo in una situazione di cooperazione ideale dobbiamo capire il valore \(x\) che minimizza la funzione \(C(x) := x \cdot x + 1 \cdot (1 - x)\) per \(x \in [0, 1]\). Prendendo la derivata prima otteniamo che

\[C'(x) = 2x - 1 = 0 \iff x = \frac12\]

dunque la situazione idale è quella in cui il flusso viene diviso equiamente nei due archi. Il costo di questa soluzione è

\[C(OPT) = C\Big(\frac12\Big) = \frac14 + \frac12 = \frac34\]

Troviamo quindi

\[\text{PoA} = \text{PoS} = \frac{1}{\frac34} = \frac43\]

Teorema (Roughgarden & Tardos, 2000): The PoA of the selfish routing game with linear latency function is at most \(4/3\).

Abbiamo già visto vari esempi che fanno vedere come il comportamento egoistico dei giocatori assume un ruolo importante nel modo in cui una rete viene utilizzata. Non dovrebbe sorprendere quindi osservare il fatto che anche quando bisogna progettare una rete risulta fondamentale tenere in considerazione il comportamento egoista dei futuri utilizzatori della rete.

Per fare un esempio concreto, consideriamo la seguente rete

e supponiamo di dover spostare \(1\) unità di traffico da \(s\) a \(t\). Ciascun giocatore gestisce una frazione infinitesimale del traffico, e l'obiettivo di ciascun giocatore è minimizzare il proprio costo.

Notiamo che con la rete così definita, l'unico NE è quello in cui il flusso viene diviso in modo equo

L'average travel time associato a questo equilibrio è anche l'outcome migliore, in quanto è pari a

\[\frac12 \cdot \frac12 + \frac12 \cdot 1 + \frac12 \cdot \frac12 + \frac12 \cdot 1 = \frac12 + 1 = 1.5\]

Supponiamo adesso che, al fine di diminuire l'average travel time, andiamo ad aggiungere un arco speciale di costo \(0\)

Osserviamo come ora l'unico NE è quello in cui tutto il flusso va nell'arco di costo \(0\). Così facendo quindi l'average travel time è diventato

\[1 \cdot 1 + 1 \cdot 0 + 1 \cdot 1 = 2\]

mentre il costo ottimale è sempre \(1.5\), ottenuto dividendo a metà il flusso. Con questo cambiamento, intuitivamente buono, abbiamo invece incrementato il PoA e il PoS

\[\text{PoA} = \frac{2}{\frac32} = \frac43 > 1\]

In altre parole, abbiamo peggiorato il modo in cui la rete viene utilizzata.

Nel corso studieremo due aree diverse della AGT, che sono:

• Mechanism design, che si occupa della creazione di giochi in modo da garantire determinate proprietà.

• Studio di PoS e PoA su giochi inspirati a problemi di natura informatica. Questo tipo di analisi verrà fatta utilizzando il seguente schema:

  1. Si considera una situazione esterna e la si modella come gioco;

  2. Si verifica l'esistenza di eventuali NE;

  3. Se esistono NE si verifica se siamo in grado di calcolarli, e ci occupiamo anche di come farlo;

  4. Compariamo la qualità di un NE rispetto ad una situazione ideale in cui gli agenti possono anche collaborare (cooperative system).

  5. Giocando in modo ripetuto cerchiamo di stabilire se e in quanti passi è possibile calcolare un NE.

• Pollution Game: Abbiamo \(n\) nazioni, ciascuna delle quali può scegliere di controllare il proprio inquinamento oppure no. Il controllo dell'inquinamento ha un costo di \(3\) per la nazione, mentre ciascuna nazione che non controlla il proprio inquinamento aggiunge un cosot di \(1\) a tutte le nazioni.

  Provare a dare dei bounds per la PoS e la PoA.

• Tragedy of Commons: Abbiamo \(n\) players che vogliono comunicare utilizzando 1 canale condiviso con una capacità massima di 1 unità.

  Il giocatore \(i\) vuole inviare \(x_i\) unità di flusso nel canale, con \(x_i \in [0, 1]\). Ogni giocatore vuole massimizare il contenuto inviato, ma la qualità del canale si deteriora all'aumentare del traffico totale inviato. Formalmente, il valore del giocatore \(i\) è definito come segue

  \[x_i \Big(1 - \sum_j x_j\Big)\]

  Provare a dare dei bounds per la PoS e la PoA.