\chapter{Zwei-Personenspiele}%
\label{cha:Zwei-Personenspiele}

\section{Bi-Matrixspiel}%
\label{sec:Bi-Matrixspiel}

\begin{itemize}
	\item Spieler $1, 2$
	\item Strategiemenge von Spieler $1$: $\left\{ 1, \ldots, m \right\} $ \\
	Strategiemenge von Spieler $2$: $\left\{ 1, \ldots, n \right\} $
\item Auszahlungsmatrix von Spieler $1$: $A \in \R^{m \times n}$ 

 Auszahlungsmatrix von Spieler $2$: $B \in \R^{n \times m}$ 

 $\implies$ 

 Spieler $1$ wählt Zeile $i \in \left\{ 1, \ldots, m \right\} $ 

 Spieler $2$ wählt Zeile $j \in \left\{ 1, \ldots, n \right\} $

 resultierende Auszahlung $a_{ij}$ bzw. $b_{ij}$ soll minimiert werden.
\end{itemize}
\underline{Wir wissen:} 

Nicht alle Bi-Matrixspiele haben ein Nash-GG. Frage: Gibt es ein ähliches Lösungskonzept, für das wir Existenz garantieren können?

\subsection{Alternative Darstellung der Probleme}
\label{sec:Alternative Darstellung der Probleme}

\begin{itemize}
	\item Spieler 1:
		\begin{align*}
		&\min\limits_{e_{i}} a_{ij} = e_{i}^{T} Ae_{j} \quad \text{ udN } e_{i} \in \left\{ e_{1}, \ldots , e_{m} \right\} \subseteq \R^{m}  \\
		\iff &\min\limits_{x} x^{T}A y \quad \text{ udN } x \in \left\{ e_{1}, \ldots , e_{m} \right\} \subseteq \R^{m}
		\end{align*}
	\item Spieler 2:
		\begin{align*}
		&\min\limits_{e_{j}} b_{ij} = e_{i}^{T} Be_{j} \quad \text{ udN } e_{j} \in \left\{ e_{1}, \ldots , e_{n} \right\} \subseteq \R^{n}  \\
	\iff &\min\limits_{y} x^{T}B y \quad \text{ udN } y \in \left\{ e_{1}, \ldots , e_{n} \right\} \subseteq \R^{n}
		\end{align*}
\end{itemize}

\begin{definition}
%\label{thm:}
	Betrachte ein Bi-Matrixspiel mit Auszahlungsmatrizen $A,B \in \R^{m \times n}$. Dann heißt das 2-Personenspiel mit
	\begin{itemize}
		\item $\min\limits_{x} x^{T}Ay \quad \text{ udN } x \geq  0, e^{T}x = 1$
		\item $\min\limits_{y} x^{T}Ay \quad \text{ udN } y \geq  0, e^{T}y = 1$
	\end{itemize}
	die \underline{gemischte Erweiterung} des Bi-Matrixspiels. Ein Nash-GG $({x}^{*},{y}^{*})$ der gemischten Erweiterung heißt \underline{Nash-GG in gemischten Strategien} des Bi-Matrixspiels. Gilt $x=e_{i}$ oder $y = e_{j}$, so nennt man $x$ bzw. $y$ eine reine Strategie.
\end{definition}
\begin{satz}
%\label{thm:}
	Jedes Bi-Matrixspiel hat mindestens ein Nash-GG in gemischten Strategien.
\end{satz}

\begin{proof}
%\label{thm:}
	Folgt direkt aus Existenzsatz von Nihaido-Isoda.
\end{proof}

\begin{beisp}
%\label{thm:}
	Schere-Stein-Papier ha kein Nash-GG (in reinen Strategien) Es gibt genau ein Nash-GG in gemischten Strategien:
	\[
		{x}^{*} = \left( \frac{1}{3}, \frac{1}{3}, \frac{1}{3} \right)  
		\qquad 
		{y}^{*} = \left( \frac{1}{3}, \frac{1}{3}, \frac{1}{3} \right)  
	.\] 
	Interpretation einer gemischten Strategie $x \in \R^{m}$: Spieler 1 wählt Strategie $i$ mit Wahrscheinlichkeit $x_{i}$
\end{beisp}

\begin{lemma}
%\label{thm:}
	Betrachte ein Bi-Matrixspiel mit Auszahlungsmatrizen $A,B \in \R^{m \times n}$.
	\begin{enumerate}[label=(\alph{enumi})]
		\item Ist $(i,j)$ ein Nash-GG (in reinen Strategien), so ist $(e_{i}, e_{j})$ ein Nash-GG in gemischten Strategie
		\item Seien $\alpha , \beta \in \R$, $E \in \R^{m \times n}$ die matrix mit $e_{ij} = 1 \quad \forall i,j$. Dann ist $({x}^{*}, {y}^{*})$ genau dann ein Nash-GG in gemischten Strategien von dem Bi-Matrixspiel mit $A,B$, wenn es ein Nash-GG in gemischten Strategien von dem Bi-Matrixspiel mit  
			\[
			A+\alpha E, B+\beta E
			\] ist.

				($\implies$ oBdA. $A\geq 0 $, $ B \geq 0$ )
			\item $({x}^{*}, {y}^{*})$ ist ein Nash-GG in gemischten Strategien genau dann, wenn gilt
				\begin{align*}
					&({x}^{*})^{T}A {y}^{*} = \min\limits_{i=1, \ldots, m} (A{y}^{*})_{i} \\
					&({x}^{*})^{T}B {y}^{*} = \min\limits_{j=1, \ldots, n} (({x}^{*})^{T} B)_{j}
				\end{align*}
				\[
				\iff
				.\] 
				\begin{align*}
					&{x}^{*}_{i} > 0 \implies (A{y}^{*})_{i} = \min\limits_{l=1, \ldots, m} (A {y}^{*})_{l} \\
					&{y}^{*}_{j} > 0 \implies (({x}^{*})^{T}B)_{j} = \min\limits_{l=1, \ldots, n} (({x}^{*})^{T}B)_{l}
				\end{align*}
				
	\end{enumerate}
\end{lemma}

\begin{mdframed}
%\label{thm:}
	\subsection{\underline{Exkurs}: Lineare Optimierung}
	primales Problem
	\begin{equation}\label{eq:PProb}\tag{P}
	\min\limits_{x}c^{T}x \quad \text{ udN } Ax=b, x\geq 0
	\end{equation}
	mit $A \in \R^{m \times n}, b \in \R^{m}, c \in \R^{n}, x \in \R^{n}$.
	
	zugehöriges duales Problem:
	\begin{equation}\label{eq:DProb}\tag{D}
	\max\limits_{y} b^{T}y \quad \text{ udN } A^{T}y \leq  c, y \in \R^{m}
	\end{equation}
	\subsubsection{Schwache Dualität}
	\label{sec:Schwache Dualität}
	$x$ zulässig für \hyperref[eq:PProb]{(P)}, $y$ zulässig für \hyperref[eq:DProb]{(D)}, dann gilt
	\[
	c^{T}x \geq  b^{T}y
	.\] 
	Gilt \[
	c^{T}{x}^{*} = b^{T}{y}^{*}
	,\] 
	so ist ${x}^{*}$ eine Lösung von \hyperref[eq:PProb]{(P)} und ${y}^{*}$ eine Lösung von \hyperref[eq:DProb]{(D)}. Es gibt folgende drei Möglichkeiten:
	\begin{itemize}
		\item \hyperref[eq:PProb]{(P)} is \underline{unzulässig}, d.h. es gibt kein $x \in \R^{n}$ mit $Ax=b$ mit $x\geq 0$.
		\item \hyperref[eq:PProb]{(P)} ist \underline{unbeschränkt}, d.h. es gibt eine zulässige Folge $(x^{k})_{k}$ mit $c^{T}x^{k} \rightarrow - \infty$
		\item \hyperref[eq:PProb]{(P)} \underline{hat eine Lösung}, d.h. es gibt ${x}^{*}$ zulässig mit $c^{T}{x}^{*} \leq  c^{T}x$ für alle anderen zulässigen Punkte $x$
	\end{itemize}
	\subsubsection{Starke Dualität}
	\label{sec:Starke Dualität}
	\begin{enumerate}[label=(\alph{enumi})]
		\item \hyperref[eq:PProb]{(P)} und \hyperref[eq:DProb]{(D)} haben zulässige Punkte
		\item \hyperref[eq:PProb]{(P)} hat eine Lösung ${x}^{*}$
		\item \hyperref[eq:DProb]{(D)} hat eine Lösung ${y}^{*}$
		\item ${x}^{*}$ ist zulässig für \hyperref[eq:PProb]{(P)}, ${y}^{*}$ ist zulässig für \hyperref[eq:DProb]{(D)} und $c^{T}{x}^{*}=b^{T}{y}^{*}$.
		\item Es gibt ${x}^{*}, {y}^{*}$ mit $A{x}^{*} = b, {x}^{*}\geq  0, A^{T}{y}^{*} \leq  c$

			$\forall i=1, \ldots, n$ mit ${x}^{*}_{i}=0$ oder $(A^{T}{y}^{*})_{i}= c_{i}$ (KKT-Bedingungen)
	\end{enumerate}
\end{mdframed}

$({x}^{*},{y}^{*})$ ist ein Nash-GG in gemischten Strategien $\iff$
\begin{itemize}
	\item ${x}^{*}$ löst das lineare Problem
		\[
		\min\limits_{x}x^{T}\underbrace{A{y}^{*}}_{c} \quad \text{ udN } \underbrace{e^{T}}_{=A} x = \underbrace{1}_{=b}, x\geq 0
		.\] 
		Das zugehörige duale Problem ist
		\[
		\max\limits_{v} 1v \quad \text{ udN } cv \leq  AT{y}^{*}
		.\] 
	\item ${y}^{*}$ löst das lineare Problem
		\[
			\min\limits_{y}\underbrace{({x}^{*})^{T}B}_{=c^{T}} y \quad \text{ udN } \underbrace{e^{T}}_{=A} y = \underbrace{1}_{=b}, y\geq 0
		.\] 
		Das zugehörige duale Problem ist
		\[
		\max\limits_{w} 1w \quad \text{ udN } cw \leq  BT{x}^{*}
		.\] 
\end{itemize}
Das gilt mit starker Dualität genau dann, wenn
\begin{itemize}
	\item Es gibt ${v}^{*} \in \R$ mit 
		\[
			e^{T}{x}^{*} = 1, {x}^{*} \geq  0, \qquad e{v}^{*} \leq  A {y}^{*}, \qquad ({x}^{*})^{T}A{y}^{*} = v
		.\] 
	\item Es gibt ein ${w}^{*} \in\R$ mit 
		\[
			e^{T}{y}^{*} = 1, {y}^{*} \geq  0, \qquad e{w}^{*} \leq  B^{T}{x}^{*}, \qquad ({x}^{*})^{T}B{y}^{*} = {w}^{*}
		.\] 
\end{itemize}
Betrachte das quadratische Problem
\begin{equation}\label{eq:QPProb}\tag{QP}
	\min\limits_{x,y,v,w} q(x,y,v,w):=(x^{T}Ay - v) + (x^{T} By -w)
\end{equation}
unter den Nebenbedingungen
\begin{align*}
	e^{T}x = 1 x, &\geq  0\\
	e^{T}y=1, y&\geq  0 \\
	Ay &\geq ev \\
	x^{T}B &\geq e^{T}w
\end{align*}

\begin{satz}
%\label{thm:}
	Betrachte ein Bi-Matrixspiel mit Auszahlungsmatrizen $A,B \in \R^{m \times n}$ und das zugehörige quadratische Programm \hyperref[eq:QPProb]{(QP)}. Dann gelten:
	\begin{enumerate}[label=(\alph{enumi})]
		\item \hyperref[eq:QPProb]{(QP)} hat mingestens ein globales Minimum
		\item $({x}^{*},{y}^{*},{v}^{*},{w}^{*})$ ist genau dann ein \underline{globales} Minimum von \hyperref[eq:QPProb]{(QP)}, wenn $({x}^{*},{y}^{*})$ ein Nash-GG in gemischten Strategien ist, dann gilt
			\[
				q({x}^{*},{y}^{*},{v}^{*},{w}^{*})=0 \quad \text{ und }\quad {v}^{*} = ({x}^{*})^{T}A{y}^{*}, {w}^{*}=({x}^{*})^{T}B{y}^{*}
			.\] 
	\end{enumerate}
\end{satz}

\section{Matrixspiele}
\label{sec:Matrixspiele}
Wir betrachten den Spezialfall $B=-A$.

\begin{satz}
%\label{thm:}
	Jedes Matrixspiel hat mindestens ein Nash-GG in gemischten Strategien. Das \hyperref[eq:QPProb]{(QP)} reduziert sich zu
	\begin{align*}
	&\min\limits_{x,w} w \quad \text{ udN } e^{T}x = 1, x \geq  0, x^{T}A \leq  we^{T} \\
	&\max\limits_{y,v} v \text{ udN } e^{T}y = 1, y\geq 0, Ay\geq  ve
	\end{align*}
\end{satz}

\begin{satz}
%\label{thm:}
	Betrachte ein Matrixspiel mit Auszahlungsmatrix $A \in \R^{m \times n}$. Dann ist $({x}^{*},{y}^{*})$ genau dann ein Nash-GG in gemischten Strategien, wenn
	\begin{enumerate}[label=(\arabic{enumi})]
		\item es ${w}^{*} \in \R$ gibt, so dass $({x}^{*}, {w}^{*})$ das lineare Program \hyperref[eq:PProb]{(P)} löst und
		\item es ${v}^{*} \in \R$ gibt, sodass $({y}^{*}, {v}^{*})$ das lineare Problem \hyperref[eq:DProb]{(D)} löst. 
	\end{enumerate}
	In diesem Fall gilt
	\[
		{v}^{*} = ({x}^{*}) ^{T} A {y}^{*} = {w}^{*}
	.\] 
\end{satz}

Jedes Matrixspiel hat mindestens ein Nash-GG $({x}^{*}, {y}^{*})$ in gemischten Strategien. Man nennt
\[
	v:= ({x}^{*}) ^{T} A{y}^{*}
\] 
den \underline{Wert des Spiels}. Dieser Wert ist trotz des beliebigen Nash-GG $({x}^{*},{y}^{*})$ eindeutig, da er für alle Nash-GG's gleich groß ist.

\begin{beisp}
%\label{thm:}
	Betrachte das Matrixspiel mit
	\[
	A= \begin{pmatrix}
		3 & 1 & 8 \\
		4 & 10 & 0
	\end{pmatrix}
	.\] 
	\begin{itemize}
		\item Spieler 1 muss Zeile $i \in \left\{ 1,2 \right\} $ wählen und will $a_{ij}$ minimieren.
		\item Spieler 2 muss Spalte $j \in \left\{ 1,2,3 \right\} $ wählen und will $a_{ij}$ maximieren.
	\end{itemize}
	Es folgen:
	\begin{itemize}
		\item Spieler 1 sollte $i=1$ wählen als Lösung von
	\[
	\overline{v} = \min\limits_{i}\max\limits_{j}a_{ij} = 8
	.\] 
		\item Spieler 2 sollte $j=1$ wählen als Lösung von
	\[
		\underline{v} := \max\limits_{j}\min\limits_{i}a_{ij} = 3
	.\] 
	\end{itemize}
	Hierbei nennen wir $\overline{v}$ den \underline{oberen Spielwert} und $\underline{v} $ den \underline{unteren Spielwert}.
\end{beisp}

\begin{lemma}
%\label{thm:}
	Sei $A \in \R^{m \times n}$. Dann gilt:
	\[
	\underline{v} := \max\limits_{j}\min\limits_{i} a_{ij} \leq  \min\limits_{i} \max\limits_{j} a_{ij} =: \overline{v}
	.\] 
\end{lemma}

\begin{proof}
%\label{thm:}
	Für alle $j,l$ gilt 
	\begin{align*}
		\qquad \min\limits_{i}a_{ij} &\leq  a_{lj}\\
		\implies \max\limits_{j}\min\limits_{i}a_{ij} &\leq  \max\limits_{j}a_{lj} \\
		\implies \max\limits_{j}\min\limits_{i} a_{ij} &\leq  \min\limits_{l}\max\limits_{j}a_{lj}
	\end{align*}
\end{proof}

\begin{lemma}
%\label{thm:}
	Betrachte ein Matrixspiel mit Auszahlungsmatrix $A \in \R^{m \times n}$. Dann gilt
	\[
	\underline{v}  \leq  v \leq  \overline{v}
	.\] 
\end{lemma}

\begin{proof}
%\label{thm:}
	Sei $({x}^{*}, {y}^{*})$ ein Nash-GG. Es gilt
	\begin{align*}
		\underline{v} &= \max\limits_{j}\min\limits_{i}a_{ij} \\
		\overline{v} &= \min\limits_{i}\max\limits_{j}a_{ij} \\
		v&= ({x}^{*})^{T}A {y}^{*}
	\end{align*}
	Then
	\begin{align*}
		v &= \min\limits_{i}(A{y}^{*})_{i} = \min\limits_{i}\underbrace{\sum_{j}^{}{a_{ij}{y}^{*}_{j}}}_{\leq  \max\limits_{j}a_{ij}} \leq  \min\limits_{i}\max\limits_{j}a_{ij} = \overline{v} \\
		v &= \max\limits_{j}(({x}^{*})^{T}A)_{j} = \max\limits_{j}\underbrace{\sum_{i}^{}{a_{ij}{x}^{*}_{i}}}_{\geq  \min\limits_{i}a_{ij}} \geq  \max\limits_{j}\min\limits_{i}a_{ij}= \underline{v} 
	\end{align*}
\end{proof}

Betrachte eine Matrix $A \in \R^{m \times n}$. Dann heißt $({i}^{*},{j}^{*})$ ein \underline{Sattelpunkt} von $A$, wenn gilt
\[
a_{{i}^{*}j} \leq  a_{{i}^{*}{j}^{*}} \leq  a_{i{j}^{*}} \qquad \forall i,j
.\] 
Es gilt $({i}^{*},{j}^{*})$ ist ein Sattelpunkt $\iff$ $({i}^{*},{j}^{*})$ ist ein Nash-GG des Matrixspiels mit Auszahlungsmatrix $A$.

\begin{satz}
%\label{thm:}
	Ein Matrixspiel mit Auszahlungsmatrix $A \in \R^{m \times n}$ hat genau dann ein Nash-GG in reinen Strategien, wenn gilt 
	\[
	\underline{v}  = \overline{v} = v
	.\] 
\end{satz}

\begin{proof}
%\label{thm:}
\begin{itemize}
	\item "$\Longrightarrow$"

		Sei $({i}^{*},{j}^{*})$ ein Nash-GG/Sattelpunkt, d.h. es gelte
		\[
		a_{{i}^{*}{j}^{*}} = \min\limits_{i}a_{i,{j}^{*}} \quad \text{ und }\quad a_{{i}^{*}{j}^{*}} = \max\limits_{j}a_{{i}^{*},j}
		.\] 
		Dann gilt
		\[
		\overline{v} = \min\limits_{i}\max\limits_{j}a_{ij} \leq  \max\limits_{j}a_{{i}^{*}j} = a_{{i}^{*}{j}^{*}} = \min\limits_{i}a_{i{j}^{*}} \leq  \max\limits_{j}\min\limits_{i}a_{ij} = \underline{v}
		.\] 
		Also gilt
		\[
		\overline{v} = \underline{v} 
		.\] 

	\item "$\Longleftarrow$"

		Sei
		\[
		\max\limits_{j}\min\limits_{i}a_{ij} = \underline{v} = \overline{v} = \min\limits_{i}\max\limits_{j}a_{ij}
		.\]
		Wähle
		\begin{itemize}
			\item ${j}^{*}$ mit $\min\limits_{i}a_{i{j}^{*}}= \min\limits_{i}\max\limits_{j}a_{ij}=\overline{v}$. 
			\item ${i}^{*}$ mit $\max\limits_{j}a_{{i}^{*}j}=\max\limits_{j}\min\limits_{i}a_{ij}= \underline{v} $
		\end{itemize}
		Wir zeigen, dass $({i}^{*},{j}^{*})$ ein Nash-GG/Sattelpunkt ist:
		\begin{itemize}
			\item
				${i}^{*}$ ist die beste Antwort für Spieler 1:
				\[ a_{{i}^{*}{j}^{*}}\leq  \max\limits_{j}a_{{i}^{*}j} = \underline{v} = \overline{v} = \min\limits_{i}a_{i{j}^{*}} .\]

			\item
				${j}^{*}$ ist die beste Antwort für Spieler 2.
				\[a_{{i}^{*}{j}^{*}} \geq  \min\limits_{i}a_{i{j}^{*}}=\overline{v} = \underline{v} = \max\limits_{j}a_{{i}^{*}j}.\]
		\end{itemize}
		Damit folgt schlussendlich
		\[
			a_{{i}^{*}j}\leq  a_{{i}^{*}{j}^{*}}\leq  a_{i{j}^{*}} \quad \forall i,j \implies \quad ({i}^{*},{j}^{*}) \text{ ist ein Nash-GG/Sattelpunkt }
		.\] 
\end{itemize}
\end{proof}

Ein Matrixspiel mit Auszahlungsmatrix $A \in \R^{m \times n}$ heißt
\begin{itemize}
	\item \underline{fair}, wenn gilt $v=0$
	\item \underline{symmetrisch}, wenn gilt $A^{T} = -A$ ($\implies$ m=n, $a_{ii}=0$)
\end{itemize}

\begin{lemma}
%\label{thm:}
	Symmetrische Spiele sind fair.
\end{lemma}

\begin{proof}
%\label{thm:}
	Ist $({x}^{*},{y}^{*})$ ein Nash-GG in gemischten Strategien, dann muss auch $({y}^{*},{x}^{*})$ ein Nash-GG in gemischten Strategien sein.
	\[
		\implies v=({x}^{*})^{T}A{y}^{*} = ({y}^{*})^{T}A{x}^{*} = \Big( ({y}^{*})^{T}A{x}^{*} \Big)^{T} = ({x}^{*})^{T}A^{T}{y}^{*} = -v
	.\] 
\end{proof}

\begin{lemma}
%\label{thm:}
	Ein symmetrisches Spiel hat genau dann ein Nash-GG, wenn  es eine Spalte ${j}^{*}$ gibt mit
	\[
	a_{i{j}^{*}}\geq  0 \quad \forall i
	.\]
	Dann ist $({j}^{*},{j}^{*})$ ein Nash-GG.
\end{lemma}

\begin{proof}
%\label{thm:}
\begin{itemize}
	\item "$\Longrightarrow$"

	Sei $a_{i{j}^{*}} \geq  0 \quad \forall i$. Dann
	\[
	a_{{j}^{*}{j}^{*}} = 0 = \min\limits_{i}a_{i{j}^{*}}
	.\]
	Wegen $A^{T} = -A$ gilt
	\[
	a_{{j}^{*}i} \leq  0 \quad \forall j
	.\] 
	\[
	\implies a_{{j}^{*}{j}^{*}} = 0 = \max\limits_{i}a_{{j}^{*}i}
	.\] 

	\item "$\Longleftarrow$"
		Sei $({i}^{*},{j}^{*})$ ein Nash-GG.
		\begin{align*}
		&\implies a_{{i}^{*} j} \leq  a_{{i}^{*}{j}^{*}} \leq  a_{i {j}^{*}} \\
		&\implies 0 = a_{{i}^{*}i} \leq  a_{i{j}^{*}} \qquad \forall i
		\end{align*}
\end{itemize}
\end{proof}

\begin{beisp}
%\label{thm:}
	\begin{itemize}
		\item Schere-Stein-Papier : 
			\[
			A = \begin{pmatrix}
				0 & -1 & 1 \\
				1 & 0 & -1 \\
				-1 & 1 & 0
			\end{pmatrix}
			= -A^{T}
			\] 
			hat keine Spalte $\geq 0$, also existiert kein Nash-GG.
		\item 
			\[
			A= \begin{pmatrix}
				0 & 1 & 1 \\
				-1 & 0 & -1 \\
				-1 & 1 & 0
			\end{pmatrix}
			= -A^{T}
			.\] 
			Hier ist $(2,2)$ ein Nash-GG.
		\item pathologisches Beispiel
			\[
			A= \begin{pmatrix}
			 0 & 0 \\
			 0&0
			\end{pmatrix}
			=-A^{T}
			.\] 
			Hat Nash-GG, die nicht auf der Diagonalen liegen.
	\end{itemize}
\end{beisp}

Wir hatten die beiden Fälle:
\begin{itemize}
	\item allgemein : \[
			X_{i}(x^{-i}) = \left\{ x^{i}~|~ g_{i}(x^{i}) \leq  0,~ G_{i}(x^{i}, x^{-i}) \leq  0 \right\} 
	.\] 
	\item gemeinsame Strategiemenge : \[
			X = \left\{ x~|~ G(x) \leq  0 \right\} \implies X_{i}(x^{-i}) = \left\{ x^{i} ~|~ G(x^{i}, x^{-i}) \leq 0 \right\} 
	.\] 
\end{itemize}

\begin{align*}
&{x}^{*}\text{ ist ein normalisiertes Nash-Gleichgewicht } \\
	\iff & {x}^{*} \in X \text{ und } {x}^{*} \text{ löst } \max\limits_{y \in X}\psi ({x}^{*},y)  = \sum_{i=1}^{N}{f_{i}(x^{*,i}, x^{*, -i}) - f_{i}(y^{i}, x^{*,-i})} \\
	\iff & {x}^{*} \in X \text{ und } {x}^{*} \text{ löst } \min\limits_{y \in X} \sum_{i=1}^{N}{f_{i}(y^{i}, x^{*,-i})}
\end{align*}

Sei $X = \left\{ x ~|~ G(x) \leq 0 \right\} $. Dann vergleichen wir:
\begin{itemize}
	\item Problem von Spieler $i$:
		\[
			\min\limits_{x^{i}}f_{i}(x^{i}, x^{*,-i}) \quad \text{ udN }\quad G(x^{i}, x^{*,-i}) \leq 0
		.\] 
		Ist ${x}^{*}$ ein Nash-GG und gilt CQ, so folgt:
		$x^{*,i}$ ist ein KKT-Punkt, d.h. $\exists Z^{i} \geq  0$ mit
		\[
			\nabla _{x^{i}}f_{i}(x^{*,i}, x^{*,-i}) + \nabla _{x^{i}}G(x^{*,i}, x^{*,-i}) Z^{i} = 0
		\] 
		mit
		\[
			Z^{i}\geq  0 \perp G(x) \leq  0
		.\] 
		% Was ist CQ
	\item gemeinsames Problem:
		\[
			\min\limits_{y}\sum_{i=1}^{N}{f_{i}(y^{i}, x^{*,-i})}\quad \text{ udN }\quad G(y) \leq 0
		.\] 
		Ist ${x}^{*}$ normalisiertes Nash-GG und gilt CQ, so folgt:
		$x^{*}$ ist ein KKT-Punkt, d.h. $\exists Z \geq  0$ mit
		\[
		\begin{pmatrix}
			\nabla _{x^{1}} f_{1}(x^{*,1}, x^{*,-i}) \\
			\vdots \\
			\nabla _{x^{N}}f_{N}(x^{*,N}, x^{*,-i})
		\end{pmatrix}
		+
		\begin{pmatrix}
			\nabla _{x^{i}}G({x}^{*}) \\
			\vdots \\
			\nabla _{x^{N}}G(x^{*})
		\end{pmatrix}
		Z = 0
		\] 
		($Z$ wird mit allen Zeilen multipliziert) mit
		\[
			Z\geq  0 \perp G(x) \leq  0
		.\] 
\end{itemize}

\begin{satz}
%\label{thm:}
	Betrachte ein GNEP
	\begin{itemize}
		\item mit gemeinsamer Strategiemenge $X \subseteq \R^{n}$
		\item $X$ nichtleer, abgeschlossen, konvex
		\item $f_{i}$ konvex bezüglich $x^{i}$
	\end{itemize}
	Dann sind äquivalent:
	\begin{enumerate}[label=(\alph{enumi})]
		\item  ${x}^{*}$ ist ein normalisiertes Nash-GG
		\item ${x}^{*}\in X$ und $\sup_{y \in X} \psi ({x}^{*},y) = 0$
		\item ${x}^{*}$ löst das Problem $\min\limits_{y} \sum_{i=1}^{N}{f_{i}(y_{i}, x^{*,-i})}$ udN $y \in X$
	\end{enumerate}
	 Ist zusätzlich $f_{i}$ stetig diffbar für alle $i=1, \ldots, N$, dann
	 \begin{enumerate}[label=(\alph{enumi})]
		 \setcounter{enumi}{3}
	 \item ${x}^{*}$ löst VIP$(X,F)$ mit $F(x) = \Big(\nabla _{x^{i}} f_{i}(x) \Big)_{i=1}^{N}$
	 \item ${x}^{*}$ löst $x=P_{X}(x-\gamma  F(x))$ für alle $\gamma  > 0$
	 \end{enumerate}
\end{satz}

\begin{proof}
	Wir wissen schon:
	\begin{itemize}
		\item $(a) \iff (b) \iff (c)$
		\item $(d) \iff (e)$
	\end{itemize}
	Wir zeigen nun: $(c) \iff (d)$

	Es gilt $X$ ist nichtleer, abgeschlossen, konvex und 
	\[
		y \mapsto \sum_{i=1}^{N}{f_{i}(y^{i}, x^{*,-i})}
	\] 
	ist konvex und stetig diffbar. Daher gilt
	\begin{align*}
		(c) \overset{\text{Min.-Prinzip}}&{\iff} \underbrace{\begin{pmatrix}
				\nabla _{x^{1}} f_{1}({x}^{*}) \\
				\vdots \\
				\nabla _{x^{N}}f_{N}({x}^{*})
		\end{pmatrix} ^{T}
	}_{=F({x}^{*})} (y - {x}^{*}) \geq  0 \quad \forall y \in X  \\
										 &\iff {x}^{*} \text{ löst VIP}(X,F) \\
										 &\iff (d)
	\end{align*}
\end{proof}

\begin{satz}
%\label{thm:}
	Betrachte ein GNEP mit
	\begin{itemize}
		\item gemeinsamer Strategiemenge $X$
		\item $X \subseteq \R^{n}$ nichtleer, abgeschlossen, konvex
		\item $f_{i}$ stetig diffbar und konvex in $x^{i}$
	\end{itemize}
	Definiere
	\[
		F(x) := \Big( \nabla_{ x^{i}} f_{i}(x) \Big)_{i=1}^{N}
	.\] 
	Dann gelten:
	\begin{enumerate}[label=(\alph{enumi})]
		\item Ist $F$ pseudomonoton, so ist die Menge der normalisierten Nash-GG konvex 

			(evtl. leer)
		\item Ist $F$ strikt monoton, so gibt es höchstens ein normalisiertes Nash-GG 

			(evtl keins)
		\item Ist $F$ gleichmäßig monoton, so gibt es genau ein normalisiertes Nash-GG

			($\implies$ mindestens ein Nash-GG)
		\item Ist $X$ kompakt, so gibt es mindestens ein normalisiertes Nash-GG

			($\implies$ mindestens ein Nash-GG)
	\end{enumerate}
	
	(Dies ist nur eine Zusammenfassung von Resultaten, daher kein Beweis)
\end{satz}

\begin{satz}
%\label{thm:}
	Betrachte ein GNEP mit
	\begin{itemize}
		\item gemeinsamer Strategiemenge $X$
		\item $X \subseteq \R^{n}$ nichtleer, konvex, \underline{kompakt} 
		\item $f_{i}$ stetig in $x$ für alle $i=1, \ldots, N$
		\item $f_{i}$ konvex bezüglich $x^{i}$ für alle festen $x^{-i}$ $\forall i=1, \ldots, N$
	\end{itemize}
	Dann hat das Spiel mindestens ein normalisiertes Nash-GG.
\end{satz}

\begin{proof}
%\label{thm:}
	Die Funktion
	\[
		\psi (x,y) = \sum_{i=1}^{N}{f_{i}(x^{i}, x^{-i}) - f_{i}(y^{i}, x^{-i})}
	\] 
	ist konvex bezüglich $y$.

	${x}^{*}$ ist ein normalisiertes Nash-GG $\iff$ 
	\[
		{x}^{*} \in X \quad\text{ und } \quad \sup_{y \in X}\psi ({x}^{*},y) = 0
	.\] 
	Angenommen es gibt \underline{kein}  normalisiertes Nash-GG
	\[
		\implies \forall x \in X \text{ gilt } \sup_{y \in X}\psi (x,y) > 0 
	,\] 
	d.h. es gibt ein $y \in X$ mit $\psi (x,y) > 0$.

	Definiere 
	\[
	U(y) := \left\{  x \in X ~|~ \psi (x,y) > 0 \right\} 
	.\] 
	 Da alle $f_{i}$ stetig sind, sind die Mengen $U(y)$ offen (bezüglich $X$). Außerdem gilt
	\[
		X \subseteq  \bigcup_{y \in X}U(y)
	.\] 
	Die Mengen $U(y)$ mit $y \in X$ bilden also eine offene Überdeckung der kompakten Menge $X$, d.h. es gibt eine endliche Teilüberdeckung
	\[
		X \subseteq \bigcup_{j=1}^{m}U(y^{j}) \quad \text{ mit }\quad y^{j} \in X
	.\] 
	Wir definieren uns eine Abbildung $h \colon X \rightarrow X $ mit
	\[
		d_{j}(x) := \max\limits_{}\left\{ 0, \psi (x,y^{j}) \right\}  \quad \forall j =1, \ldots, m
	.\] 
	\[
		Z_{j}(x) := \frac{d_{j}(x)}{\sum_{l=1}^{m}{d_{l}(x)}} \quad \forall j=1, \ldots, m
	.\] 
	\[
		h(x) := \sum_{j=1}^{m}{Z_{j}(x) \cdot  y^{j}} \in X
	.\] 
	Dann ist $h \colon X \rightarrow X $ eine stetige Abbildung mit $X$ kompakt. Nach dem Browerschen Fixpunktsatz gibt es daher einen Fixpunkt ${x}^{*} = h({x}^{*}) \in X$.
	\[
		\implies 0 = \psi ({x}^{*}, {x}^{*}) = \psi ({x}^{*}, \sum_{j=1}^{m}{Z_{j}({x}^{*}) y^{j}} \geq \sum_{j=1}^{m}{\underbrace{Z_{j}({x}^{*})}_{\geq 0} \psi ({x}^{*}, y^{j}) }> 0
	.\] 
	Das ist ein Widerspruch. $\lightning$
\end{proof}

\subsection{GNEPs und Quasivariationsungleichungen}%
\label{sec:GNEPs und Quasivariationsungleichungen}

Betrachte ein allgemeines GNEP, d.h.
\[
	\forall i =1, \ldots, N \qquad  \min\limits_{x^{i}}f_{i}(x^{i}, x^{-i}) \quad \text{ udN }\quad x^{i} \in X_{i}(x^{-i})
.\] 
Definiere die Menge der zulässigen Reaktionen:
\[
	\Omega (x) = X_{1}(x^{-1}) \times  \ldots  \times X_{N}(x^{-N})
.\] 
Dann ist ${x}^{*}$ genau dann ein Nash-GG, wenn gilt
$\forall i=1, \ldots, N$
\[
	{x}^{*} \in \Omega ({x}^{*}) \quad \text{ und }\quad f_{i}(x^{*,i}, x^{*,-i}) \leq  f_{i}(x^{i}, x^{*,-i}) \quad \forall x^{i} \in X_{i}(x^{*,-i})
.\] 
Sind $X_{i}(x^{-i})$ abgeschlossen, konvex und $f_{i}$stetig diffbar und bezüglich $x^{i}$ konvex, so gilt
\begin{align*}
	&&f_{i}(x^{*,i}, x^{*,-i}) &\leq  f_{i}(x^{i}, x^{*,-i}) \quad &&\forall x^{i} \in X_{i}(x^{*,-i}) \\
	\iff
	&&\nabla _{x^{i}}f_{i}(x^{*,i}, x^{*,-i})^{T}(x^{i} - x^{*,i}) &\geq  0 \quad &&\forall x^{i} \in X_{i}(x^{*,-i}) \\
\end{align*}
Dann folgt
\[
{x}^{*} \text{ ist ein Nash-GG } \iff \begin{cases}
	{x}^{*} \in \Omega ({x}^{*}) \text{ und } \\
	F({x}^{*})^{T}(x-{x}^{*})\geq 0 \quad \forall x \in \Omega ({x}^{*}) \\
	\text{mit } F(x) = \Big( \nabla _{x^{i}}f_{i}(x) \Big)_{i=1}^{N}
\end{cases}
.\] 
\underline{Quasivariationsungleichung}

Gegeben $F \colon \R^{n} \rightarrow \R^{n} $ und $\Omega \colon \R^{n} \rightrightarrows \R^{n}$, heißt das Problem, ein ${x}^{*} \in \Omega ({x}^{*})$ mit 
\[
	F({x}^{*})^{T}(x-{x}^{*}) \geq  0 \quad \forall x \in \Omega ({x}^{*})
\]
zu finden, ein Quasivariationsungleichungsproblem, kurz QVI$(\Omega ,F)$.
Spezialfall: $\Omega (x) = X + \varphi (x)$ "moving set"
