AGT - 04 - Algorithmic Mechanism Design I

In questo meccanismo il quadro viene dato al giocatore \(a_i\) che ha dichiarato il bid più alto, \(r_i = \max_{j = 1 \ldots k} \{r_j\}\). Il giocatore che vince poi non paga niente.

Notiamo che questo meccanismo non incentiva gli agenti a dire la verità. Infatti tutti gli agenti sono incentivati a dire \(r_i = +\infty\).

In questo meccanismo, come nel precedente, il quadro viene dato al giocatore \(a_i\) che ha dichiarato il bid più alto, \(r_i = \max_{j=1 \ldots k} \{r_j\}\). Questa volta però il giocatore che vince paga il valore da lui dichiarato \(r_i\)

Notiamo che neanche questo meccanismo incentiva gli agenti a dire la verità. Il giocatore \(a_i\) potrebbe infatti dichiarare \(r_i < t_i\) in modo da incrementare la sua utility. Questo significa che non sempre il quadro viene vinto dal giocatore con il valore privato \(t_i\) più alto.

In questo meccanismo il quadro viene dato al giocatore \(a_i\) che ha dichiarato il bid più alto, \(r_i = \max_{j=1 \ldots k} \{r_j\}\). Il giocatore che vince poi paga il secondo valore dichiarato più alto \(R = \max_{j \neq i} \{r_j\}\).

Questo meccanismo invece funziona. In particolare vale il seguente risultato.

Teorema: Nell'asta di Vickery, per ogni giocatore \(a_i\), dire la verità, ovvero \(r_i = t_i\) è una strategia dominante.

dim: Fissiamo \(i\) e \(t_i\), e sia \(R = \max_{j \neq i} \{r_j\}\). Notiamo che \(i\) non conosce \(R\). Andiamo adesso ad analizzare due casi distinti:

• \(t_i \geq R\).

  In questo caso se l'agente dice la verità, ovvero \(r_i = t_i\), allora abbiamo una utility di \(u_i = t_i - R \geq 0\) nel caso in cui vinciamo, che può accadere quando \((t_i > R)\) oppure quando \((t_i = R)\) e vinciamo il tie-break con l'altro giocatore. Se invece perdiamo, che succede quando \((t_i = R)\) e perdiamo il tie-break, allora abbiamo una utility di \(u_i = 0\).

  Se poi l'agente mente dichiarando \(r_i > R\), \(r_i \neq t_i\), allora l'agente vince con la stessa utility che avrebbe ottenuto se avesse detto la verità \(u_i = t_i - R \geq 0\). Infine, se l'agente mente dichiarando \(r_i < R\), allora perde con una utility di \(u_i = 0\).a

  ---

• \(t_i < R\).

  In questo caso se diciamo la verità (\(r_i = t_i\)), allora perdiamo con \(u_i = 0\). Se invece mentiamo e diciamo \(r_i < R\), \(r_i \neq t_i\), allora perdiamo nuovamente. Infine, se mentiamo dicendo \(r_i > R\), vinciamo, ma con una utility negativa \(u_i = T_i - R < 0\).

  ---

Notiamo come in tutti i casi analizzati, dichiarare \(r_i \neq t_i\) non porta ad un aumento effettivo della utility. Dunque, dire la verità è una strategia dominante.

\[\tag*{$\blacksquare$}\]

Cerchiamo adesso di formalizzare la proprietà speciale che aveva l'asta di Vickery in confronto agli altri due meccanismi che avevamo visto per risolvere il problema della single ttem auction.

Def. Un meccanismo \(M = \langle g(r), p(x) \rangle\) è una implementation with dominant strategies se esiste un vettore di tipi riportati \(r^* = (r_1^*, r_2^*, \ldots, r_N^*)\) tale che \(f(t) = g(r^*)\) nei dominant strategy equilibrium.

Se poi dire la verità è la strategia dominante \((r^* = t)\) allora il meccanismo è detto truthful, o strategy-proof, o incentive compatible. In questi casi gli agenti dicono i loro veri tipi \(t_i\) e non manipolano il valore dichiarato per fini strategici.

Le questioni principali da affrontare del disegno dei meccanismi hanno quindi a che fare su come definire dei meccanismi che garantiscono una implementazione truthful di una determinata social-choice function.

Alcuni possibi problemi che possono essere affrontati con gli strumenti del mechanism design sono i seguenti:

• Multiunit auction

• Sponsored search auction

• Public project

• Bilateral trade

• Buying a path in a network

I problemi di mechanism design possono essere pensati come problemi di ottimizzazione in cui parte dell'input è nascosta dagli agenti. L'obiettivo del meccanismo è quindi quello di incentivare gli agenti a rivelare il loro input.

Concentriamoci in particolare sui problemi di minimizzazione, che sono così descritti:

• Per ogni outcome \(x \in \mathcal{F}\), la valutazione \(v_i(t_i, x)\) rappresenta il costo del giocatore \(i\) in quel particolare outcome.

• La social-choice function \(f(t)\) associa al vettore dei tipi \(t\) la soluzione che minimizza una qualche misura di \(t\).

• I pagementi sono dal meccanismo verso gli agenti.

Il meccanismo VCG (Vicker, Clarke, Groves) è l'unico meccanismo truthful per i problemi utilitari, ed è descritto come segue:

• L'algoritmo \(g(r)\) calcola l'outcome nel seguente modo

  \[g(r) := \underset{x \in \mathcal{F}}{\arg\min} \sum_i v_i(r_i, x)\]

• Il pagamento per il giocatore \(i\) è invece

  \[p_i(x) := h_i(r_{-i}) - \sum_{j \neq i} v_j(r_j, x)\]

  dove \(h_i(r_{-i})\) è una funzione arbitraria che prende in input i valori riportati da tutti i giocatori escluso \(a_i\).

Il seguente risultato dimostra ciò che abbiamo menzionato.

Teorema: I meccanismi VCG sono truthful per i problemi di utilità.

dim. Fissiamo il giocatore \(a_i\), il suo tipo \(t_i\) e le scelte degli altri giocatori \(r_{-i}\). Applichiamo adesso l'algoritmo \(g(\cdot)\) per calcolare i seguenti due outcomes, a seconda che \(a_i\) mente oppure no, e calcoliamo l'utilità per entrambi i casi.

• L'outcome ottenuto quando \(a_i\) dice la verità \((r_i = t_i)\) è

  \[x = g(r_{-i}, t_i) = g(\hat{r})\]

  L'utilità in questo caso è

  \[\begin{split} u_i(t_i, x) &= p_i(x) - v_i(t_i, x) \\ &= \Big(h_i(r_{-i}) - \sum_{j \neq i} v_j(r_j, x) \Big) - v_i(t_i, x) \\ &= h_i(r_{-i}) - \sum_j v_j(\hat{r}_j, x) \\ \end{split}\]

• L'otucome ottenuto quando \(a_i\) mente invece \((r_i \neq t_i)\) è

  \[x' = g(r_{-i}, r_i)\]

  L'utilità in questo caso è

  \[\begin{split} u_i(t_i, x') &= p_i(x') - v_i(t_i, x') \\ &= \Big(h_i(r_{-i}) - \sum_{j \neq i} v_j(r_j, x') \Big) - v_i(t_i, x') \\ &= h_i(r_{-i}) - \sum_j v_j(\hat{r}_j, x') \\ \end{split}\]

A questo punto notiamo che per come è stata definita \(g(\cdot)\) l'outcome \(x\) è l'outcome che minimizza la quantià \(\sum_{i} v_i(\hat{r}_i, x)\). Ma allora

\[\sum_j v_j(\hat{r}_j, x) \leq \sum_j v_j(\hat{r}_j, x')\]

e quindi

\[u_i(t_i, x) \geq u_i(t_i, x')\]

In altre parole, al giocatore \(i\) conviene sempre dire la verità \(t_i\).

\[\tag*{$\blacksquare$}\]