Help with a definition of a two-person game in a referenced paper

Question

In the paper "Finding Mixed Nash Equilibria of Generative Adversarial Networks" the authors write in equation (1) on page 2:

Consider the classical formulation of a two-player game with finitely many strategies: \begin{equation*} \tag1\label1 \min_{\boldsymbol{p} \in \Delta_m} \max_{\boldsymbol{q} \in \Delta_n} \langle \boldsymbol{q},\boldsymbol{a} \rangle - \langle \boldsymbol{q},A\boldsymbol{p} \rangle , \end{equation*} where $A$ is a payoff matrix, $\boldsymbol a$ is a vector, and $ \Delta_d := \{\boldsymbol{z} \in \mathbb{R}_{\geq 0}^d \mid \sum\nolimits_{i=1}^d z_i = 1\}$ is the probability simplex, representing the mixed strategies (i.e., probability distributions) over $d$ pure strategies. A pair $(\boldsymbol{p}_{\text{NE}},\boldsymbol{q}_{\text{NE}})$ achieving the min-max value in (\ref{1}) is called a mixed NE.

I was wondering:

• What does this formulation mean?
• The formulation seems to result in a parametrized by a vector $\boldsymbol a$ pair of strategies $(\boldsymbol p, \boldsymbol q)$. What is the role of vector $\boldsymbol a$ in the above equation?

Thank you

After further contemplating: I guess they want to align their application (GAN) with the game theory framework. To that end, they write on page 3:

[W]e consider the set of all probability distributions over $\Theta$ and $\mathcal{W}$, and we search for the optimal distribution that solves the following program: \begin{equation*} \tag4\label4 \min_{\nu \in \mathcal{M}(\Theta)} \max_{\mu \in \mathcal{M}(\mathcal{W})} \mathbb{E}_{\boldsymbol{w} \sim \mu} \mathbb{E}_{X \sim \mathbb{P}_{real}} [f_\boldsymbol{w}(X)] - \mathbb{E}_{\boldsymbol{w} \sim \mu} \mathbb{E}_{\boldsymbol{\theta} \sim \nu} \mathbb{E}_{X \sim \mathbb{P}_{\boldsymbol{\theta}}} [f_\boldsymbol{w}(X)] . \end{equation*}

They then show that the above can be cast as

\begin{equation*} \tag5\label5 \min_{\nu \in \mathcal{M}(\Theta)} \max_{\mu \in \mathcal{M}(\mathcal{W})} \langle \mu,g \rangle - \langle \mu,G\nu \rangle , \end{equation*} with $g$ defined as $g : \mathcal{W} \rightarrow \mathbb{R}$ by $g(w) := \mathbb{E}_{X \sim \mathbb{P}_{real}} [f_\boldsymbol{w}(X)]$, the operator $G : \mathcal{M}(\Theta) \rightarrow \mathcal{F}(\mathcal{W})$ as $(G\nu)(w) := \mathbb{E}_{\boldsymbol{\theta} \sim \nu} \mathbb{E}_{X \sim \mathbb{P}_{\boldsymbol{\theta}}} [f_\boldsymbol{w}(X)]$ and denoting $\langle \mu,h \rangle := \mathbb{E}_{\mu}h$ for any probability measure $\mu$ and function $h$ (where $\langle \mu,h \rangle$ is NOT an inner product, but a dual pairing in Banach spaces),

which looks like (\ref{1}) (for finitely many strategies). Notice that (\ref{4}) has a free parameter $\mathbb{P}_{real}$ (hidden in $g$ in (\ref{5})), which $\boldsymbol{a}$ in (\ref{1}) seems to have been introduced to account for.

Also, \begin{equation*} \min_{\boldsymbol{p} \in \Delta_m} \max_{\boldsymbol{q} \in \Delta_n} \langle \boldsymbol{q},\boldsymbol{a} \rangle - \langle \boldsymbol{q},A\boldsymbol{p} \rangle = \min_{\boldsymbol{p} \in \Delta_m} \max_{\boldsymbol{q} \in \Delta_n} \langle \boldsymbol{q}, (\boldsymbol{a} \otimes \boldsymbol{1} - A)\boldsymbol{p} \rangle \end{equation*}

This is because $\boldsymbol{p}$ is a probability simplex and therefore each row $m$ of vector $\boldsymbol{a}$ increases row $m$ of payoff matrix $A$. Therefore, the above game is equivalent to a standard zero-sum game with payoff matrix $\tilde{A}=(\boldsymbol{a} \otimes \boldsymbol{1} - A)$.

Answer 1

The classical formulation of a two player zero sum game with finitely many strategies is $\langle q, Ap \rangle$. There is no need to introduce the vector $a$, as it can be incorporated in the matrix $A$. In the paper you mention, the authors assume that it is too costly to evaluate $A$; maybe the formulation they provide is useful in their analysis.

Answer 2

This non-standard formulation matches better the intended application - (Wasserstein) GAN. It can be mapped to the standard formulation $\langle \boldsymbol{q}, \tilde{A}\boldsymbol{p} \rangle$ through a new payoff matrix $\tilde{A} = \boldsymbol{a} \otimes \boldsymbol{1} - A$, where $\otimes$ is the outer product operation ($\boldsymbol{a} \otimes \boldsymbol{b} = \boldsymbol{a} \boldsymbol{b}^T)$