Teorema del minimax

Il teorema del minimax è dovuto a von Neumann. Il teorema del minimax fornisce condizioni sufficienti affinché la disuguaglianza max-min

$\underset{y\in {𝐾}_2}{\max }\underset{x\in {𝐾}_1}{\min }f(x,y)\le \underset{x\in {𝐾}_1}{\min }\underset{y\in {𝐾}_2}{\max }f(x,y).$

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).

Enunciato

Sia $f:{𝐾}_1\times {𝐾}_2\to ℝ$ una funzione continua dove ${𝐾}_1\subset {ℝ}^n$ e ${𝐾}_2\subset {ℝ}^m$ sono insiemi convessi compatti. Se $f$ è una funzione convessa-concava, ossia tale che

$f(\cdot ,y):{𝐾}_1\to ℝ$ è convessa per $y$ fissato e

$f(x,\cdot ):{𝐾}_2\to ℝ$ è concava per $x$ fissato,

allora

$\underset{x\in {𝐾}_1}{\min }\underset{y\in {𝐾}_2}{\max }f(x,y)=\underset{y\in {𝐾}_2}{\max }\underset{x\in {𝐾}_1}{\min }f(x,y).$

Esempi

• 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 $f:S_1\times S_2\to ℝ$ come ad una forma bilineare alternante la cui proprietà di alternanza $f(s_1,s_2)=-f(s_2,s_1)$ matematizza la contrapposizione totale dei due giocatori, ossia il fatto che la somma dei pagamenti sia zero. Indicato con $S_1$ e $S_2$ l’insieme delle strategie pure dei due giocatori e ponendo

$f_1(s_1,s_2):=f(s_1,s_2)$

$f_2(s_1,s_2):=f(s_2,s_1)$

si ottiene la definizione di gioco a somma zero:

$f_1(s_1,s_2)+f_2(s_1,s_2)$ ≡ $0$ per ogni $s_1\in S_1$ e per ogni $s_2\in S_2$

Nei giochi finiti è immediato constatare che i due insiemi $S_1$ e $S_2$ risultano essere compatti poiché sono finiti e dunque privi di punti di accumulazione. Le funzioni dei pagamenti $f_i$ risultano definite su insiemi privi di punti di accumulazione, insiemi dunque costituiti dai soli punti isolati, punti cioè in cui le due funzioni $f_i$ risultano essere continue (di più uniformemente continue). In merito alla richiesta che i due insiemi $S_1$ e $S_2$ siano convessi è sufficiente considerarne il politopo (involucro convesso) una volta introdotto il concetto di strategia mista come una ennupla non negativa di numeri $({\tilde{s}}_1,\dots ,{\tilde{s}}_n)$ tali che ${\tilde{s}}_1+...+{\tilde{s}}_n=1$. 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 $n$ ennuple ordinate, mentre le strategie miste sono definite su un sottoinsieme dello spazio vettoriale di dimensione $n$ costituito da tutte le combinazioni lineari convesse delle $n$ strategie pure e come tale risulta convesso ed avente dimensione finita pari a $n+1$. L’inviluppo convesso è compatto perché è costruito sull’insieme compatto delle strategie pure. Se $f_1(\cdot ,{\tilde{s}}_2)$ risulta essere convessa rispetto a ${\tilde{s}}_1$ per ${\tilde{s}}_2$ fissato e poiché $f_1=-f_2$, allora $f_2({\tilde{s}}_1,\cdot )$ risulta essere concava rispetto a ${\tilde{s}}_2$ per ${\tilde{s}}_1$ 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. Il valore di un gioco per definizione è

$\underset{{\tilde{s}}_1}{\min }\underset{{\tilde{s}}_2}{\max }f({\tilde{s}}_1,{\tilde{s}}_2)=v^{*}=\underset{{\tilde{s}}_2}{\max }\underset{{\tilde{s}}_1}{\min }f({\tilde{s}}_1,{\tilde{s}}_2)$

Si consideri dapprima la parte sinistra delle due eguaglianze appena scritte $v*=\underset{{\tilde{s}}_1}{\min }\underset{{\tilde{s}}_2}{\max }f({\tilde{s}}_1,{\tilde{s}}_2)$, per ipotesi è $f({\tilde{s}}_1,{\tilde{s}}_2)=-f({\tilde{s}}_2,{\tilde{s}}_1)$ dunque

$v^{*}=\underset{{\tilde{s}}_1}{\min }\underset{{\tilde{s}}_2}{\max }f({\tilde{s}}_1,{\tilde{s}}_2)=\underset{{\tilde{s}}_1}{\min }\underset{{\tilde{s}}_2}{\max }[-f({\tilde{s}}_2,{\tilde{s}}_1)]=-\underset{{\tilde{s}}_1}{\max }\underset{{\tilde{s}}_2}{\min }f({\tilde{s}}_2,{\tilde{s}}_1)$.

Poiché l'insieme delle strategie per i due giocatori sono identiche $S_1=S_2$, scambiando ${\tilde{s}}_1$ con ${\tilde{s}}_2$ si ottiene

$-\underset{{\tilde{s}}_1}{\max }\underset{{\tilde{s}}_2}{\min }f({\tilde{s}}_2,{\tilde{s}}_1)=-\underset{{\tilde{s}}_2}{\max }\underset{{\tilde{s}}_1}{\min }f({\tilde{s}}_1,{\tilde{s}}_2)=-v^{*}$.

Per confronto risulta $v^{*}=-v^{*}$ e quindi necessariamente il valore del gioco è $v^{*}=0$.

• La matrice associata alla funzione dei pagamenti $f$ è una matrice antisimmetrica e presenta quali elementi della diagonale principale solo zeri in quanto da $f(s_1,s_2)=-f(s_2,s_1)$ per ogni $s_1$,$s_2$ segue immediatamente che è $f(s_1,s_1)=0$ per ogni $s_1$ una volta scelto $s_1=s_2$.

Il teorema del min-max e la programmazione convessa

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 $({𝐱}^{\ast },{𝐲}^{\ast })$ della funzione lagrangiana $ℒ(𝐱,𝐲)$. Se ${𝐱}^{\ast }$ è soluzione del problema primale di massimizzazione e se ${𝐲}^{\ast }$ è soluzione del problema duale di minimizzazione allora il valore all'ottimo della funzione lagrangiana del problema primale, $maxminℒ$, coincide con il valore all'ottimo della funzione lagrangiana del problema duale, $minmaxℒ$. In altri termini vale la relazione di dualità:

$\underset{x\in {𝐾}_1}{\max }\underset{y\in {𝐾}_2}{\min }ℒ(𝐱,𝐲)=ℒ({𝐱}^{\ast },{𝐲}^{\ast })=\underset{y\in {𝐾}_2}{\min }\underset{x\in {𝐾}_1}{\max }ℒ(𝐱,𝐲)$

In generale almeno uno dei due insiemi ${𝐾}_1$ o ${𝐾}_2$ è un insieme illimitato, dunque non è compatto: ciò costituisce il motivo per cui il teorema di von Neumann non è largamente applicato nella programmazione convessa.

Esempio

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

$\underset{x\in {𝐾}_1}{\max }v$

soggetto ai vincoli:

$\{\begin{array}{c}\begin{array}{c}\sum _{j=1}^n{a}_{i,j}\cdot x_j\end{array}\ge v\mathrm{\forall }i=1,...,m\\ \begin{array}{c}\sum _{j=1}^n{x}_j\end{array}=1\\ x_j\ge 0\mathrm{\forall }j=1,...,n\end{array}$

La funzione lagrangiana associata a questo problema è:

$ℒ(𝐱,𝐲)=v+⟨𝐲,A𝐱-𝐯⟩$

dove $𝐯=(v,\cdots ,v)$, mentre $𝐲=(y_1,\cdots ,y_m)$ rappresentano i moltiplicatori di lagrange e costituiscono le strategie miste del giocatore avversario.

Osservato che la funzione lagrangiana $ℒ(𝐱,𝐲)=v+⟨𝐲,A𝐱-𝐯⟩$ risulta essere una funzione convessa nella variabile $𝐱$ sull'insieme ${𝐾}_1=\{x\in {ℝ}^n|\sum _{j=1}^n{x}_j\cdot {\alpha }_j|{\alpha }_j=1,\sum _{j=1}^n{x}_j=1,x_j\ge 0\mathrm{\forall }j\}$, 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 ${𝐾}_1$ e ${𝐾}_2$ sono compatti, si deduce che la relazione di dualità

$\underset{x\in {𝐾}_1}{\max }\underset{y\in {𝐾}_2}{\min }ℒ(𝐱,𝐲)=\underset{y\in {𝐾}_2}{\min }\underset{x\in {𝐾}_1}{\max }ℒ(𝐱,𝐲)$

è diretta conseguenza del teorema del minimax.

La formulazione esplicita del problema duale si ottiene considerando

$\underset{y\in {𝐾}_2}{\min }\underset{x\in {𝐾}_1}{\max }ℒ(𝐱,𝐲)$

Dapprima si massimizza la lagrangiana per $𝐲$ fisso e $𝐱$ variabile in ${𝐾}_1$

$\underset{x\in {𝐾}_1}{\max }ℒ(𝐱,𝐲)=\underset{x\in {𝐾}_1}{\max }[v-⟨𝐲,𝐯⟩+⟨𝐲,A𝐱⟩]$

Essendo $\sum _{j=1}^n{x}_j=1$ si può scrivere $v=v\cdot 1=v\dot{\left(\sum _{j=1}^n{x}_j\right)}=v{x}_1+\cdots +v{x}_n=⟨𝐯,𝐱⟩$ dove $𝐯=(v,\cdots ,v)$. Ricordato che $⟨𝐲,A𝐱⟩=⟨A^t𝐲,𝐱⟩$ si ottiene

$\underset{x\in {𝐾}_1}{\max }[-⟨𝐲,𝐯⟩+⟨𝐯,𝐱⟩+⟨A^t𝐲,𝐱⟩]=-⟨𝐲,𝐯⟩+\underset{x\in {𝐾}_1}{\max }\left[⟨𝐯+A^t𝐲,𝐱⟩\right]$.

Poiché $x_j\ge 0$ per tutti i j da $1$ a $m$, si avrà $⟨𝐯+A^t𝐲,𝐱⟩>0$ se $𝐯+A^t𝐲>0$ oppure $⟨𝐯+A^t𝐲,𝐱⟩\le 0$ se $𝐯+A^t𝐲\le 0$.

Dunque si ha:

$\underset{y\in {𝐾}_2}{\min }\underset{x\in {𝐾}_1}{\max }ℒ(𝐱,𝐲)=-\underset{y\in {𝐾}_2}{\min }\left[⟨𝐲,𝐯⟩\right]=\underset{y\in {𝐾}_2}{\min }-v$ per $𝐯+A^t𝐲\le 0$

ed il problema duale presenta la formulazione seguente:

$\underset{y\in {𝐾}_2}{\min }-v$

soggetto ai vincoli:

$\{\begin{array}{c}\begin{array}{c}\sum _{i=1}^m{a}_{i,j}\cdot y_i\end{array}\le -v\mathrm{\forall }j=1,...,n\\ \begin{array}{c}\sum _{i=1}^m{y}_i\end{array}=1\\ y_i\ge 0\mathrm{\forall }i=1,...,m\end{array}$

Posto $\tilde{v}=-v$ si ha

$\underset{y\in {𝐾}_2}{\min }\tilde{v}$

$\{\begin{array}{c}\begin{array}{c}-A^t\cdot 𝐲\end{array}\ge -\tilde{v}\\ \begin{array}{c}\sum _{i=1}^m{y}_i\end{array}=1\\ y_i\ge 0\mathrm{\forall }i=1,...,m\end{array}$