ADRC - Lesson 23

Supponiamo di aver individuato un cammino minimo \(P_G(s,t)\) di lunghezza minima in \(G=(V,E,r)\). Per sempio abbiamo calcolato tale cammino con l'algoritmo di Dijkstra in tempo \(O(m + n\log{n})\). Supponiamo che il cammino \(P_G(s,t)\) sia composto da \(k\) archi. Per avere uno schema di pagamento dobbiamo calcolare il cammino minimo residuo per oguno dei \(k\) archi in \(P_G(s,t)\). Supponendo di calcolare i camminimi minimi con lo stesso algoritmo (ovvero quello di Dijkstra), allora avremo che è possibile calcolare lo schema di pagamenti in tempo \(O(k(m + n \log{n}))\). Se \(k \in O(n)\), allora risulta particolarmente non efficiente calcolare \(p(r)\), il quale richiederà un tempo di \(O(nm + n^2\log{n})\).

Per fortuna esiste un risultato che mostra come è possibile calcolare i \(k\) cammini di rimpiazzo in tempo \(O(m + n\log{n})\).

Le principali differenze tra meccanismi VCG e OP sono:

• VCG: non ci sono vincoli su come devono essere i tipi e le valutazioni, ma si richiede che la funzione di costo sociale debba essere pari alla somma delle valutazioni (problemi utilitari)
• OP: non c'è vincolo su come deve essere fatta la funzione di costo sociale, ma si richiede che i tipi siano valori reali e che la valutazione di un individuo deve essere pari al suo tipo privato moltiplicato il carico di lavoro.

Le due classi di problemi non si includono, ma si intersecano. Ciò significa che esistono problemi utilitari che non sono a singolo parametro e viceversa, oppure che esistono problemi che sono sia utilitari che a singolo parametro. In questo ultima cosa i meccanismi VCG e OP coincidono.

Un algoritmo \(g(\cdot)\) per un problema one-parameter di minimizzazione si dice monotono se per ogni agente \(i\), \(w_i(g(r_{-i},r_i))\) è non crescente rispetto a \(r_i\), qualunque siano \(r_{-i}=(r_1, ..., r_{i-1}, r_{i+1}, ..., r_n)\). Perciò se consideriamo il carico di lavoro \(w_i(g(r))\), esso non crescerà mai al crescere del parametro \(r_i\).

Per comodità d'ora in poi ci riferiremo al valore \(w_i(g(r))\) semplicemente con \(w_i(r)\).

THM 1 (Mayerson ‘81)
Condizione necessaria affinché un meccanismo \(M = \langle g(r), p(r) \rangle\) per un problema OP sia veritiero è che \(g(r)\) sia monotono. Ovvero dato un problema OP, un relativo meccanismo \(M\) veritiero per tale problema ha necessariamente \(g(\cdot)\) monotono.

Proof: Supponiamo per assurdo di avere un meccanismo \(M\) truthfull per un problema OP di minimizzazione, con algoritmo \(g(\cdot)\) non monotono. Verrà mostrato che non è possibile trovare alcuno schema di pagamento \(p\) che renda \(M\) veritiero.

Se \(g\) non è monotona, allora esisterà un certo agente \(i\) e un vettore \(r_{-i} \in \mathbb{R}^{n-1}\) tale che la funzione carico di lavoro \(w_i(r_{-i}, r_i)\) è non "non crescente" rispetto alla variabile \(r_i\). Ovvero esisteranno due valori \(x < y\) tale che \(w_i(r_{-i}, x) < w_i(r_{-i}, y)\).

Caso \(i\) sincero
Consideriamo il caso in cui il player \(i\) dichiara la verità \(r_i = t_i\). Se il tipo del player \(i\) è pari a \(t_i = x\) allora la sua valutazione sarà uguale all'area in verde \(x \cdot w_i(r_{-i}, x)\)

Figura 6: \(r_i = t_i = x\).

mentre se pari a \(t_i = y\) assumerà il valore dell'area in viola \(y \cdot w_i(r_{-i}, y)\)

Figura 7: \(r_i = t_i = y\).

Caso \(i\) non sincero
Consideriamo il caso in cui il player \(i\) non dichiara la verità \(r_i \neq t_i\). Possono succedere due cose, o \(i\) dichiara di più del suo tipo, per esempio \(r_i = y > x = t_i\), oppure \(i\) dichiara meno del reale, per esempio \(r_i = x < y = t_i\).

Se \(i\) dichiara più di \(t_i\), allora la sua valutazione sarà pari a \(x \cdot w_i(r_{-i}, y)\), ovvero all'area GIALLA in figura.

Figura 8: \(r_i = y > x = t_i\).

Viceversa, se dichiara meno del tipo reale \(t_i\), allora la sua valutazione sarà pari a \(y \cdot w_i(r_{-i}, x)\), ovvero all'area AZZURRA in figura.

Figura 9: \(r_i = x < y = t_i\).

Considerando i seguenti rettangoli nella figura contrassegnati come A e k, possiamo ricapitolare i 4 possibili scenari appena visti come segue:

1. se \(r_i = t_i = x \implies v_i(t_i, \star) = x \cdot w_i(r_{-i}, x)\)
2. se \(r_i = t_i = y \implies v_i(t_i, \star) = y \cdot w_i(r_{-i}, y)\)
3. se \(r_i = y > x = t_i\) \(\implies v_i(t_i, \star) = x \cdot w_i(r_{-i}, y)\) \(\implies\) \(i\) aumenta il suo costo di A
4. se \(r_i = x < y = t_i\) \(\implies v_i(t_i, \star) = y \cdot w_i(r_{-i}, x)\) \(\implies\) \(i\) diminuisce il suo costo di A + k

Vediamo ora la differenza d'utilità in base alle possibili dichiarazioni che \(i\) può fare, \(x\) o \(y\). Supponiamo di avere un meccanismo \(M\) truthfull, e indichiamo con \(\Delta p = p_i(r_{-i}, y) - p_i(r_{-i}, x)\) il pagamento che il meccanismo \(M\) da ad \(i\) se dichiara \(y\) meno il pagamento che avrebbe dichiarando \(x\). Ovviamente i pagamenti dipendono solamente dai tipi riportati e non da quelli reali, in quanto il meccanismo non conosce i tipi reali.

\(\Delta p \leq A\)

Se \(\Delta p > A\) e \(t_i = x\), allora al player converrebbe mentire e riportare \(r_i = y\). Infatti se \(i\) fosse sincero dichiarando \(r_i = t_i = x\) avrebbe un certo pagamento \(p_i(r_{-i}, x)\), mentre se dichiara di più \(r_i = y > x = t_i\), il suo costo aumenterebbe di A, ma il suo pagamento aumenterebbe di quantità maggiore di A (risultando in una utilità migliore). Perciò affinché \(M\) sia truthfull, allora necessariamente deve essre che \(\Delta p \leq A\).

\(\Delta p \geq A+k\)

Se invece \(\Delta p < A+k\) e \(t_i = y\), allora al player converrebbe mentire e riportare \(r_i = x\). Infatti se \(i\) fosse sincero dichiarando \(r_i = t_i = y\) avrebbe un certo pagamento \(p_i(r_{-i}, y)\), mentre se dichiara di meno \(r_i = x < y = t_i\), il suo costo diminuirebbe di A+k, mentre il suo pagamento diminuirebbe di una quantità minore di A+k (risultando ancora una volta in una utilità migliore). Perciò un'altra condizione affinché \(M\) sia truthfull è che \(\Delta p \geq A + k\).

Infine, dato che per assunzione \(x < y\) e \(w_i(r_{-i}, x) < w_i(r_{-i}, y)\), allora l'area di k è non nulla. Perciò se \(M\) è truthfull con funzione \(g(\cdot)\) non monotona, allora incorreremo in uno schema di pagamento tale che \(\Delta p \leq A\) e \(\Delta p > A\) (assurdo!) \(\square\).

È possibile progettare un meccanismo truthfull \(M\) one-parameter per i problemi OP. Tale meccanismo è definito come segue:

• \(g(r)\) un qualsiasi algoritmo monotono
• sia \(h_i(r_{-i})\) una qualsiasi funzione indipendente da \(i\), allora possiamo porre lo schema di pagamanto di \(i\) pari a \[ p_i(r) = h_i(r_{-i}) + r_i \cdot w_i(r) - \int_{0}^{r_i}w_i(r_{-i}, z)\,dz \]

THM 2 (Mayerson ‘81)
Un meccanismo OP (per un problema OP) è veritiero.

Proof: Basta far vedere che qualsiasi strategia che non sia dichiarare il vero è sempre peggiore.

Fissiamo un generico player \(i\), e consideriamo una qualsiasi configurazione di strategie \(r_{-i}\) (per tutti gli altri player eccetto \(i\)). Considerando uno schema OP come quello visto in precedenza, poniamo la funzione \(h_i(r_{-i}) = 0\) in quanto ininfluente dato che indipendente da \(r_i\). Supponiamo che \(i\) dichiari un certo tipo \(r_i\) ed indicando con \(r = (r_{-i},r)\), avremo che il suo pagamento sarà \[ p_i(r) = r_i \cdot w_i(r) - \int_{0}^{r_i}w_i(r_{-i}, z)\,dz \]

Calcoliamo ora quanto vale l'utilità di \(i\) se dovesse dichiarare il suo tipo reale \(t_i\)

\begin{align*} u_i(t_i, (r_{-i}, t_i)) &= p_i(r_{-i}, t_i) - v_i(t_i, g(r_{-i}, t_i))\\ &= t_i \cdot w_i(r_{-i}, t_i) - \int_{0}^{r_i} w_i(r_{-i}, z)\,dz - t_i \cdot w_i(r_{-i}, t_i)\\ &= - \int_{0}^{r_i} w_i(r_{-i}, z)\,dz \end{align*}

Caso \(i\) dichiara \(x > t_i\)
Se \(i\) dichiara un tipo maggiore di quello reale \(x > t_i\) avremo che l'utilità diminuisce.

\begin{align*} u_i(t_i, (r_{-i}, x)) &= \underbrace{ x \cdot w_i(r_{-i}, x) - \int_{0}^{x} w_i(r_{-i}, z)\,dz }_{- P} - \underbrace{ t_i \cdot w_i(r_{-i}, x) }_{ C }\\ &= u_i(t_i, (r_{-i}, t_i)) - G \end{align*}

Caso \(i\) dichiara \(x < t_i\)
Anche se \(i\) dichiara un tipo minore di quello reale \(x < t_i\) avremo che l'utilità diminuisce. \[ u_i(t_i, (r_{-i}, x)) = - P - C = u_i(t_i, (r_{-i}, t_i)) - G \]

Perciò, se \(i\) mente la sua utilità non può che peggiorare \(\square\).

Un meccanismo garantisce la volontaria partecipazione dei player se l’utilità di un qualsiasi agente (che dichiara il vero) ha sempre un utile non negativo, altrimenti non avrebbe senso partecipare al gioco.

Ponendo \(h_i(r_{-i}) = 0\) (come nella dimostrazione precedente) otterremo in ogni caso un'utilità negativa. Perciò per ottenere utilità positiva si vuole (_per chi dichiara il vero_) che \[ p_i(r_{-i}, t_i) > v_i(t_i, g(r_{-i}, t_i))\\ \\ h_i(r_{-i}) + t_i \cdot w_i(r_{-i}, t_i) - \int_{0}^{r_i} w_i(r_{-i}, z)\,dz > t_i \cdot w_i(r_{-i}, t_i)\\ \\ h_i(r_{-i}) - \int_{0}^{r_i} w_i(r_{-i}, z)\,dz > 0\\ \\ h_i(r_{-i}) > \int_{0}^{r_i} w_i(r_{-i}, z)\,dz \] Dato che \(w_i(\cdot)\) è decrescente rispetto ad \(r_i\) (per via della monotonia di \(g\)), possiamo porre \[ h_i(r_{-i}) = \int_{0}^{\infty} w_i(r_{-i}, z)\,dz \] e di conseguenza il pagamanto diventa pari a

\begin{align*} p_i(r_{-i}, r_i) &= \int_{0}^{\infty} w_i(r_{-i}, z)\,dz + r_i \cdot w_i(r_{-i}, r_i) - \int_{0}^{r_i} w_i(r_{-i}, z)\,dz\\ &= r_i \cdot w_i(r_{-i}, r_i) + \int_{r_i}^{\infty} w_i(r_{-i}, z)\,dz \end{align*}

Perciò l'utilità di un agente \(i\) che dichiara il vero sarà sempre non negativa \[ u_i(t_i, g(r_{-i}, t_i)) = \int_{t_i}^{\infty} w_i(r_{-i}, z)\,dz \geq 0 \]

Per dimostrare la truthfulness del maccanismo \(M_{SPT}\) appena descritto, è necessario che l'algoritmo di Dijkstra usato per calcolare \(g(r)\) è monotono. Osservare che se un player \(e\) dichiara un valore più piccolo del suo tipo \(t_e\) verrà comunque scelto nella soluzione finale. Perciò esisterà un certa soglia critica \(\theta_e \geq t_e\) tale che:

• se \(e\) dichiara al più il valore della soglia (ovvero \(r_e \leq \theta_e\)) allora viene scelto nella soluzione.
• se \(e\) dichiara più della soglia (ovvero \(r_e > \theta_e\)) allora non viene scelto nella soluzione.

Perciò per ogni player \(e\) la sua funzione carico di lavoro \(w_e\) sarà non crescente di \(r_e\), ovvero della forma

È facile osservare che se l'arco \(e\) non è presente nella soluzione allora il pagamento sarà nullo \(p_e(r) = 0\). Infatti, se \(e\) non è stato scelto, allora avrà certamente dichiarato \(r_e > \theta_e\). Perciò il pagamento sarà \[ p_e(r) = r_e \cdot 0 + \int_{r_e}^{\infty} 0 \,dz = 0 \]

Viceversa se \(e\) è nella soluzione, allora \(p_e(r) = \theta_e\). Infatti dato che \(r_e \leq \theta_e\) allora il pagamento sarà \[ p_e(r) = r_e \cdot 1 + \int_{r_e}^{\infty} 1 \,dz = r_e + \theta_e - r_e = \theta_e \]

Ritornando al problema dello SPT non cooperativo, sappiamo che un arco \(e\) appartiene alla soluzione finché la sorgente \(s\) utilizza \(e\) per raggiungere un nodo \(v\). Perciò affinché \(e\) sia incluso nella soluzione, è necessario che qualsiasi altro suo cammino di rimpiazzo \(P_{G-e}(r_{-e}, r_e)\) sia maggiore del cammino \(P_G(r_{-e}, r_e)\).

Possiamo quindi dire che la soglia di adozione per l'arco \(e\) nella soluzione è pari a \[ \theta_e = d_{G-e}(s,v) - d_G(s,v) \]

---