Teorema del minimax

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

Il teorema del minimax è dovuto a von Neumann[1][2]. Il teorema del minimax fornisce condizioni sufficienti affinché la disuguaglianza max-min sia un’uguaglianza. Il teorema costituisce non solo il punto di inizio della teoria dei giochi, ma altresì un teorema della dualità per i problemi di programmazione lineare laddove la regione ammissibile è convessa e compatta (chiusa e limitata).

Sia una funzione continua dove e sono insiemi convessi compatti. Se è una funzione convessa-concava, ossia tale che

è convessa per fissato e
è concava per fissato,

allora

Esempi[modifica | modifica wikitesto]

  • Nella teoria dei giochi per un gioco finito a somma zero a due giocatori con un numero finito n di strategie (c.d. giochi simmetrici), è facile pensare alla funzione di pagamento come ad una forma bilineare alternante la cui proprietà di alternanza matematizza la contrapposizione totale dei due giocatori, ossia il fatto che la somma dei pagamenti sia zero. Indicato con e l’insieme delle strategie pure dei due giocatori e ponendo
si ottiene la definizione di gioco a somma zero:
per ogni e per ogni
Nei giochi finiti è immediato constatare che i due insiemi e risultano essere compatti poiché sono finiti e dunque privi di punti di accumulazione. Le funzioni dei pagamenti risultano definite su insiemi privi di punti di accumulazione, insiemi dunque costituiti dai soli punti isolati, punti cioè in cui le due funzioni risultano essere continue (di più uniformemente continue). In merito alla richiesta che i due insiemi e siano convessi è sufficiente considerarne il politopo (involucro convesso) una volta introdotto il concetto di strategia mista come una ennupla non negativa di numeri tali che . Il dominio di variazione delle strategie miste è più esteso di quello delle strategie pure: per queste ultime infatti il dominio è un semplice insieme finito di ennuple ordinate, mentre le strategie miste sono definite su un sottoinsieme dello spazio vettoriale di dimensione costituito da tutte le combinazioni lineari convesse delle strategie pure e come tale risulta convesso ed avente dimensione finita pari a . L’inviluppo convesso è compatto perché è costruito sull’insieme compatto delle strategie pure. Se risulta essere convessa rispetto a per fissato e poiché , allora risulta essere concava rispetto a per fissato, sicché le condizioni del teorema del minimax risultano soddisfatte.
  • Il valore di un gioco simmetrico a somma zero a due giocatori esteso a strategie miste presenta valore pari a zero[3]. Il valore di un gioco per definizione è
Si consideri dapprima la parte sinistra delle due eguaglianze appena scritte , per ipotesi è dunque
.
Poiché l'insieme delle strategie per i due giocatori sono identiche , scambiando con si ottiene
.
Per confronto risulta e quindi necessariamente il valore del gioco è .
  • La matrice associata alla funzione dei pagamenti è una matrice antisimmetrica e presenta quali elementi della diagonale principale solo zeri in quanto da per ogni , segue immediatamente che è per ogni una volta scelto .

Il teorema del min-max e la programmazione convessa[modifica | modifica wikitesto]

Il teorema alla base dei giochi antagonisti può essere preso come punto di unione tra la teoria della dualità ed i problemi di programmazione convessa, in particolare quelli di programmazione lineare. Le coppie di problemi constitute dal problema primale e dal suo problema duale sono infatti strettamente legate al problema di determinare i punti di sella della funzione lagrangiana . Se è soluzione del problema primale di massimizzazione e se è soluzione del problema duale di minimizzazione allora il valore all'ottimo della funzione lagrangiana del problema primale, , coincide con il valore all'ottimo della funzione lagrangiana del problema duale, . In altri termini vale la relazione di dualità:

In generale almeno uno dei due insiemi o è un insieme illimitato, dunque non è compatto: ciò costituisce il motivo per cui il teorema di von Neumann non è largamente applicato nella programmazione convessa[4].

Esempio[modifica | modifica wikitesto]

In un generico gioco a somma zero a due persone per il giocatore massimizzante si ha il problema primale seguente:

soggetto ai vincoli:

La funzione lagrangiana associata a questo problema è:

dove , mentre rappresentano i moltiplicatori di lagrange e costituiscono le strategie miste del giocatore avversario.

Osservato che la funzione lagrangiana risulta essere una funzione convessa nella variabile sull'insieme , che la lagrangiana è chiaramente una funzione lineare in , dunque risulta essere banalmente concava in in quanto ogni funzione lineare è sia concava che convessa e che i due insiemi e sono compatti, si deduce che la relazione di dualità

è diretta conseguenza del teorema del minimax.

La formulazione esplicita del problema duale si ottiene considerando

Dapprima si massimizza la lagrangiana per fisso e variabile in

Essendo si può scrivere dove . Ricordato che si ottiene

.

Poiché per tutti i j da a , si avrà se oppure se .

Dunque si ha:

per

ed il problema duale presenta la formulazione seguente:

soggetto ai vincoli:

Posto si ha

Note[modifica | modifica wikitesto]

  1. ^ J. von Neumann, Zur Theorie der Gesselschaftsspiele, Math. Ann. 100, 1928, p. 295-320.
  2. ^ J. von Neumann, Contributions to the theory of games. Vol. IV, Annals. of Mathematics Studies, no.40, Princeton Univ. Press, 1959, p. 13-42.
  3. ^ E. Burger, Introduction to the Theory of Games, Prentice-Hall, Inc., 1959, p. 74.
  4. ^ E. G. Goldstein, Theory of Convex Programming, Providence, U.S., American Mathematical Society, 1972, p. 7.