8. Il Bargaining Set, il Kernel e il Nucleolo
8.1 Premessa
Questo capitolo è dedicato ad analizzare i concetti di soluzione basati sull’idea di contrattazione. In altre parole i giocatori possono ridiscutere una allocazione x (ovviamente a loro vantaggio) se esistono dei fondamenti “razionali”, su cui basare la loro richiesta. In un certo senso si vuole studiare anche il problema di quale, o quali, coalizioni possono formare, al fine di dare una valutazione della forza, o potere contrattuale dei giocatori. È inutile sottolineare che la decisione di formare una coalizione dipende in gran parte dal payoff che i singoli giocatori possono garantirsi nelle differenti situazioni.
8.2 Il Bargaining Set
Per cominciare è necessario introdurre l’idea di obiezione di un giocatore i contro un altro giocatore j rispetto all’imputazione x.
Definizione 8.2.1 Un’obiezione di i contro j rispetto ad x è una coppia (C, y), con C ⊂ N, i ∈C, j ∉C e y è un’imputazione tale che:
y(C) = v(C)
yk > xk, ∀k ∈C
Successivamente è necessario introdurre l’idea di controbiezione del giocatore j contro il giocatore i rispetto all’obiezione (C, y).
Definizione 8.2.2 Una controbiezione di j contro i rispetto a (C, y) è una coppia (D, z), con D ⊂N, j ∈D, i ∉D e z è un’imputazione tale che:
z(D) = v(D)
zk ≥yk, ∀k ∈D ∩C
zk ≥xk, ∀k ∈D \ C
A questo punto si può definire il Bargaining Set.
Definizione 8.2.3 Il Bargaining Set di un gioco (N, v) è l’insieme delle imputazioni x tali che per ogni obiezione ad x esiste una controbiezione, cioè l’insieme delle imputazioni x per le quali non esistono obiezioni giustificate; si indica con Mi1.
Si può dare la seguente interpretazione: Il giocatore i non è soddisfatto della ripartizione x in quanto ritiene che il giocatore j ottenga troppo, per cui minaccia di formare la coalizione C che esclude j, nella quale tutti i componenti saranno avvantaggiati (obiezione); ma se l’obiezione non è giustificata questo vuol dire che il giocatore j può a sua volta formare la coalizione D, di cui possono far parte anche membri di C, con la quale non svantaggerà nessuno.
Esempio 8.2.1 (Gioco di maggioranza) Data un’imputazione x, sia (C, y) un’obiezione di i contro j; C deve essere della forma {i, h}, perché v(i) = 0, con yᵢ > xᵢ e quindi yₕ < 1 − xᵢ, essendo y(C) = v(C) = 1. Se xⱼ + yₕ ≤ 1 allora j ha una controbiezione e quindi se x ∈ Mi1 si ha yₕ < 1 − xᵢ ⇒ yₕ ≤ 1 − xⱼ da cui si ricava xⱼ ≤ xᵢ, ∀i, j e quindi xᵢ = xⱼ = xₕ = ⅓. Quindi Mi1 = {(⅓, ⅓, ⅓)}.
Esempio 8.2.2 (Io e mia zia (da Osborne - Rubinstein)) Si consideri il gioco semplice monotono a 4 giocatori le cui coalizioni vincenti minimali sono:
W = {{1, 2}, {1, 3}, {1, 4}, {2, 3, 4}}
Data un’imputazione x con x₂ < x₃, un’obiezione di 2 contro 3 è data dalla coalizione {1, 2}, assegnando y₁ = 1 − x₂ − ε e y₂ = x₂ + ε, con ε < x₃ − x₂. 3 non ha alcuna controbiezione (infatti y₁ + x₃ > 1), per cui per la simmetria dei giocatori 2, 3, 4 si ha che x ∈ Mi1 se x₁ = 1 − 3α, x₂ = x₃ = x₄ = α.
Un’obiezione di 1 contro 2 rispetto ad x è data dalla coalizione {1, 3}, assegnando y₁ > 1 − 3α e y₃ < 3α. 2 non ha alcuna controbiezione rispetto ad y (con la coalizione {2, 3, 4}), se α + 3α + α > 1, cioè se α > ⅕.
Un’obiezione di 2 contro 1 rispetto ad x è data dalla coalizione {2, 3, 4}, assegnando y₂ > α e y₃ = y₄ < (1 − α)/2. 1 non ha alcuna controbiezione rispetto ad y (con la coalizione {1, 3} oppure {1, 4}), se 1 − 3α + (1 − α)/2 > 1, cioè se α < 1/7.
Quindi Mi1 = {(1 − 3α, α, α, α), 1/7 ≤ α ≤ ⅕}.
8.3 Il Kernel
A partire dalla definizione di eccesso di una coalizione S rispetto ad un’imputazione x (e(S, x)) si può introdurre l’idea di surplus di un giocatore i contro un altro giocatore j rispetto all’imputazione x.
Definizione 8.3.1 Il surplus di i contro j rispetto ad x è dato da:
In altre parole il surplus rappresenta il massimo guadagno (o minima perdita) del giocatore i se forma una coalizione senza j, supponendo che gli altri giocatori si “accontentino” del payoff x.
A questo punto si possono definire il Kernel e il Prekernel, che fa riferimento alle preimputazioni.
Definizione 8.3.2 Il Kernel di un gioco (N, v) è l’insieme delle imputazioni x tali che si,j(x) > sj,i(x) ⇒xj = v(j), ∀i, j ∈N; si indica con K. Il Prekernel di un gioco (N, v) è l’insieme delle preimputazioni x tali che si,j(x) = sj,i(x); si indica con K̄.
Teorema 8.3.1 Il Kernel è un sottoinsieme del Bargaining Set.
Esempio 8.3.1 (Gioco di maggioranza) Per il Teorema 8.3.1 K = {(⅓, ⅓, ⅓)}.
Esempio 8.3.2 (Io e mia zia (da Osborne - Rubinstein)) Data un’imputazione x ∈ K, per il Teorema 8.3.1 si ha x = (1 − 3α, α, α, α), 1/7 ≤ α ≤ ⅕; allora s₁,₂(x) = 2α e s₂,₁(x) = 1 − 3α; essendo 1 − 3α > 0, cioè x₁ > v(1), deve essere verificato s₂,₁ ≤ s₁,₂, cioè 1 − 3α ≤ 2α da cui α ≥ ⅕ e quindi K = {(⅖, ⅕, ⅕, ⅕)}.
Esiste una definizione alternativa del Kernel che si basa su differenti definizioni di obiezione e controbiezione.
Definizione 8.3.3 Un’obiezione di i contro j rispetto ad x è una coalizione C ⊂N, i ∈ C, j ∉C e xj > v(j). Una controbiezione di j contro i è una coalizione D ⊂N, j ∈D, i ∉D e e(D, x) ≥e(C, x). Il Kernel è l’insieme delle imputazioni x tali che per ogni obiezione C di un qualsiasi i contro j esiste una controbiezione D di j contro i.
8.4 Il Nucleolo
Per finire è possibile definire anche il nucleolo in funzione di una opportuna obiezione e controbiezione.
Definizione 8.4.1 Un’obiezione ad x è una coppia (C, y), con C ⊂N e y è un’imputazione tale che e(C, x) > e(C, y), cioè y(C) > x(C). Una controbiezione rispetto a (C, y) è una coalizione D ⊂N tale che e(D, y) > e(D, x), cioè x(D) > y(D) e e(D, y) ≥e(C, x). Il nucleolo è l’insieme delle imputazioni x tali che per ogni obiezione (C, y) esiste una controbiezione D.
Teorema 8.4.1 Il nucleolo è un elemento del Kernel.
Esempio 8.4.1 (Giochi precedenti) Per il Teorema 8.4.1 il nucleolo del gioco di maggioranza è ν = {(⅓, ⅓, ⅓)} e quello del gioco io e mia zia è ν = {(⅖, ⅕, ⅕, ⅕)}.
Per concludere si possono esaminare due classi di giochi per le quali è particolarmente semplice determinare il nucleolo, i bankruptcy game e i fixed tree game.
Per un bankruptcy game (E, c) il nucleolo si può calcolare facilmente come:
Questa soluzione è nota anche come “regola del Talmud”, per la seguente citazione nel libro della legge ebraica: Se un uomo muore lasciando tre mogli alla prima delle quali aveva promesso 100, alla seconda 200 e alla terza 300, si divida il patrimonio nel modo seguente:
| Lascito | Prima | Seconda | Terza |
|---|---|---|---|
| 100 | 33⅓ | 33⅓ | 33⅓ |
| 200 | 50 | 75 | 75 |
| 300 | 50 | 100 | 150 |
Questa regola può essere rappresentata tramite i seguenti vasi comunicanti:
Per un fixed tree game si può utilizzare la seguente procedura (painting story). Si può supporre che la manutenzione dell’albero consista in nella tinteggiatura; tutti i giocatori dipingono alla stessa velocità e iniziano contemporaneamente. Ogni giocatore inizia a dipingere il secondo arco a lui più vicino, escludendo cioè quello entrante nel vertice a lui associato, che non sia ancora stato dipinto; per ultimo dipinge l’arco entrante. Quando un qualsiasi arco viene terminato si riassegnano i giocatori, sempre con le stesse regole.
Esempio 8.4.2 (Nucleolo di un fixed tree game) Per la situazione rappresentata nella figura si ha:
- Le assegnazioni iniziali dei giocatori sono: 1 →(0, 1), 2 →(0, 1), 3 →(0, 1), 4 →(1, 3), 5 →(1, 3) dopo due unità di tempo 4 e 5 hanno terminato l’arco (1, 3);
- Le nuove assegnazioni sono: 1 →(0, 1), 2 →(0, 1), 3 →(0, 1), 4 →(0, 1), 5 →(0, 1) dopo una unità di tempo l’arco (0, 1) è terminato; 1 e 3 hanno terminato;
- Le ultime assegnazioni sono: 2 →(1, 2), 4 →(3, 4), 5 →(3, 5) 5 termina dopo due unità di tempo; 4 termina dopo tre unità di tempo; 2 termina dopo cinque unità di tempo.
Il nucleolo è ν = (3, 8, 3, 6, 5).