AGT - 07 - Stackelberg MST Game

Per risolvere questo problema è possibile utilizzare l'algoritmo di Kruskal, che funziona come segue:

• Si inizia con un albero vuoto \(T\);

• Si procede considerando gli archi di \(G\) in ordine non-decrescente, ovvero dal più piccolo al più grande, e si aggiunge l'arco \(e\) a \(T\) se e solo se l'aggiunta di questo arco non va a creare in \(T\) cicli.

Andiamo a vedere un esempio dello stackelberg MST game. Nei seguenti esempi gli archi saranno colorati di vari colori utilizzando il seguente schema:

• Gli archi rappresentano archi in \(R\), che sono archi il cui peso è scelto in modo statico all'inizio del gioco.

• Gli archi rappresentano archi in \(B\), che sono archi il cui peso deve essere scelto dal leader definendo la funzione di pesatura \(p(\cdot)\).

• Gli archi infine sono gli archi che il follower sceglie di includere nella costruzione del MST. Di questi archi verdi, il peso di quelli che originariamente erano blu dovrà essere aggiunto al guadagno finale del leader.

Consideriamo quindi la seguente istanza.

Una volta che il leader ha scelto i pesi degli archi blu, il follower può utilizzare l'algoritmo di kruskal per ottenere il seguente MST

Il guadagno del leader in questo caso è \(6\). È possibile però fare di meglio, come mostra la seguente pesatura.

Il guadagano adesso infatti è di 12!

Prima di analizzare il problema è importante esplicitare le seguenti assunzioni:

• Il grafo \(G\) deve contenere uno spanning tree composto da soli archi rossi. Se così non fosse infatti non sarebbe possibile dare un limite superiore al guadagno ottimale del leader.

• Tra tutti gli archi con lo stesso peso, quelli blu sono sempre i preferiti. Notiamo che se riusciamo ad ottenere un guadagno \(r\) con questa assunzione, allora anche rimuovendola siamo comunque in grado di ottenere un guadagno di \(r - \epsilon\), con \(\epsilon > 0\) abbastanza leggermente i pesi.

---

Siamo adesso in grado di analizzare il gioco sotto due aspetti diversi:

1. Un risultato di NP-hardness;

2. Un algoritmo approssimante.

Il problem MSC è così definito:

• Input:

  • Insieme di oggetti \(U = \{u_1, u_2, \ldots, u_n\}\).

  • Insieme di sottoinsiemi di \(U\), \(S = \{S_1, \ldots, S_m\}\), con \(S_j \subseteq U\)

• Objective: Trovare un cover \(C \subseteq S\), ovvero un sottoinsieme di \(S\) tale che

  \[\bigcup\limits_{x \in C} x = U\]

  e minimizzare la sua taglia \(|C|\).

---

Sia \(I = \langle U, S\rangle\) una istanza del MSC. Prima di iniziare assumiamo l'esistenza di un elemento \(u_n \in U\) che fa parte di ogni sottoinsieme \(S_j\). Formalmente \(\forall S_j \in S: \exists u_n \in U: u_n \in S_j\). Notiamo che questa assunzione non modifica la complessità del problema.

Data l'istanza \(I\) con \(U = \{u_1, \ldots, u_n\}\) e \(S = \{S_1, \ldots, S_m\}\) costruiamo il seguente grafo \(G = (V, R \cup B, w)\).

dove gli archi connettono \(u_i\) a \(S_j\) se e solo se \(u_i \in S_j\). Formalmente,

\[ B := \{(u_i, S_j): \,\, u_i \in S_j \text{ in } I\}\]

Per capire meglio la riduzione vediamo qualche pesatura semplice che il leader può effettuare:

• Tutti i pesi a 2: In questo caso applicando Kruskal costruiamo come prima cosa il cammino rosso che collega tutti i nodi tra loro

  

  dopo questo prendiamo un arco blu di costo \(2\) per toccare ogni sottoinsieme

  

  Tutti gli MST ottenibili in questo modo portano dunque un guadagno di \(2m\) al leader.

  ---

• Tutti i pesi a 1: In questo caso prima vengono scelti tutti gli archi blu che collegano un sottoinsieme \(S_j\) ad un nodo \(n_i\) per ogni nodo \(n_i\) del grafo

  

  e poi un ulteriore arco blu per ciascuno dei restanti \(t\) sottoinsiemi non ancora toccati.

  

  In questo modo ho un MST formato completamente da archi blu, e quindi il guadagno totale è \(n + m - 1\).

---

Da questi esempi è possibile intuire che al leader possa convenire il seguente approccio: pesare con \(1\) il numero sufficient di archi per poter coprire tutti i nodi \(n_i\), e pesare con \(2\) i restanti archi. In particolare, supponiamo di avere un set cover \(C\) di size \(t\). Definiamo quindi la seguente pesatura

\[\forall e = (u_i, S_j) \in R: \,\, p(e) = \begin{cases} 1 \,\,&,\,\, S_j \in C \\ 2 \,\,&,\,\, \text{ altrimenti } \\ \end{cases}\]

Con questa pesatura il follower prenderà tutti gli archi blu della forma \((u_n, S_j)\) con \(S_j \in C\), che sono \(t\), per i restanti \(n-1\) nodi \(u_i\) prenderà degli archi blu di costo \(1\), e per i tutti i sottoinsiemi che non appartengono al cover \(C\) prenderà degli archi blu di costo \(2\).Il guadagno finale è quindi di

\[t + (n - 1) + 2(m - t)\]

---

Procediamo quindi dimostrando il seguente claim: \(I = \langle U, S\rangle\) ha un cover set di size \(\leq t\) se e solo se il valore massimo ottenibile dal leader è \(r^{*} \geq n + t - 1 + 2(m - t) = m + 2m - t - 1\).

Siano \(c_1 < c_2 < \ldots < c_k\) i diversi costi fissati degli archi rossi. Il Single Price Algorithm definisce per ogni costo \(c_i\) la pesatura \(p_{c_i}(\cdot)\) nel seguente modo

\[$\forall e \in B: \,\,\ p_{c_i}(e) := c_i\]

e guarda il guadagno ottenuto con questa pesatura. Alla fine ritorna la pesatura \(p_{c_j}\) che ritorna il migliore guardagno.

Notiamo che il nome dell'algoritmo deriva dal fatto che di volta in volta tutti gli archi blu vengono pesati con lo stesso peso.

Vale il seguente risultato di approssimazione

Teorema: Sia \(\hat{r}\) il guadagno ottimale, e sia \(r\) il guadagno ottenuto applicando il single price algorithm. Allora

\[\hat{r} \leq r \cdot \rho \iff \frac{\hat{r}}{r} \leq \rho\]

dove,

\[\rho := 1 + \min\{\log{|B|}, \log{(n-1)}, \log{\Big(\frac{c_k}{c_1}\Big)}\}\]

dim: Sia \(T\) l'MST associato alla funzione di pesatura ottima, e sia \(h_i\) il numero di archi blu in \(T\) di costo \(c_i\). Esprimendo il guadagno del leader come somma di aree di rettangoli troviamo la seguente figura

Andiamo adesso a racchiudere questa area totale sotto una curva che segue l'andamento di \(g(x) = 1/x\) e che è tangente ad un vertice di questi rettangoli.

Notiamo che la particolare equazione di questa curva è data da

\[f(x) = x_a \cdot A \cdot \frac1x\]

In questo modo infatti imponiamo che \(f(x_a) = A\). Infine, per avere che la curva si trovi sopra ciascun rettangolo, dobbiamo avere che \(x_a \cdot A \geq c_k\).

---

Come proprietà della funzione \(g(x) = 1/x\) abbiamo che l'area di ogni rettangolo ha la stessa area. Graficamente,

In particolare quindi l'area del rettangolo con base \(1\) è proprio \(x_a \cdot A\).

---

Questo significa che possiamo dare il seguente upper bound al guadagno della soluzione ottima

\[\hat{r} \leq x_a A + \int\limits_{1}^{x_b} x_a \cdot A \cdot \frac1x \,\, dx = x_a A(1 + \log{x_b} - \log{1}) = x_a A (1 + \log{x_b})\]

Andiamo ora a dare dei lower bounds al valore della soluzione calcolata dal nostro single price algorithm. A tale fine iniziamo notando che per come funziona l'algoritmo abbiamo che

\[r = \underset{c_i}{\max} |B| \cdot c_i\]

e quindi, dato che \(A\) è uguale al peso di qualche arco rosso \(c_j\), abbiamo che

\[r \geq |B| c_j \geq x_a c_j = x_a A\]

ovvero

\[\frac{\hat{r}}{r} \leq 1 + \log{x_b}\]

Continuando, notiamo che

\[x_b = \sum_{j} h_j \leq \min\{n-1, |B|\}\]

e quindi

\[\frac{\hat{r}}{r} \leq 1 + \min\{\log{(n-1)}, \log{|B|}\}\]

---

Per finire, è possibile possibile dimostrare anche che \(\hat{r}/r \leq 1 + \log{\frac{c_k}{c_1}}\). Per fare questo dobbiamo analizzare il grafico di prima pensando però a \(x\) come alla variable dipendente e a \(y\) come alla variable indipendente. Graficamente

Nuovamente, l'area sotto la curva ci permette di dare un upper bound al guadagno totale. Questa volta però troviamo che

\[\begin{split} \hat{r} \leq x_aA + \int\limits_{c_1}^{c_j} x_aA \frac1y \,\, dy &= x_aA (1 + \log{c_k} - \log{c_1}) \\ &= x_a A \Big( 1 + \log{\frac{c_k}{c_1}}\Big) \\ \end{split}\]

Mettendo tutto assieme troviamo

\[\frac{\hat{r}}{r} \leq 1 + \min\{\log{(n-1)}, \,\, \log{|B|}, \,\, \log{\frac{c_k}{c_1}}\}\]

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

L'analisi appena effettuata ci dice che nel caso peggiore il single price algorithm ci permette di ottenere una approssimazione di \(\theta(\log n)\). In generale però potrebbero esistere altre analisi che migliorano il rapporto di approssimazione. Detto altrimenti, il nostro algoritmo potrebbe essere migliore di quanto dimostrato.

In questo caso però non è così. Infatti esiste un caso in cui l'approssimazione ottenuta dall'algoritmo è proprio \(\theta(\log n)\). Questo ci permette quindi di affermare che l'analisi che abbiamo fatto è "tight", nel senso che con questo particolare algoritmo non possiamo fare meglio di così.

L'esempio menzionato è il seguente

In questo caso la soluzione ottiamle ottiene un guadagno di

$$\hat{r} = ^n \frac{1}{j} = H_n = (n)$

dove \(H_n\) è l'n-esimo numero armonico. Notiamo invece che il single price algorithm invece ottiene al massimo un guadagno di \(r = 1\), in quanto

\[r = \underset{j \in \{1, \ldots, 1/n\}}{\max} j \cdot \frac{1}{j} = \underset{j \in \{1, \ldots, 1/n\}}{\max} 1 = 1\]