AGT - 05 - Algorithmic Mechanism Design II

Calcolare la shorest path significa calcolare il cammino di costo minimo. Dato un cammino \(P\) il suo costo è la somma dei pesi degli archi presenti nel cammino. In formula,

\[\sum_{e \in P} \tau_e = \sum_{e \in E} v_e(\tau_e, P)\]

Questo significa che la social-choice function per il nostro obiettivo è proprio la seguente

\[f(\tau) = \underset{P \in \mathcal{F}}{\arg\min} \sum\limits_{e \in E} v_e(\tau_e, P)\]

In altre parole il problema che vogliamo risolvere è un problema utilitario. Per progettare un meccanismo truthful possiamo quindi utilizzare i meccanismi VCG introdotti nella scorsa lezione. Ricordiamo che \(M = \langle g(r), p(x) \rangle\) è un meccanismo VCG se ha la seguente forma

• \(g(r) := \underset{x \in \mathcal{F}}{\arg\min} \sum\limits_j v_j(r_j, x)\)

• \(p_i := \sum_{j \neq i} v_j(r_j, g(r_{-i})) - \sum_{j \neq i} v_j(r_j, g(r))\)

Nel nostro caso particolare troviamo che

• L'algoritmo \(g(r)\) calcola un cammino minimo \(P_G(s, t)\) nel grafo \(G = (V, E, r)\) pesato con i tipi ripotati.

• Fissato un outcome \(g(r) = P_G(s, t)\), l'agente \(e \in E\) viene pagato nel seguente modo

  \[p_e(P_G(s, t)) = \sum_{j \neq e} v_j(r_j, g(r_{-e})) - \sum_{j \neq e} v_j(r_j, P_G(s, t))\]

  ovvero,

  \[p_e(P_G(s, t)) = \begin{cases} d_{G - e}(s, t) - (d_G(s, t) - r_e) \,\,&,\,\, e \in P_G(s, t) \\ 0 \,\,&,\,\, \text{ altrimenti } \\ \end{cases}\]

Per il calcolo dei pagamenti per ogni \(e \in P_G(s, t)\) dobbiamo quindi calcolare \(P_{G - e}(s, t)\) detto anche il cammino minimo di rimpiazzo nel grafo \(G - e := (V, E \setminus \{e\}, r_{-e})\) tra \(s\) e \(t\).

---

Esempio: Consideriamo il seguente grafo

Per calcolare il pagamento di \(e \in P_G(s, t)\) dobbiamo prima calcolare il cammino di rimpiazzo per \(e\)

Alla fine troviamo

\[P_e = d_{G - e}(s, t) - (d_G(s, t) - r_e) = 12 - (11 - 2) = 3\]

Sia \(n := |V|\), \(m := |E|\), e indichiamo con \(d_G(s, t)\) la distanza in \(G\) da \(s\) a \(t\).

Notiamo che i nodi \(s\) e \(t\) sono 2-edge connessi, ovvero esistono in \(G\) almeno \(2\) cammini tra \(s\) e \(t\) che sono disgiunti sugli archi. Se così non fosse infatti ci sarebbe almeno un arco in \(P_G(s, t)\) che è un ponte, e quindi che se rimosso spezza \(G\) in due componenti \(C_1\) e \(C_2\), con \(s \in C_1\) e \(t \in C_2\). In questo caso abbiamo che \(d_{G - e}(s, t) = + \infty\). In altre parole, il possessore del pointe può chiedere qualsiasi cifra. Restringendoci dunque a tutte le instanze in cui \(s\) e \(t\) sono 2-edge connessi, abbiamo che per ogni arco \(e \in P_G(s, t)\) rimosso esiste almeno un cammino alternativo in \(G - e\) che collega \(s\) a \(t\).

Per calcolare i pagamenti possiamo quindi applicare, per ogni arco \(e \in P_G(s, t)\), l'algoritmo di Dijkstra al grafo \(G - e\). La complessità di questo approccio è

\[\underbrace{O(n)}_{\text{# archi in } P_G(s, t)} \cdot \underbrace{O(m + n \log{n})}_{\text{Calcolo $P_{G-e}(s, t)$ fissato $e \in P_G(s, t)$}} = O(nm + n^2 \log {n})\]

In realtà vale un risultato ancora migliore, dimostrato da Malik, Mitta, Gutpa nell'articolo "The \(k\) most vital arcs in the shortest path problem", 1989, che risolve il problema in \(O(m + m \log n)\).

Stesso problema ma un agente può controllare più archi. In particolare abbiamo \(k \leq m := |E|\) agenti, ciascuno dei quali controlla un sottoinsieme di archi \(E_i \subseteq E\). L'agente \(a_i\) dichiara \(r:i E_i \to \mathbb{R}^+\), dove \(r_i(e)\) è il peso dichiarato dall'agente \(i\) per l'arco \(e \in E_i\), mentre il vero costo dell'arco è \(\tau_i(e)\).

Dato un outcome \(P \in \mathcal{F}\), la valutazione dell'agente \(i\) è

\[v_i(r_i, P) = \sum_{e \in E_i \cap P} r_i(e)\]

Notiamo che nuovamente il problema è un problema utilitario. Per risolverlo possiamo quindi utilizzare un meccanismo VCG \(M = \langle g(r), p(x) \rangle\) in cui l'algoritmo \(g(r)\) calcola il cammino minimo sul grafo pesato con i valori riportati dagli agenti, mentre il pagamento per l'agente \(i\) è dato da

\[\begin{split} p_i(P_G(s, t)) &= \sum_{j \neq i} v_j(r_j, P_{G \setminus E_i}(s, t)) - \sum_{j \neq i} v_j(r_j, P_G(s, t)) \\ &= d_{G - E_i}(s, t) - \Big( d_G(s, t) - \sum_{e \in E_i \cap P} r_i(e) \Big) \\ \end{split}\]

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

Per introdurre un meccanismo da poter utilizzare per i problemi one-parameter, è utile introdurre la seguente definizione, che ci permetterà di identificare una condizione necessaria affinché un meccanismo \(M\) per un problema OP sia truthful.

Def. Un algoritmo \(g(\cdot)\) per un problema OP di minimizzazione è monotono se per ogni agente \(a_i\), il carico di lavoro \(w_i(g(r_{-i}, r_i))\) è non crescente rispetto a \(r_i\) per tutti gli \(r_{-i} = (r_1, \ldots, r_{i-1}, r_{i+1}, \ldots, r_N)\).

Vale quindi il seguente.

Teorema 1 (Mayerson '81): Una condizione necessaria affinché un meccanismo \(M = \langle g(r), p(x) \rangle\) per un problema OP sia truthful è che \(g(r)\) sia monotono.

dim. Supponiamo per assurdo che \(g(\cdot)\) non sia monotono. Allora esiste un agente \(a_i\) e un vettore \(r_{-i}\) tale che la funzione \(w_i(g(r_{-i}, r_{i}))\) è non "non crescente" rispetto a \(r_i\). Graficamente,

Consideriamo adesso i seguenti quattro casi:

1. \(t_i = x, r_i = x \implies v_i(t_i, o) = x \cdot w_i(g(r_{-i}, x))\)

2. \(t_i = y, r_i = y \implies v_i(t_i, o) = y \cdot w_i(g(r_{-i}, y))\)

3. \(t_i = x, r_i = y \implies v_i(t_i, o) = x \cdot w_i(g(r_{-i}, y)) \implies a_i \text{ aumenta il suo costo di } A\)

4. \(t_i = y, r_i = x \implies v_i(t_i, o) = y \cdot w_i(g(r_{-i}, x)) \implies a_i \text{ ha un risparmio di } A +k\)

Dove \(A\) e \(k\) sono le seguenti aree

Sia quindi \(\Delta p = p_i(g(r_{-i}, y)) - p_i(g(r_{-i}, x))\). Per avere un meccanismo truthful dobbiamo sicuramente avere

• \((\Delta p \leq A)\). Se così non fosse infatti nel caso in cui \(t_i = x\) al giocatore \(a_i\) converrebbe mentire e riportare \(r_i = y\). Così facendo infatti l'aumento del pagamento supererebbe quello del costo aggiuntivo, e il giocatore avrebbe una utility finale \(> 0\) mentendo.

• \((\Delta p \geq A + k)\). Se così non fosse, nel caso in cui \(t_i = y\) al giocatore \(a_i\) converebbe riportare \(r_i = x\), in quanto l'incremento del pagamento da \(x\) a \(y\) non supera il risparmio nel riportare \(x\) al posto di \(y\). Nuovamente, il giocatore avrebbe una utility finale \(> 0\) mentendo.

Ma \(k > 0\), e quindi non possono valere queste due condizioni assieme.

\[\tag*{$\Huge\unicode{x21af}$}\]

Dato un problema OP, un meccanismo che possiamo utilizzare è \(M = \langle g(r), p(x) \rangle\), dove l'unica restrizione che imponiamo sull'algoritmo \(g(r)\) è che deve essere monotono, e fissato un outcome \(x \in \mathcal{F}\), il pagamento da assegnare all'agente \(i\) è il seguente

\[p_i(r) := h_i(r_{-i}) + r_i \cdot w_i(x) + \int\limits_{0}^{r_i} w_i(g(r_{-i}, z)) \,\, dz\]

Osserviamo come questo meccanismo è truthful. Vale infatti il seguente risultato.

Teorema 2 (Mayerson '81): Un meccanismo OP per un problema OP è truthful.

dim. L'idea è di mostrare che se \(a_i\) mente la sua utilità non può fare altro che diminuire. A tale fine fissiamo le dichiarazioni degli altri agenti \(r_{-i}\). Per come abbiamo definito il meccanismo, il pagamento fornito da \(a_i\) quando dichiara \(r_i\) è dato da

\[p_i(g(r)) = h_i(r_{-i}) + r_i \cdot w_i(g(r)) - \int\limits_{0}^{r_i} w_i(g(r_{-i}, z)) \,\, dz\]

Dato che \(h_i(r_{-i})\) non dipende dalla scelta del giocatore \(i\), posso ignorare questo fattore ponendolo a \(0\), \(h_i(r_{-i}) = 0\).

Cominciamo quindi considerando l'utilità di \(a_i\) quando dice la verità.

\[\begin{split} u_i(t_i, g(r_{-i}, t_i)) &= p_i(g(r_{-i}, t_i)) - v_i(t_i, g(r_{-i}, t_i)) \\ &= \Big(t_i w_i(g(r_{-i}, t_i)) - \int\limits_{0}^{t_i} w_i(g(r_{-i}, z)) \,\, dz \Big) - t_i \cdot w_i(g(r_{-i}, t_i)) \\ &= - \int\limits_{0}^{t_i} w_i(g(r_{-i}, z)) \,\, dz \\ \end{split}\]

Graficamente,

---

Se invece \(a_i\) mente, allora dichiara un valore \(r_i\) diverso da \(t_i\). la valutazione diventa

\[C = t_i \cdot w_i(g(r_{-i}, x))\]

il pagamento diventa

\[P = x \cdot w_i(g(r_{-i}, x)) - \int\limits_0^x w_i(g(r_{-i}, z)) \,\, dz \]

e l'utilità diventa

\[\begin{split} U &= P - C \\ &= x \cdot w_i(g(r_{-i}, x)) - \int\limits_0^x w_i(g(r_{-i}, z)) \,\, dz - t_i \cdot w_i(g(r_{-i}, x)) \\ &= (x - t_i) \cdot w_i(g(r_{-i}, x)) - \int\limits_0^x w_i(g(r_{-i}, z)) \,\, dz \\ \end{split}\]

Andiamo quindi ad analizzare i due possibili casi in cui ci possiamo trovare.

• (\(a_i\) dichiara \(r_i = x > t_i\)). In questo caso troviamo la seguente situazione

  

  Confrontando questo grafico con quello precedente, notiamo che questa volta prendiamo in considerazione anche l'aria aggiuntiva \(G\). Dato che queste aree vengono sottratte all'utilità finale, concludiamo che \(a_i\) sta perdendo \(G\) se mente dicendo \(x > t_i\).

---

• (\(a_i\) dichiara \(r_i = x < t_i\)). In questo caso troviamo la seguente situazione

  

  Nuovamente, abbiamo più area negativa da sottrarre. In particolare \(a_i\) perde l'area \(H\), e dunque anche in questo caso ad \(a_i\) non conviene mentire.

In entrambi i casi dunque all'agente \(a_i\) non conviene mentire.

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

Un meccanismo possibile è quindi il meccanismo \(M_{\text{SPT}} = \langle g(r), p(x) \rangle\) con

• \(g(r)\) che calcola uno shortest-path-tree (SPT) \(S_G(s)\) del grafo con i pesi riportati \(G = (V, E, r)\) utilizzando l'algoritmo di Dijkstra.

• Il pagamento dell'arco \(e \in E\) è invece dato da

  \[p_e(x) = r_e \cdot w_e(x) + \int\limits_{r_e}^{+ \infty} w_e(g(r_{-e}, z)) \,\, dz\]

Notiamo che tale meccanismo è truthful in quanto l'algoritmo di Dijkstra è monotono. Fissato \(r_{-e}\) il carico di lavoro per un agente \(a_e\) ha infatti sempre la seguente forma

Il valore \(\theta_e\) in cui il carico passa da \(1\) a \(0\) è chiamato soglia, ed è importante nel calcolo dei pagamenti. Abbiamo infatti che

• Se \(e\) non fa parte della soluzione, ovvero \(e \not \in E(T)\), allora

  \[p_e = r_e \cdot w_e(g(r)) + \int\limits_{r_e}^{+ \infty} w_e(g(r_{-e}, z)) \,\, dz = 0 + 0 = 0\]

• Se \(e\) fa parte della soluzione, ovvero \(e \in E(T)\), allora

  \[p_e = r_e \cdot w_e(g(r)) + \int\limits_{r_e}^{+ \infty} w_e(g(r_{-e}, z)) \,\, dz = r_e + (\theta_e - r_e) = \theta_e\]

---

Sia \(e = (u, v)\) un arco in \(S_G(s)\), con \(u\) più vicino a \(s\) che \(v\), e andiamo a calcolare il valore della soglia \(\theta_e\). Notiamo che \(e\) resta in \(S_G(s)\) fintantoché utilizzo \(e\) per raggiungere \(v\), come mostra il seguente esempio

In particolare il momento in cui \(r_e\) è tale che

\[d_G(s, u) + r_e > d_{G - e}(s, v)\]

allora \(e\) non viene più scelto. Dunque il valore soglia per \(e\) è tale che

\[\begin{split} &\,\,\, d_G(s, u) + \theta_e = d_{G - e}(s, v) \\ \iff&\,\,\, \theta_e = d_{G - e}(s, v) - d_G(s, u) \\ \end{split}\]

---

Mettendo tutto assieme, una soluzione banale per il problema dello SPT non cooperativo consiste nel calcolare \(S_g(s)\) utilizzando Dijkstra sul grafo con i pesi riportati, per poi calcolare \(d_{G - e}(s, v)\) per ogni \(e \in S_g(s)\) sempre utilizzando Dijkstra sul grafo \(G - e\) in modo tale da calcolare il pagamento per \(e\).

Sia \(n := |V|\), \(m := |E|\). La complessità di questo approccio è

\[\underbrace{O(n)}_{\text{# archi in } S_g(s)} \cdot \underbrace{O(m + n \log{n})}_{\text{Calcolo $d_{G-e}(s, v)$ fissato $e \in S_g(s)$}} = O(nm + n^2 \log {n})\]

Vale poi il seguente teorema.

Teorema: \(M_{\text{SPT}}\) è calcolabile in tempo \(O(m + n \log n)\).