Teoria dei giochi.

9. Giochi su reti

9.1 Giochi sugli archi e sui nodi

Col termine giochi su reti si indicano quelle classi di giochi che fanno riferimento ad un problema che può essere rappresentato tramite una rete. Questi giochi appartengono alla classe degli Operations Research Games, cioè giochi derivanti da problemi di ricerca operativa. Gli ORG risultano estremamente interessanti da un punto di vista strutturale e computazionale in quanto “ereditano” dalla struttura del problema alcune caratteristiche che permettono di semplificare alcuni aspetti complessi della Teoria dei Giochi, quali la determinazione della funzione caratteristica e il suo stesso significato. Solitamente si distinguono due tipi di giochi su reti: Giochi sugli archi: I giocatori controllano gli archi. Giochi sui nodi: I giocatori controllano i nodi.

Il controllo non è necessariamente biunivoco, nel senso che un giocatore può controllare più elementi oppure un elemento può essere controllato da più giocatori (comitato) oppure possono esistere elementi non controllati da alcun giocatore (pubblici).

Ai problemi su reti, o comunque legati ai grafi, può essere associato un gioco supponendo di avere più decisori. In questa trattazione verrano analizzati alcuni problemi, evidenziando alcune caratteristiche interessanti del gioco TU associato, precisando se, nella versione classica, si tratta di giochi di costo o di profitto.

9.1.1 Flow Game

Sono giochi di profitto associati ad un problema di flusso massimo. Ogni giocatore può controllare più archi e ogni arco è controllato da un solo giocatore; non ci sono archi pubblici. Il valore di una coalizione è dato dal valore del flusso massimo dalla sorgente al pozzo, utilizzando la sottorete che contiene solo archi controllati dai giocatori della coalizione. Questi giochi sono bilanciati e in particolare sono totalmente bilanciati, cioè il gioco ristretto ad una qualsiasi coalizione è bilanciato; una allocazione nel nucleo si ottiene assegnando ai giocatori che controllano gli archi di un taglio di capacità minima le capacità degli archi del taglio, in accordo col risultato di Owen. Le allocazioni corrispondenti ai tagli di capacità minima non rispettano alcun criterio di equità.

Esempio 9.1.1 (Nucleo di un flow game) Si consideri il seguente problema di flusso da v_s a v_t, dove il giocatore I controlla il primo arco e II controlla il secondo:

La funzione caratteristica del gioco associato è:

v(I) = v(II) = 0; v(I, II) = 1

Applicando il risultato esposto si ottiene l’allocazione x = (1, 0) corrispondente al taglio contenente l’arco da v_s a v₁. Tale allocazione sta nel nucleo, ma tratta in modo diverso i giocatori che sono simmetrici rispetto al gioco, mentre il giocatore II “contribuisce” anche maggiormente alla rete, fornendo un arco di capacità superiore.

Un altro risultato interessante è dato dal seguente teorema.

Teorema 9.1.1 (Kalai e Zemel, 1982) Un gioco è totalmente bilanciato se e solo se è un flow game.

La dimostrazione è abbastanza articolata.

Definizione 9.1.1 Dati due giochi u, v si chiama gioco minimo di u e v il gioco w = min(u, v) definito da w(S) = min (u(S), v(S)), ∀S ⊆N.

Osservazione 9.1.1

• Se u e v sono totalmente bilanciati allora il gioco w è totalmente bilanciato in quanto Core(u_S) ⊆Core(w_S) oppure Core(v_S) ⊆Core(w_S), ∀S ⊆N.

Teorema 9.1.2 Un gioco è totalmente bilanciato se e solo se è il gioco minimo di un insieme finito di giochi additivi.

Dimostrazione Per l’osservazione precedente la condizione è sufficiente. Viceversa sia v un gioco totalmente bilanciato e sia {v^S}_S⊆N, un insieme finito di giochi additivi a n giocatori costruiti nel seguente modo: per ogni S ⊆N

• sia (x_i)_i∈S una allocazione di Core(v_S);
• siano x_j, j ∈N \ S
  n −s numeri reali con x_j ≥v(N);
• sia v^S il gioco additivo generato da (x₁, ..., x_n);

allora si ha:

min
_S⊆N{v^S(T)} = v^T(T) = v(T), ∀T ⊆N ⇒v = min{v^S}

Osservazione 9.1.2

• (x_i)_i∈S ∈Core(v_S) ⇒v^S(T) ≥v(T) se T ⊆S, con v^S(T) = v(T) se T = S.
• x_j ≥v(N), j ∈N \ S ⇒v^S(T) ≥v(T) se T ⊈S.

Lemma 9.1.1 Ogni gioco additivo è un flow game.

Dimostrazione Il gioco additivo generato da (x₁, ..., x_n) equivale al flow game generato da una rete con n archi che collegano la sorgente al pozzo, in cui l’arco a_i appartiene al giocatore i e ha capacità x_i.

Lemma 9.1.2 Il gioco minimo di due flow game è un flow game.

Dimostrazione Dati due giochi v^′ e v^′′ generati dalle reti G^′ e G^′′ il gioco v = min(v^′, v^′′) è generato dalla rete ottenuta facendo coincidere il pozzo di G^′ con la sorgente di G^′′.

Dimostrazione del Teorema di Kalai-Zemel Per i Lemmi 9.1.1 e 9.1.2 e il Teorema 9.1.2 la condizione è sufficiente. Viceversa un flow game è totalmente bilanciato poiché i suoi sottogiochi sono flow game.

9.1.2 Shortest Path Game

Sono giochi di profitto associati ad un problema di cammino minimo. Ogni giocatore può controllare più nodi e ogni nodo è controllato da un solo giocatore; non ci sono nodi pubblici; alcuni nodi sono detti sorgenti, altri pozzi. Il valore di una coalizione è dato dalla differenza tra il ricavo ottenuto trasportando un bene da una qualsiasi sorgente ad un qualsiasi pozzo tra quelli controllati dai giocatori della coalizione e il costo del cammino minimo che attraversa solo nodi posseduti dai giocatori della coalizione; se la differenza è negativa il valore della coalizione è nullo. Poiché il nucleo può essere vuoto si può utilizzare il valore di Shapley come regola di ripartizione dei profitti che risponda ai seguenti principi di equità (Fragnelli, GarcíaJurado, Mendez-Naya, 2000):

• efficienza;
• irrilevanza (i giocatori che controllano solo nodi isolati ricevono un payoff nullo);
• adiacenza (i giocatori che controllano gli estremi di un arco hanno la stessa variazione di payoffse si elimina l’arco);
• non collegamento (due giocatori che non sono connessi hanno la stessa variazione di payoffse si elimina l’altro giocatore).

9.1.3 Minimum Cost Spanning Tree Game

Sono giochi di costo associati ad un problema di minimo albero ricoprente. Ogni giocatore controlla un solo nodo e ogni nodo è controllato da un solo giocatore; non ci sono nodi pubblici, eccetto la sorgente, alla quale tutti vogliono essere collegati. Il problema richiede che il grafo sia non orientato e completo (clique). Il valore di una coalizione è dato dal valore dell’albero ricoprente di costo minimo che unisce i nodi corrispondenti ai giocatori della coalizione con la sorgente, attraversando solo nodi posseduti dai giocatori della coalizione. Eliminando la restrizione sui nodi si ottiene un gioco monotono, cioè un gioco in cui il valore della coalizione non decresce se si aggiungono altri giocatori. Questi giochi sono bilanciati e un’allocazione nel nucleo, detta allocazione di Bird (1976), si ottiene assegnando ad ogni giocatore il costo dell’ultimo arco dell’unico cammino non orientato che nell’albero di costo minimo collega il nodo corrispondente alla radice.

Il nucleo e il nucleolo equivalgono al prodotto cartesiano del nucleo e del nucleolo di una decomposizione in sottogiochi secondo una struttura efficiente {P₁, ..., P_m} dei giocatori (Granot e Huberman, 1981), cioè secondo i sottoalberi dell’albero di costo minimo aventi origine dalla sorgente, e ridefinendo il costo c_0j degli archi (0, j) come:

Tale risultato non si estende al valore di Shapley.

Esempio 9.1.2 (Decomposizione di uno spanning tree) Nella figura seguente il nodo 0 rappresenta la sorgente, gli archi “spessi” rappresentano uno spanning tree di costo

minimo e a destra è rappresentata la decomposizione efficiente {{1, 3}, {2, 4}} (si noti che il costo dell’arco (0, 4) diventa 3 unità).

La decomposizione vale per il nucleo e per il nucleolo, ma non per il valore di Shapley.

L’allocazione di Bird non è equa per i giocatori “più vicini” alla sorgente. Esistono due modi per ottenere altre ripartizioni che risultano preferibili per questi giocatori (Granot e Huberman, 1984).

Richiesta debole: Un giocatore chiede ad alcuni successori secondo la soluzione di Bird di “rimborsare” il risparmio ottenuto grazie alla sua presenza.

Richiesta forte: Un giocatore chiede ad alcuni successori di “rimborsare” oltre al risparmio ottenuto grazie alla sua presenza anche il “rimborso” che lui ha versato ai suoi predecessori.

La richiesta debole genera soluzioni nel nucleo se applicata alla soluzione di Bird; la richiesta forte genera soluzioni nel nucleo se applicata a una soluzione nel nucleo.

Esempio 9.1.3 (Richiesta debole - Richiesta forte) Si consideri il gioco associato alla rete seguente:

La soluzione di Bird assegna ai giocatori i payoff(1, 1, 1). Il primo giocatore con una richiesta debole ottiene (0, 2, 1). Il secondo giocatore con una richiesta debole può ottenere (0, 1, 2), mentre con una richiesta forte può ottenere (0, 0, 3).

9.1.4 Minimum Cost Forest Game

Sono giochi di costo associati ad un problema di minima foresta ricoprente. Ogni giocatore controlla un solo nodo e ogni nodo è controllato da un solo giocatore; non ci sono nodi pubblici, eccetto le sorgenti; ogni nodo vuole essere collegato a una o più sorgenti; gli archi possono servire per il collegamento a qualunque sorgente. Il problema richiede che il grafo sia non orientato ma non necessariamente completo. Il valore di una coalizione è dato dal valore della foresta di costo minimo che unisce i nodi corrispondenti ai giocatori della coalizione con le sorgenti richieste, attraversando qualsiasi nodo (algoritmo di Kruskal modificato).

Teorema 9.1.3 (Kuipers, 1977) Il nucleo di un MCFG è non vuoto se è verificata una delle due condizioni seguenti:

1. esiste almeno un nodo connesso con tutte le sorgenti (la soluzione è un albero);
2. nessun nodo è connesso con più di una sorgente (la soluzione è un insieme di alberi);

Osservazione 9.1.3

• Se il gioco ha al più due sorgenti (o al più due giocatori) il nucleo è certamente non vuoto, in quanto una delle due condizioni precedenti è certamente verificata.

Esempio 9.1.4 (Nucleo vuoto) Sia dato il gioco rappresentato dalla seguente rete in cui le richieste giocatore-sorgente sono 1 −I, 2 −II, 3 −III e gli archi ’fini’ hanno costo 3 e quelli ’spessi’ costo 5.

Si consideri la collezione bilanciata N = ½((12), (13), (23)).

I corrispondenti valori sono: c(N) = C(I −2, 2 −1, 1 −II) + C(III −3) = 14
c(12) = C(I −2, 2 −1, 1 −II) = 9
c(13) = C(I −3, 3 −1, 1 −III) = 9
c(23) = C(II −3, 3 −2, 2 −III) = 9
e quindi:

14 = c(N) ≤ ½c(12) + ½c(13) + ½c(23) = 27/2.

Assurdo.

9.1.5 Traveling Salesman Game

Sono giochi di costo associati ad un problema del commesso viaggiatore. Ogni giocatore controlla un solo nodo e ogni nodo è controllato da un solo giocatore; non ci sono nodi pubblici, eccetto la sorgente. Il problema richiede che il grafo sia fortemente connesso. Il valore di una coalizione è dato dal costo del circuito di costo minimo che unisce i nodi corrispondenti ai giocatori della coalizione e la sorgente.

Teorema 9.1.4 (Potters, Curiel e Tijs, 1992) Il nucleo di un TSG è non vuoto se ci sono al più tre giocatori.

Esempio 9.1.5 (Nucleo vuoto) Si consideri il gioco rappresentato dalla seguente matrice dei costi, in cui 0 rappresenta la sorgente:

Si consideri la collezione bilanciata N = ½((123), (124), (34)). I corrispondenti valori sono:

c(N) = C(0 − 1 − 2 − 3 − 4 − 0) = 6
c(123) = C(0 − 1 − 2 − 3 − 0) = 4
c(124) = C(0 − 4 − 2 − 1 − 0) = 4
c(34) = C(0 − 4 − 3 − 0) = 3

e quindi:

6 = c(N) ≤ ½c(123) + ½c(124) + ½c(34) = 11/2.

Assurdo.

Teorema 9.1.5 (Kuipers, 1991 e Tamir, 1989) Se il problema è simmetrico il nucleo di un TSG è non vuoto se ci sono al più cinque giocatori.

9.2 Grafi e cooperazione

In generale si suppone che tutti i giocatori possano o vogliano formare qualsiasi coalizione, ma questo non è necessariamente verificato in numerose situazioni reali, ad esempio si pensi alle coalizioni politiche. In questo caso si parla di strutture cooperative, che possono essere rappresentate con un grafo non orientato in cui i nodi rappresentano i giocatori e gli archi uniscono i giocatori che accettano di unirsi in una coalizione (Myerson, 1977).

Formalmente il nodo v_i è associato al giocatore i e l’arco a_ij = (v_i, v_j) indica che i giocatori i e j sono disposti a far parte della stessa coalizione.

In alcune situazioni può essere necessario che per formare una coalizione ciascun giocatore debba essere disposto a unirsi a tutti gli altri, mentre in altre è sufficiente la disponibilità a formare la coalizione “attraverso alcuni giocatori intermedi”. In altre parole nel primo caso una coalizione si forma se il corrispondente sottografo è completo, mentre nel secondo caso è sufficiente che sia connesso.

Gioco ristretto rispetto a un grafo G I giocatori possono realizzare solo le coalizioni indotte dal grafo G; il valore della coalizione è dato dalla somma dei valori delle sottocoalizioni che possono effettivamente formarsi.

Osservazione 9.2.1

• Esiste una formulazione più restrittiva in cui due giocatori i e j possono far parte della stessa coalizione solo se entrambi esprimono questa volontà (Claim game). In questo caso è necessario utilizzare un grafo orientato, in cui l’arco a_ij esprime che il giocatore i accetta di entrare in una coalizione con il giocatore j, ma non viceversa.

Esempio 9.2.1 (Coalizioni indotte) Si consideri un gioco a quattro giocatori con la struttura indotta dal seguente grafo G:

Se per formare una coalizione si richiede la reciprocità si hanno le seguenti coalizioni effettive:

1 - 2 - 3 - 4 - 12 - 13 - 34 Se non si richiede la reciprocità le coalizioni effettive sono:

1 - 2 - 3 - 4 - 12 - 13 - 34 - 123 - 134 - 1234 Il gioco v_G ristretto rispetto a G risulta nel primo caso:

v_G(1) = v(1)
v_G(12) = v(12)
v_G(123) = max {v(12) + v(3), v(13) + v(2)}
v_G(2) = v(2)
v_G(13) = v(13)
v_G(124) = v(12) + v(4)
v_G(3) = v(3)
v_G(14) = v(1) + v(4)
v_G(134) = max {v(13) + v(4), v(1) + v(34)}
v_G(4) = v(4)
v_G(23) = v(2) + v(3)
v_G(234) = v(2) + v(34)
v_G(24) = v(2) + v(4)
v_G(34) = v(34)
v_G(N) = max {v(12) + v(34), v(13) + v(2) + v(4)}

e nel secondo caso:

v_G(1) = v(1)
v_G(12) = v(12)
v_G(123) = v(123)
v_G(2) = v(2)
v_G(13) = v(13)
v_G(124) = v(12) + v(4)
v_G(3) = v(3)
v_G(14) = v(1) + v(4)
v_G(134) = v(134)
v_G(4) = v(4)
v_G(23) = v(2) + v(3)
v_G(234) = v(2) + v(34)
v_G(24) = v(2) + v(4)
v_G(34) = v(34)
v_G(N) = v(1234)

Regola di allocazione rispetto a un grafo G

dove G è l’insieme dei grafie S ∈N/G è una coalizione indotta da una componente connessa di G.

Stabilità Una regola di allocazione x è stabile se e solo se:

x_i(G) ≥x_i(G \ (i, j)) e x_j(G) ≥x_j(G \ (i, j))
∀(i, j) ∈G

Equità Una regola di allocazione x è equa se e solo se:

x_i(G) −x_i(G \ (i, j)) = x_j(G) −x_j(G \ (i, j))
∀(i, j) ∈G

Teorema 9.2.1 (Myerson, 1977) L’unica regola di allocazione equa è il valore di Shapley del gioco ristretto rispetto al grafo. Inoltre se il gioco è superadditivo l’allocazione è stabile.

Esempio 9.2.2 (Valore di Shapley del gioco ristretto) Sia dato il gioco:

N = 1, 2, 3 v(1) = 1; v(2) = 2; v(3) = 3; v(12) = 6; v(13) = 8; v(23) = 10; v(N) = 12 I giochi ristretti (non reciproci) e i valori di Shapley sono: