ADRC - Lesson 24

È possibile dimostrare che il problema CA è anche un problema one-parameter (OP), più precisamente del tipo binary-demand (BD).

Certamente i tipi privati sono un singolo paramentro \(t_i \in \mathbb{R}\). Inoltre ponendo la funzione di carico di lavoro su valori binari \(w_i(\cdot) \in \lbrace 0, 1 \rbrace\) otterremo che la valutazione sarà \[ v_i(t_i, x) = t_i \cdot w_i(x) = \begin{cases} t_i &\mbox{se } i \in x\\ 0 &\mbox{altrimenti} \end{cases} \;\;\; \forall x \in F \] ergo CA è anche un gioco OP.

Nella lezione precedente abbiamo visto i meccanismi one-parameter per problemi di minimizzazione. In questo caso il problema è di massimizzazione, perciò la monotonia dell'algoritmo \(g\) deve essere in non decrescente, ovvero:

per ogni player \(i\) e per ogni configurazione di strategie degli altri player \(r_{-i} = (r_1, ..., r_{i-1},r_{i+1}, ..., r_n)\) la funzione di carico di lavoro \(w_i(r_{-i}, r_i)\) deve essere non decrescente al crescere del valore dichiarato \(r_i\), ovvero della froma

Figura 1: Funzione di carico di lavoro \(w_i\) per un problema binary demand di massimizzazione.

Sappiamo già che lo schema di pagamenti del player \(i\) sarà una quantità \(p_i(r) = \theta_i(r_{-i})\). Ciò che manca per concludere la definizione di un meccanismo truthful è la definizione di algorimo \(g\) che sia monotono, che approssimi bene una soluzione ottima e che sia calcolabile in tempo polinomiale.

Alg

Input

Una serie di tipi dichiarati \(r_1, r_2, ..., r_n\) e una serie rispettivi insiemi desiderati \(S_1, S_2, ..., S_n \subseteq \left[ m \right]\).

Output

Un sottoinsieme \(W \subseteq \left[ n \right]\) di vincitori dell'asta con insiemi non in conflitto. Ovvero per ogni \(i,j \in W\) avremo che \(S_i \cap \S_j \equiv \emptyset\).

ALG

1. riordina (e rinomina) le offerte (i tipi dichiarati) secondi il seguente ordine \[ \frac{r_1}{\sqrt{\vert S_1 \vert}} \geq \frac{r_2}{\sqrt{\vert S_2 \vert}} \geq ... \geq \frac{r_n}{\sqrt{\vert S_n \vert}} \]
2. Poni gli insiemi \(W = \emptyset\) e \(X = \emptyset\).
3. \begin{align*} \texttt{for } &\texttt{i=1:n do}\\ &\texttt{if } S_i \cap X \equiv \emptyset \texttt{ then}\\ &\;\;\;W = W \cup \lbrace i \rbrace\\ &\;\;\;E = E \cup S_i \end{align*}
4. return \(W\).

Lemma 1 l'algoritmo \(g\) appena descritto è monotono.

Proof: è sufficiente dimostrare che dato un agente \(i\) selezionato nella soluzione \(W\), anche se esso aumenta la sua offerta lui continuerà ad essere selezionato. Infatti, rifacendoti alla funzione di carico di lavoro dei problemi binary demand (come quella in Figura 1), avremo che una volta che \(r_i\) supera la soglia \(\theta_i(r_{-i})\) i valore di \(w_i\) non decresce più (rimane fisso a 1).

Osservando l'ordinamento dell'algoritmo \[ \frac{r_1}{\sqrt{\vert S_1 \vert}} \geq ... \geq \frac{r_i}{\sqrt{\vert S_i \vert}} \geq ... \geq \frac{r_n}{\sqrt{\vert S_n \vert}} \] avremo che aumentando \(r_i\) la posizione nel raching cresce, spostandosi verso sinistra.

Dato che l'algoritmo sceglie in maniera greedy da sinistra verso destra, avremo che se \(i\) veniva selezionato dichiarando \(r_i\), certamente continuerà ad essere selezionato se dichiara \(r_i + k\), per qualsiasi \(k > 0\) \(\square\).

Abbiamo visto che i pagamenti per i giochi OP binary demand sono del tipo \(p_i(r) = \theta_i(r_{-i})\). Ciò che serve sapere è come ricavare la soglia \(\theta_i(r_{-i})\). Una volta individuato un modo per ricavare la soglia, è possibile farlo in maniera efficiente?

Fissiamo un player \(i\), una configurazione di strategie \(r = (r_{-i}, r_i)\) e consideriamo sempre l'ordinamento fatto nell'algoritmo \(g\). Vogliamo sapere quanto deve essere grande almeno \(r_i\) affinché nell'ordinamento \(i\) venga scelto.

Certamente chi sta prima di lui nell'algoritmo viene scelto e non interferisce con \(i\). Perciò considerimo il primo player \(j\) non compatibile a destra di \(i\) nell'ordinamento, ovvero tale che \(S_i \cap S_j \not\equiv \emptyset\). Dato che \(j\) è incompatibile con \(i\), se \(j\) venisse scelto allora per forza \(i\) non apparterrebbe alla soluzione \(W\).

Perciò affinché \(i\) venga scelto nella soluzione deve essere necessariamente vero che \[ \frac{r_i}{\sqrt{\vert S_i \vert}} \geq \frac{r_j}{\sqrt{\vert S_j \vert}} \] ovvero la soglia di accettazione per \(i\) sarà \[ \theta_i(r_{-i}) = \frac{r_j}{\sqrt{\vert S_j \vert}} \sqrt{\vert S_i \vert} = r_j \frac{ \sqrt{\vert S_i \vert} }{ \sqrt{\vert S_j \vert} } \] Se invece non ci sono player incompatibili con \(i\), allora certamente \(i\) verrà scelto in \(W\) e quindi avremo che \(\theta_i(r_{-i}) = 0\).

Lemma 2 Sia \(OPT\) una soluzione ottima per il problema CA, e sia \(W\) una soluzione calcolata dall'algoritmo descritto. Allora avremo che \[ \sum_{i \in OPT} r_i \leq \sqrt{m} \sum_{i \in W} r_i \] ovvero l'algoritmo è \(\sqrt{m}\)-approssimante.

Proof: consideriamo un player vincente \(i \in W\). Definiamo l'insieme \[ OPT_i \equiv \lbrace j \in OPT : j \geq i \land S_j \cap S_i \not\equiv \emptyset \rbrace \] ovvero l'insieme di tutti i player \(j\) non compatibili con \(i\) rispetto all'ordinamento dell'algrotimo, e che si trovano alla sua destra.

Osserviamo che \[ \bigcup_{i \in W} OPT_i \equiv OPT \] Infatti consideriamo un player nella soluzione ottima \(j \in OPT\). Abbiamo due casi:

Caso 1

Se \(j\) appartiene anche alla soluzione \(W\) calcolata dall'algoritmo, allora certamente \(j \in OPT_j\).

Caso 2

Se invece \(j \notin W\) sicuramente esisterà un \(i \in W\) con \(i < j\) incompatibile (ovvero \(S_j \cap S_i \not\equiv \emptyset\)). Infatti, l'algoritmo inserisce i player nella soluzione \(W\) in ordine dal più piccolo al più grande, e se una volta arrivato a \(j\) esso fosse compatibile coi precenti, allora sarebbe stato inserito nella soluzione \(W\) (ritornando al caso 1). Perciò necessariamente \(j \in OPT_i\).

Per dimostrare il teorema basterà dimostrare che \(\forall i \in W\) \[ \sum_{j \in OPT_i} r_j \leq \sqrt{m} \; r_i \] infatti se così fosse avremo che \[ \sum_{j \in OPT} r_j \leq \sum_{i \in W} \sum_{j \in OPT_i} r_j \leq \sum_{i \in W} \sqrt{m} \; r_i = \sqrt{m} \sum_{i \in W} r_i \]

---

Consideriamo un \(i \in W\). Dalla sezione precende sappiamo che per ogni \(j\) a destra di \(i\) (ovvero \(j \geq i\)), \(i\) verrà scelto dall'algoritmo se e solo se \[ r_i \geq r_j \frac{ \sqrt{\vert S_i \vert} }{ \sqrt{\vert S_j \vert} } \] perciò viceversa \[ r_j \leq r_i \frac{ \sqrt{\vert S_j \vert} }{ \sqrt{\vert S_i \vert} } \] e questo è anche vero per ogni \(j \in OPT_i\).

Perciò avremo che per ogni \(i \in W\) \[ \sum_{j \in OPT_i} r_j \leq \sum_{j \in OPT_i} r_i \frac{ \sqrt{\vert S_j \vert} }{ \sqrt{\vert S_i \vert} } = \frac{ r_i }{ \sqrt{\vert S_i \vert} } \sum_{j \in OPT_i} \sqrt{\vert S_j \vert} \] Diamo ora un upperbound alla sommatoria \(\sum_{j \in OPT_i} \sqrt{\vert S_j \vert}\).

La disuguaglianza di Cauchy-Schwarz ci dice che dati due vettori \(n\)-dimensionali \(x,y\) è vero che \[ \left( \sum_{j = 1}^{n} x_i y_i \right) \leq \left( \sum_{j = 1}^{n} x_i^2 \right)^{1/2} \left( \sum_{j = 1}^{n} y_i^2 \right)^{1/2} \] Nel nostro caso ponendo \(x_j = 1\), \(y_j = \sqrt{\vert S_j \vert}\) ed \(n = \vert OPT_i \vert\) otterremo che

\begin{align*} \sum_{j \in OPT_i} \sqrt{\vert S_j \vert} &= \sum_{j = 1}^{\vert OPT_i \vert} 1 \cdot \sqrt{\vert S_j \vert} \leq \left( \sum_{j = 1}^{\vert OPT_i \vert} 1 \right)^{1/2} \left( \sum_{j = 1}^{\vert OPT_i \vert} \vert S_j \vert \right)^{1/2}\\ \\ &= \sqrt{\vert OPT_i \vert} \cdot \sqrt{ \sum_{j = OPT_i} \vert S_j \vert } \end{align*}

Per quanto riguarda \(\vert OPT_i \vert\) ci potrà essere al più un altro player \(j\) per ogni oggetto desiderato da \(i\) in \(S_i\). Perciò \(\vert OPT_i \vert \leq \vert S_i \vert\).

Invece per \(\sum_{j = OPT_i} \vert S_j \vert\), dato che tutti i \(j\) appartengono alla soluzione \(OPT\), certamente saranno tutti compatibili tra di loro, e quindi \[ \sum_{j = OPT_i} \vert S_j \vert\ = \vert \bigcup_{j \in OPT_i} S_j\vert \] Infine dato che \[ \bigcup_{j \in OPT_i} S_j \subseteq \bigcup_{j \in OPT} S_j \subseteq \left[ m \right] \] possiamo concludere che \(\sum_{j = OPT_i} \vert S_j \vert \leq m\).

Ricapitolando abbiamo dimostrato che \[ \sum_{j \in OPT_i} \sqrt{\vert S_j \vert} \leq \sqrt{\vert OPT_i \vert} \cdot \sqrt{ \sum_{j = OPT_i} \vert S_j \vert } \leq \sqrt{\vert S_i \vert} \cdot \sqrt{m} \] \[ \implies \sum_{j \in OPT_i} r_j \leq \frac{ r_i }{ \sqrt{\vert S_i \vert} } \sum_{j \in OPT_i} \sqrt{\vert S_j \vert} \leq \frac{ r_i }{ \sqrt{\vert S_i \vert} } \sqrt{\vert S_i \vert} \cdot \sqrt{m} = \sqrt{m} \cdot r_i \] \[ \implies \sum_{j \in OPT} r_j \leq \sum_{i \in W} \sum_{j \in OPT_i} r_j \leq \sqrt{m} \sum_{i \in W} r_i \;\;\; \square \]