AGT - 06 - Algorithmic Mechanism Design III

Notiamo che per poter applicare questo meccanismo dobbiamo essere in grado di calcolare la soluzione ottima \(g(r)\) fissato il vettore \(r\). Questo, purtroppo, risulta essere un problema difficile, come mostra il seguente risultato.

Teorema 1: Approssimare CA con un fattore migliore di \(m^{\frac12 - \epsilon}\) è un problema NP-hard per ogni \(\epsilon > 0\).

per dimostrare questo teorema effettueremo una riduzione a partire da un problema famoso noto come indipendent set (IS). Per IS infatti vale il seguente risultato di impossibilità

Teorema 2: (J. Hastod, 2002): Approssimare IS con un fattore migliore di \(n^{1 - \epsilon}\) è un problema NP-Hard per ogni \(\epsilon > 0\) fissato.

Procediamo quindi con la dimostrazione del teorema 1.

dim: Andiamo a far vedere che \(\text{IS} \preceq \text{CA}\).

Consideriamo dunque una istanza \(I = \langle G=(V, E), k \rangle\in \text{IS}\), e costruiamo la relativa istanza \(I^{'} \in \text{CA}\) nel seguente modo:

• Ogni arco in \(E\) diventa un oggetto in \(I^{'}\).

• Ogni nodo in \(i \in V\) diventa un agente in \(I^{'}\), con

  • \(S_i := \{ \text{ insieme di oggetti associati ad archi incidenti ad } i\}\)

  • \(t_i := 1\)

Così facendo abbiamo che l'istanza \(I^{'}\) ha una soluzione di valore $ k$ se e solo se esiste un indipendent set di size \(\geq k\). Da questo segue che una soluzione di valore \(k\) per una istanza di \(\text{CA}\) con

\[\frac{\text{OPT}_{\text{CA}}}{k} \leq m^{\frac12 - \epsilon}\]

implicherebbe l'esistenza di una soluzione di valore \(k\) per l'istanza di \(\text{IS}\) con

\[\frac{\text{OPT}_{\text{IS}}}{k} = \frac{\text{OPT}_{\text{CA}}}{k} \leq m^{\frac12 - \epsilon} \leq n^{1 - 2 \epsilon}\]

In quanto \(m \leq n^2\) e quindi \(m^{\frac12 - \epsilon} \leq (n^2)^{\frac12 - \epsilon} = n^{1 - 2 \epsilon}\).

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

---

il nostro obiettivo è quindi quello di definire un meccanismo \(M = \langle g(r), p(x) \rangle\) tale che

• L'algoritmo \(g(\cdot)\) è monotono e calcola una "buona" approsimzione della soluzione ottima.

• Sia \(g(\cdot)\) che \(p(\cdot)\) sono calcolabili in tempo polinomiale.

A tale fine è possibile utilizzare il seguente algoritmo greedy per calcolare l'outcome.

Valgono quindi i seguenti risultati.

Lemma: L'algoritmo \(g()\) appena descritto è monotono.

dim: Per dimostrare questo risultato dobbiamo dimostrare che, fissato un agente \(a_i\) che viene selezionato da \(g()\), abbiamo che \(a_i\) viene comunque selezionato quando aumenta la sua proposta. Ma questo è garantito, in quanto considerando l'ordinamento effettuato dall'algoritmo all'inizio

\[\frac{v_1}{\sqrt{|S_1|}} \geq \ldots \geq \frac{v_i}{\sqrt{|S_i|}} \geq \ldots \frac{v_n}{\sqrt{|S_n|}}\]

abbiamo che aumentando il valore di \(v_i\), l'agente \(a_i\) potrebbe solo muoversi più a sinistra, riuscendo ad essere selezionato ancora più velocemente di prima.

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

---

Dato che abbiamo a che fare con un problema BD, il pagamento dell'agente \(a_i\) equivale al valore della soglia \(\theta_i(r_{-i})\) che determina il punto in cui \(a_i\) viene selezionato.

Per calcolare tale valore consideriamo l'ordinamento effettuato dal nostro algoritmo greedy andando però a rimuovere l'agente \(a_i\)

\[\frac{v_1}{\sqrt{|S_1|}} \geq \ldots \geq \cancel{\frac{v_i}{\sqrt{|S_i|}}} \geq \ldots \frac{v_n}{\sqrt{|S_n|}}\]

e utilizziamo l'algoritmo greedy per trovare il più piccolo indice \(j\) che viene selezionato e tale che \(S_j \cap S_i \neq \emptyset\). Allora il pagamento dell'agente \(a_i\) è così calcolato

\[p_i = \theta_i(r_{-i}) = \begin{cases} 0 \,\,&,\,\, j \text{ non esiste } \\ \displaystyle{v_j \cdot \frac{\sqrt{|S_i|}}{\sqrt{|S_j|}}} \,\,&,\,\, \text{ altrimenti } \\ \end{cases}\]

---

Per concludere, dimostriamo che l'algoritmo \(g(\cdot)\) ritorna una approssimazione della soluzione ottima.

Lemma: Sia \(\text{OPT}\) una soluzione ottimale per il problema CA, e sia \(W\) la soluzione calcolata dall'algoritmo greedy. Allora

\[\sum_{i \in \text{OPT}} v_i \leq \sqrt{m} \cdot \sum_{i \in W} v_i\]

dim. Definiamo, per ogni \(i \in W\), il seguente insieme

\[\text{OPT}_i := \{j \in \text{OPT}: \,\, j \geq i \,\, \land S_j \cap S_i \neq \emptyset\}\]

Notiamo subito che

\[\bigcup\limits_{i \in W} \text{OPT}_i = \text{OPT}\]

Infatti, dato \(k \in \text{OPT}\), consideriamo l'indice \(h\) più piccolo tale che \(h \in W\) e \(S_h \cap S_k \neq \emptyset\). Notiamo che necessariamente \(h \geq k\), e quindi \(k \in \text{OPT}_h\). L'altro lato è dimostrato banalmente per definizione.

Ma allora, per dimostrare il nostro risultato, ci basta dimostrare che

\[\forall i \in W: \,\, \sum_{j \in \text{OPT}_i} v_j \leq \sqrt{m} \cdot v_i\]

infatti se fosse così, allora

\[\sum_{i \in \text{OPT}} v_i \leq \sum_{i \in W} \sum_{j \in \text{OPT}_i} v_j \leq \sum_{i \in W} \sqrt{m} \cdot v_i = \sqrt{m} \sum_{i \in W} v_i\]

---

Notiamo a questo punto che per come è stato definito il nostro algoritmo greedy abbiamo che per ogni \(j \in \text{OPT}_i\), vale

\[\frac{v_j}{\sqrt{|S_j|}} \leq \frac{v_i}{\sqrt{|S_i|}} \iff v_j \leq v_i \cdot \frac{\sqrt{|S_j|}}{\sqrt{|S_i|}}\]

Ma allora per ogni \(i \in W\)

\[\sum_{j \in \text{OPT}_i} v_j \leq \frac{v_i}{\sqrt{|S_i|}} \cdot \sum_{j \in \text{OPT}_i} \sqrt{|S_j|}\]

A questo punto è utile ricordare la Cauchy-Schwarz inequality, che ci dice che dati due vettori \(x = (x_1, \ldots, x_n)\) e \(y = (y_1, \ldots, y_n)\), vale che

\[\sum_{j = 1}^n x_j y_j \leq \Big(\sum_{j = 1}^n x_j^2 \Big)^{\frac12} \cdot \Big(\sum_{j = 1}^n y_j^2 \Big)^{\frac12}\]

Nel nostro caso particolare poniamo \(n := |\text{OPT}_i|\) e per ogni \(j = 1,...,n\) poniamo \(x_j := 1\) e \(y_j := \sqrt{|S_j|}\) per ottenere

\[\begin{split} \sum_{j = 1}^n \sqrt{|S_j|} = \sum_{j = 1}^n x_j y_j &\leq \Big(\sum_{j = 1}^n x_j^2 \Big)^{\frac12} \cdot \Big(\sum_{j = 1}^n y_j^2 \Big)^{\frac12} \\ &= \sqrt{|\text{OPT}_i|} \cdot \sqrt{\sum_{j = 1}^n |S_j|} \\ &\leq \sqrt{|S_i|} \cdot \sqrt{m} \\ \end{split}\]

In quanto abbiamo al massimo \(m\) oggetti, e quindi \(\sum_{j = 1}^m |S_j| \leq m\), e il numero di agenti in \(|\text{OPT}_i|\) non può superare \(|S_i|\), perché altrimenti ci sarebbero due agenti interessati allo stesso oggetto.

Mettendo tutto insieme otteniamo

\[\begin{split} \sum_{j \in \text{OPT}_i} v_j &\leq \frac{v_i}{\sqrt{|S_i|}} \cdot \sum_{j \in \text{OPT}_i} \sqrt{|S_j|} \\ &\leq \frac{v_i}{\sqrt{|S_i|}} \cdot \sqrt{|S_i|} \cdot \sqrt{m} \\ &= v_i \sqrt{m} \\ \end{split}\]

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