Teorema del minimax

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

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 ${\displaystyle {\displaystyle f:{\mathit {K_{1}}}\times {\mathit {K_{2}}}\to \mathbb {R} }}$ una funzione continua dove ${\displaystyle {\mathit {K_{1}}}\subset \mathbb {R} ^{n}}$ e ${\displaystyle {\mathit {K_{2}}}\subset \mathbb {R} ^{m}}$ sono insiemi convessi compatti. Se ${\displaystyle f}$ è una funzione convessa-concava, ossia tale che

${\displaystyle f(\cdot ,y):{\mathit {K_{1}}}\to \mathbb {R} }$ è convessa per ${\displaystyle y}$ fissato e

${\displaystyle f(x,\cdot ):{\mathit {K_{2}}}\to \mathbb {R} }$ è concava per ${\displaystyle x}$ 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).}$

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 ${\displaystyle f:S_{1}\times S_{2}\rightarrow \mathbb {R} }$ come ad una forma bilineare alternante la cui proprietà di alternanza ${\displaystyle 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 ${\displaystyle S_{1}}$ e ${\displaystyle S_{2}}$ l’insieme delle strategie pure dei due giocatori e ponendo

${\displaystyle f_{1}(s_{1},s_{2}):=f(s_{1},s_{2})}$

${\displaystyle f_{2}(s_{1},s_{2}):=f(s_{2},s_{1})}$

si ottiene la definizione di gioco a somma zero:

${\displaystyle f_{1}(s_{1},s_{2})+f_{2}(s_{1},s_{2})}$ ≡ ${\displaystyle 0}$ per ogni ${\displaystyle s_{1}\in S_{1}}$ e per ogni ${\displaystyle s_{2}\in S_{2}}$

Nei giochi finiti è immediato constatare che i due insiemi ${\displaystyle S_{1}}$ e ${\displaystyle S_{2}}$ risultano essere compatti poiché sono finiti e dunque privi di punti di accumulazione. Le funzioni dei pagamenti ${\displaystyle 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 ${\displaystyle f_{i}}$ risultano essere continue (di più uniformemente continue). In merito alla richiesta che i due insiemi ${\displaystyle S_{1}}$ e ${\displaystyle 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 ${\displaystyle ({\tilde {s}}_{1},\ldots ,{\tilde {s}}_{n})}$ tali che ${\displaystyle {\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 ${\displaystyle n}$ ennuple ordinate, mentre le strategie miste sono definite su un sottoinsieme dello spazio vettoriale di dimensione ${\displaystyle n}$ costituito da tutte le combinazioni lineari convesse delle ${\displaystyle n}$ strategie pure e come tale risulta convesso ed avente dimensione finita pari a ${\displaystyle n+1}$. L’inviluppo convesso è compatto perché è costruito sull’insieme compatto delle strategie pure. Se ${\displaystyle f_{1}(\cdot ,{\tilde {s}}_{2})}$ risulta essere convessa rispetto a ${\displaystyle {\tilde {s}}_{1}}$ per ${\displaystyle {\tilde {s}}_{2}}$ fissato e poiché ${\displaystyle f_{1}=-f_{2}}$, allora ${\displaystyle f_{2}({\tilde {s}}_{1},\cdot )}$ risulta essere concava rispetto a ${\displaystyle {\tilde {s}}_{2}}$ per ${\displaystyle {\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^[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})}$

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

${\displaystyle v^{*}=\min _{{\tilde {s}}_{1}}\max _{{\tilde {s}}_{2}}f({\tilde {s}}_{1},{\tilde {s}}_{2})=\min _{{\tilde {s}}_{1}}\max _{{\tilde {s}}_{2}}[-f({\tilde {s}}_{2},{\tilde {s}}_{1})]=-\max _{{\tilde {s}}_{1}}\min _{{\tilde {s}}_{2}}f({\tilde {s}}_{2},{\tilde {s}}_{1})}$.

Poiché l'insieme delle strategie per i due giocatori sono identiche ${\displaystyle S_{1}=S_{2}}$, scambiando ${\displaystyle {\tilde {s}}_{1}}$ con ${\displaystyle {\tilde {s}}_{2}}$ si ottiene

${\displaystyle -\max _{{\tilde {s}}_{1}}\min _{{\tilde {s}}_{2}}f({\tilde {s}}_{2},{\tilde {s}}_{1})=-\max _{{\tilde {s}}_{2}}\min _{{\tilde {s}}_{1}}f({\tilde {s}}_{1},{\tilde {s}}_{2})=-v^{*}}$.

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

• La matrice associata alla funzione dei pagamenti ${\displaystyle f}$ è una matrice antisimmetrica e presenta quali elementi della diagonale principale solo zeri in quanto da ${\displaystyle f(s_{1},s_{2})=-f(s_{2},s_{1})}$ per ogni ${\displaystyle s_{1}}$,${\displaystyle s_{2}}$ segue immediatamente che è ${\displaystyle f(s_{1},s_{1})=0}$ per ogni ${\displaystyle s_{1}}$ una volta scelto ${\displaystyle 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 ${\displaystyle (\mathbf {x} ^{\ast },\mathbf {y} ^{\ast })}$ della funzione lagrangiana ${\displaystyle {\mathcal {L}}(\mathbf {x} ,\mathbf {y} )}$. Se ${\displaystyle \mathbf {x} ^{\ast }}$ è soluzione del problema primale di massimizzazione e se ${\displaystyle \mathbf {y} ^{\ast }}$ è soluzione del problema duale di minimizzazione allora il valore all'ottimo della funzione lagrangiana del problema primale, ${\displaystyle maxmin{\mathcal {L}}}$, coincide con il valore all'ottimo della funzione lagrangiana del problema duale, ${\displaystyle minmax{\mathcal {L}}}$. 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} )}$

In generale almeno uno dei due insiemi ${\displaystyle {\mathit {K_{1}}}}$ o ${\displaystyle {\mathit {K_{2}}}}$ è 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

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}$

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.}$

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 }$

dove ${\displaystyle \mathbf {v} =\left(v,\cdots ,v\right)}$, mentre ${\displaystyle \mathbf {y} =(y_{1},\cdots ,y_{m})}$ rappresentano i moltiplicatori di lagrange e costituiscono le strategie miste del giocatore avversario.

Osservato che la funzione lagrangiana ${\displaystyle {\mathcal {L}}(\mathbf {x} ,\mathbf {y} )=v+\left\langle \mathbf {y} ,A\mathbf {x} -\mathbf {v} \right\rangle }$ risulta essere una funzione convessa nella variabile ${\displaystyle \mathbf {x} }$ sull'insieme ${\displaystyle {\mathit {K_{1}}}=\left\{x\in \mathbb {R} ^{n}|\sum _{j=1}^{n}x_{j}\cdot \alpha _{j}\quad |\quad \alpha _{j}=1,\quad \sum _{j=1}^{n}x_{j}=1,\quad x_{j}\geq 0\quad \forall j\right\}}$, che la lagrangiana ${\displaystyle {\mathcal {L}}(\mathbf {x} ,\mathbf {y} )}$ è chiaramente una funzione lineare in ${\displaystyle \mathbf {y} }$, dunque risulta essere banalmente concava in ${\displaystyle \mathbf {y} }$ in quanto ogni funzione lineare è sia concava che convessa e che i due insiemi ${\displaystyle {\mathit {K_{1}}}}$ e ${\displaystyle {\mathit {K_{2}}}}$ 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} )}$

è 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} )}$

Dapprima si massimizza la lagrangiana per ${\displaystyle \mathbf {y} }$ fisso e ${\displaystyle \mathbf {x} }$ variabile in ${\displaystyle {\mathit {K_{1}}}}$

${\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]}$

Essendo ${\displaystyle \sum _{j=1}^{n}x_{j}=1}$ si può scrivere ${\displaystyle v=v\cdot 1=v{\dot {\left(\sum _{j=1}^{n}x_{j}\right)}}=vx_{1}+\cdots +vx_{n}=\left\langle \mathbf {v} ,\mathbf {x} \right\rangle }$ dove ${\displaystyle \mathbf {v} =\left(v,\cdots ,v\right)}$. Ricordato che ${\displaystyle \left\langle \mathbf {y} ,A\mathbf {x} \right\rangle =\left\langle A^{t}\mathbf {y} ,\mathbf {x} \right\rangle }$ si ottiene

${\displaystyle \max _{x\in {\mathit {K_{1}}}}\left[-\left\langle \mathbf {y} ,\mathbf {v} \right\rangle +\left\langle \mathbf {v} ,\mathbf {x} \right\rangle +\left\langle A^{t}\mathbf {y} ,\mathbf {x} \right\rangle \right]=-\left\langle \mathbf {y} ,\mathbf {v} \right\rangle +\max _{x\in {\mathit {K_{1}}}}\left[\left\langle \mathbf {v} +A^{t}\mathbf {y} ,\mathbf {x} \right\rangle \right]}$.

Poiché ${\displaystyle x_{j}\geq 0}$ per tutti i j da ${\displaystyle 1}$ a ${\displaystyle m}$, si avrà ${\displaystyle \left\langle \mathbf {v} +A^{t}\mathbf {y} ,\mathbf {x} \right\rangle >0}$ se ${\displaystyle \mathbf {v} +A^{t}\mathbf {y} >0}$ oppure ${\displaystyle \left\langle \mathbf {v} +A^{t}\mathbf {y} ,\mathbf {x} \right\rangle \leq 0}$ se ${\displaystyle \mathbf {v} +A^{t}\mathbf {y} \leq 0}$.

Dunque si ha:

${\displaystyle \min _{y\in {\mathit {K_{2}}}}\max _{x\in {\mathit {K_{1}}}}{\mathcal {L}}(\mathbf {x} ,\mathbf {y} )=-\min _{y\in {\mathit {K_{2}}}}\left[\left\langle \mathbf {y} ,\mathbf {v} \right\rangle \right]=\min _{y\in {\mathit {K_{2}}}}-v}$ per ${\displaystyle \mathbf {v} +A^{t}\mathbf {y} \leq 0}$

ed il problema duale presenta la formulazione seguente:

${\displaystyle \min _{y\in {\mathit {K_{2}}}}-v}$

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.}$

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

${\displaystyle \min _{y\in {\mathit {K_{2}}}}{\tilde {v}}}$

${\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.}$

Note

Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica