Olga Bondareva

Olga Nikolaevna Bondareva (in russo: Ольга Николаевна Бо́ндарева; Leningrado, 27 aprile 1937 – San Pietroburgo, 9 dicembre 1991) è stata una matematica sovietica esperta nel campo della teoria dei giochi. Il teorema di Bondareva-Shapley è chiamato in onore di O. N. Bondareva.

Biografia

Nel 1954 Olga entrò alla Facoltà di Matematica e Meccanica dell'Università statale di Leningrado e nel 1963 discusse la propria tesi in scienze fisiche e matematiche. Il docente supervisore era Nikolai Nikolayevich Vorobyov, fondatore della scuola russa di teoria dei giochi.

Nel 1984 presso la Facoltà di Matematica Computazionale e Cibernetica dell'Università Statale di Mosca discusse la propria tesi di dottorato in Scienze Fisiche e Matematiche.

Dall'ottobre 1959 all'aprile 1972 lavorò come assistente di ricerca junior, in seguito come assistente professore (nel campo della ricerca operativa), infine come assistente di ricerca senior presso la Facoltà di Matematica e Meccanica dell’Università statale di Leningrado (oggi San Pietroburgo).

Nel maggio del 1972 venne licenziata per aver sostenuto uno studente che aveva richiesto di lasciare l'URSS per Israele. Il mese seguente venne assunta alla Facoltà di Economia dell'Università statale di Leningrado come ricercatore senza però aver diritto ad insegnare.

Dal luglio 1984 al marzo 1989 fu Ricercatore senior presso l'Istituto di Fisica, nell'ottobre 1989 fece ritorno alla Facoltà di Matematica e Meccanica dell’Università statale di Leningrado con il ruolo di Ricercatore principale e lì lavorò fino alla sua morte.

Olga è stata sposata con Lev Alexandrovich Gordon e dalla loro unione nacquero Maxim (1966) e Gregory (1974).

Olga Bondareva morì il 9 dicembre 1991 investita da un camion mentre attraversava la strada nelle vicinanze della sua casa a San Pietroburgo. Nel Bollettino dell’Università di San Pietroburgo, serie 1. Matematica-Meccanica-Astronomia, numero 3, 1992 è pubblicato il seguente necrologio: Per alcuni, Olga Nikolaevna era altamente qualificata ed esperta, una sorgente di idee, di valutazioni scientifiche, di consigli professionali, per altri era un sostegno nell'oceano della vita. Olga possedeva una forte libertà interiore ed un grande senso di giustizia […].

Matematica e Teoria dei Giochi

Bondareva ha pubblicato oltre 70 articoli scientifici sulla teoria dei giochi e sulla matematica. È stata membro del comitato editoriale della rivista internazionale Games and Economic Behaviour. Il suo lavoro sulla teoria dei giochi cooperativi ha ricevuto riconoscimenti internazionali. Il risultato più famoso, ottenuto durante i suoi studi post-laurea, sono le condizioni necessarie e sufficienti affinché il nucleo di un gioco cooperativo sia non vuoto. Fu pubblicato nel 1963 nella raccolta Problems of Cybernetics, una pubblicazione piuttosto prestigiosa, ma non tradotta in inglese, e non fu notata subito nel blocco occidentale. Nel 1967, un risultato simile venne pubblicato da Lloyd Shapley. Shapley, dopo aver appreso della pubblicazione di Bondareva, riconobbe incondizionatamente la sua anteriorità assicurando così ad O. Bondareva il riconoscimento unanime.

La teoria del nucleo per i giochi cooperativi

Nel 1963, sulla rivista Проблемы кибернетики (Problemi di Cibernetica) comparve l'articolo di Olga Bondareva екоторые применения методов линейного программирования к теории кооперативных игр (Alcune applicazioni dei metodi della programmazione lineare alla teoria dei giochi cooperativi). L'articolo ^[1] della matematica russa in apertura afferma che se l’insieme delle soluzioni $L$ di un gioco cooperativo ad n persone coincide con il nucleo $U$ allora $L$ presenta una ed un’unica soluzione, l’articolo continua fornendo condizioni necessarie e sufficienti affinché il nucleo di un gioco cooperativo ad n giocatori sia non vuoto: $U\neq \{\varnothing \}$ . Infine Olga B. introduce il concetto di copertura dell’insieme dei giocatori attraverso un insieme di numeri reali non negativi (pesi) ed esprime la ricerca delle soluzioni $L$ nel senso di von Neumann-Morgenstern nei termini di un problema di programmazione lineare. La formulazione del problema di programmazione lineare presenta come incognite i pesi e come funzione da massimizzare la combinazione dei pesi con i valori delle singole coalizioni. Olga B. svela che l’eventuale risoluzione del problema della copertura massimale implica che il gioco presenti nucleo non vuoto e che pertanto la coalizione $R$ costituita da tutti i giocatori risulta stabile. In sintesi, il nucleo del gioco rappresenta quell'insieme di allocazioni di vincite e di perdite all'interno di $R$ che non possono essere ostacolate da nessuna sotto-coalizione.

Una volta che si è ricondotto un gioco alla forma $(0-1)$ attraverso la seguente trasformazione sulla funzione caratteristica $w$

w(G)\longmapsto v(G):={{w(G)-\sum _{j\in G}w({j})} \over {w(R)-\sum _{j=1}^{n}w({j})}}

per la nuova funzione caratteristica $v$ risulterà: $v({j})=0$ per ogni $j\in R$ e $v(R)=1$ .

Si consideri dunque un gioco cooperativo ad $n$ giocatori $R=\{1,2,\ldots ,n\}$ in forma $(0-1)$ ; si indichi con $H=\{G_{1},\ldots ,G_{m}\}$ l’insieme costituito da tutti i sottoinsiemi possibili di $R$ : $m\leq 2^{n}$ $-2$ se si escludono l'insieme $R$ e l’insieme vuoto $\{\varnothing \}$ . Si individuino ora i giocatori all’interno di una coalizione generica $j$ attraverso un vettore ${\mathbf {g} _{j}}$ ad $n$ componenti. Ciascuna coalizione $G_{j}\in H$ viene così posta in corrispondenza con un vettore riga ${\mathbf {g} _{j}}=(g_{j1},\ldots ,g_{jn})$ in modo tale che:

g_{ij}=\left\{{\begin{array}{l}1&{se}&i\in G_{j}\\0&{se}&i\notin G_{j}\\\end{array}}\right.

e l'insieme $H$ può essere rappresentato dalla matrice seguente $\mathbf {G} ={\begin{pmatrix}{\mathbf {g} ^{1}}\cdots {\mathbf {g} ^{n}}\end{pmatrix}}={\begin{pmatrix}g_{11}&\cdots &g_{1n}\\\vdots &\ddots &\vdots \\g_{m1}&\cdots &g_{mn}\end{pmatrix}}={\begin{pmatrix}{\mathbf {g} _{1}}\\\vdots \\{\mathbf {g} _{m}}\end{pmatrix}}$ dove $g_{ij}\in \{0;1\}$ .

La totalità dei giocatori, la grande-coalizione $R$ , viene indicata dal vettore ${\mathbf {1} }=({\begin{matrix}\underbrace {1,\ldots ,1} _{n}\end{matrix}})$ .

La definizione di nucleo $U$ corrisponde all’insieme delle soluzioni ${\mathbf {x} }$ (imputazioni) del sistema di dis-eguaglianze lineari seguente

U:\left\{{\begin{array}{l}{\mathbf {g} _{1}}\cdot {\mathbf {x} }\geq v(G_{1})\\\vdots \\{\mathbf {g} _{m}}\cdot {\mathbf {x} }\geq v(G_{m})\\{\mathbf {1} }\cdot {\mathbf {x} }=v(R)\\\end{array}}\right.

L'ultima eguaglianza rappresenta la condizione (efficienza) che caratterizza un'imputazione per potersi appellare come tale. Introdotto il vettore colonna ${\mathbf {v} }=(v_{1},\ldots ,v_{m})^{t}$ avente come elementi i valori delle coalizioni $v_{j}=v(G_{j})$ per ciascun $j=1,\ldots ,m$ , la disequazione matriciale che definisce il nucleo del gioco si scrive come

U:\left\{{\begin{array}{l}{\mathbf {G} }\cdot {\mathbf {x} }\geq {\mathbf {v} }\\{\mathbf {1} }\cdot {\mathbf {x} }=1\\\end{array}}\right.

Il nucleo consiste nell’intersezione dell’iperpiano ${\mathbf {1} }\cdot {\mathbf {x} }=1$ con il poliedro convesso definito da ${\mathbf {G} }\cdot {\mathbf {v} }\geq {\mathbf {x} }$ e risulta essere un sottospazio n-dimensionale chiuso, limitato e convesso di $\mathbb {R} ^{n}$ . L’idea è di scegliere il vincolo ${\mathbf {1} }\cdot {\mathbf {x} }=1$ e porlo in forma di funzione obiettivo.

Olga Bondareva fa notare che il nucleo $U$ è non vuoto se, e soltanto se, è risolvibile il programma lineare seguente:

z=min\sum _{i=1}^{n}x_{i}

\left\{{\begin{array}{l}{\mathbf {G} }\cdot {\mathbf {x} }\geq {\mathbf {v} }\\\end{array}}\right.

Indicato con $z^{*}$ il valore all’ottimo della funzione obiettivo e ricordata la definizione di minimo, si ha che $z^{*}\leq \sum _{i=1}^{n}x_{i}$ per ${\mathbf {x} }$ qualsiasi, pertanto $z^{*}$ è il più piccolo valore in grado di garantire la cooperazione.

La formulazione del problema duale si può ottenere considerando la funzione lagrangiana ed applicando ad essa il teorema del mini-max. La funzione lagrangiana associata è

{\mathcal {L}}(\mathbf {x} ,\mathbf {\lambda } )=\left\langle \mathbf {1} ,\mathbf {x} \right\rangle -\left\langle \mathbf {\lambda } ,{\mathbf {G} }\cdot {\mathbf {x} }-{\mathbf {v} }\right\rangle =\left\langle \mathbf {v} ,\mathbf {\lambda } \right\rangle +\left\langle \mathbf {1} -{\mathbf {G} ^{t}}\cdot {\mathbf {\lambda } },{\mathbf {x} }\right\rangle

La formulazione esplicita del problema duale si ottiene considerando

\max _{\lambda \in {\mathit {\Omega }}}\min _{x\in {\mathit {R^{n}}}}{\mathcal {L}}(\mathbf {x} ,\mathbf {\lambda } )

Dapprima si minimizza la lagrangiana per ${\displaystyle \mathbf {\lambda } }$ fisso e ${\displaystyle \mathbf {x} }$ variabile

\min _{x\in {\mathit {\mathbb {R} ^{n}}}}{\mathcal {L}}(\mathbf {x} ,\mathbf {\lambda } )=\left\langle \mathbf {v} ,\mathbf {\lambda } \right\rangle +\min _{x\in {\mathit {\mathbb {R} ^{n}}}}[\left\langle \mathbf {1} -{\mathbf {G} ^{t}}\cdot {\mathbf {\lambda } },{\mathbf {x} }\right\rangle ]=\left\{{\begin{matrix}0&{\mbox{ se }}\mathbf {1} -{\mathbf {G} ^{t}}\cdot {\mathbf {\lambda } }=0&{\mbox{ con }}\mathbf {\lambda } \geq \mathbf {0} \\\pm \infty &{\mbox{ se }}{\mathbf {1} -{\mathbf {G} ^{t}}\cdot {\mathbf {\lambda } }}\neq 0\\\end{matrix}}\right.

Pertanto il minimo di ${\mathcal {L}}$ esiste finito per ${\mathbf {1} -{\mathbf {G} ^{t}}\cdot {\mathbf {\lambda } }}=0$ con $\mathbf {\lambda } \geq \mathbf {0}$

La formulazione del problema duale è la seguente:

w=\max _{\lambda \in {\mathit {\Omega }}}\sum _{j=1}^{m}v_{j}\cdot \lambda _{j}

\Omega :\left\{{\begin{array}{l}{\mathbf {G} ^{t}}\cdot \mathbf {\lambda } =\mathbf {1} \\\lambda _{j}\geq 0&j=1,\ldots ,m\\\end{array}}\right.

Olga Bondareva definisce i pesi $\lambda _{j}$ (copertura) come quei coefficienti numerici $(\lambda _{1},\lambda _{2},\ldots ,\lambda _{m})$ tali che

\sum _{j=1}^{m}\lambda _{j}\cdot \mathbf {g} _{j}=\mathbf {1}

La sommatoria per esteso si scrive come

\lambda _{1}\cdot \mathbf {g} _{1}+\lambda _{2}\cdot \mathbf {g} _{2}+\ldots +\lambda _{m}\cdot \mathbf {g} _{m}=(\lambda _{1}\cdot g_{11},\ldots ,\lambda _{1}\cdot g_{1n})+\ldots +(\lambda _{m}\cdot g_{m1},\ldots ,\lambda _{m}\cdot g_{mn})=\mathbf {1}

poiché la somma tra $m$ vettori è definita come la somma componente per componente di ciascun vettore, si ottiene l’equazione vettoriale ${\mathbf {G} ^{t}}\cdot \mathbf {\lambda } =\mathbf {1}$ che equivale al sistema di $n$ equazioni in $m$ incognite seguente

\left\{{\begin{array}{l}g_{11}\lambda _{1}+g_{21}\lambda _{2}+g_{m1}\lambda _{m}=1\\\vdots \\g_{1n}\lambda _{1}+g_{2n}\lambda _{2}+g_{mn}\lambda _{m}=1\\\end{array}}\right.

Si può osservare che qualora si avesse $\lambda _{1}=\lambda _{2}=\ldots =\lambda _{m}=1$ allora l’insieme $H=\{G_{1},\ldots ,G_{m}\}$ altro non sarebbe che una partizione dell'insieme dei giocatori $R$ , nel qual caso l’intersezione delle coalizioni prese a due a due è vuota e la matrice ${\mathbf {G} ^{t}}$ presenterà $m$ elementi non nulli.

Dalla definizione di massimo si ha che, per qualsiasi $\lambda$ ,

\sum _{j=1}^{m}\lambda _{j}\cdot v(G_{j})\leq \max _{\lambda \in {\mathit {\Omega }}}\sum _{j=1}^{m}\lambda _{j}\cdot v(G_{j})

posto $w^{*}=\max _{\lambda \in {\mathit {\Omega }}}\sum _{j=1}^{m}\lambda _{j}\cdot v(G_{j})$ , per il teorema della dualità forte risulta $w^{*}=z^{*}$ , ma $z^{*}\leq v(R)$ dunque si deduce che $w^{*}\leq v(R)$ , quindi $\sum _{j=1}^{m}\lambda _{j}\cdot v(G_{j})\leq v(R)$ che è quanto enunciato nel teorema di Bondareva-Shapley.

Teorema di Bondareva-Shapley

Il nucleo $U$ di un gioco è non vuoto se, e soltanto se, ogni insieme di pesi $(\lambda _{1},\lambda _{2},\cdots ,\lambda _{m})$ soddisfa alla diseguaglianza

\sum _{j=1}^{m}\lambda _{j}\cdot v(G_{j})\leq v(R)

Corollario

Il nucleo $U$ di un gioco è vuoto se, e soltanto se, esiste un insieme di pesi $(\lambda _{1}^{0},\lambda _{2}^{0},\cdots ,\lambda _{m}^{0})$ tali che

\sum _{j=1}^{m}\lambda _{j}^{0}\cdot v(G_{j})>v(R)

Olga B. analizzò anche la relazione tra il nucleo $U$ e l’insieme delle soluzioni $L$ nel senso di von Neumann-Morgenstern e giunse a formulare una condizione sufficiente per l’esistenza di un’unica soluzione basata sul valore delle coalizioni.

Condizione sufficiente affinché un gioco abbia un’unica soluzione è che tutte le coalizioni $G\subset R$ soddisfino alla condizione $v(G)\leq 1/r$ , dove $r$ è il rango della matrice: