Olga Nikolaevna Bondareva (in russo: Ольга Николаевна Бо́ндарева; Leningrado, 27 aprile 1937San 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

modifica

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

modifica

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

modifica

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   di un gioco cooperativo ad n persone coincide con il nucleo   allora   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:  . 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   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   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   che non possono essere ostacolate da nessuna sotto-coalizione.

Una volta che si è ricondotto un gioco alla forma   attraverso la seguente trasformazione sulla funzione caratteristica  

 

per la nuova funzione caratteristica   risulterà:   per ogni   e  .

Si consideri dunque un gioco cooperativo ad   giocatori   in forma  ; si indichi con   l’insieme costituito da tutti i sottoinsiemi possibili di  :    se si escludono l'insieme   e l’insieme vuoto  . Si individuino ora i giocatori all’interno di una coalizione generica   attraverso un vettore   ad   componenti. Ciascuna coalizione   viene così posta in corrispondenza con un vettore riga   in modo tale che:

 

e l'insieme   può essere rappresentato dalla matrice seguente   dove  .

La totalità dei giocatori, la grande-coalizione  , viene indicata dal vettore  .

La definizione di nucleo   corrisponde all’insieme delle soluzioni   (imputazioni) del sistema di dis-eguaglianze lineari seguente

 

L'ultima eguaglianza rappresenta la condizione (efficienza) che caratterizza un'imputazione per potersi appellare come tale. Introdotto il vettore colonna   avente come elementi i valori delle coalizioni   per ciascun  , la disequazione matriciale che definisce il nucleo del gioco si scrive come

 

Il nucleo consiste nell’intersezione dell’iperpiano   con il poliedro convesso definito da   e risulta essere un sottospazio n-dimensionale chiuso, limitato e convesso di  . L’idea è di scegliere il vincolo   e porlo in forma di funzione obiettivo.

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

 
 

Indicato con   il valore all’ottimo della funzione obiettivo e ricordata la definizione di minimo, si ha che   per   qualsiasi, pertanto   è 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 è

 

La formulazione esplicita del problema duale si ottiene considerando

 

Dapprima si minimizza la lagrangiana per   fisso e   variabile

 

Pertanto il minimo di   esiste finito per   con  

La formulazione del problema duale è la seguente:

 
 

Olga Bondareva definisce i pesi   (copertura) come quei coefficienti numerici   tali che

 

La sommatoria per esteso si scrive come

 

poiché la somma tra   vettori è definita come la somma componente per componente di ciascun vettore, si ottiene l’equazione vettoriale   che equivale al sistema di   equazioni in   incognite seguente

 

Si può osservare che qualora si avesse   allora l’insieme   altro non sarebbe che una partizione dell'insieme dei giocatori  , nel qual caso l’intersezione delle coalizioni prese a due a due è vuota e la matrice   presenterà   elementi non nulli.

Dalla definizione di massimo si ha che, per qualsiasi  ,

 

posto  , per il teorema della dualità forte risulta  , ma   dunque si deduce che  , quindi   che è quanto enunciato nel teorema di Bondareva-Shapley.

Teorema di Bondareva-Shapley

modifica

Il nucleo   di un gioco è non vuoto se, e soltanto se, ogni insieme di pesi   soddisfa alla diseguaglianza

 

Corollario

Il nucleo   di un gioco è vuoto se, e soltanto se, esiste un insieme di pesi   tali che

 


Olga B. analizzò anche la relazione tra il nucleo   e l’insieme delle soluzioni   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   soddisfino alla condizione  , dove   è il rango della matrice:

 

Collegamenti esterni

modifica
Controllo di autoritàVIAF (EN15574513 · ISNI (EN0000 0000 1338 6126 · GND (DE119197421