Il teorema del minimax è dovuto a von Neumann[1][2]. Il teorema del minimax fornisce condizioni sufficienti affinché la disuguaglianza max-min
![{\displaystyle \max _{y\in {\mathit {K_{2}}}}\min _{x\in {\mathit {K_{1}}}}f(x,y)\leq \min _{x\in {\mathit {K_{1}}}}\max _{y\in {\mathit {K_{2}}}}f(x,y).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e32d94a97f516516c5f297aec9a849e524f6fe5e)
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
![{\displaystyle \min _{x\in {\mathit {K_{1}}}}\max _{y\in {\mathit {K_{2}}}}f(x,y)=\max _{y\in {\mathit {K_{2}}}}\min _{x\in {\mathit {K_{1}}}}f(x,y).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dc93e4adcf2b4a80ec4f63fa68fdf15fbc20091e)
- 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
![{\displaystyle f_{1}(s_{1},s_{2}):=f(s_{1},s_{2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d19d0696d16898460c6a48dfbf6de587d0a9a8e)
![{\displaystyle f_{2}(s_{1},s_{2}):=f(s_{2},s_{1})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/184abc1cdcebafcbb23e14f36484b6f81886b171)
- si ottiene la definizione di gioco a somma zero:
≡
per ogni
e per ogni ![{\displaystyle s_{2}\in S_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a223e4ea58af31cda0bc4cc70e1b49e93c64f0da)
- 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 è
![{\displaystyle \min _{{\tilde {s}}_{1}}\max _{{\tilde {s}}_{2}}f({\tilde {s}}_{1},{\tilde {s}}_{2})=v^{*}=\max _{{\tilde {s}}_{2}}\min _{{\tilde {s}}_{1}}f({\tilde {s}}_{1},{\tilde {s}}_{2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/966ac4a1bee10311c35610c75bc2379e8a53634a)
- 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 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à:
![{\displaystyle \max _{x\in {\mathit {K_{1}}}}\min _{y\in {\mathit {K_{2}}}}{\mathcal {L}}(\mathbf {x} ,\mathbf {y} )={\mathcal {L}}(\mathbf {x} ^{\ast },\mathbf {y} ^{\ast })=\min _{y\in {\mathit {K_{2}}}}\max _{x\in {\mathit {K_{1}}}}{\mathcal {L}}(\mathbf {x} ,\mathbf {y} )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e80210409218a9986cc8172fcae13d6313d5b75)
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].
In un generico gioco a somma zero a due persone per il giocatore massimizzante si ha il problema primale seguente:
![{\displaystyle \max _{x\in {\mathit {K_{1}}}}v}](https://wikimedia.org/api/rest_v1/media/math/render/svg/01e02500da685413b8de3684f236ab0446989c57)
soggetto ai vincoli:
![{\displaystyle \left\{{\begin{array}{l}{\begin{matrix}\sum _{j=1}^{n}a_{i,j}\cdot x_{j}\end{matrix}}\geq v\quad \forall i=1,...,m\\{\begin{matrix}\sum _{j=1}^{n}x_{j}\end{matrix}}=1\\x_{j}\geq 0\quad \forall j=1,...,n\\\end{array}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/381a609ce54cb2105e962e3f51f0375e8fcc2fca)
La funzione lagrangiana associata a questo problema è:
![{\displaystyle {\mathcal {L}}(\mathbf {x} ,\mathbf {y} )=v+\left\langle \mathbf {y} ,A\mathbf {x} -\mathbf {v} \right\rangle }](https://wikimedia.org/api/rest_v1/media/math/render/svg/b6c1f10f198e9ef4f40fccab9e5cbbbc8e68c0a5)
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à
![{\displaystyle \max _{x\in {\mathit {K_{1}}}}\min _{y\in {\mathit {K_{2}}}}{\mathcal {L}}(\mathbf {x} ,\mathbf {y} )=\min _{y\in {\mathit {K_{2}}}}\max _{x\in {\mathit {K_{1}}}}{\mathcal {L}}(\mathbf {x} ,\mathbf {y} )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/236a1c4efab187b8f812c0e0d3b152c12dcb3632)
è diretta conseguenza del teorema del minimax.
La formulazione esplicita del problema duale si ottiene considerando
![{\displaystyle \min _{y\in {\mathit {K_{2}}}}\max _{x\in {\mathit {K_{1}}}}{\mathcal {L}}(\mathbf {x} ,\mathbf {y} )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2121be6075d0f6393b3a7526a216deb9f96c8107)
Dapprima si massimizza la lagrangiana per
fisso e
variabile in
![{\displaystyle \max _{x\in {\mathit {K_{1}}}}{\mathcal {L}}(\mathbf {x} ,\mathbf {y} )=\max _{x\in {\mathit {K_{1}}}}\left[v-\left\langle \mathbf {y} ,\mathbf {v} \right\rangle +\left\langle \mathbf {y} ,A\mathbf {x} \right\rangle \right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/04e4ddbd64ca94dc4a2a8e51847be4ce2b3c1f0d)
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 ![{\displaystyle \mathbf {v} +A^{t}\mathbf {y} \leq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec4b388289b0d2009deb5de242709819a1392e1d)
ed il problema duale presenta la formulazione seguente:
![{\displaystyle \min _{y\in {\mathit {K_{2}}}}-v}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22d11e31ec940f9e8a877ec48dc13a7cfac68bbe)
soggetto ai vincoli:
![{\displaystyle \left\{{\begin{array}{l}{\begin{matrix}\sum _{i=1}^{m}a_{i,j}\cdot y_{i}\end{matrix}}\leq -v\quad \forall j=1,...,n\\{\begin{matrix}\sum _{i=1}^{m}y_{i}\end{matrix}}=1\\y_{i}\geq 0\quad \forall i=1,...,m\\\end{array}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b77b240a949230b3a0b4717aeab7866dae86a2c)
Posto
si ha
![{\displaystyle \min _{y\in {\mathit {K_{2}}}}{\tilde {v}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aaf27339ec124f927cadf6a877253d3d117b7ed2)
![{\displaystyle \left\{{\begin{array}{l}{\begin{matrix}-A^{t}\cdot \mathbf {y} \mathbf {} \end{matrix}}\geq -{\tilde {v}}\\{\begin{matrix}\sum _{i=1}^{m}y_{i}\end{matrix}}=1\\y_{i}\geq 0\quad \forall i=1,...,m\\\end{array}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9ba94b79bb2ee24d96d0645b85b37faaba3c5fe)
- ^ J. von Neumann, Zur Theorie der Gesselschaftsspiele, Math. Ann. 100, 1928, p. 295-320.
- ^ J. von Neumann, Contributions to the theory of games. Vol. IV, Annals. of Mathematics Studies, no.40, Princeton Univ. Press, 1959, p. 13-42.
- ^ E. Burger, Introduction to the Theory of Games, Prentice-Hall, Inc., 1959, p. 74.
- ^ E. G. Goldstein, Theory of Convex Programming, Providence, U.S., American Mathematical Society, 1972, p. 7.