# On two-player zero-sum games and conic linear programming

Nick Dimou111Prospective student; recently completed undergraduate studies at
the National and Kapodistrian University of Athens, Department of Mathematics,
Athens, Greece. We would like to thank professor Alexander Shapiro for helping
us develop a better understanding concerning some important parts of his work
[36].

###### Abstract

We show that strong duality for conic linear programming directly implies the
minimax theorem for a wide class of infinite two-player zero-sum games. In
fact, for every two-player zero-sum game with “cone-leveled” strategy sets,
its game value and (approximate) Nash equilibria can be calculated by simply
solving a primal-dual pair of conic linear problems. The original results
proven by von Neumann and Dantzig are therefore naturally generalized to the
infinite-dimensional case, and a strong connection between two-player zero-sum
games and mathematical programming is established.

Key words: Minimax theorem, Conic linear programming, Nash equilibrium, Two-
player zero-sum games, Cone-leveled strategy sets, Infinite games

MSC 2020 subject classification: Primary: 91A05, 91B50, 90C47, 90C90;
Secondary: 90C23, 91A70

##  1 Introduction

In 1947 G.B. Dantzig met with J. von Neumann in order to consult with him
regarding solution techniques of linear programs and the Simplex method which
the former had developed; after Dantzig’s short presentation, to his big
surprise, von Neumann went on to give him an hour and a half lecture on the
mathematical theory of linear programming [10]. After this iconic meeting, the
connection between the famous minimax theory developed by von Neumann [39] and
the strong duality theory of linear programming, as well as the computation of
game equilibria with the use of the Simplex method were established [9], [40],
which in turn paved the way towards the evolution of game theory and
mathematical programming.

Throughout the years, several attempts have been made regarding the connection
between different two-player zero-sum games and general classes of linear
programming problems, many of which have been characterized by their
corresponding authors as generalizations of the original relation mentioned
above: In 1989 E.J. Anderson et al. [4] discussed the application of general
capacity problems in two-player zero-sum games and the existence and
calculation of Nash equilibria in mixed strategies. Similar references
regarding the connection between two-player zero-sum games and continuous
linear programming (CLP) have appeared previously in Bellman [6]. The most
commonly used class of mathematical programming (other than LP) in the
existence and calculation of Nash equilibria in zero-sum games (and not just
bimatrix games) is that of semi-definite programming (SDP). In particular,
Parrilo [32] showed that two-player zero-sum polynomial games in the closed
interval $[-1,1]$ can be calculated by solving a primal-dual pair of SDP
problems. This result was later extended by Laraki and Lasserre [26] to static
and dynamic games, as well as to polynomial stochastic games by Shah and
Parrilo [35]. Semi-definite programming has been shown to also play a
significant role in specific classes of two-player zero-sum quantum games (see
e.g. [19] and the references within). On a different note, forty years after
the original definition of complex games, the author managed to give a proof
of the minimax theorem and prove the existence of mixed complex Nash
equilibria via linear programming in complex space [13]. Despite all these
isolated cases however, a complete theory regarding the connection between
game theory and mathematical programming has not been yet given, and the
question about which two-player zero-sum games, finite or infinite, can be
effectively described by a primal-dual pair of generalized linear programming
problems has remained open.

The main purpose of this paper is to present a wide class of infinite two-
player zero-sum games that can be described by a primal-dual pair of conic
linear problems. In particular, we show that in every two-player zero-sum game
with a bilinear payoff function of the form $u(x,y)=\langle y,Ax\rangle$ and
cone-leveled strategy sets $S,\;T$, the generalized minimax equation
$\adjustlimits{\sup}_{x\in S}{\inf}_{y\in T}u(x,y)=\adjustlimits{\inf}_{y\in
T}{\sup}_{x\in S}u(x,y)$ always holds and the game value is equivalent to the
common optimal value of a primal-dual pair of conic linear problems, if strong
duality holds for that specific pair. It directly follows that an
(approximate) Nash equilibrium can be easily calculated by finding the
(approximate) optimal solutions for that pair of conic linear problems. A
cone-leveled set defined here is essentially the intersection of a (convex)
cone with a “hyperplane” generated by a bilinear form
$\langle\cdot,\cdot\rangle_{X}$ defined over a pairing of spaces $(X,W)$. More
formally, a cone-leveled set $S\subset X$ is a set that can be written as
$S:=\\{x\in C:\langle\alpha,x\rangle_{X}=\mu\\}$, where $C\subset X$ is a
(convex) cone, $\alpha\in W$ and $\mu\in\mathbb{R}\setminus\\{0\\}$. We show
that an important subfamily of such strategy sets are those of mixed
strategies (see Example 5.3). The main minimax results of this paper therefore
characterize a wide class of strategy sets (of either pure or mixed
strategies) with a geometric structure that is sufficient for the solution of
the game to come down to the solution of a pair of conic linear programs. It
is worth clarifying that while this class of games includes the finite case,
here we mainly deal with infinite games, for the computational aspect of the
latter is not fully covered in the relevant literature in comparison to that
of finite games, as it is seen by the subsequent paragraphs.

The gist of our contribution relies on the increased generality of the class
of games treated and of the mathematical programming problems that are
associated with them. To be more specific, we allow arbitrary properties for
both the payoff functions and the strategy spaces; the payoff functions need
only be bilinear, that is no continuity is assumed; the strategy spaces are
not assumed to be compact; the spaces $X,\;W$ (and $Z,\;Y$ respectively) can
either be finite or infinite-dimensional vector spaces, not necessarily
topological. Furthermore, we show that the treated class of two-player zero-
sum games can be described and therefore solved by the following pair of conic
linear problems:

${(P)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}min\;\;\langle c,x\rangle_{X}\\\
s.t.\;\;Ax-b\in K^{*}\\\ \;\;\;\;\;\;\;\;x\in C\end{array}$
${(D)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}max\;\;\langle y,b\rangle_{Z}\\\
s.t.\;\;-A^{*}y+c\in C^{*}\\\ \;\;\;\;\;\;\;\;\;\;\;y\in K\end{array}$

Here $\langle\cdot,\cdot\rangle_{X}$ is a bilinear form defined over a pairing
of vector spaces $(X,W)$, $\langle\cdot,\cdot\rangle_{Z}$ is a bilinear form
defined over a pairing of vector spaces $(Z,Y)$, $A:X\rightarrow Z$ is a
linear mapping, $A^{*}:Y\rightarrow W$ is its linear adjoint, $C\subset X$ and
$K\subset Y$ are convex cones and $C^{*},\;K^{*}$ are their positive dual
cones, $b\in Z$, and $c\in W$. This primal-dual pair of conic linear problems
constitutes a very general form of linear programming problems, whose
subclasses include among others those of linear programming problems (LP),
semi-definite programming problems (SDP), semi-infinite programming problems
(SIP), quadratic programming problems (QP), copositive programming problems
(CP), second order cone programming problems (SOCP), continuous linear
programming problems (CLP), general capacity problems (GCAP) and linear
programming problems in complex space (LPC). Therefore, the key results that
appear in this paper can be characterized as natural extensions of the
original results given by von Neumann and Dantzig, as well as generalizations
of all the aforementioned related results that have appeared previously in the
literature. Quoting Gürkon and Pang [18], “In contrast to optimization
problems, the approximation of Nash equilibria is a subject that has so far
received only minimal attention in the literature of mathematical programming.
In essence, all the reasons, practical and theoretical, for studying the
approximation of optimization problems persist in the computation of Nash
equilibria”, we believe that this paper, to the best of our knowledge,
presents the strongest and most generic connection between two-player zero-sum
games and mathematical programming currently known.

It must be mentioned that the motivation for this paper did not only originate
from the need for a complete theoretical relation between game theory and
mathematical programming, but also from the open questions that resolve the
computational aspects of infinite games. Firstly, one needs to take a look at
the historic background regarding the computational complexity and algorithmic
methods for calculating Nash equilibria in finite games: Dantzig’s first
efficient algorithm, known as the Simplex method, was followed by Khachiyan’s
polynomial-efficient ellipsoid algorithm back in 1979 [21]. Soon after, a
path-following interior-point algorithm was given by Karmarkar [20]. The
computational aspect and complexity of finite games have been since then
studied for years, up until 2006, when Daskalakis, Goldberg and Papadimitriou
[11] proved that the problem of computing a Nash equilibrium in a finite game
with four or more players was PPAD-complete. This result was improved by
Daskalakis and Papadimitriou [12] for the case of three players and soon after
by Chen and Deng [7] for two-player finite games. Despite these groundbreaking
results, computational complexity has not been studied to such an extend for
infinite games. The relevant literature contains some efficient calculation
methods for the problem of finding a Nash equilibrium in specific cases of
(two-player zero-sum) infinite games (see [1], [15], [18], [26], [32], [35],
[38] and the references within). However, a complete answer to the question
set by Kuhn and Tucker [24] regarding finding “a computational technique of
general applicability for zero-sum two-person games with infinite sets of
strategies” has not yet been given.

The main theorems presented here give a partial answer to such open problem.
Indeed by describing an infinite two-player zero-sum game as a primal-dual
pair of conic linear problems, the (approximate) calculation of a Nash
equilibrium eventually comes down to the calculation of the optimal solutions
for those two problems problems via interior-point methods, discretization
techniques, first and second order subgradient type algorithms, etc., when a
duality gap does not exist. As mentioned above, these two problems may take a
known form of mathematical programming, such as SDP, SIP, CLP, GCAP, for all
of which calculation methods already exist in the relevant literature (see for
example [16] [25], [37], [42] and the references withing for some textbooks,
surveys and papers that cover both the theoretical and computational aspects
of the forms of MP mentioned).

In addition, the analysis presented in this paper gives rise to several
important logical questions relevant with recent results that concern both the
theoretical and computational aspects of two-player zero-sum games, and
therefore sets the basis for future work on the related ground. Firstly, since
we show that duality theory for conic linear problems directly implies the
generalized minimax theorem, it is only natural to ask whether or not the
converse is also true. This question concerns the equivalence between infinite
two-player zero-sum games and mathematical programming. The answer for finite
two-player zero-sum games, while believed to be known for several decades by
the work of Dantzig [8], it has only been (positively) given very recently by
Adler [2]; the matter still receives attention (see von Stengel [41]).
Secondly, Parrilo [32] showed that any two-player zero-sum polynomial game
defined over $[-1,1]$ can be solved by equivalently solving a pair of SDP
problems. In Example 5.7 below, we show that if we translate Parrilo’s work
into our framework, we obtain that any such polynomial game is strategically
equivalent to a different two-player zero-sum game, say $\mathcal{G}^{\prime}$
that has cone-leveled sets. In this particular case, by using the theory that
appears in Sections 3 and 5, a polynomial game can be solved by a pair of GCAP
problems, while the corresponding strategically equivalent game
$\mathcal{G}^{\prime}$ can be solved, obviously more efficiently, by a pair of
SDP problems. This observation is of great significance, since it implies that
if a game $\mathcal{G}$ is strategically equivalent to a different game
$\mathcal{G}^{\prime}$ that also has cone-leveled strategy sets, then it
suffices to solve the game that is associated with the simplest form of conic
linear problems. Hence this exact same methodology may be applied to other
types of infinite two-player zero-sum games.

The rest of the paper is organized as follows: in Section 2 we give some basic
preliminaries regarding two-player zero-sum games and conic linear problems,
and we properly define cone-leveled sets. Section 3 includes the main results.
The first two minimax theorems are complementary to one another, while Theorem
3.3 is more general and complete and includes the previous two under
additional assumptions. As mentioned above, the existence of a Nash
equilibrium eventually comes down to a zero duality gap between two conic
linear problems. Therefore, in Section 4 we present numerous cases where this
strong duality condition holds and Nash equilibria exist, using known results
by Shapiro [36], Anderson [3], Anderson and Nash [5], Kretschmer [23] and
Khanh et al. [22]. In Section 5 we present numerous examples of games where
the strategy sets are cone-leveled. Most of these represent known two-player
zero-sum games whose solution comes down to that of LP, CLP, SDP, SIP, GCAP
problems, in order to illustrate both the theoretical and the computational
purposes of this paper. In Section 6, we give a simple criterion for a set to
be cone-leveled, by using the analytical form of the Hahn-Banach theorem.
Lastly, we briefly discuss future work and set some questions related to our
work.

##  2 Preliminaries and notation

We firstly give the topological framework and the structure of the conic
linear programming problems that will appear in the next sections. The same
topological framework is used to define the class of games that we treat in
this paper. We will assume that the reader is familiar with the basic theory
of topological vector spaces.

Let $(X,W)$, $(Z,Y)$ be dual pairs of vector spaces, meaning that bilinear
forms $\langle\cdot,\cdot\rangle_{X}:W\times X\rightarrow\mathbb{R}$,
$\langle\cdot,\cdot\rangle_{Z}:Y\times Z\rightarrow\mathbb{R}$ are defined,
and that each vector space separates the points of the other with respect to
the corresponding bilinear form. We assume that there is no confusion between
the pairings and we will therefore denote $\langle\cdot,\cdot\rangle$ for both
bilinear functions without loss of generality. In order to deal with the most
general case possible, we will for now assume that the pairings are not
equipped with particular compatible topologies. Given a linear operator
$A:X\rightarrow Z$ however, we assume that “for every $y\in Y$ there exists a
unique $w\in W$ such that $\langle y,Ax\rangle=\langle w,x\rangle$ for every
$x\in X$”. That is, the adjoint of $A$, $A^{*}:Y\rightarrow W$ is a linear
operator and it is well defined by $\langle A^{*}y,x\rangle=\langle
y,Ax\rangle$. Here the existence of $w=A^{*}y$ means that the vector space $W$
is “large” enough to include all linear functions that send $x\in X$ to
$\langle\cdot,Ax\rangle$, while the uniqueness is satisfied by the dual pair.
The above assumption particularly holds if we equip the spaces $X,\;Z$ with
any compatible topologies with respect to their pairing, for example if $A$ is
assumed $\sigma(X,W)-\sigma(Z,Y)$ continuous with respect to the weak
topologies (the same assumption holds if we equip the spaces with their
strong-Mackey topologies $\tau$).

Let also the convex cones $C\subset X$ and $K\subset Y$. Their corresponding
positive dual cones are defined by:

$C^{*}:=\\{w\in W:\langle w,x\rangle\geq 0\;\forall x\in C\\}$ $K^{*}:=\\{z\in
Z:\langle y,z\rangle\geq 0\;\forall y\in K\\}$

Note that these are convex cones as well. The positive dual cones of
$C^{*},\;K^{*}$ can also be defined by:

$C^{**}:=\\{x\in X:\langle w,x\rangle\geq 0\;\forall w\in C^{*}\\}$
$K^{**}:=\\{y\in Y:\langle y,z\rangle\geq 0\;\forall z\in K^{*}\\}$

It is known that if $X$ is equipped with a topology $\mathcal{T}_{1}$ and $W$
equipped with a topology $\mathcal{T}_{2}$, both compatible with the duality
between $X$ and $W$, then $C^{*}$ is $\mathcal{T}_{1}$-closed and
$C^{**}=cl_{\mathcal{T}_{2}}(C)$ (see e.g. [23], Lemma 2). The same holds for
the convex cone $K$ and the dual pair $(Z,Y)$.

The primal-dual pair of conic linear problems that appears in the following is
of the form:

${(P)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}min\;\;\langle c,x\rangle\\\
s.t.\;\;Ax-b\in K^{*}\\\ \;\;\;\;\;\;\;\;x\in C\end{array}$

${(D)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}max\;\;\langle y,b\rangle\\\
s.t.\;\;-A^{*}y+c\in C^{*}\\\ \;\;\;\;\;\;\;\;\;\;\;y\in K\end{array}$

We will often refer to this particular pair as $\\{(P),(D)\\}$. The optimal
value of the primal problem $(P)$ is defined by $val(P):=inf\\{\langle
c,x\rangle:Ax-b\in K^{*}$, $x\in C\\}$ and the optimal value of the dual
problem $(D)$ is defined by $val(D):=sup\\{\langle y,b\rangle:-A^{T}y+c\in
C^{*}$, $y\in K\\}$, when of course the respective feasibility sets are non-
empty (we define $val(P):=\infty$, $val(D):=-\infty$ if the problems have no
feasible solutions). The following weak duality relation holds by the standard
minimax duality:

$val(P)\geq val(D)$ (2.1)

Indeed, let $x^{*}$ be a feasible solution of $(P)$ and $y^{*}$ be a feasible
solution of $(D)$, then:

$\langle c,x^{*}\rangle\geq\langle c,x^{*}\rangle+\langle
y^{*},Ax^{*}-b\rangle=\langle c-A^{*}y^{*},x^{*}\rangle+\langle
y^{*},b\rangle\geq\langle y^{*},b\rangle$ (2.2)

Since (2.2) holds for every feasible $x,\;y$ we obtain (2.1).

######  Definition 2.1.

We say that there is no duality gap between $(P)$ and $(D)$ or that the strong
duality condition holds iff $val(P)=val(D)$.

The $``\textit{strong duality condition}"$ does not appear in the literature
that is relevant with strong duality of conic linear problems. The only reason
for which we refer to the zero duality gap as a $``\textit{strong duality
condition}"$ is because strong duality will eventually be a crucial condition
for the proof of the minimax theorems in Section 3.

We also say that a feasible solution $x^{*}$ of $(P)$ is optimal if $\langle
c,x^{*}\rangle=val(P)$. Accordingly, we say that a feasible solution $y^{*}$
of $(D)$ is optimal if $\langle y^{*},b\rangle=val(D)$.

From (2.2) we obtain that the equality $\langle c,x^{*}\rangle=\langle
y^{*},b\rangle$ holds for some feasible $x^{*}$, $y^{*}$, and therefore there
is no duality gap between $(P)$ and $(D)$ and $x^{*},\;y^{*}$ are optimal
solutions if and only if the complementarity condition (slackness) holds:

$\langle y^{*},Ax^{*}-b\rangle=\langle c-A^{*}y^{*},x^{*}\rangle=0$ (2.3)

We now give some preliminaries regarding the theory of two-player zero-sum
games:

A two-player zero-sum game is an ordered triple
$\mathcal{G}:=(\\{I,II\\},\\{S,T\\},u)$, where $\\{I,II\\}$ is the set of
players $I$ and $II$, $S\subset X$ and $T\subset Y$ are the strategy sets of
players $I$ and $II$ respectively, and $u:S\times T\rightarrow\mathbb{R}$ is
the payoff function of player $I$ (the payoff function of player $II$ is
defined by $-u$).

When studying two-player zero-sum games, we usually concern ourselves with the
following minimax equality:

$\adjustlimits{\max}_{x\in S}{\min}_{y\in T}u(x,y)=\min_{y\in T}\max_{x\in
S}u(x,y)$ (2.4)

In the cases where this equality holds, we then search for a Nash equilibrium,
that is we search for (optimal strategies) $x^{*}\in S$ and $y^{*}\in T$ such
that $u(x^{*},y^{*})=\adjustlimits{\max}_{x\in S}{\min}_{y\in
T}u(x,y)=\adjustlimits{\min}_{y\in T}{\max}_{x\in S}u(x,y)$.

When working however in games where the spaces are infinite-dimensional, the
payoff function is not always continuous and the strategy spaces are not
compact, then the existence of Nash equilibrium is not guaranteed. In fact
even (2.4) may not be guaranteed since the maximum or minimun value of
$u(x,y)$ (and of $\inf\limits_{y\in T}u(x,y)$, $\sup\limits_{x\in S}u(x,y)$)
may not be acquired for some points $x\in S$ and $y\in T$.

We will therefore concern ourselves with the following “generalized” minimax
equality:

$\adjustlimits{\sup}_{x\in S}{\inf}_{y\in T}u(x,y)=\adjustlimits{\inf}_{y\in
T}{\sup}_{x\in S}u(x,y)$ (2.5)

as well as with the search of (approximate) Nash equilibrium.

We define the “security levels” of players $I$ and $II$ respectively by:

$\underline{v}:=\adjustlimits{\sup}_{x\in S}{\inf}_{y\in
T}u(x,y)\;\;\mbox{and\;\;}\overline{v}:=\adjustlimits{\inf}_{y\in
T}{\sup}_{x\in S}u(x,y)$

It is easy to see that the following minimax relation always holds:

$\underline{v}\leq\overline{v}$ (2.6)

We denote the value of the game by $v$. It is readily obtained by (2.5) that
for the value of a two-player zero-sum game we have

$\underline{v}=v=\overline{v}$ (2.7)

Moreover, we define by $\mathcal{B}^{I}:=\\{x^{*}\in
S:\underline{v}=\adjustlimits{\inf}_{y\in T}{u}({x}^{*},y)\\}$ and
$\mathcal{B}^{II}:=\\{y^{*}\in T:\overline{v}=\sup\limits_{x\in
S}u(x,y^{*})\\}$ the sets of optimal strategies for players $I$ and $II$
respectively when (2.7) holds. A pair of optimal strategies $(x^{*},y^{*})$
represents a Nash equilibrium and $v=u(x^{*},y^{*})$, when (2.7) holds.
Indeed, we have

$\underline{v}=\inf\limits_{y\in T}u(x^{*},y)\leq
u(x^{*},y^{*})\leq\sup\limits_{x\in
S}u(x,y^{*})=\overline{v}\Rightarrow\underline{v}=u(x^{*},y^{*})=\overline{v}$

A mathematical relation that will turn out to be important in Section 5 is
that of the “strategical equivalence” between two games. Specifically, we say
that a two-player zero-sum game $\mathcal{G}:=(\\{I,II\\},\\{S,T\\},u)$ and a
two-player zero-sum game
$\mathcal{G}^{\prime}:=(\\{I,II\\},\\{S^{\prime},T^{\prime}\\},u^{\prime})$
are strategically equivalent iff they have the exact same sets of Nash
equilibria.

We now define cone-leveled sets, a notion important for our analysis and the
proof of the main results. As already mentioned in the beginning of this
section, we use the same topological framework over which the primal-dual pair
$\\{(P),(D)\\}$ was defined in the above.

######  Definition 2.2.

A set $S\subset X$ is said to be cone-leveled if there exist a convex cone
$C\subset X$, $\alpha\in X\setminus\\{0_{X}\\}$ and a non-zero
$\lambda\in\mathbb{R}$ such that

$S=\\{x\in C:\langle\alpha,x\rangle=\lambda\\}=C\cap\\{x\in
X:\langle\alpha,x\rangle=\lambda\\}$

Respectively, a set $T\subset Y$ is said to be cone-leveled if there exist a
convex cone $K\subset Y$, $\beta\in Y\setminus\\{0_{Y}\\}$ and a non-zero
$\mu\in\mathbb{R}$ such that

$T=\\{y\in K:\langle y,\beta\rangle=\mu\\}=K\cap\\{y\in Y:\langle
y,\beta\rangle=\mu\\}$

Note that due to the linearity of the bilinear forms
$\langle\cdot,\cdot\rangle$, $\lambda$ and $\mu$ may be assumed strictly
positive real numbers. In fact we may take $\lambda=\mu=1$ without any loss of
generality.

##  3 Minimax Theorems and Existence of Nash equilibria

In this Section we prove the key minimax theorems of this paper. The proof of
each theorem follows the structure that appears in the proof of the minimax
theorem that we gave in [13] for complex games.

Before we state and prove the main results, we firstly describe the class of
two-player zero-sum games treated. In all the subsequent, the games have the
following form:

(F1): The strategy sets $S\subset X$, $T\subset Y$ are cone-leveled, that is
$S=\\{x\in C:\langle\alpha,x\rangle=\lambda\\}$ and $T=\\{y\in K:\langle
y,\beta\rangle=\mu\\}$ for some convex cones $C\subset X$, $K\subset Y$,
$\alpha\in X\setminus\\{0_{X}\\}$, $\beta\in Y\setminus\\{0_{Y}\\}$ and
$\lambda,\;\mu\in\mathbb{R}\setminus\\{0\\}$.

(F2): The payoff function is given by $u(x,y)=\langle y,Ax\rangle=\langle
A^{*}y,x\rangle$, for every $x\in S$, $y\in T$.

We write once again the following primal-dual pair of conic linear problems:

${(P)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}min\;\;\langle c,x\rangle\\\
s.t.\;\;Ax-b\in K^{*}\\\ \;\;\;\;\;\;\;\;x\in C\end{array}$
${(D)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}max\;\;\langle y,b\rangle\\\
s.t.\;\;-A^{*}y+c\in C^{*}\\\ \;\;\;\;\;\;\;\;\;\;\;y\in K\end{array}$

We now state the first main minimax theorem of this paper:

######  Theorem 3.1.

Let a two-player zero-sum game defined by (F1)-(F2) and assume that
$\underline{v}>0$. If the strong duality condition holds for $b:=\beta/\mu$,
$c:=\alpha/\lambda$, then $\underline{v}=\overline{v}$, and for the value $v$
of the game the equality $\frac{1}{val(P)}=v=\frac{1}{val(D)}$ holds.
Moreover, if $x^{*}$ is an optimal solution of $(P)$, then
$\tilde{x}:=x^{*}\cdot v$ is an optimal strategy for player $I$, and similarly
if $y^{*}$ is an optimal solution of $(D)$, then $\tilde{y}:=y^{*}\cdot v$ is
an optimal strategy for player $II$, and $(\tilde{x},\tilde{y})$ is a Nash
equilibrium.

###### Proof.

Let the optimization problem:

${(P1)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}\max\limits_{\xi,x}\;\;\xi\\\
s.t.\;\;Ax-\xi\frac{\beta}{\mu}\in T^{*}\\\ \;\;\;\;\;\;\;\;x\in S\\\
\;\;\;\;\;\;\;\;\xi\geq 0\end{array}$

This can equivalently be written as:

${(P2)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}\max\limits_{\xi,x}\;\;\xi\\\
s.t.\;\;\langle y,Ax\rangle\geq\xi\langle y,\frac{\beta}{\mu}\rangle\;\forall
y\in T\\\ \;\;\;\;\;\;\;\;x\in S\\\ \;\;\;\;\;\;\;\;\xi\geq 0\end{array}$

Here, we are aiming to maximize $\xi\geq 0$ for some $x\in S$ (if such $x$
exists) such that $\langle y,Ax\rangle\geq\xi\langle
y,\frac{\beta}{\mu}\rangle\;\forall y\in T$. However, since the latter
inequality will hold for every $y\in T=\\{y\in K:\langle
y,\beta\rangle=\mu\\}$, we equivalently have to search for $\xi\geq 0$ for
some $x\in S$ (if such $x$ exists) such that $\langle y,Ax\rangle\geq\xi$ for
every $y\in T$. We therefore know for the optimal value of the problem that it
satisfies:

$val(P1)=val(P2)=\sup\xi\leq\inf\limits_{y\in T}\langle y,Ax\rangle,\;\;x\in
S$

Hence if $\xi^{*}:=\sup\xi$ is the optimal value of $(P1)$ we have
$\xi^{*}\leq\adjustlimits{\sup}_{x\in S}{\inf}_{y\in T}\langle
y,Ax\rangle=\underline{v}$. In fact, by definition ($\underline{v}$ belongs to
the set of feasible solutions) the equality $\xi^{*}=\underline{v}$ holds.
Also, if $(P2)$ has an optimal solution $\hat{x}\in S$, then
$\xi^{*}=\adjustlimits{\max}_{x\in S}{\inf}_{y\in T}\langle
y,Ax\rangle=\inf\limits_{y\in T}\langle y,A\hat{x}\rangle$, which means that
$\hat{x}$ is an optimal strategy for player $I$.

By hypothesis we can assume that $\xi^{*}>0$. Now $(P2)$ is equivalent to the
optimization problem:

${(P3)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}\max\limits_{\xi,x}\;\;\xi\\\
s.t.\;\;\langle y,Ax\rangle\geq\xi\langle y,\frac{\beta}{\mu}\rangle\;\forall
y\in T\\\ \;\;\;\;\;\;\;\;x\in C\\\
\;\;\;\;\;\;\;\langle\alpha,x\rangle=\lambda\\\
\;\;\;\;\;\;\;\;\xi>0\end{array}$

where we write the constraint $x\in S$ in its equivalent form induced by the
fact that $S$ is cone-leveled. Now, since the objective function $\xi$ is
strictly positive and $C$ is a cone, $(P3)$ is equivalent to the optimization
problem:

${(P4)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}\max\limits_{\xi,x}\;\;\xi\\\
s.t.\;\;\langle y,A\frac{x}{\xi}\rangle\geq\langle
y,\frac{\beta}{\mu}\rangle\;\forall y\in T\\\ \;\;\;\;\;\;\;\;\frac{x}{\xi}\in
C\\\
\;\;\;\;\;\;\;\langle\frac{\alpha}{\lambda},\frac{x}{\xi}\rangle=\frac{1}{\xi}\\\
\;\;\;\;\;\;\;\;\xi>0\end{array}$

For $x^{\prime}:=x/\xi$ we turn $(P4)$ into a minimization problem, which
almost takes the form of a conic linear problem:

${(P5)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}\min\limits_{x^{\prime}}\;\;\langle\frac{\alpha}{\lambda},x^{\prime}\rangle\\\
s.t.\;\;Ax^{\prime}-\frac{\beta}{\mu}\in T^{*}\\\
\;\;\;\;\;\;\;\;x^{\prime}\in C\end{array}$

Note that due to $val(P1)=val(P2)=val(P3)=val(P4)=\underline{v}$ we have
$val(P5)=\displaystyle\frac{1}{\underline{v}}>0$. However, $K^{*}\subset
T^{*}$ since $T\subset K$. Therefore, for the conic linear problem $(P)$ as
defined prior to the formulation of the theorem, where
$b:=\displaystyle\frac{\beta}{\mu}$ and
$c:=\displaystyle\frac{\alpha}{\lambda}$ we have:

$val(P)\geq val(P5)=\displaystyle\frac{1}{\underline{v}}$ (3.1)

Consider now the following minimization problem:

${(D1)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}\min\limits_{\zeta,y}\;\;\zeta\\\
s.t.\;\;\zeta\frac{\alpha}{\lambda}-A^{*}y\in S^{*}\\\ \;\;\;\;\;\;\;\;y\in
T\\\ \;\;\;\;\;\;\;\;\zeta\geq 0\end{array}$

This can equivalently be written as:

${(D2)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}\min\limits_{\zeta,y}\;\;\zeta\\\
s.t.\;\;\langle
A^{*}y,x\rangle\leq\zeta\langle\frac{\alpha}{\lambda},x\rangle\;\forall x\in
S\\\ \;\;\;\;\;\;\;\;y\in T\\\ \;\;\;\;\;\;\;\;\zeta\geq 0\end{array}$

Similarly to the previous, here we are aiming to minimize $\zeta\geq 0$ for
some $y\in T$ such that $\langle
A^{*}y,x\rangle\leq\zeta\langle\frac{\alpha}{\lambda},x\rangle\;\forall x\in
S$. However, since the latter inequality will hold for every $x\in S=\\{x\in
C:\langle\alpha,x\rangle=\lambda\\}$, we equivalently search for $\zeta\geq 0$
for some $y\in T$ such that $\langle A^{*}y,x\rangle\leq\zeta$ $\forall x\in
S$. We therefore have:

$val(D1)=val(D2)=\inf\zeta\geq\sup\limits_{x\in S}\langle
A^{*}y,x\rangle,\;\;y\in T$

Hence if $\zeta^{*}:=\inf\zeta$ is the optimal value of $(D1)$ we acquire the
relation $\zeta^{*}\geq\adjustlimits{\inf}_{y\in T}{\sup}_{x\in S}\langle
A^{*}y,x\rangle=\overline{v}$. In fact, by definition ($\overline{v}$ belongs
to the set of feasible solutions) the equality $\zeta^{*}=\overline{v}$ holds.
Also, if $(D2)$ has an optimal solution $\hat{y}\in T$, then
$\zeta^{*}=\adjustlimits{\min}_{y\in T}{\sup}_{x\in S}\langle
y,Ax\rangle=\sup\limits_{x\in S}\langle\hat{y},Ax\rangle$, which means that
$\hat{y}$ is an optimal strategy for player $II$.

Due to the hypothesis and (2.6) we can assume that $\zeta^{*}>0$. Now $(D2)$
is equivalent to the optimization problem:

${(D3)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}\min\limits_{\zeta,y}\;\;\zeta\\\
s.t.\;\;\langle
A^{*}y,x\rangle\leq\zeta\langle\frac{\alpha}{\lambda},x\rangle\;\forall x\in
S\\\ \;\;\;\;\;\;\;\;y\in K\\\ \;\;\;\;\;\;\;\langle y,\beta\rangle=\mu\\\
\;\;\;\;\;\;\;\;\zeta>0\end{array}$

where we write the constraint $y\in T$ in its equivalent form induced by the
fact that $T$ is cone-leveled. Now, since the objective function $\zeta>0$ and
$K$ is a cone, $(D3)$ is equivalent to:

${(D4)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}\min\limits_{\zeta,y}\;\;\zeta\\\
s.t.\;\;\langle
A^{*}\frac{y}{\zeta},x\rangle\leq\langle\frac{\alpha}{\lambda},x\rangle\;\forall
x\in S\\\ \;\;\;\;\;\;\;\;\frac{y}{\zeta}\in K\\\
\;\;\;\;\;\;\;\langle\frac{y}{\zeta},\frac{\beta}{\mu}\rangle=\frac{1}{\zeta}\\\
\;\;\;\;\;\;\;\;\zeta>0\end{array}$

For $y^{\prime}:=y/\zeta$ we turn $(D4)$ into a maximization problem, which
almost takes the form of a conic linear problem:

${(D5)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}\max\limits_{y^{\prime}}\;\;\langle
y^{\prime},\frac{\beta}{\mu}\rangle\\\
s.t.\;\;\frac{\alpha}{\lambda}-A^{*}y^{\prime}\in S^{*}\\\
\;\;\;\;\;\;\;\;y^{\prime}\in K\end{array}$

Note that due to $val(D1)=val(D2)=val(D3)=val(D4)=\overline{v}$ we have
$val(D5)=\displaystyle\frac{1}{\overline{v}}$. However, $C^{*}\subset S^{*}$
since $S\subset C$. Therefore, if we consider the conic linear problem $(D)$
as defined prior to the formulation of the theorem, where
$b:=\displaystyle\frac{\beta}{\mu}$ and
$c:=\displaystyle\frac{\alpha}{\lambda}$ we have:

$val(D)\leq val(D5)=\displaystyle\frac{1}{\overline{v}}$ (3.2)

The strong duality condition holds by hypothesis, that is $val(P)=val(D)$. By
(3.1) and (3.2) it follows that $\underline{v}\geq\overline{v}$. By (2.6) we
finally acquire $\underline{v}=\overline{v}$.

The above relations between $(P),\;(P1)-(P5)$ and $(D),\;(D1)-(D5)$ directly
reveal the methodology for calculating both the value of the game and the
optimal strategies of players $I$ and $II$, if such strategies exist:

Obviously
$\underline{v}=\displaystyle\frac{1}{val(P)}=v=\frac{1}{val(D)}=\overline{v}$.
The value of the game can be readily calculated by the common optimal value of
the primal-dual pair $\\{(P),(D)\\}$.

Now the existence of optimal strategies for players $I$ and $II$ eventually
comes down to the existence of optimal solutions for $(P)$ and $(D)$
respectively: Let $x^{*}\in C$ be an optimal solution for $(P)$. Then $x^{*}$
is also an optimal solution for $(P5)$ and
$v=\displaystyle\frac{1}{val(P5)}=\xi^{*}=\frac{1}{\langle\frac{\alpha}{\lambda},x^{*}\rangle}$.
Define $\tilde{x}:=x^{*}\cdot v$. Then $\tilde{x}$ is an optimal solution for
$(P4)$. Indeed, since $v>0$ we have $\tilde{x}/v=x^{*}\in C$ and
$\langle\frac{\alpha}{\lambda},\tilde{x}\rangle=1$ by the above equation, that
is $\tilde{x}\in S$. Also, the inequality $\langle
y,A\frac{\tilde{x}}{v}\rangle=\langle y,Ax^{*}\rangle\geq\langle
y,\frac{\beta}{\mu}\rangle$ holds for every $y\in T$ since $x^{*}$ is an
optimal solution for $(P5)$. Therefore $\tilde{x}=x^{*}\cdot v$ is an optimal
solution for $(P4)$. Since $\tilde{x}$ is also an optimal solution for $(P2)$
we have $\langle y,A\tilde{x}\rangle\geq v$ for every $y\in T$ $\Rightarrow$
$\inf\limits_{y\in T}\langle y,A\tilde{x}\rangle\geq\adjustlimits{\sup}_{x\in
S}{\inf}_{y\in T}\langle y,Ax\rangle$, and therefore only the equality holds.
In fact $\adjustlimits{\sup}_{x\in S}{\inf}_{y\in T}\langle
y,Ax\rangle=\adjustlimits{\max}_{x\in S}{\inf}_{y\in T}\langle
y,Ax\rangle=\inf\limits_{y\in T}\langle y,A\tilde{x}\rangle$. That means
$\tilde{x}\in\mathcal{B}^{I}$, that is $\tilde{x}=x^{*}\cdot v$ is an optimal
strategy for player $I$.

Similarly, if $y^{*}$ is an optimal solution of $(D)$, then
$\tilde{y}:=y^{*}\cdot v$ is an optimal strategy for player $II$. It directly
follows that if $\tilde{x}$, $\tilde{y}$ are optimal strategies, then
$(\tilde{x},\tilde{y})$ is a Nash equilibrium.

∎

We have the following important remarks:

(i) As seen by the proof, the sets $C,\;K$ do not need to be convex and the
objective functions need not be bilinear. Therefore, one could define cone-
leveled sets by non-convex cones. However, the convexity of the cones $C,\;K$
as well as the biliearity of the forms $\langle\cdot,\cdot\rangle$ are
necessary for strong duality to hold, as seen by the known results regarding
duality theory in conic linear programming (see Section 4).

(ii) The strong duality condition is sufficient but not necessary for the
equality $\underline{v}=\overline{v}$ to hold. Indeed, suppose that a non-zero
duality gap between $(P)$ and $(D)$ exists. Then $val(P)>val(D)$,
$val(P)\geq\displaystyle\frac{1}{\underline{v}}$ and
$val(D)\leq\displaystyle\frac{1}{\overline{v}}$, and therefore no conclusion
regarding the gap between the security levels of the players can be obtained.
However if we a priori know that $\underline{v}=\overline{v}$, a duality gap
between $(P)$ and $(D)$ may still exist:
$\frac{1}{val(P)}\leq\underline{v}=\overline{v}\leq\frac{1}{val(D)}\Rightarrow
val(P)\geq val(D)$, which is already known by (2.1). Therefore, in the case
where the strong duality condition does not hold between $(P)$ and $(D)$ but
the equation $\underline{v}=\overline{v}$ does hold, we simply have to solve
any of $(P1)-(P4)$ with any of $(D1)-(D4)$ or $(P5)$ with $(D5)$, in order to
obtain the value of the game and possible optimal solutions. Of course, if
such optimal solutions cannot be calculated (exactly), which is very common in
many MP classes (see [18]), we then search for approximate optimal solutions,
that is we search for approximate Nash equilibria.

In the formulation of Theorem 3.1 we assumed that $\underline{v}>0$. However,
this is not always the case. In fact we may have $\overline{v}<0$. The
following theorem can be characterized as partially complementary to Theorem
3.1:

######  Theorem 3.2.

Let a two-player zero-sum game defined by (F1)-(F2) and assume that
$\overline{v}<0$. If the strong duality condition holds for $b:=-\beta/\mu$,
$c:=-\alpha/\lambda$, then $\underline{v}=\overline{v}$, and for the value $v$
of the game the equality $\frac{1}{val(P)}=v=\frac{1}{val(D)}$ holds.
Moreover, if $x^{*}$ is an optimal solution of $(P)$, then
$\tilde{x}:=x^{*}\cdot v$ is an optimal strategy for player $I$, and similarly
if $y^{*}$ is an optimal solution of $(D)$, then $\tilde{y}:=y^{*}\cdot v$ is
an optimal strategy for player $II$, and $(\tilde{x},\tilde{y})$ is a Nash
equilibrium.

The structure of the proof of this theorem is completely analogous to the one
of Theorem 3.1, except from the fact that the “starting” optimization problems
considered are:

${(P1)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}\max\limits_{\xi,x}\;\;-\xi\\\
s.t.\;\;Ax+\xi\frac{\beta}{\mu}\in T^{*}\\\ \;\;\;\;\;\;\;\;x\in S\\\
\;\;\;\;\;\;\;\;\xi\geq 0\end{array}$

${(D1)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}\min\limits_{\zeta,y}\;\;-\zeta\\\
s.t.\;\;-\zeta\frac{\alpha}{\lambda}-A^{*}y\in S^{*}\\\ \;\;\;\;\;\;\;\;y\in
T\\\ \;\;\;\;\;\;\;\;\zeta\geq 0\end{array}$

The proof is omitted in order to avoid superfluous repeated methods and
contiguous results (we leave the details to the reader).

As mentioned above, Theorem 3.2 can only be considered as partially
complementary to Theorem 3.1, simply because the case
$0\in[\underline{v},\overline{v}]$ is not covered (note that if
$0\in(\underline{v},\overline{v})$ then the equation
$\underline{v}=\overline{v}$ is not possible). In order to include this
“unsavory” case, which essentially implies $\underline{v}=\overline{v}=0$, and
propose a more general minimax result that includes the previous two, we shall
need the following assumptions:

(A1): There exist a linear mapping $E:X\rightarrow Z$ and its adjoint
$E^{*}:Y\rightarrow W$, both well defined, such that $\langle
y,Ex\rangle=\langle E^{*}y,x\rangle=e$ $\;\forall y\in T$ $\;\forall x\in S$
for some non-zero $e\in\mathbb{R}$.

(A2): The functions $\langle y,Ax\rangle$, $\inf\limits_{y\in T}\langle
y,Ax\rangle$, $\sup\limits_{x\in S}\langle y,Ax\rangle$ are finite for every
$x\in S$, $y\in T$.

######  Theorem 3.3.

Let a two-player zero-sum game defined by (F1)-(F2) and assume that (A1)-(A2)
hold. Also let at least one of the following hold:

(i) the strong duality condition holds for $b:=\beta/\mu$,
$c:=\alpha/\lambda$;

(ii) the strong duality condition holds for $b:=-\beta/\mu$,
$c:=-\alpha/\lambda$.

Then $\underline{v}=\overline{v}$, and for the value $v$ of the game the
equality $\frac{1}{val(P^{\prime})}\mp\kappa
e=v=\frac{1}{val(D^{\prime})}\mp\kappa e$ holds for some $\kappa\in\mathbb{R}$
and a primal-dual pair $\\{(P^{\prime}),(D^{\prime})\\}$ of conic linear
problems, which is defined exactly like the pair $\\{(P),(D)\\}$ but $A$ is
replaced by $A\pm\kappa E$. Moreover, if $x^{*}$ is an optimal solution of
$(P^{\prime})$, then $\tilde{x}:=x^{*}\cdot v$ is an optimal strategy for
player $I$, and similarly if $y^{*}$ is an optimal solution of $(D^{\prime})$,
then $\tilde{y}:=y^{*}\cdot v$ is an optimal strategy for player $II$, and
$(\tilde{x},\tilde{y})$ is a Nash equilibrium.

###### Proof.

Assume that (i) holds (the proof in the case where (ii) holds is similar, and
Theorem 3.2 is used). We explore two different cases:

(a) Suppose that the real number $e$ of (A1) is positive. We may assume that
$\underline{v}<0$ (if $\underline{v}>0$ then we have nothing to prove by
Theorem 3.1; the theorem holds for $\kappa=0$). We then consider a two-player
zero-sum game, say $\mathcal{G^{\prime}}$, defined by (F1) and the payoff
function $u^{\prime}(x,y):=\langle y,(A+\kappa E)x\rangle=\langle(A^{*}+\kappa
E^{*})y,x\rangle$, for every $x\in S$ and $y\in T$, for some $\kappa>0$. Due
to (A1) we equivalently have $u^{\prime}(x,y)=u(x,y)+e\kappa$. In addition, by
(A2) for $\underline{v}^{\prime}:=\adjustlimits{\sup}_{x\in S}{\inf}_{y\in
T}u^{\prime}(x,y)$ and $\overline{v}^{\prime}:=\adjustlimits{\inf}_{y\in
T}{\sup}_{x\in S}u^{\prime}(x,y)$ we obtain:

$\underline{v}^{\prime}=\underline{v}+e\kappa,\;\mbox{and\;}\overline{v}^{\prime}=\overline{v}+e\kappa$
(3.3)

Without loss of generality we may assume that $\kappa$ is such that
$\underline{v}^{\prime}>0$. Since $\mathcal{G^{\prime}}$ is defined by
$u^{\prime}(x,y)$ and $(F1)$ has the same strategy sets as the former, by
Theorem 3.1 we obtain $\underline{v}^{\prime}=\overline{v}^{\prime}$,
therefore $\underline{v}=\overline{v}$ by (3.3). Denote $v^{\prime}$ the value
of $\mathcal{G^{\prime}}$. Then
$\frac{1}{val(P^{\prime})}=v^{\prime}=\frac{1}{val(D^{\prime})}$, therefore
$\frac{1}{val(P^{\prime})}-e\kappa=v=\frac{1}{val(D^{\prime})}-e\kappa$.

Now let $x^{*}$ be an optimal solution of $(P^{\prime})$. By Theorem 3.1
$\tilde{x}:=x^{*}v^{\prime}$ is an optimal strategy for player $I$ of
$\mathcal{G^{\prime}}$. That is,

$v^{\prime}=\inf\limits_{y\in T}\langle y,(A+\kappa
E)\tilde{x}\rangle\Rightarrow v+e\kappa=\inf\limits_{y\in T}\langle
y,A\tilde{x}\rangle+e\kappa\Rightarrow v=\inf\limits_{y\in T}\langle
y,A\tilde{x}\rangle$

Hence $\tilde{x}$ is also an optimal strategy for player $I$ in the game
defined by (F1), (F2). Same goes for an optimal solution $y^{*}$ of
$(D^{\prime})$.

(b) Suppose that the real number $e$ of (A1) is negative. Then we do exactly
the same as in (a), but we instead define a two-player zero-sum game
$\mathcal{G^{\prime\prime}}$ for suitable $\kappa<0$ such that
$\underline{v}^{\prime\prime}>0$. ∎

Note that (A1) particularly holds if we find a linear operator $E:X\rightarrow
Z$ such that $Ex=e\beta/\mu$ and $E^{*}y=e\alpha/\lambda$ for every $x\in S$,
$y\in T$, for some non-zero $e\in\mathbb{R}$.

##  4 The strong duality condition

An interesting question directly rises by the formulation of the above
theorems: When does the strong duality condition hold? That is, we would like
to know under which conditions there exists a zero duality gap between $(P)$
and $(D)$, so that the relation $\underline{v}=\overline{v}$ can be
guaranteed. Assuming that strong duality does indeed hold for $(P)$ and $(D)$,
we would also like to know when do optimal solutions of $(P)$ and $(D)$ exist
respectively, so that the existence of either exact or approximate Nash
equilibria can also be guaranteed.

When the pair of conic linear problems $\\{(P),(D)\\}$ takes a known special
form, for example LP, SDP, SIP, CLP, GCAP etc., then the answers to these
questions are already known and the literature is enriched with certain
conditions under which strong duality as well as the existence of optimal
solutions hold. The more important part about this case, however, is that
there already exist numerous efficient interior-point, simplex, first and
second order subgradient-type, discretization methods and algorithms for
either the exact or approximate calculation of the common optimal value and
the optimal strategies of the two problems. The interested reader is referred
to [4], [6], [9], [16], [20], [21], [25], [37], [42] and the references
within.

We will therefore not concern ourselves with such special cases; in the
sequent we treat the pair $\\{(P),(D)\\}$ in its original generic form, in the
topological framework under which it was defined in Section 2. We will also
only deal with the infinite-dimensional case, since duality theory in finite-
dimensional spaces has been extensively studied and many simple CQ-related
(e.g. Slater’s CQ) results can be found in any textbook of mathematical
programming (see e.g. [16]). Duality results regarding conic linear problems
have been given in Shapiro [36], Anderson [3], Anderson and Nash [5],
Kretschmer [23] and Khanh et al. [22]. We use here the known theory alongside
with Theorem 3.1 in order to efficiently replace the strong duality condition
and prove the existence of optimal strategies.

We begin with results from the work done by Shapiro [36], as the topological
framework and conic linear programming setup of this paper resemble the one
that appears in the latter. We first need to make the following assumptions:

(A3): The spaces $Z,\;Y$ are paired locally convex topological vector spaces.
(A4): $K=K^{**}$

Assumption (A4) is not actually necessary. Due to the fact that the primal-
dual pair $\\{(P),(D)\\}$ is not in agreement with the one that appears in
[36], many minor changes need to be made in the analysis that appears in the
latter in order to show that the results of [36] also hold for the pair
$\\{(P),(D)\\}$. In order to avoid presenting such changes in detail (this is
not the purpose of this section after all), we simply assume that $K=K^{**}$.

Let the optimal function of $(P)$
$v(z):=inf\\{\langle\frac{\alpha}{\lambda},x\rangle:x\in C,\;Ax-z\in K^{*}\\}$
and $lsc(v(z)):=\min\\{v(z),\lim\limits_{p\rightarrow z}\inf v(p)\\}$. Here
$val(P)=v(b)$. We say that $(P)$ is subconsistent if and only if
$lsc(v(z))<+\infty$. Obviously, if $(P)$ is consistent, that is if it has a
non-empty feasible set, then it is also subconsistent. We obtain the following
by Theorem 3.1 and [36, Proposition 2.3]:

######  Proposition 4.1.

Let a two-player zero-sum game defined by (F1)-(F2), and let (A3)-(A4) hold.
If $\underline{v}>0$, $(P)$ is subconsistent and $v(z)$ is lower-
semicontinuous at $z=\frac{\beta}{\mu}$, then $\underline{v}=\overline{v}$.
Moreover, $\frac{1}{val(P)}=v=\frac{1}{val(D)}$.

Lower-semicontinuity of $v(z)$ however may not be easy to verify. In addition,
the first result does not give any information regarding the existence of
optimal solutions. The second proposition of this section verifies both the
lower-semicontinuity of $v(z)$ and the existence of optimal solutions. In
particular, by Theorem 3.1 and [36, Proposition 2.4] we have:

######  Proposition 4.2.

Let a two-player zero-sum game defined by (F1)-(F2), and let (A3)-(A4) hold.
Assume that $X$ is a topological vector space, that
$\langle\frac{\alpha}{\lambda},\cdot\rangle$ is lower-semicontinuous,
$A:X\rightarrow Z$ is continuous, $C,\;K^{*}$ are closed convex cones with
respect to their corresponding topologies and that the following holds: “there
exists $r\in\mathbb{R}$ and a compact set $G\subset X$ such that for every $z$
in a neighborhood of $\frac{\beta}{\mu}$ the level set $F(z):=\\{x\in
C:\langle\frac{\alpha}{\lambda},x\rangle\leq r,\;Ax-z\in K^{*}\\}$ is a subset
of $G$ and $F(\frac{\beta}{\mu})\neq\O$”. If $\underline{v}>0$, then
$\underline{v}=\overline{v}$ and $\mathcal{B}^{I}\neq\O$. In fact,
$\frac{1}{val(P)}=v=\frac{1}{val(D)}$ and there exists an optimal strategy
$\tilde{x}$ for player $I$ such that $\tilde{x}=x^{*}\cdot v$ for some optimal
solution $x^{*}$ of $(P)$.

We say that the function $v(z)$ is subdifferentiable at $z_{0}$, iff $\lvert
v(z_{0})\rvert<+\infty$ and $\partial v(z_{0})\neq\O$, where $\partial
v(z_{0}):=\\{y\in Y:v(z)-v(z_{0})\geq\langle y,z-z_{0}\rangle,\;\forall z\in
Z\\}$. We obtain the following result from Theorem 3.1 and [36, Proposition
2.5], which gives us the set of optimal strategies for player $II$:

######  Proposition 4.3.

Let a two-player zero-sum game defined by (F1)-(F2), and let (A3)-(A4) hold.
If $\underline{v}>0$ and $v(z)$ is subdifferentiable at $z=\frac{\beta}{\mu}$,
then $\underline{v}=\overline{v}$ and $\mathcal{B}^{II}=\partial
v(\frac{\beta}{\mu})\cdot v$. In fact, $\frac{1}{val(P)}=v=\frac{1}{val(D)}$
and there exists an optimal strategy $\tilde{y}$ for player $II$ such that
$\tilde{y}=y^{*}\cdot v$ for some optimal solution $y^{*}\in\partial
v(\frac{\beta}{\mu})$ of $(D)$.

Let the convex cone $M:=\\{(z,r)\in Z\times\mathbb{R}:z=Ax-k,\;k\in
K^{*},\;r\geq\langle\frac{\alpha}{\lambda},x\rangle\;\forall x\in C\\}$. The
next four results indicate the sets of optimal strategies of players $I$ and
$II$ are non-empty under certain conditions. These are proved by Theorem 3.1
and Propositions 2.6-2.9 of [36] one–to–one respectively:

######  Proposition 4.4.

Let a two-player zero-sum game defined by (F1)-(F2), and let (A3)-(A4) hold.
Also let $val(P)$ be finite and $M$ be closed with respect to the product
topology of $Z\times\mathbb{R}$. If $\underline{v}>0$, then
$\underline{v}=\overline{v}$ and $\mathcal{B}^{I}\neq\O$. In fact,
$\frac{1}{val(P)}=v=\frac{1}{val(D)}$ and there exists an optimal strategy
$\tilde{x}$ for player $I$ such that $\tilde{x}=x^{*}\cdot v$ for some optimal
solution $x^{*}$ of $(P)$.

######  Proposition 4.5.

Let a two-player zero-sum game defined by (F1)-(F2), and let (A3)-(A4) hold.
Also assume that $v(z)$ is continuous at $\frac{\beta}{\mu}$. If
$\underline{v}>0$, then $\underline{v}=\overline{v}$ and
$\mathcal{B}^{II}\neq\O$. In fact, $\frac{1}{val(P)}=v=\frac{1}{val(D)}$ and
there exists an optimal strategy $\tilde{y}$ for player $II$ such that
$\tilde{y}=y^{*}\cdot v$ for some optimal solution $y^{*}$ of $(D)$.

For the next two propositions, the known generalized Slater’s CQ in infinite-
dimensional space is required. Similar results in a slightly more strict
topological framework and problem form can be found in [3], [5].

######  Proposition 4.6.

Let a two-player zero-sum game defined by (F1)-(F2), and let (A3)-(A4) hold.
Also let $val(P)$ be finite and int$K^{*}\neq\O$ with respect to the topology
of $Z$. If there exists $\hat{x}\in C$ such that $A\hat{x}-b\in$ int$K^{*}$
and if $\underline{v}>0$, then $\underline{v}=\overline{v}$ and
$\mathcal{B}^{II}\neq\O$. In fact, $\frac{1}{val(P)}=v=\frac{1}{val(D)}$ and
there exists an optimal strategy $\tilde{y}$ for player $II$ such that
$\tilde{y}=y^{*}\cdot v$ for some optimal solution $y^{*}$ of $(D)$.

######  Proposition 4.7.

Let a two-player zero-sum game defined by (F1)-(F2), and let (A3)-(A4) hold.
Also let $X,\;Z$ be Banach spaces, $C,\;K^{*}$ be closed,
$\langle\frac{\alpha}{\lambda},\cdot\rangle$ be continuous, $A:X\rightarrow Z$
be continuous and $intK^{*}\neq\O$, all with respect to the corresponding
topologies. If there exists $\hat{x}\in C$ such that $A\hat{x}-b\in$
int$K^{*}$ and if $\underline{v}>0$, then $\underline{v}=\overline{v}$ and
$\mathcal{B}^{II}$ is non-empty and bounded. In fact,
$\frac{1}{val(P)}=v=\frac{1}{val(D)}$ and there exists an optimal strategy
$\tilde{y}$ for player $II$ such that $\tilde{y}=y^{*}\cdot v$ for some
optimal solution $y^{*}$ of $(D)$.

We now deal with conic linear problems of the form $\\{(P),(D)\\}$, where the
vector spaces of the pairings are equipped with the corresponding weak
topologies. We also assume that the linear mapping $A:X\rightarrow Z$ is
$\sigma(X,W)-\sigma(Z,Y)$ continuous, that $K$ is $\sigma(Z,Y)$-closed and
that $C$ is $\sigma(X,W)$-closed.

The next result is derived by Theorem 3.1 and [23, Theorem 3], [3, Theorem 7],
[22, Theorem 3.1]:

######  Proposition 4.8.

Let a two-player zero-sum game defined by (F1)-(F2). Also assume that $(P)$ is
consistent, $val(P)$ is finite and the set
$H:=\\{(Ax-z,\langle\frac{\alpha}{\lambda},x\rangle+r):x\in C,\;z\in
K^{*},\;r\geq 0\\}$ is $\sigma(Z\times\mathbb{R},Y\times\mathbb{R})$-closed.
If $\underline{v}>0$, then $\underline{v}=\overline{v}$ and
$\mathcal{B}^{I}\neq\O$. In fact, $\frac{1}{val(P)}=v=\frac{1}{val(D)}$ there
exists an optimal strategy $\tilde{x}$ for player $I$ such that
$\tilde{x}=x^{*}\cdot v$ for some optimal solution $x^{*}$ of $(P)$.

The set $H:=\\{(Ax-z,\langle\frac{\alpha}{\lambda},x\rangle+r):x\in C,\;z\in
K^{*},\;r\geq 0\\}$ is $\sigma(Z\times\mathbb{R},Y\times\mathbb{R})$-closed if
“$C^{*}$ has a non-empty interior with respect to the strong (Mackey) topology
$\tau(W,X)$ and there exists $y_{0}\in K$ such that
$-A^{*}y_{0}+\frac{\alpha}{\lambda}\in$ int$C^{*}$”. Other sufficient
conditions for $H$ to be closed are given in [29].

It should be mentioned that due to the symmetry that appears in the form of
the problems $(P)$, $(D)$, all the symmetric versions (i.e. with respect to
the problem $(D)$ instead of $(P)$, and vice versa) of Propositions 4.1-4.8
can also be formulated, hence the existence of optimal strategies for both
players can be guaranteed under specific conditions. Lastly, instead of
Theorem 3.1, one can also use Theorems 3.2 and 3.3 to acquire similar useful
and more complete results (we leave the details to the reader).

##  5 Two-player zero-sum games with cone-leveled strategy sets

Here we present a number of two-player zero-sum games, most of which are
known, where the strategy sets are cone-leveled. The following examples
indicate that the main theory of this paper can be characterized as a natural
generalization of previously made connections between two-player zero-sum
games and different classes of mathematical programming problems.

Probably the most interesting of the subsequent is the last example of
polynomial games. This particular example, whose analysis first appears in
[32], indicates that in general a two-player zero-sum game with cone-leveled
strategy sets, say $\mathcal{G}$, can be strategically equivalent to a
different two-player zero-sum game with cone-leveled strategy sets, say
$\mathcal{G}^{\prime}$, and therefore the game value as well as the optimal
strategies of $\mathcal{G}$ can be in fact calculated by solving a simpler and
much easier pair of conic linear problems, those associated with
$\mathcal{G^{\prime}}$.

######  Example 5.1.

(The fundamental result due to von Neumann)
Let the standard two-player zero-sum game where $X=W=\mathbb{R}^{m}$,
$Z=Y=\mathbb{R}^{n}$, both equipped with the standard inner product $\langle
a,b\rangle=a^{T}b$. Also let $A$ represent an $m\times n$ real matrix, and the
payoff function be defined by $u(x,y):=x^{T}Ay$. The strategy sets are defined
by:

$S:=\\{x\in\mathbb{R}^{m}:x\geqq
0,\;\sum_{i=1}^{m}x_{i}=1\\}\mbox{\;\;and\;\;}T:=\\{y\in\mathbb{R}^{n}:y\geqq
0,\;\sum_{j=1}^{n}y_{j}=1\\}$

which represent the standard m and n-simplex respectively. These sets are
cone-leveled for convex cones $C:=\\{x\in\mathbb{R}^{m}:x_{i}\geq
0,\;i=1,2,...,m\\}$, $K:=\\{y\in\mathbb{R}^{n}:y_{j}\geq 0,\;j=1,2,...,n\\}$,
with $\alpha:=e^{m}=(1,1,...,1)\in\mathbb{R}^{m}$,
$\beta:=e^{n}=(1,1,...,1)\in\mathbb{R}^{n}$ and $\lambda=\mu=1$.

######  Example 5.2.

(Complex games)
Let a two-player zero-sum complex game, where $X=W=\mathbb{C}^{m}$,
$Z=Y=\mathbb{C}^{n}$, both equipped with the bilinear function $\langle
a,b\rangle:=Re(a\cdot b)=Re(\sum_{k=1}^{l}\bar{a_{k}}b_{k})$. Also let $C$
represent an $m\times n$ complex matrix, and the payoff function be defined by
$u(x,y):=Re(x^{*}Cy)$ (we therefore let $A:=C^{*}$). The strategy sets are
defined by:

$S:=\\{x\in\mathbb{C}^{m}:0\leqq\lvert argx\rvert\leqq
p,\;\displaystyle\sum_{i=1}^{m}x_{i}=1\\}\mbox{\;\;and\;\;}T:=\\{y\in\mathbb{C}^{n}:0\leqq\lvert
argy\rvert\leqq q,\;\displaystyle\sum_{j=1}^{n}y_{j}=1\\}$

where $p_{i}\in(0,\frac{\pi}{2})$ for $i=1,2,...,m$ and
$q_{j}\in(0,\frac{\pi}{2})$ for $j=1,2,...,n$. These are cone-leveled sets for
convex cones:

$C:=\\{x\in\mathbb{C}^{m}:0\leqq\lvert argx\rvert\leqq
p,\;\displaystyle\sum_{i=1}^{m}Im(x_{i})=0\\}$
$K:=\\{y\in\mathbb{C}^{n}:0\leqq\lvert argy\rvert\leqq
q,\;\displaystyle\sum_{j=1}^{n}Im(y_{j})=0\\}$

with $\alpha:=e^{m}$, $\beta:=e^{n}$ and $\lambda=\mu=1$. Complex games of
this form have been studied by the author in [13].

######  Example 5.3.

(Mixed extension of a two-player zero-sum game)
The mixed extension of a two-player zero-sum game has rightfully turned out to
be the most studied type of game since it was quite early proven that a two-
player zero-sum game may not have a Nash equilibrium in pure strategies,
whereas in the former case a Nash equilibrium always exists under some simple
assumptions.

In this example we deal with the mixed extension ($\mathcal{G}^{\prime}$) of a
two-player zero-sum game ($\mathcal{G}$) as it is defined by the use of
probability measures. In $\mathcal{G}$ players $I$ and $II$ originally have
strategy spaces that are Hausdorff compact topological vector spaces, and the
game’s payoff function $p(x,y)$ is continuous (not necessarily bilinear). In
this case, the minimax theorem (also known as Ville’s Theorem) is derived by
strong duality for a primal-dual pair of general capacity problems (GCAP).
This connection has been shown in [4].

Let a two-player zero-sum game $\mathcal{G}$ where the strategy set of player
$I$ is a compact Hausdorff topological vector space $V$ and the strategy set
of player $II$ is a compact Hausdorff topological vector space $U$. Also let
the payoff function $p(x,y)$ be continuous in $V\times U$. Now let the mixed
extension of $\mathcal{G}$ be defined as a two-player zero-sum game
$\mathcal{G}^{\prime}$, where $W:=C(V)$, $X:=C(V)^{*}$, $Z:=C(U)$,
$Y:=C(U)^{*}$, where $C(V)$ is the space of all continuous functions over $V$,
and $C(V)^{*}$ is its continuous dual. Note that with respect to the
$\sigma^{*}$ topology, $C(V)^{*}$ is a convex Hausdorff topological vector
space. The pair $(X,W)$ is equipped with a bilinear form
$\langle\cdot,\cdot\rangle:W\times X\rightarrow\mathbb{R}$ defined by $\langle
a(x),b(x)\rangle:=\int_{V}a(x)db(x)$. Similarly, the pair $(Z,Y)$ is equipped
with a bilinear form $\langle\cdot,\cdot\rangle:Y\times
Z\rightarrow\mathbb{R}$ defined by $\langle
c(y),d(y)\rangle:=\int\limits_{V}d(y)dc(y)$.

Now let $A:X\rightarrow Z$ be defined by $A(f(x)):=\int_{V}p(x,y)df(x)$, which
is $\sigma^{*}(X,W)-\sigma^{*}(Z,Y)$-continuous since $p(x,y)$, $f(x)$ are
continuous and $V$ is compact (by Riesz’s theorem of representation). The
adjoint of $A$ is $A^{*}:Y\rightarrow Z$ defined by
$A^{*}(g(y)):=\int\limits_{U}p(x,y)dg(y)$, which is also continuous with
respect to the $\sigma^{*}$ topology.

In $\mathcal{G}^{\prime}$, the strategy set $S$ of player $I$ is the set of
all regular Borel probability measures on $V$. Note that $S$ is a compact
convex subset of $C(V)^{*}$. Similarly, the strategy set $T$ of player $II$ is
the set of all regural Borel probability measures on $U$, and it is a compact
convex subset of $C(U)^{*}$. By all the above and the Fubini theorem, the
payoff function of $\mathcal{G}^{\prime}$ is defined by:

$\langle g(y),A(f(x))\rangle=\langle
A^{*}(g(y)),f(x)\rangle=\iint\limits_{V\times U}p(x,y)df(x)dg(y)$

Now the strategy sets are cone-leveled for convex sets $C:=M(V)$, $K:=M(U)$,
where $M(V)$ is the set of all non-negative regular Borel measures on $V$ (and
similarly for $M(U)$). Since $\int\limits_{V}1df(x)=1$ for every $f(x)\in S$
we have $\alpha(x)=1$ and $\lambda=1$, and similarly $\beta(y)=1$ and $\mu=1$.

The study of the equation $\underline{v}=\overline{v}$ eventually comes down
to the study of the pair:

${(P)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}min\;\;\int\limits_{V}df(x)\\\
s.t.\;\;\iint\limits_{V\times U}p(x,y)df(x)dg(y)\geq 1\;\forall g(y)\in
M(U)\\\ \ \;\;\;\;\;\;\;\;f(x)\in M(V)\end{array}$ (5.1)
${(D)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}max\;\;\int\limits_{U}dg(y)\\\
s.t.\;\;\iint\limits_{V\times U}p(x,y)df(x)dg(y)\leq 1\;\forall f(x)\in
M(V)\\\ \;\;\;\;\;\;\;\;\;\;\;g(y)\in M(U)\end{array}$ (5.2)

or, as showed in [4] to the (GCAP) pair:

${(P^{*})\;\;\;\;\;\;\;\;}\begin{array}[]{ll}min\;\;\int\limits_{V}df(x)\\\
s.t.\;\;\iint\limits_{V}p(x,y)df(x)\geqq 1\;\forall x\in V\\\ \
\;\;\;\;\;\;\;\;f(x)\in M(V)\end{array}$
${(D^{*})\;\;\;\;\;\;\;\;}\begin{array}[]{ll}max\;\;\int\limits_{U}dg(y)\\\
s.t.\;\;\int\limits_{U}p(x,y)dg(y)\leqq 1\;\forall y\in U\\\
\;\;\;\;\;\;\;\;\;\;\;g(y)\in M(U)\\\ \\\ \end{array}$

######  Example 5.4.

(An infinite set of pure strategies)
Here we treat a two-player zero-sum game where the set of pure strategies of
one of the players is infinite. We will work with the standard mixed extension
of the game:

Without loss of generality we assume that player $I$ has an infinite set of
strategies. Let $X=\mathbb{R}^{(\mathbb{N})}$ be the generalized finite
sequence space, that is the space of all real sequences with a finite number
of non-zero terms. We let $W=\mathbb{R}^{\mathbb{N}}$ the space of all real
sequences. Spaces $X$ and $W$ are paired with the bilinear function $\langle
w,x\rangle:=\displaystyle\sum_{i=1}^{\infty}x_{i}w_{i}$ and are equipped with
their corresponding weak topologies. Let $Z=Y=\mathbb{R}^{n}$ for some
$n\in\mathbb{N}$ equipped with the standard inner product $\langle
y,z\rangle:=y^{T}z$. Here we let the payoff function be defined by a payoff
matrix $D$ with infinite rows and $n$ columns as follows (again we let
$A:=D^{T}$):

$\langle y,Ax\rangle=\langle
A^{*}y,x\rangle=\displaystyle\sum_{i=1}^{\infty}\sum_{j=1}^{n}x_{i}d_{ji}y_{j}$

Specifically, the payoff function is defined over the strategy sets $S$, $T$
as these are defined by:

$S:=\\{x\in\mathbb{R}^{(\mathbb{N})}:x_{i}\geq
0\;\mbox{for\;}i=1,2,...,\;\displaystyle\sum_{i=1}^{\infty}x_{i}=1\\}$
$T:=\\{y\in\mathbb{R}^{n}:y_{j}\geq
0\;\mbox{for\;}j=1,2,...,n,\;\displaystyle\sum_{j=1}^{n}y_{j}=1\\}$

These strategy sets are cone-leveled for convex cones
$C:=\\{x\in\mathbb{R}^{(\mathbb{N})}:x_{i}\geq 0\;\mbox{for\;}i=1,2,...\\}$,
$K:=\\{y\in\mathbb{R}^{n}:y_{j}\geq 0\;\mbox{for\;}j=1,2,...,n\\}$,
$\alpha:=(1,1,...)\in\mathbb{R}^{\mathbb{N}}$, $\beta:=(1,1,...,1)=e^{n}$ and
$\lambda=\mu=1$. The existence of Nash equilibria eventually comes down to the
solution of a primal-dual pair of semi-infinite linear programming problems.

######  Example 5.5.

(Generalized semi-definite games)
Let $X=W=\mathcal{S}^{n}$ the space of all $n\times n$ symmetric matrices over
$\mathbb{R}$, equipped with the Frobenious inner product

$\langle B,C\rangle:=Tr(BC)=B\bullet
C=\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n}b_{ij}c_{ij}$

Let $Y=Z=\mathbb{R}^{m}$ equipped with the standard inner product $\langle
y,z\rangle:=y^{T}z$. Here we let $A:\mathcal{S}^{n}\rightarrow\mathbb{R}^{m}$
be defined by $A(B):=(A_{1}\bullet B,A_{2}\bullet B,...,A_{m}\bullet
B)^{T}\in\mathbb{R}^{m}$ for some $A_{1},A_{2},...,A_{m}\in\mathcal{S}^{n}$,
that is $A$ is essentially defined by $m$ $n\times n$ symmetric matrices. The
adjoint of $A$, $A^{*}:\mathbb{R}^{m}\rightarrow\mathcal{S}^{n}$ is defined by
$A^{*}(y):=\displaystyle\sum_{j=1}^{m}y_{j}A_{j}$. Hence the payoff function
of the game is also defined by such matrices, as it is defined by:

$\langle y,A(B)\rangle=\langle
A^{*}(y),B\rangle:=\displaystyle\sum_{j=1}^{m}y_{j}A_{j}\bullet B$

The strategy set of player $II$ is $T:=\\{y\in\mathbb{R}^{m}:y_{j}\geq
0\;\mbox{for\;}j=1,2,...,m,\;\displaystyle\sum_{j=1}^{m}y_{j}=1\\}$. Instead
of player $I$ having the standard spectraplex as her strategy set, we consider
the more generalized one:

$S:=\\{B\in C:Tr(\Lambda B)=\lambda\\}$

for some convex cone $C$ (e.g. the set of all symmetric matrices $B$ that
satisfy “$\sum_{i=1}^{k}P_{i}BQ_{i}\succeq 0$ for some fixed $n\times n$
matrices $P_{i},\;Q_{i}$”), a symmetric $n\times n$ matrix $\Lambda$ and some
non-zero $\lambda\in\mathbb{R}$. Obviously $S$ and $T$ are cone-leveled and
the solution of the game comes down to the solution of a primal-dual pair of
semi-definite programming problems.

######  Example 5.6.

(A time-continuous class of infinite games)
Let $X=L_{\infty}[0,T]^{m}$ and $W=L_{1}[0,T]^{m}$ paired with their weak and
weak∗ topologies respectively. Here $L_{\infty}[0,T]$ represents the space of
all essentially bounded measurable functions on $[0,T]$, and $L_{1}[0,T]$
represents the space of all Lebesgue integrable functions on $[0,T]$. Recall
that $L_{1}[0,T]^{*}=L_{\infty}[0,T]$. The spaces $X,\;W$ are equipped with
the bilinear form $\langle w(t)),x(t)\rangle:=\int_{0}^{T}w(t)^{T}x(t)dt$.
Similarly, let $Y=L_{\infty}[0,T]^{n}$ and $Z=L_{1}[0,T]^{n}$ equipped with
the bilinear form $\langle y(t),z(t)\rangle:=\int_{0}^{T}y(t)^{T}z(t)dt$.

Let $A:X\rightarrow Z$ be defined by
$(Ax)(t):=x(t)B(t)-\int_{t}^{T}x(s)C(s,t)ds$, $t\in[0,T]$, and its adjoint
$A^{*}:Y\rightarrow W$ by $(A^{*}y)(t):=B(t)y(t)-\int_{0}^{t}C(s,t)y(s)ds$,
$t\in[0,T]$. Here $B(t)$ is an $m\times n$ matrix for $t\in[0,T]$, $C(s,t)$ is
an $m\times n$ matrix for $s,t\in[0,T]$ which is equal to zero for $s>t$. We
also assume that both are bounded Lebesgue measurable for every $s,t\in[0,T]$.

The payoff function is defined by:

$\langle
y(t),(Ax)(t)\rangle=\langle(A^{*}y)(t),x(t)\rangle=:\int_{0}^{T}x(t)B(t)y(t)dt-\int_{0}^{T}\left(\int_{t}^{T}x(s)C(s,t)ds\cdot
y(t)\right)dt$

Notice that the payoff function is well defined since the following equation
holds by the Fubini theorem:

$\int_{0}^{T}\left(\int_{t}^{T}x(s)C(s,t)ds\cdot
y(t)\right)dt=\int_{0}^{T}\left(x(t)\cdot\int_{0}^{t}C(s,t)y(s)ds\right)dt$

In this game the strategy sets are as follows:

$S:=\left\\{x(t)\in
L_{\infty}^{+}[0,T]^{m}:\int_{0}^{T}\alpha(t)^{T}x(t)dt=1\right\\}$
$T:=\left\\{y(t)\in
L_{\infty}^{+}[0,T]^{n}:\int_{0}^{T}\beta(t)^{T}y(t)dt=1\right\\}$

The space $L_{\infty}^{+}[0,T]$ represents the space of all almost everywhere
on $[0,T]$ non-negative essentially bounded Lebesgue measurable functions. In
addition, $\alpha(t)\in C^{+}[0,T]^{m}$ and $\beta(t)\in C^{+}[0,T]^{n}$,
where $C^{+}[0,T]$ is the space of all non-negative continuous functions on
$[0,T]$. These strategy sets are obviously cone-leveled for convex cones
$C:=L_{\infty}^{+}[0,T]^{m}$ and $K:=L_{\infty}^{+}[0,T]^{n}$.

The solution of the game comes down to the solution of the following primal-
dual pair of continuous linear programming problems:

${(P^{*})\;\;\;\;\;\;\;\;}\begin{array}[]{ll}min\;\;\mathop{{\int_{0}^{T}}}\alpha(t)^{T}x(t)dt\\\
s.t.\;\;x(t)B(t)\geqq\beta(t)+\mathop{{\int_{t}^{T}}}x(s)K(s,t)ds\;\;\;\;\;\;f.a.e.\;\;t\in[0,T]\\\
x(t)\geqq 0\;\;f.a.e.\;\;t\in[0,T]\\\ \\\ \end{array}$
${(D^{*})\;\;\;\;\;\;\;\;}\begin{array}[]{ll}max\;\;\mathop{{\int_{0}^{T}}}y(t)^{T}\beta(t)dt\\\
s.t.\;\;B(t)y(t)\leqq\alpha(t)+\mathop{{\int_{0}^{t}}}K(s,t)y(s)ds\;\;\;\;\;\;f.a.e.\;\;t\in[0,T]\\\
y(t)\geqq 0\;\;f.a.e.\;\;t\in[0,T]\\\ \\\ \end{array}$

where “$f.a.e.$” means “for almost every”, and the solutions $x(t),\;y(t)$
that we are looking for are bounded Lebesgue measurable.

Also, a similar two-player zero-sum game can be defined via a more complex
linear operator $A$ (see [36] for an example).

######  Example 5.7.

(Polynomial games)
As already mentioned, this example turns out to be of high significance. Here
we deal with a two-player zero-sum game with cone-leveled strategy sets that
is strategically equivalent to a polynomial game. This equivalence was first
shown by Parrilo [32].

Let $X=W=\mathbb{R}^{m+1}$ and $Y=Z=\mathbb{R}^{n+1}$ both equipped with the
standard inner product $\langle a,b\rangle:=a^{T}b$. We assume that $m,\;n$
are even positive numbers. Also let $A$ represent an $(n+1)\times(m+1)$ (real)
matrix. The payoff function of the game is defined by
$\langle\nu,A\mu\rangle:=\mu^{T}A^{T}\nu$.

We define now the linear operator
$\mathcal{H}:\mathbb{R}^{2k-1}\rightarrow\mathcal{S}^{k}$ whose image of every
vector represents the associated Hankel matrix. That is, let

$\mathcal{H}:\begin{pmatrix}a_{1}\\\ a_{2}\\\ \vdots\\\
a_{2k-1}\end{pmatrix}\mapsto\begin{pmatrix}a_{1}&a_{2}&\ldots&a_{k}\\\
a_{2}&a_{3}&\ldots&a_{k+1}\\\ \vdots&\vdots&\ddots&\vdots\\\
a_{k}&a_{k+1}&\ldots&a_{2k-1}\end{pmatrix}$

Its corresponding adjoint
$\mathcal{H}^{*}:\mathcal{S}^{k}\rightarrow\mathbb{R}^{2k-1}$ is defined by
adding all terms along each antidiagonal of a matrix:

$\mathcal{H}^{*}:\begin{pmatrix}b_{11}&b_{12}&\ldots&b_{1k}\\\
b_{12}&b_{22}&\ldots&b_{2k}\\\ \vdots&\vdots&\ddots&\vdots\\\
b_{1k}&b_{2k}&\ldots&b_{kk}\end{pmatrix}\mapsto\begin{pmatrix}b_{11}\\\
2b_{12}\\\ b_{22}+2b_{13}\\\ \vdots\\\ 2b_{k-1k}\\\ b_{kk}\end{pmatrix}$

The strategy sets of players $I$ and $II$ are defined by:

$S:=\\{\mu=(\mu_{0},\mu_{1},...,\mu_{m})\in\mathbb{R}^{m+1}:\mathcal{H}(\mu)\succeq
0,\;L_{1}^{T}\mathcal{H}(\mu)L_{1}-L_{2}^{T}\mathcal{H}(\mu)L_{2}\succeq
0,\;e_{1}^{T}\mu=1\\}$
$T:=\\{\nu=(\nu_{0},\nu_{1},...,\nu_{n})\in\mathbb{R}^{n+1}:\mathcal{H}(\nu)\succeq
0,\;M_{1}^{T}\mathcal{H}(\nu)M_{1}-M_{2}^{T}\mathcal{H}(\nu)M_{2}\succeq
0,\;e_{1}^{T}\nu=1\\}$

Here $L_{1}:=\begin{pmatrix}I_{\frac{m}{2}\times\frac{m}{2}}\\\
0_{1\times\frac{m}{2}}\end{pmatrix}$,
$L_{2}:=\begin{pmatrix}0_{1\times\frac{m}{2}}\\\
I_{\frac{m}{2}\times\frac{m}{2}}\end{pmatrix}$,
$M_{1}:=\begin{pmatrix}I_{\frac{n}{2}\times\frac{n}{2}}\\\
0_{1\times\frac{n}{2}}\end{pmatrix}$,
$M_{2}:=\begin{pmatrix}0_{1\times\frac{n}{2}}\\\
I_{\frac{n}{2}\times\frac{n}{2}}\end{pmatrix}$, $e_{1}$ is the $m+1$ ($n+1$
resp.) vector equal to $(1,0,...,0)$.

These strategy sets are cone-leveled for convex cones

$C:=\\{\mu=(\mu_{0},\mu_{1},...,\mu_{m})\in\mathbb{R}^{m+1}:\mathcal{H}(\mu)\succeq
0,\;L_{1}^{T}\mathcal{H}(\mu)L_{1}-L_{2}^{T}\mathcal{H}(\mu)L_{2}\succeq 0\\}$
$K:=\\{\nu=(\nu_{0},\nu_{1},...,\nu_{n})\in\mathbb{R}^{n+1}:\mathcal{H}(\nu)\succeq
0,\;M_{1}^{T}\mathcal{H}(\nu)M_{1}-M_{2}^{T}\mathcal{H}(\nu)M_{2}\succeq 0\\}$

and $\alpha=e_{1}$, $\beta=e_{1}$, $\lambda=\mu=1$ (here we mean the non-
negative number $\mu$ as in Definition 2.2, not an element of $C$ or $S$).

Parillo [32] showed that this two-player zero-sum game is equivalent to the
mixed extension of a polynomial game, as its original normal form is described
by the payoff function
$P(x,y):=\displaystyle\sum_{i=0}^{m}\sum_{j=0}^{n}p_{ij}x^{i}y^{j}$, for
$x,y\in[-1,1]$ and $p_{ij}=a_{ji}$ for every $i,j$.

Therefore, in order to find a Nash equilibrium of a polynomial game in mixed
strategies, instead of trying to solve a primal-dual pair of GCAP problems
(see Example 5.3), we simply have to solve the following pair of problems:

${(P)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}min\;\;\mu_{0}\\\ s.t.\;\;P^{T}\mu-
e_{1}\in K^{*}\\\
L_{1}^{T}\mathcal{H}(\mu)L_{1}-L_{2}^{T}\mathcal{H}(\mu)L_{2}\succeq 0\\\
\;\;\;\;\;\;\;\;\mathcal{H}(\mu)\succeq 0\end{array}$
${(D)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}max\;\;\nu_{0}\\\
s.t.\;\;-P\nu+e_{1}\in C^{*}\\\
M_{1}^{T}\mathcal{H}(\nu)M_{1}-M_{2}^{T}\mathcal{H}(\nu)M_{2}\succeq 0\\\
\;\;\;\;\;\;\;\;\;\;\;\mathcal{H}(\nu)\succeq 0\end{array}$

where $P:=(p_{ij})_{i,j}$. In fact, Parillo showed that the constraint
“$-P\nu+e_{1}\in C^{*}$” can equivalently be replaced by the constraint
“$-P\nu+e_{1}=\mathcal{H}^{*}(U+L_{1}VL_{1}^{T}-L_{2}VL_{2}^{T})$, $U,V\succeq
0$”. This is obtained by the lemma:

Lemma. ([32, Lemma 2.5]) The univariate polynomial
$p(x)=\sum_{i=0}^{2k}p_{i}x^{i}$ is non-negative in [-1,1] if and only if
there exist $U\in\mathcal{S}^{k+1}$, $U\succeq 0$ and $V\in\mathcal{S}^{k}$,
$V\succeq 0$ such that
$\mathcal{H}^{*}(U+L_{1}VL_{1}^{T}-L_{2}VL_{2}^{T})=(p_{0},p_{1},...,p_{2k})^{T}$.

Therefore, instead of $\\{(P),(D)\\}$ it suffices to solve the pair of SDP
problems:

${(P^{\prime})\;\;\;\;\;\;\;\;}\begin{array}[]{ll}min\;\;\mu_{0}\\\
s.t.\;\;P^{T}\mu-e_{1}=\mathcal{H}^{*}(R+M_{1}QM_{1}^{T}-M_{2}QM_{2}^{T})\\\
L_{1}^{T}\mathcal{H}(\mu)L_{1}-L_{2}^{T}\mathcal{H}(\mu)L_{2}\succeq 0\\\
\;\;\;\;\;\;\;\;\mathcal{H}(\mu)\succeq 0\\\ \;\;\;\;\;\;\;\;R,Q\succeq
0\end{array}$
${(D^{\prime})\;\;\;\;\;\;\;\;}\begin{array}[]{ll}max\;\;\nu_{0}\\\
s.t.\;\;-P\nu+e_{1}=\mathcal{H}^{*}(U+L_{1}VL_{1}^{T}-L_{2}VL_{2}^{T})\\\
M_{1}^{T}\mathcal{H}(\nu)M_{1}-M_{2}^{T}\mathcal{H}(\nu)M_{2}\succeq 0\\\
\;\;\;\;\;\;\;\;\;\;\;\mathcal{H}(\nu)\succeq 0\\\
\;\;\;\;\;\;\;\;\;\;\;U,V\succeq 0\end{array}$

for
$U\in\mathcal{S}^{\frac{n}{2}+1},\;V\in\mathcal{S}^{\frac{n}{2}},\;R\in\mathcal{S}^{\frac{m}{2}+1},\;Q\in\mathcal{S}^{\frac{m}{2}}$.

It should be noted that in many of the above examples, in the cases where the
payoff function involved a matrix, say $B$, we used the relation $A=B^{T}$ in
order to bring the known two-player zero-sum game to the form that appears in
the analysis of this paper. This should not invoke any questions; it derives
from the fact that the payoff function is defined by $\langle y,Ax\rangle$
instead of $\langle x,Ay\rangle$. This “obscure” situation can readily be
reversed by defining the payoff function by the latter form and working with
the mirrored pairs of spaces $W,X$ and $Y,Z$. In this paper we chose not to
work with such “convenient” definition of payoff function, simply because many
changes would be needed in Section 4, most of which would turn out to be
annoying to the reader who is already familiar with the duality results
presented there.

##  6 A criterion for a set to be cone-leveled

As seen by the examples in the previous section, the sets of mixed strategies
are already cone-leveled by definition. However, there are cases where a
strategy set does not necessarily have a standard “mixed” form (see Examples
5.5-5.7). We may in fact deal with games where the exact form of a (compact)
set of (pure) strategies is not known. Since the question “when is a strategy
set cone-leveled?” logically derives from the aforementioned and the purposes
of this paper, we present here a simple criterion.

######  Theorem 6.1.

Let the dual pair of topological vector spaces $(X,X^{*})$ equipped with their
corresponding weak topologies and let a set $S\subset X$. If there exist an
open convex absorbing $G\subset X$ and a linear functional
$\phi:V\rightarrow\mathbb{R}$ defined over a linear subspace $Z\supset S$ of
$X$ such that:

(i) $S=\phi^{-1}(\\{\mu\\})$ for some $\mu>0$ that also satisfies $S\cap\mu
G=\O$
(ii) $\left\\{\displaystyle\frac{x}{\phi(x)}:x\in V\setminus
S,\;\phi(x)>0\right\\}\cap G=\O$

then $S$ is cone-leveled.

###### Proof.

Since by $(i)$ we have $S=\\{x\in V:\phi(x)=\mu\\}$, it suffices to show that
$\phi$ can be extended to an element of $X^{*}$. We define the Minkowski
functional of $G$, that is let $p_{G}:X\rightarrow\mathbb{R}$ with
$p_{G}(x):=\inf\\{\lambda>0:x\in\lambda G\\}$. Then the inequality
$\phi(x)\leq p_{G}(x)$ holds for every $x\in V$:

(a) If $x\in S$, then $\phi(x)=\mu$. Suppose that $p_{G}(x)<\mu\Rightarrow
p_{G}(\frac{x}{\mu})<1$. Since $G$ is convex, we have $\\{x\in
X:p_{G}(x)<1\\}\subset G$, hence $\frac{x}{\mu}\in G\Rightarrow x\in\mu G$.
This is a contradiction by $(i)$.

(b) Let $x\in V\setminus S$. Since $p_{G}(x)\geq 0$ we can assume that
$\phi(x)>0$ (if $\phi(x)\leq 0$ we have nothing to show). Suppose that
$p_{G}(x)<\phi(x)\Rightarrow p_{G}(\frac{x}{\phi(x)})<1$. Since $G$ is convex,
we have $\\{x\in X:p_{G}(x)<1\\}\subset G$, hence $\frac{x}{\phi(x)}\in G$.
This is a contradiction by $(ii)$.

Therefore $\phi(x)\leq p_{G}(x)$ for every $x\in V$. From the analytical form
of the Hanh-Banach Theorem there exists a linear functional
$x^{*}:X\rightarrow\mathbb{R}$ such that $x^{*}\restriction_{V}=\phi$ and
$x^{*}(x)\leq p_{G}(x)$ for every $x\in X$. Then $S=\\{x\in
V:\phi(x)=\mu\\}\subset\\{x\in X:x^{*}(x)=\mu\\}$ and $\mu G\cap\\{x\in
X:x^{*}(x)=\mu\\}=\O$. Since $G$ is a non-empty open subset of $X$, the set
$\\{x\in X:x^{*}(x)=\mu\\}$ is not dense in $X$, therefore $x^{*}\in X^{*}$. ∎

A special case of the above appears in [31, Proposition 11.24], where
$S:=x_{0}+Y$ for some linear subspace $Y$ of $X$.

We close this section by mentioning the following: Given a convex cone $C$,
one can construct a cone-leveled set that is $\sigma(X,W)$-compact and spans
$C$, if $C^{*}$ has a non-empty interior with respect to the Mackey topology
of $W$. The interested reader should look at [3, Theorem 11].

##  7 Discussion

In this paper we showed that if a two-player zero-sum game has cone-leveled
strategy sets, then it can be solved by simply solving a pair of conic linear
problems. That is, we proved that strong duality for conic linear programming
directly implies the minimax theorem for a wide class of finite and infinite
two-player zero-sum games, as well as the existence of Nash equilibria under
specific assumptions. Due to the generic form of this class of games and of
the structure of the conic linear problems, the main minimax theorems
presented can be characterized as natural generalizations of the original
results proved by von Neumann [40] and Dantzig [9]. We also translated into
our analysis the strategical equivalence between polynomial games and a
different class of two-player zero-sum games with cone-leveled strategy sets,
that was originally proved by Parrilo [32]. This relation implies that if two
games with cone-leveled sets are strategically equivalent, then it suffices to
solve the simplest pair of conic linear problems associated with either one of
these two games. Therefore, a deeper search is needed regarding equivalent
strategic forms of known two-player zero-sum games for which the existence and
computation of Nash equilibria is of high interest. Another area that is
directly related with our theory is the study of the equivalence between two-
player zero-sum games and conic linear programming. Since the equivalence
between (finite) two-player zero-sum games and linear programming was just
recently proved by Adler [2], it is only logical to try and show the same
mathematical connection for the infinite-dimensional case. Lastly, the
following question is naturally derived: “When is a game strategically
equivalent to a two-player zero-sum game with cone-leveled strategy sets?”. We
strongly believe that an answer to such question would offer a significant
contribution towards the associated mathematical concern raised by Kuhn and
Tucker [24], regarding the existence of “a computational technique of general
applicability for zero-sum two-person games with infinite sets of strategies”.

## References

  * [1] L. Adam, R. Horčik, T. Kasl, and T. Kroupa, Double oracle algorithm for computing equilibria in continuous games, Proceedings of the AAAI Conference on Artificial Intelligence, 35 (2021), 5070–5077.
  * [2] I. Adler, The equivalence of linear programs and zero-sum games. Int. J. Game Theory, 42 (2013), 165–177.
  * [3] E.J. Anderson, A review of duality theory for linear programming over topological vector spaces, J. Math. Anal. Appl., 97 (1983), 380–392.
  * [4] E.J. Anderson, A.S. Lewis, and S.Y. Wu, The capacity problem, Optimization, 20 (1989), 725–742.
  * [5] E.J. Anderson, and P. Nash, Linear Programming in Infinite–Dimensional Spaces, New York, NY: Wiley, 1987.
  * [6] R. Bellman, Dynamic Programming, Princeton University Press, Princeton, 1957.
  * [7] X. Chen, and X. Deng, Settling the complexity of two-player nash equilibrium, J. ACM, 56 (2009), 1–57.
  * [8] G.B. Dantzig, A proof of the equivalence of the programming problem and the game problem, In: T.C. Koopmans (ed) Activity analysis of production and allocation, Wiley, New York, 330–335, 1951.
  * [9] G.B. Dantzig, Constructive proof of the Min-Max theorem, Pacific J. of Math., 6 (1956), 25–33.
  * [10] G.B. Dantzig, Reminiscences about the origins of linear programming, Oper. Res. Lett., 1 (1982), 43–48.
  * [11] C. Daskalakis, P.W. Goldberg, C.H. Papadimitriou, The complexity of computing a Nash equilibrium, SIAM J. Comp., 39 (2009), 195–259.
  * [12] C. Daskalakis, C.H. Papadimitriou, Three-player games are hard, Electronic Colloquium on Computational Complexity, 139 (2005), 81–87.
  * [13] N. Dimou, An Introduction to Complex Game Theory, Undergraduate Paper, ArXiv: 2204.02277, 2022.
  * [14] K. Fan, Fixed-Point and Minimax Theorems in Locally Convex Topological Linear Spaces, PNAS, 38 (1952), 121–126.
  * [15] S. Ganzfried, Algorithm for Computing Approximate Nash Equilibrium in Continuous Games with Application to Continuous Blotto, Games, 12 (2021).
  * [16] B. Gränder, and J. Matoušek, Approximation Algorithms and Semidefinite Programming, Berlin, Germany, Springer-Verlag, 2012.
  * [17] I.L. Glicksberg, A Further Generalization of the Kakutani Fixed Point Theorem with Application to Nash Equilibrium Points, Proc. of AMS, 3 (1952), 170–174.
  * [18] G. Gürkan, and JS. Pang, Approximations of Nash equilibria, Math. Program. 117 (2009), 223–253.
  * [19] R. Jain, and J. Watrus, Parallel approximation of non-interactive zero-sum quantum games, Proceedings of the 24th IEEE Conference on Computational Complexity (CCC 2009), 243–253, 2009.
  * [20] N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373–395.
  * [21] L. Khachiyan, A polynomial algorithm in linear programming, Dokl. Akad. Nauk SSSR 224 (in Russian), 1093–1096, English translation in: Soviet Math. Dokl, 20 (1979), 191–194.
  * [22] P.D. Khanh, T. Hong Mo and Thrinh T.T. Tran, Necessary and Sufficient Conditions for Qualitative Properties of Infinite Dimensional Linear Programming Problems, Numerical Functional Analysis and Optimization, 40 (2019), 924–943, 2019.
  * [23] K.S. Kretschmer, Programmes in paired spaces, Can. J. Math, 13 (1961), 221–238.
  * [24] H. W. Kuhn, and A. W. Tucker, Contributions to the Theory of Games, Annals of Mathematics Studies, no. 24, Princeton University Press, Princeton, N.J., 1950.
  * [25] H.C. Lai, and S.Y. Wu, Extremal points and optimal solutions for general capacity problems, Mathematical Programming, 54 (1992), 87–113.
  * [26] R. Laraki, and J.B. Lasserre, Semidefinite programming for min–max problems and games, Math. Program., 131 (2012), 305–332.
  * [27] N. Levinson, A class of continuous linear programming problems, J. Math. Anal. Appl., 16 (1966), 78–83.
  * [28] C. Melolidakis, Game Theory: Mathematical models of conflict and cooperation (in Greek), Sophia Publications, Thessaloniki, 2009.
  * [29] T. Nakamura, and M. Yamasaki, Sufficient Conditions for Duality Theorems in Infinite Linear Programming Problems, Hiroshima Math. J., 9 (1979), 323–334.
  * [30] L. Narici, and E. Beckenstein, Topological Vector Spaces, Pure and applied mathematics (Second ed.), Boca Raton, FL: CRC Press, 2011.
  * [31] S. Negrepontis, T. Zachariadis, N. Kalamidas, and V. Farmaki, General Topology and Functional Analysis (in Greek), Symmetria Publications, Athens, 1997.
  * [32] P.A. Parrilo, Polynomial games and sum of squares optimization, Proceedings of the 45th IEEE Conference on Decision and Control, 2855–2860, 2006.
  * [33] R.T. Rockafellar, Conjugate Duality and Optimization, Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, 1974.
  * [34] R.T. Rockafellar, and R.J. Wets, Variational Analysis, Berlin Heidelberg: Springer, 2009.
  * [35] P. Shah, and P.A. Parrilo, Polynomial stochastic games via sum of squares optimization, Decision and Control, 46th IEEE Conference, 745–750, IEEE, 2007.
  * [36] A. Shapiro, On duality theory of conic linear problems, In Semi-infinite programming (Alicate, 1999), Nonconvex Opt. Appl., 57 (2001), 135–165, Klumer Acad. Publ., Dordrecht.
  * [37] A. Shapiro, Semi-infinite programming, duality, discretization and optimality conditions, Optimization, 58 (2009), 133–161.
  * [38] N.D. Stein, A. Ozdaglar, and P.A. Parrilo, Separable and low-rank continuous games, Int. J. Game Theory, 37 (2008), 475–504.
  * [39] J. von Neumann, Zur theorie der gesellshaftsspiele, Mathematische Annalen, 100, 1928.
  * [40] J. von Neumann, and O. Morgenstern, Theory of games and economic behaviour, Princeton Univ. Press, Princeton, 1944.
  * [41] B. von Stengel, Zero-Sum Games and Linear Programming Duality, preprint, Arxiv: 2205.11196, 2022.
  * [42] G. Weiss, A simplex based algorithm to solve separated continuous linear programs, Math. Program. 115 (2008), 151–198.