# Finding mixed-strategy equilibria of continuous-action games without
gradients using randomized policy networks

Carlos Martin  Computer Science Department, Carnegie Mellon University  Tuomas
Sandholm  Computer Science Department, Carnegie Mellon University  Strategy
Robot, Inc.  Optimized Markets, Inc.  Strategic Machine, Inc.

###### Abstract

We study the problem of computing an approximate Nash equilibrium of
continuous-action game without access to gradients. Such game access is common
in reinforcement learning settings, where the environment is typically treated
as a black box. To tackle this problem, we apply zeroth-order optimization
techniques that combine smoothed gradient estimators with equilibrium-finding
dynamics. We model players’ strategies using artificial neural networks. In
particular, we use randomized policy networks to model mixed strategies. These
take noise in addition to an observation as input and can flexibly represent
arbitrary observation-dependent, continuous-action distributions. Being able
to model such mixed strategies is crucial for tackling continuous-action games
that lack pure-strategy equilibria. We evaluate the performance of our method
using an approximation of the Nash convergence metric from game theory, which
measures how much players can benefit from unilaterally changing their
strategy. We apply our method to continuous Colonel Blotto games, single-item
and multi-item auctions, and a visibility game. The experiments show that our
method can quickly find high-quality approximate equilibria. Furthermore, they
show that the dimensionality of the input noise is crucial for performance. To
our knowledge, this paper is the first to solve general continuous-action
games with unrestricted mixed strategies and without any gradient information.

##  1 Introduction

Most work on computing equilibria of games has focused on settings with
finite, discrete action spaces. Yet many games involving space, time, money,
_etc._ actually have continuous action spaces. Examples include continuous
resource allocation games [Ganzfried, 2021], security games in continuous
spaces [Kamra et al., 2017, 2018, 2019], network games [Ghosh and Kundu,
2019], simulations of military scenarios and wargaming [Marchesi et al.,
2020], and video games [Berner et al., 2019, Vinyals et al., 2019].
Furthermore, even if the action space is discrete, it may be fine-grained
enough to treat as continuous for computational efficiency purposes [Borel,
1938, Chen and Ankenman, 2006, Ganzfried and Sandholm, 2010b].

The typical approach to computing an equilibrium of a game with continuous
action spaces involves discretizing the action space. That entails loss in
solution quality [Kroer and Sandholm, 2015]. Also, it does not scale well; for
one, in multidimensional action spaces it entails a combinatorial explosion of
discretized points (exponential in the number of dimensions). Therefore, other
approaches are called for. Furthermore, in many applications, explicit
gradient information about the game is not available.

This paper is, to our knowledge, the first to solve general continuous-action
games with unrestricted mixed strategies and without any gradient information.
We start by introducing some background needed to formulate the problem. We
then describe related research that tackles the problem of computing
approximate equilibria of such games. Next, we describe our method and its
components, including smoothed gradient estimators, equilibrium-finding
dynamics, and representation of mixed strategies111We use the terms policy and
strategy interchangeably. The former is common in reinforcement learning, the
latter in game theory. using randomized policy networks. We then describe the
various games that we use in the experiments. After that, we present our
experimental results and discussion. Finally, we present our conclusion and
suggest directions for future research.

##  2 Problem description

First, we introduce some notation: $\triangle X$ is the set of probability
measures on $X$, $\mathcal{U}(X)$ is the uniform probability measure on $X$,
and $[\cdot]$ is an Iverson bracket, which is 1 if its argument is true and 0
otherwise.

A _strategic-form game_ is a tuple $(I,S,u)$ where $I$ is a set of players,
$S_{i}$ a set of strategies for player $i$, and
$u_{i}:\prod_{j:I}S_{j}\to\mathbb{R}$ a utility function for player $i$. A
strategy profile $s:\prod_{i:I}S_{i}$ maps players to strategies and $s_{-i}$
denotes $s$ excluding $i$’s strategy. Player $i$’s best response utility
$b_{i}(s_{-i})=\sup_{s_{i}:S_{i}}u_{i}(s)$ is the highest utility they can
attain given the other players’ strategies. Their utility gap
$g_{i}(s)=b_{i}(s_{-i})-u_{i}(s)$ is the highest utility they can gain from
unilaterally changing their strategy, and $s$ is an $\varepsilon$-equilibrium
iff $\sup_{i:I}g_{i}(s)\leq\varepsilon$. A 0-equilibrium is called a Nash
equilibrium. A common measure of closeness to Nash equilibrium is _NashConv_ ,
defined as $\bar{g}=\int_{i\sim\mu}g_{i}$, where $\mu$ is some measure on $I$.
Typically, $I$ is finite and $\mu$ is the counting measure, making $\bar{g}$ a
finite sum of utility gaps. However, some games may have infinitely many
players, such as mean field games. A game is zero-sum iff
$\int_{i\sim\mu}u_{i}=0$, which makes $\bar{g}=\int_{i\sim\mu}b_{i}$. In a
two-player zero-sum game, $\bar{g}$ reduces to the so-called “duality gap”
[Grnarova et al., 2019]:
$\bar{g}(s)=\sup_{s_{1}^{\prime}}u(s_{1}^{\prime},s_{2})-\inf_{s_{2}^{\prime}}u(s_{1},s_{2}^{\prime})$.

In many games, the $S_{i}$ are infinite. The following theorems apply to such
games. If for all $i$, $S_{i}$ is nonempty and compact, and $u_{i}$ is
continuous in $s$, a mixed strategy Nash equilibrium exists [Glicksberg,
1952]. If for all $i$, $S_{i}$ is nonempty, compact, and convex, and $u_{i}$
is continuous in $s$ and quasi-concave in $s_{i}$, a pure strategy Nash
equilibrium exists [Fudenberg and Tirole, 1991, p. 34]. Other results include
the existence of a mixed strategy Nash equilibrium for games with
discontinuous utilities under some mild semicontinuity conditions on the
utility functions [Dasgupta and Maskin, 1986], and the uniqueness of a pure
Nash equilibrium for continuous games under diagonal strict concavity
assumptions [Rosen, 1965].

A _Bayesian game_ is a game of incomplete information, that is, a game in
which players have only partial information about the game and other players.
Formally, it is a tuple $(I,\Omega,\mu,O,\tau,A,r)$ where $I$ is a set of
players, $\Omega$ a set of states, $\mu:\triangle\Omega$ a distribution over
states, $O_{i}$ a set of observations for $i$, $\tau_{i}:\Omega\to O_{i}$ an
observation function for $i$, $A_{i}$ a set of actions for $i$, and
$r_{i}:\Omega\times\prod_{j:I}A_{j}\to\mathbb{R}$ a payoff function for $i$. A
strategy for player $i$ is a function $s_{i}:O_{i}\to\triangle A_{i}$. Given
strategy profile $s$, player $i$’s expected payoff is
$u_{i}(s)=\operatorname{E}_{\omega\sim\mu}\operatorname{E}_{a_{j}\sim
s_{j}(\tau_{j}(\omega)),\forall j:I}r_{i}(\omega,a)$ and their best response
payoff $b_{i}(s_{-i})=\sup_{s_{i}}u_{i}(s)$ is

$\displaystyle\sup_{s_{i}}\operatorname{E}_{\omega}\operatorname{E}_{a}r_{i}(\omega,a)$
$\displaystyle=\operatorname{E}_{o_{i}}\sup_{s_{i}}\operatorname{E}_{\omega|o_{i}}\operatorname{E}_{a}r_{i}(\omega,a)$
(1)
$\displaystyle=\operatorname{E}_{o_{i}}\sup_{a_{i}}\operatorname{E}_{\omega|o_{i}}\operatorname{E}_{a_{-i}}r_{i}(\omega,a)$
(2)

where $\omega|o_{i}$ conditions $\omega$ on player $i$’s observation being
$o_{i}$.

##  3 Related research

McMahan et al. [2003] introduce the double oracle algorithm for normal-form
games and prove convergence. Adam et al. [2021] extended it to two-player
zero-sum continuous games. Kroupa and Votroubek [2021] extend it to $n$-player
continuous games. Their algorithm maintains finite strategy sets for each
player and iteratively extends them with best responses to an equilibrium of
the induced finite sub-game. It “converges fast when the dimension of strategy
spaces is small, and the generated subgames are not large.” For example, in
the two-player zero-sum case: “The best responses were computed by selecting
the best point of a uniform discretization for the one-dimensional problems
and by using a mixed-integer linear programming reformulation for the Colonel
Blotto games.” This approach does not scale to high-dimensional games with
general payoffs where best-response computation is difficult. Moreover, if the
game is stochastic, estimating the finite subgame can be difficult and require
many samples. Furthermore, this approach does not learn observation-dependent
strategies that generalize across observations.

Ganzfried [2021] introduce an algorithm for approximating equilibria in
continuous games called “redundant fictitious play” and apply it to a
continuous Colonel Blotto game. Kamra et al. [2019] present DeepFP, an
approximate extension of fictitious play [Brown, 1951, Berger, 2007] to
continuous action spaces. They demonstrate stable convergence to equilibrium
on several classic games and a large forest security domain. DeepFP represents
players’ approximate best responses via generative neural networks. The
authors state that such models cannot be trained directly in the absence of
gradients, and thus employ a game-model network that is a differentiable
approximation of the game’s payoff function, training these networks end-to-
end in a model-based learning regime. Our approach shows, however, that these
generative models _can_ be trained directly.

Li and Wellman [2021] extend the double oracle approach to $n$-player general-
sum continuous Bayesian games. They represent agents as neural networks and
optimize them using _natural evolution strategies (NES)_ [Wierstra et al.,
2008, 2014]. To approximate a pure-strategy equilibrium, they formulate the
problem as a bi-level optimization and employ NES to implement both inner-loop
best response optimization and outer-loop regret minimization. Bichler et al.
[2021] represent strategies as neural networks and apply simultaneous
gradients to provably learn local equilibria. They focus on symmetric auction
models, assuming symmetric prior distributions and symmetric equilibrium
bidding strategies. Bichler and Kohring [2022] extend that to asymmetric
auctions, where one needs to train multiple neural networks. Both papers
restrict their attention to pure strategies. Fichtl et al. [2022] compute
distributional strategies [Milgrom and Weber, 1985] (a form of mixed
strategies for Bayesian game) on a discretized version of the game via online
convex optimization, specifically _simultaneous online dual averaging_ , and
show that the equilibrium of the discretized game approximates an equilibrium
in the continuous game. That is, they discretize the type and action spaces
and implement gradient dynamics in the discretized version of the game without
using neural networks. In contrast, our approach does not use discretization,
which can work well for small games but does not scale to high-dimensional
observation and action spaces.

A _generative adversarial network (GAN)_ [Goodfellow et al., 2014] consists of
a generator that learns to generate fake data and a discriminator that learns
to distinguish it from real data. Grnarova et al. [2019] propose using an
approximation of the game-theoretic _duality gap_ as a performance measure for
GANs. Grnarova et al. [2021] propose using this measure as the training
objective itself, proving some convergence guarantees. Lockhart et al. [2019]
present exploitability descent, which computes approximate equilibria in two-
player zero-sum extensive-form games by direct strategy optimization against
worst-case opponents. They prove that the exploitability of a player’s
strategy converges asymptotically to zero. Hence, if both players employ this
optimization, the strategy profile converges to an equilibrium. Unlike
extensive-form fictitious play [Heinrich et al., 2015] and counterfactual
regret minimization [Zinkevich et al., 2007], their result pertains to last-
iterate rather than average-iterate convergence. [Timbers et al., 2022]
introduce approximate exploitability, which uses an approximate best response
computed through search and reinforcement learning. This is a generalization
of local best response, a domain-specific evaluation metric used in poker
[Lisý and Bowling, 2017].

Gemp et al. [2022] propose an approach called _average deviation incentive
descent with adaptive sampling_ that iteratively improves an approximation to
a Nash equilibrium through joint play by tracing a homotopy that defines a
continuum of equilibria for the game regularized with decaying levels of
entropy. To encourage iterates to remain near this path, they minimize average
deviation incentive via stochastic gradient descent.

Ganzfried and Sandholm [2010a, b] present a procedure for solving large
imperfect-information games by solving an infinite approximation of the
original game and mapping the equilibrium to a strategy profile in the
original game. Perhaps counterintuitively, the infinite approximation can
often be solved much more easily than the finite game. The algorithm exploits
some qualitative model of equilibrium structure as an additional input to find
an equilibrium in continuous games.

##  4 Game-solving technique

We now describe the components of our game-solving technique.

###  4.1 Gradient estimation

Consider the problem of maximizing $f:\mathbb{R}^{d}\to\mathbb{R}$ with access
to its values but not derivatives. This setting is called _zeroth-order
optimization_. One approach to this problem is to compute estimates of the
gradient $g(x)\approx\nabla f(x)$ and apply gradient-based optimization. The
gradient could be estimated via finite differences as
$g(x)_{i}=\tfrac{1}{\sigma}(f(x+\sigma e_{i})-f(x))$ for all $i\in[d]$, where
$e_{i}$ is the $i$th standard basis vector and $\sigma$ is a small number.
However, the number of queries needed scales linearly with the number of
dimensions $d$. Another approach is to evaluate the function at _randomly-
sampled_ points and estimate the gradient as a sum of estimates of directional
derivatives along random directions [Duchi et al., 2015, Nesterov and
Spokoiny, 2017, Shamir, 2017, Berahas et al., 2022]. These methods compute an
unbiased estimator of the gradient of a _smoothed_ version of $f$ induced by
stochastically perturbing the input under some distribution $\mu_{1}$ and
taking the expectation [Duchi et al., 2012]. Specifically, for distributions
$\mu_{1}$ and $\mu_{2}$, $\nabla_{x}\operatorname{E}_{u\sim\mu_{1}}f(x+\sigma
u)=\tfrac{1}{\sigma}\operatorname{E}_{u\sim\mu_{2}}f(x+\sigma u)u$. Gaussian
smoothing uses $\mu_{1}=\mu_{2}=\mathcal{N}(0,I_{d})$. Ball smoothing uses
$\mu_{1}=\mathcal{U}(\sqrt{d}\mathbb{B}_{d}),\mu_{2}=\mathcal{U}(\sqrt{d}\mathbb{S}_{d})$,
where $\mathbb{B}_{d}$ and $\mathbb{S}_{d}$ are the $d$-dimensional unit ball
and sphere. These yield instances of a class of black box optimization
algorithms called _evolution strategies_ [Rechenberg and Eigen, 1973,
Schwefel, 1977, Rechenberg, 1978], which maintain and evolve a population of
parameter vectors. Specifically, they yield instances of _natural evolution
strategies_ [Wierstra et al., 2008, 2014, Yi et al., 2009], which represent
the population as a distribution over parameters and maximize its average
objective value using the score function estimator. For example, Gaussian
smoothing has been applied to single-agent reinforcement learning and obtains
competitive results on standard benchmarks [Salimans et al., 2017].

To estimate the smoothed gradient, various _stencils_ can be used. These have
the form $\tfrac{1}{\sigma N}\sum_{i=1}^{N}a_{i}u_{i}$ where
$u_{i}\sim\mu_{2}$ independently and $a_{i}$ is $f(x+\sigma u_{i})$,
$f(x+\sigma u_{i})-f(x)$, and $\tfrac{1}{2}(f(x+\sigma u_{i})-f(x-\sigma
u_{i}))$ for the single-point, forward-difference, and central-difference
stencils, respectively. The single-point stencil has a large variance that
diverges to infinity as $\sigma$ approaches 0, so the latter two are typically
used in practice [Berahas et al., 2022]. A related method is _simultaneous-
perturbation stochastic approximation (SPSA)_ [Spall, 1992], which perturbs
each coordinate with Rademacher variates $u\sim\mathcal{U}(\\{-1,1\\}^{d})$
and uses the central-difference stencil. A Taylor expansion of $f$ shows that
this is a good estimate of the true gradient when $\sigma$ is small. Spall
[1997] introduced a one-measurement variant of SPSA that uses the single-point
stencil. In our experiments, we use Gaussian smoothing with the central-
difference stencil.

###  4.2 Equilibrium-finding dynamics

Several gradient-based algorithms exist for finding equilibria in continuous
games, as described in the appendix. Their convergence is analyzed in various
works, including Balduzzi et al. [2018], Letcher et al. [2019], Mertikopoulos
and Zhou [2019], Grnarova et al. [2019], Mazumdar et al. [2019], Hsieh et al.
[2021]. In the games we tested, simultaneous gradient ascent was sufficient to
obtain convergence to equilibrium and the other dynamics did not yield further
improvements. Mertikopoulos and Zhou [2019] analyze the conditions under which
simultaneous gradient ascent converges to Nash equilibria. They prove that, if
the game admits a pseudoconcave potential or if it is monotone, the players’
actions converge to Nash equilibrium, no matter the level of uncertainty
affecting the players’ feedback. Bichler et al. [2021] write that most
auctions in the literature assume symmetric bidders and symmetric equilibrium
bid functions [Krishna, 2002]. This symmetry creates a potential game, and
simultaneous gradient dynamics provably converge to a pure local Nash
equilibria in finite-dimensional continuous potential games [Mazumdar et al.,
2020]. Thus in any symmetric and smooth auction game, symmetric gradient
ascent with appropriate (square-summable but not summable) step sizes almost
surely converges to a local ex-ante approximate Bayes-Nash equilibrium
[Bichler et al., 2021, Proposition 1]. These results apply to most of our
experiments, except for the asymmetric-information auction.

###  4.3 Distributed training algorithm

Our algorithm for training strategy profiles can also be efficiently
distributed, as we now describe. The pseudocode is given as Algorithm 1. On
any iteration, there is a set of available workers $\mathcal{J}$. Each worker
is assigned the task of computing a pseudogradient for a particular player.
The vector $\\{a_{j}\\}_{j\in\mathcal{J}}$ contains the assignment of a player
for each worker. Each worker’s pseudorandom number generator (PRNG) is
initialized with the same fixed seed. On any iteration, one of the workers is
the _coordinator_. Initially, or when the current coordinator goes offline,
the workers choose a coordinator by running a leader election algorithm.

On each iteration, each worker evaluates the utility function (generally the
most expensive operation and bottleneck for training) twice to compute the
finite difference required for the pseudogradient. It then sends this computed
finite difference (a single scalar) to the coordinator. The coordinator then
sends the vector of these scalars to every worker, ensuring that all workers
see each other’s scalars. Thus the information that needs to be passed between
workers is minimal. This greatly reduces the cross-worker bandwidth required
by the algorithm compared to schemes that pass parameters or gradients between
workers, which can be very expensive for large models.

Algorithm 1 Distributed multiagent pseudogradient ascent

The following algorithm runs on each worker:

$\mathcal{I}$ is the set of players

$u$ is the utility function

initialize PRNG state with fixed seed

$\mathbf{x}\leftarrow$ initial strategy profile

for $i\in\mathcal{I}$ do

$S_{i}\leftarrow\text{init}(\mathbf{x}_{i})$ $\triangleright$ initial state of
optimizer $i$

loop

$\mathcal{J}\leftarrow$ set of available workers

for $j\in\mathcal{J}$ do

$a_{j}\leftarrow$ player $\in\mathcal{I}$ $\triangleright$ can be set
dynamically

$\varepsilon_{j}\leftarrow$ scale $\in\mathbb{R}_{>0}$ $\triangleright$ can be
set dynamically

$\mathbf{z}_{j}\sim N(\mathbf{0},\mathbf{I}_{\dim\mathbf{x}_{i}})$ where
$i=a_{j}$

$j\leftarrow$ own worker ID

$\delta_{j}\leftarrow\frac{u(\mathbf{x}_{i}+\varepsilon_{j}\mathbf{z}_{j},\mathbf{x}_{-i})_{i}-u(\mathbf{x}_{i}-\varepsilon_{j}\mathbf{z}_{j},\mathbf{x}_{-i})_{i}}{2\varepsilon_{j}}$
where $i=a_{j}$

send $\delta_{j}$ to coordinator

receive $\delta$ from coordinator

for $i\in\mathcal{I}$ do

$\mathcal{K}\leftarrow\\{j\in\mathcal{J}\mid a_{j}=i\\}$ $\triangleright$
workers assigned $i$

$\mathbf{v}_{i}\leftarrow\frac{1}{|\mathcal{K}|}\sum_{j\in\mathcal{K}}\delta_{j}\mathbf{z}_{j}$
$\triangleright$ $i$’s pseudogradient

$S_{i},\mathbf{x}_{i}\leftarrow\text{step}(S_{i},\mathbf{v}_{i})$
$\triangleright$ step optimizer $i$

This massively parallelizes [Bichler et al., 2021, Algorithm 1] (“NPGA using
ES gradients”). Simultaneously, it generalizes [Salimans et al., 2017,
Algorithm 2] (“Parallelized Evolution Strategies”), which also uses shared
seeds, to the multiplayer setting, with separate gradient evaluations and
optimizers for each player. Furthermore, it allows for the possibility of
setting the worker-player assignments $a_{j}$ and perturbation noise scales
$\varepsilon_{j}$ dynamically over time, provided that this is done
consistently across workers (e.g., based on their common state variables).
Vanilla gradient descent, momentum gradient descent, optimistic gradient
descent, or other optimization algorithms can be used. More information about
the different optimization algorithms is in the appendix in the section on
alternative equilibrium-finding dynamics.

The set of available workers can also change dynamically over time. If a
worker leaves or joins the pool, the coordinator notifies all workers of its
ID so they can remove it from, or add it to, their $\mathcal{J}$ sets,
respectively. The new worker is brought up to speed by passing it the current
PRNG state, strategy profile parameters, and optimizer states (what state
information is needed depends on the algorithm used, for example, whether
momentum is used).

###  4.4 Policy representation

Another key design choice is how the players’ strategies are modeled. Bichler
et al. [2021] model strategies using neural networks [McCulloch and Pitts,
1943, Rosenblatt, 1958]. Each player’s policy network takes as input a
player’s observation and outputs an action. These policy networks were then
trained using _neural pseudogradient ascent_ , which uses Gaussian smoothing
and applies simultaneous gradient ascent. As the authors note, their policy
networks can only model pure strategies, since the output action is
deterministic with respect to the input observation.

We also model strategies using neural networks, with one crucial difference:
our policy network $f_{\theta}$ takes as input the player’s observation $o$
_together with noise_ $z$ from some fixed latent distribution, such as the
standard multivariate Gaussian distribution. Thus the output
$a=f_{\theta}(o,z)$ of the network is _random_ with respect to $o$. The
network can then learn to transform this randomness into a desired action
distribution (see Figure 1 in the appendix). This lets us model mixed
strategies, which is especially desirable in games that lack pure-strategy
equilibria. Some approaches in the literature use the output of a policy
network to parameterize some parametric distribution on the action space, such
as a Gaussian mixture model. However, taking the randomness _as input_ and
letting the neural network reshape it as desired allows us to model arbitrary
distributions more flexibly.

Figure 1 illustrates the high-level structure of a randomized policy network.
It takes as input an observation and random noise, concatenates them, passes
the result through a feedforward neural network, and outputs an action.

ptneural networkobservationrandomnessaction

Figure 1: Structure of a randomized policy network.

Since the dimensionality of noise fed into a randomized policy network is an
important hyperparameter, we now review the literature that studies the
relation between input noise dimension and representational power in neural
network-based generative models.

The universal approximation theorem [Cybenko, 1989, Hornik, 1991, Leshno et
al., 1993, Pinkus, 1999] states that a single (sufficiently wide) hidden layer
suffices to approximate arbitrary continuous functions on a compact domain.
Furthermore, if $\mathcal{X},\mathcal{Y},\subseteq\mathbb{R}^{m}$, $X$ is an
$\mathcal{X}$-valued random variable, $f:\mathcal{X}\to\mathcal{Y}$, and
$f_{n}$ is a sequence of functions that converges pointwise to $f$, the
sequence of random variables $Y_{n}=f_{n}(X)$ converges in distribution to
$Y=f(X)$ [Huang et al., 2018, Lemma 4]. Gaussian input noise of _lower_
dimension than the output space does not suffice to approximate arbitrary
distributions on the output space. In particular, Sard’s theorem [Sard, 1942]
says the following: Let $f:\mathbb{R}^{n}\to\mathbb{R}^{m}$ be $k$ times
continuously differentiable, where $k\geq\max\\{n-m+1,1\\}$. Let
$X\subseteq\mathbb{R}^{n}$ be the set of critical points of $f$ (that is,
points where the Jacobian matrix of $f$ has rank less than $m$). Then the
image $f[X]$ has Lebesgue measure zero in $\mathbb{R}^{m}$. As a corollary, if
$n<m$, then all points in $\mathbb{R}^{n}$ are critical. Thus
$\operatorname{im}f$ has Lebesgue measure zero in $\mathbb{R}^{m}$.222From a
standard uniform random variable, one can extract two independent variables by
de-interleaving its binary expansion, but this operation is highly
discontinuous and pathological.

Padala et al. [2021] study the effect of input noise dimension in GANs. They
show that the right dimension of input noise for optimal results depends on
the dataset and architecture used. Feng et al. [2021] study how noise
injection in GANs helps them overcome the “adversarial dimension trap”, which
arises when the generated manifold has an intrinsic dimension lower than that
of the data manifold: that is, when the latent space is low-dimensional
compared to the high-dimensional space of real image details. Citing Sard’s
theorem [Petersen, 2006], they advise against mapping low-dimensional feature
spaces into feature manifolds with higher intrinsic dimensions. Bailey and
Telgarsky [2018] investigate the ability of generative networks to convert
input noise distributions into other distributions. One question they study is
how easy it is to create a network that outputs _more_ dimensions of noise
than it receives. They derive bounds showing that an increase in dimension
requires a large, complicated network. For example, an approximation of the
uniform distribution on the unit square using the uniform distribution on the
unit interval could use an (almost) space-filling curve such as the iterated
tent map. (A space-filling curve is a continuous surjection from the unit
interval to the unit square or volume of higher dimension.) This function is
highly nonlinear and it can be shown that neural networks must be large to
approximate it well. Thus the dimensionality of input noise is essential in
practice. As we discuss later in this paper, our experiments support this
conclusion for the game context. Bailey and Telgarsky [2018] also show that,
even when the input dimension is greater than the output dimension, increased
input dimension can still sometimes improve accuracy. For example, to
approximate a univariate Gaussian distribution with a high dimensional uniform
distribution, one can sum the inputs. By the Berry-Esseen theorem [Berry,
1941], a refinement of the central limit theorem, the output is close to a
Gaussian distribution. This uses no nonlinearity, but simply takes advantage
of the fact that projecting a hypercube onto a line results in an
approximately Gaussian distribution. In our experiments, we show an example of
excess dimensionality improving performance.

##  5 Games used in experiments

We now describe the games used as benchmarks.

###  5.1 Colonel Blotto games

The Colonel Blotto game is a two-player zero-sum game in which two players
distribute resources over several battlefields. A battlefield is won by
whoever devotes the most resources to it. A player’s payoff is the number of
battlefields they win. This game was introduced by Borel [1953]. It
illustrates fundamental strategic considerations that arise in conflicts or
competition involving resource allocation, such as political campaigns,
research and development competition (where innovation may involve obtaining a
collection of interrelated patents), national security and military and
systems defense [Kovenock and Roberson, 2021].

Gross and Wagner [1950] analyzed a continuous variant in which both players
have continuous, possibly unequal budgets. They obtained exact solutions for
various special cases, including all 2-battlefield cases and all 3-battlefield
cases with equal budgets. Washburn [2013] generalized to the case where
battlefield values are unequal across battlefields. Kovenock and Roberson
[2021] generalized to the case where battlefield values are also unequal
across players. Adamo and Matros [2009] studied a variant in which players
have incomplete information about the other player’s resource budgets.
Kovenock and Roberson [2011] studied a model where the players are subject to
incomplete information about the battlefield valuations. Boix-Adserà et al.
[2021] analyzed the natural multiplayer generalization of the continuous
Colonel Blotto game.

We describe the case with heterogeneous budgets, heterogeneous battlefield
values across both players and battlefields, and several players. Formally,
suppose there are $J$ battlefields. Let $b_{i}$ be the budget of player $i$.
Let $v_{ij}$ be the value to player $i$ of battlefield $j$. Player $i$’s
action space is the standard $J$-simplex dilated by their budget:
$A_{i}=\\{a_{ij}:\mathbb{R}\mid a_{ij}\geq
0,\textstyle\sum_{j}a_{ij}=b_{i}\\}$. Player $i$’s reward function is
$r_{i}(a)=\textstyle\sum_{j}v_{ij}w_{ij}(a)$ where $w_{ij}$ is the probability
that $i$ wins $j$. Ties are broken uniformly at random.

###  5.2 Single-item auctions

An auction is a mechanism by which _items_ are sold to _bidders_. Auctions
play a central role in the study of markets and are used in a wide range of
contexts. In a single-item sealed bid auction, bidders simultaneously submit
bids and the highest bidder wins the item. Let $w_{i}(a)$ be the probability
$i$ wins given action profile $a$, where ties are broken uniformly at random.
Let $v_{i}(\omega)$ be the item’s value for the $i$th player given state
$\omega$. In a $k$th-price _winner-pay_ auction, the winner pays the $k$th
highest bid: $r_{i}(\omega,a)=w_{i}(a)(v_{i}(\omega)-a_{(k)})$, where
$a_{(k)}$ is the $k$th highest bid. In an _all-pay_ auction, each player
always pays their bid: $r_{i}(\omega,a)=w_{i}(a)v_{i}(\omega)-a_{i}$. This
auction is widely used to model lobbying for rents in regulated and trade
protected industries, technological competition and R&D races, political
campaigns, job promotions, and other contests [Baye et al., 1996]. The all-pay
complete-information auction lacks pure-strategy equilibria [Baye et al.,
1996]. The 2-player 1st-price winner-pay asymmetric-information auction also
lacks pure-strategy equilibria [Krishna, 2002, section 8.3]. In particular,
the second player must randomize. More details about each type of auction can
be found in the appendix.

###  5.3 Multi-item auctions

Multi-item auctions are of great importance in practice, for example in
strategic sourcing [Sandholm, 2013] and radio spectrum allocation [Milgrom and
Segal, 2014, 2020]. However, deriving equilibrium bidding strategies for
multi-item auctions is notoriously difficult. A rare notable instance where it
has been derived is the _chopstick auction_ , which was introduced and
analyzed by Szentes and Rosenthal [2003b, a]. In this auction, 3 chopsticks
are sold simultaneously in separate first-price sealed-bid auctions. There are
2 bidders, and it is common knowledge that a pair of chopsticks is worth $1, a
single chopstick is worth nothing by itself, and 3 chopsticks are worth the
same as 2. In short, one needs two chopsticks to eat. Pure strategies are
triples of non-negative real numbers (bids). This game has an interesting
equilibrium: let the tetrahedron $T$ be defined as the convex hull of the four
points $(\tfrac{1}{2},\tfrac{1}{2},0)$, $(\tfrac{1}{2},0,\tfrac{1}{2})$,
$(0,\tfrac{1}{2},\tfrac{1}{2})$, and $(0,0,0)$. Then the uniform probability
measure on the 2-dimensional surface of $T$ generates a symmetric equilibrium.
(Furthermore, all points inside the tetrahedron are pure best responses to
this equilibrium mixture.) We benchmark on the chopsticks auction since it is
a rare case of a multi-item auction where the solution can be checked because
the equilibrium is known. It is also a canonical case of simultaneous separate
auctions under combinatorial preferences.

###  5.4 Visibility game

Lotker et al. [2008] introduced the _visibility game_ , a noncooperative,
complete-information strategic game. In this game, each player $i$ chooses a
point $x_{i}\in[0,1]$. Their payoff is the distance to the next higher point,
or to $1$ if $x_{i}$ is the highest. This game models a situation where
players seek to maximize their _visibility time_ , and is a variant of the
family of “timing games” [Fudenberg and Tirole, 1991]. It resembles the “war
of attrition” game formalized by Smith [1974]. In this game, both players are
engaged in a costly competition and they need to choose a time to concede.
More formally, the first player to concede (called “leader”) gets a smaller
payoff than the other player (called “follower”). Furthermore, the payoff to
the leader strictly decreases as time progresses. That is, conceding early is
better than conceding late.

They prove that the $n$-player visibility game has no pure equilibrium, but
has a unique mixed equilibrium, which is symmetric. In the 2-player case, up
to a set of measure zero, there is a unique equilibrium whose strategies have
probability densities $p(x)=1/(1-x)$ when $0\leq x\leq 1-1/\mathrm{e}$ and 0
otherwise. Each player’s expected payoff is $1/\mathrm{e}$.

##  6 Hyperparameters used in the experiments

To initialize our networks, we use He initialization [He et al., 2015], which
is widely used for feedforward networks with ReLU-like activation functions.
It initializes bias vectors to zero and weight matrices with normally-
distributed entries scaled by $\sqrt{2/n}$, where $n$ is the layer’s input
dimension. We use the ELU activation function [Clevert et al., 2016] for
hidden layers. Like Bichler et al. [2021], we use 2 hidden layers with 10
neurons each.

We illustrate the performance of our method by plotting NashConv against the
number of epochs, where each epoch consists of $10^{6}$ optimization steps.
Each hyperparameter setting is labeled in the legend and shown in a different
color. Each individual setting is run 20 times with different random seeds.
Solid lines indicate means across trials. Bands indicate a confidence interval
for this mean with a confidence level of 0.95. These confidence intervals are
computed using bootstrapping [Efron, 1979], specifically the bias-corrected
and accelerated (BCa) method [Efron, 1987].

For the gradient estimator, we use the Gaussian distribution with scale
$\sigma=10^{-2}$, $N=1$ samples, and the central-difference stencil (so 2
evaluations per step). For the optimizer, we use standard gradient descent
with a learning rate of $10^{-6}$. To estimate NashConv (Equation 2), we use
100 observation samples and 300 state samples (given each observation). We use
a 100-point discretization of the action space for the auctions and visibility
game. For Colonel Blotto games, we use a 231-point discretization of the
action space. It is obtained by enumerating all partitions of the integer 20
into 3 parts and renormalizing them to sum to 1.

##  7 Experimental results

We now describe our experimental results for each game. Figures illustrating
analytically-derived equilibria in cases where they are known can be found in
the appendix.

###  7.1 Colonel Blotto games

Actions in the continuous Colonel Blotto game are points on the standard
simplex. Thus we use a softmax activation function for the output layer of the
randomized policy network. Figure 2 illustrates the performance of our method
on the continuous Colonel Blotto game with 2 players and 3 battlefields. Since
the game has no pure-strategy Nash equilibrium, deterministic strategies
perform badly, as expected. 1-dimensional noise results in slightly better
performance, but does not let players randomize well enough to approximate the
equilibrium. On the other hand, noise of dimension 2 and higher is sufficient
for good performance. The very slight increase in exploitability after 1e8
steps is most likely due to fluctuations introduced by the many sources of
stochasticity in the training process, including the game and gradient
estimates, as well as the fact that we are training a multi-layer neural
network. Even in the supervised learning setting, loss does not always
decrease monotonically.

Figure 2: Continuous Colonel Blotto game.

Figure 3 illustrates the strategies at different stages of training for one
trial that uses 2-dimensional noise. Each scatter plot is made by sampling
$10^{5}$ actions from each player’s strategy. The strategies converge to the
analytical solution derived by Gross and Wagner [1950]. More details about
this solution can be found in the appendix.

Figure 3: Strategies at epochs 0, 60, 120, and 180 (left to right). Each
histogram uses $10^{4}$ action samples.

Figure 4 also illustrates performances on the continuous Colonel Blotto game
with 2 players and 3 battlefields. This time, however, the budgets for each
player are sampled from the standard uniform distribution and revealed to both
players. Thus each player must adjust their action distribution accordingly.
To our knowledge, prior approaches [Adam et al., 2021, Kroupa and Votroubek,
2021, Ganzfried, 2021] do not learn strategies that can generalize across
different parameters (like budgets and valuations), which requires the use of
function approximators such as neural networks.

Figure 4: Continuous Colonel Blotto game with random budgets.

###  7.2 Single-item and multi-item auctions

We now turn to the auction setting. Unlike Bichler et al. [2021], we use an
absolute value function in the output layer rather than a ReLU function. The
reason is that, as we found in our experiments, ReLU can easily cause
degenerate initializations: if the randomly-initialized neural network happens
to map all of the unit interval (the observation space) to negative bids, no
gradient signal can be received and the network is stuck. By default, auctions
are 2-player, 1st-price, and winner-pay unless otherwise noted.

Figures 5 and 6 illustrate performances and strategies for the asymmetric
information auction. Figures 7 and 8 illustrate performances and strategies
for the complete-information all-pay auction. Recall that these auctions have
no pure-strategy equilibria. Thus, as expected, deterministic strategies
perform poorly. As with Colonel Blotto games, our experiments in these auction
settings show that the ability to flexibly model mixed strategies is crucial
for computing approximate Nash equilibria in certain auction settings.

Figure 5: The asymmetric-information auction.

Figure 6: Strategies at epochs 0, 30, 60, and 90 (left to right). X and Y axes
denote observation and bid, respectively. Each histogram uses $10^{4}$ action
samples per observation. Figure 7: The all-pay complete-information auction.

Figure 8: Strategies at epochs 0, 30, 60, and 90 (left to right). X and Y axes
denote observation and bid, respectively. Each histogram uses $10^{4}$ action
samples per observation.

Figure 9 and 10 illustrate performances and strategies for the chopstick
auction. Here we encounter an interesting phenomenon: Recall that this game
has a symmetric equilibrium generated by the uniform measure on the surface of
a tetrahedron. Although the tetrahedron itself is 3-dimensional, its surface
is only 2-dimensional. Thus one may wonder whether 2-dimensional noise is
sufficient: that is, whether the network can learn to project this lower-
dimensional manifold out into the third dimension while “folding” it in the
way required to obtain the surface of the tetrahedron. Through our
experiments, we observe that 2-dimensional noise indeed suffices to
(approximately) match the performance of higher-dimensional noise. Thus the
_intrinsic dimension_ of the equilibrium action distribution (as opposed to
the extrinsic dimension of the ambient space it is embedded in) seems to be
the decisive factor.

Figure 9: The chopstick auction.

Figure 10: Illustration of player strategies, based on $10^{5}$ action
samples. Left to right: Players 1 and 2. Top to bottom: Epochs 30, 60, and 90.

###  7.3 Visibility game

Figures 11 illustrates performances on the 2-player visibility game. Figure 12
illustrates strategies during training for a trial with 1-dimensional noise.
The players’ distributions converge to the expected distribution (there is a
distinctive cutoff at $1-1/\mathrm{e}\approx 0.632$). As expected,
0-dimensional noise, which yields deterministic strategies, performs very
poorly. More interestingly, there is a noticeable gap in performance between
1-dimensional noise, which matches the dimensionality of the action space, and
higher-dimensional noise. That is, using noise of higher dimension than the
action space accelerates convergence in this game.

Figure 11: Performance on the 2-player visibility game.

Figure 12: Strategies at epochs 0, 100, 200, and 300 (left to right). X and Y
axes denote observation and bid, respectively. Each histogram uses $10^{5}$
action samples.

##  8 Conclusions and future research

We presented the first paper, to our knowledge, to solve general continuous-
action games with unrestricted mixed strategies and without any gradient
information. We accomplished this using zeroth-order optimization techniques
that combine smoothed gradient estimators with equilibrium-finding gradient
dynamics. We modeled players’ strategies using _randomized policy networks_
that take noise as input and can flexibly represent arbitrary observation-
dependent, continuous-action distributions. Being able to model such mixed
strategies is crucial for tackling continuous-action games that can lack pure-
strategy equilibria.

We evaluated our method on various games, including continuous Colonel Blotto
games, single-item and multi-item auctions, and a visibility game. The
experiments showed that our method can quickly compute high-quality
approximate equilibria for these games. Furthermore, they show that the
dimensionality of the input noise is crucial for representing and converging
to equilibria. In particular, noise of too low dimension (or no noise, which
yields a deterministic policy) results in failure to converge. Randomized
policy networks flexibly model observation-dependent action distributions.
Thus, in contrast to prior work, we can flexibly model mixed strategies and
directly optimize them in a “black-box” game with access only to payoffs.

This work opens many directions for tackling even more complex multiagent
environments. In multi-step environments, the current observation may not
contain all information about past observations and actions that is relevant
to choosing an action. To give agents memory, one can use recurrent networks
[Rumelhart et al., 1986, Werbos, 1988] such as LSTMs [Hochreiter and
Schmidhuber, 1997] or GRUs [Cho et al., 2014]. In that case, the policy
network would receive as input an observation, source of randomness, and
memory state and output an action and new memory state. One can also consider
games with more complex observation and action spaces, including high-
dimensional arrays like images. Convolutional networks [LeCun et al., 1998,
1989] can be used to process such inputs. Very complex environments, including
real-time strategy games like StarCraft II, may require more sophisticated
neural architectures [Vinyals et al., 2019] such as pointer networks [Vinyals
et al., 2015], transformers [Vaswani et al., 2017], and scatter connections
that integrate spatial and non-spatial information.

##  9 Acknowledgements

This material is based on work supported by the National Science Foundation
under grants IIS-1901403 and CCF-1733556 and by the ARO under award
W911NF2210266.

## References

  * Adam et al. [2021] Lukáš Adam, Rostislav Horčík, Tomáš Kasl, and Tomáš Kroupa.  Double oracle algorithm for computing equilibria in continuous games.  _AAAI Conference on Artificial Intelligence (AAAI)_ , 35:5070–5077, 2021.
  * Adamo and Matros [2009] Tim Adamo and Alexander Matros.  A Blotto game with incomplete information.  _Economics Letters_ , 105:100–102, 2009.
  * Bailey and Telgarsky [2018] Bolton Bailey and Matus Telgarsky.  Size-noise tradeoffs in generative networks.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , pages 6490–6500, 2018.
  * Balduzzi et al. [2018] David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel.  The mechanics of n-player differentiable games.  In _International Conference on Machine Learning (ICML)_ , volume 80, pages 354–363, 2018.
  * Baye et al. [1996] Michael R. Baye, Dan Kovenock, and Casper G. de Vries.  The all-pay auction with complete information.  _Economic Theory_ , 8:291–305, 1996.
  * Berahas et al. [2022] Albert S. Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg.  A theoretical and empirical comparison of gradient approximations in derivative-free optimization.  _Foundations of Computational Mathematics_ , 22:507–560, 2022.
  * Berger [2007] Ulrich Berger.  Brown’s original fictitious play.  _Journal of Economic Theory_ , 135:572–578, 2007.
  * Berner et al. [2019] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemysław Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al.  Dota 2 with large scale deep reinforcement learning.  _arXiv preprint arXiv:1912.06680_ , 2019.
  * Berry [1941] Andrew C. Berry.  The accuracy of the Gaussian approximation to the sum of independent variates.  _Transactions of the American Mathematical Society_ , 49:122–136, 1941.
  * Bichler and Kohring [2022] Martin Bichler and Stefan Heidekrüger Nils Kohring.  Learning equilibria in asymmetric auction games.  To appear in INFORMS Journal on Computing, 2022.
  * Bichler et al. [2021] Martin Bichler, Maximilian Fichtl, Stefan Heidekrüger, Nils Kohring, and Paul Sutterer.  Learning equilibria in symmetric auction games using artificial neural networks.  _Nature Machine Intelligence_ , 3:687–695, 2021.
  * Boix-Adserà et al. [2021] Enric Boix-Adserà, Benjamin L. Edelman, and Siddhartha Jayanti.  The multiplayer Colonel Blotto game.  _Games and Economic Behavior_ , 129:15–31, 2021.
  * Borel [1938] Émile Borel.  _Traité du calcul des probabilités et ses applications_ , volume IV of _Applications aux jeux des hazard_.  Gauthier-Villars, Paris, 1938.
  * Borel [1953] Émile Borel.  The theory of play and integral equations with skew symmetric kernels.  _Econometrica_ , 21:97–100, 1953.
  * Brown [1951] George W. Brown.  Iterative solutions of games by fictitious play.  In Tjalling C. Koopmans, editor, _Activity Analysis of Production and Allocation_ , pages 374–376. John Wiley & Sons, 1951.
  * Chen and Ankenman [2006] Bill Chen and Jerrod Ankenman.  _The Mathematics of Poker_.  ConJelCo, 2006.
  * Cho et al. [2014] Kyunghyun Cho, Bart van Merrienboer, Dzmitry Bahdanau, and Yoshua Bengio.  On the properties of neural machine translation: encoder-decoder approaches, 2014.
  * Clevert et al. [2016] Djork-Arné Clevert, Thomas Unterthiner, and Sepp Hochreiter.  Fast and accurate deep network learning by exponential linear units (ELUs).  In _International Conference on Learning Representations (ICLR)_ , 2016.
  * Cybenko [1989] G. Cybenko.  Approximation by superpositions of a sigmoidal function.  _Mathematics of Control, Signals and Systems_ , 2:303–314, 1989.
  * Dasgupta and Maskin [1986] P. Dasgupta and Eric Maskin.  The existence of equilibrium in discontinuous economic games.  _Review of Economic Studies_ , 53:1–26, 1986.
  * Daskalakis et al. [2018] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng.  Training GANs with optimism.  In _International Conference on Learning Representations (ICLR)_ , 2018.
  * Duchi et al. [2012] John C Duchi, Peter L Bartlett, and Martin J Wainwright.  Randomized smoothing for stochastic optimization.  _SIAM Journal on Optimization_ , 22(2):674–701, 2012.
  * Duchi et al. [2015] John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono.  Optimal rates for zero-order convex optimization: the power of two function evaluations.  _IEEE Transactions on Information Theory_ , 61:2788–2806, 2015.
  * Efron [1979] Bradley Efron.  Bootstrap methods: another look at the jackknife.  _The Annals of Statistics_ , 7:1–26, 1979.
  * Efron [1987] Bradley Efron.  Better bootstrap confidence intervals.  _Journal of the American Statistical Association_ , 82:171–185, 1987.
  * Feng et al. [2021] Ruili Feng, Deli Zhao, and Zheng-Jun Zha.  Understanding noise injection in GANs.  In _International Conference on Machine Learning (ICML)_ , volume 139, pages 3284–3293, 2021.
  * Fichtl et al. [2022] Maximilian Fichtl, Matthias Oberlechner, and Martin Bichler.  Computing Bayes Nash equilibrium strategies in auction games via simultaneous online dual averaging, 2022.
  * Fudenberg and Tirole [1991] Drew Fudenberg and Jean Tirole.  _Game theory_.  MIT Press, Cambridge, MA, 1991.  ISBN 0-262-06141-4.
  * Ganzfried [2021] Sam Ganzfried.  Algorithm for computing approximate Nash equilibrium in continuous games with application to continuous Blotto.  _Games_ , 12:47, 2021.
  * Ganzfried and Sandholm [2010a] Sam Ganzfried and Tuomas Sandholm.  Computing equilibria by incorporating qualitative models.  In _International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS)_ , 2010a.
  * Ganzfried and Sandholm [2010b] Sam Ganzfried and Tuomas Sandholm.  Computing equilibria by incorporating qualitative models.  Technical report, Carnegie Mellon University, 2010b.
  * Gemp and Mahadevan [2018] Ian Gemp and Sridhar Mahadevan.  Global convergence to the equilibrium of GANs using variational inequalities, 2018.
  * Gemp et al. [2022] Ian Gemp, Rahul Savani, Marc Lanctot, Yoram Bachrach, Thomas Anthony, Richard Everett, Andrea Tacchetti, Tom Eccles, and János Kramár.  Sample-based approximation of Nash in large many-player games via gradient descent.  In _Autonomous Agents and Multi-Agent Systems_ , pages 507–515, 2022\.
  * Ghosh and Kundu [2019] Papiya Ghosh and Rajendra P. Kundu.  Best-shot network games with continuous action space.  _Research in Economics_ , 73:225–234, 2019.
  * Glicksberg [1952] I. L. Glicksberg.  A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points.  _Proceedings of the American Mathematical Society_ , 3(1):170–174, 1952.
  * Goodfellow et al. [2014] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , volume 27, 2014.
  * Grnarova et al. [2019] Paulina Grnarova, Kfir Y. Levy, Aurelien Lucchi, Nathanael Perraudin, Ian Goodfellow, Thomas Hofmann, and Andreas Krause.  A domain agnostic measure for monitoring and evaluating GANs.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , volume 32, 2019.
  * Grnarova et al. [2021] Paulina Grnarova, Yannic Kilcher, Kfir Y. Levy, Aurelien Lucchi, and Thomas Hofmann.  Generative minimization networks: training GANs without competition, 2021.
  * Gross and Wagner [1950] Oliver Alfred Gross and R. A. Wagner.  _A continuous Colonel Blotto game_.  RAND Corporation, 1950.
  * He et al. [2015] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: surpassing human-level performance on ImageNet classification.  In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , 2015.
  * Heinrich et al. [2015] Johannes Heinrich, Marc Lanctot, and David Silver.  Fictitious self-play in extensive-form games.  In _International Conference on Machine Learning (ICML)_ , volume 37, pages 805–813, 2015.
  * Hochreiter and Schmidhuber [1997] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  _Neural Computation_ , 9:1735–1780, 1997.
  * Hornik [1991] Kurt Hornik.  Approximation capabilities of multilayer feedforward networks.  _Neural Networks_ , 4:251–257, 1991.
  * Hsieh et al. [2021] Ya-Ping Hsieh, Panayotis Mertikopoulos, and Volkan Cevher.  The limits of min-max optimization algorithms: convergence to spurious non-critical sets.  In _International Conference on Machine Learning (ICML)_ , volume 139, pages 4337–4348, 2021.
  * Huang et al. [2018] Chin-Wei Huang, David Krueger, Alexandre Lacoste, and Aaron Courville.  Neural autoregressive flows.  In _International Conference on Machine Learning (ICML)_ , volume 80, pages 2078–2087, 2018.
  * Kagel and Levin [1993] John H. Kagel and Dan Levin.  Independent private value auctions: bidder behaviour in first-, second- and third-price auctions with varying numbers of bidders.  _The Economic Journal_ , 103:868–879, 1993.
  * Kamra et al. [2017] Nitin Kamra, Fei Fang, Debarun Kar, Yan Liu, and Milind Tambe.  Handling continuous space security games with neural networks.  In _Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)_ , 2017.
  * Kamra et al. [2018] Nitin Kamra, Umang Gupta, Fei Fang, Yan Liu, and Milind Tambe.  Policy learning for continuous space security games using neural networks.  _AAAI Conference on Artificial Intelligence (AAAI)_ , 32, 2018.
  * Kamra et al. [2019] Nitin Kamra, Umang Gupta, Kai Wang, Fei Fang, Yan Liu, and Milind Tambe.  Deepfp for finding Nash equilibrium in continuous action spaces.  In _Decision and Game Theory for Security_ , pages 238–258, 2019\.
  * Korpelevich [1976] G. M. Korpelevich.  The extragradient method for finding saddle points and other problems.  _Ekonomika i Matematicheskie Metody_ , 12:747–756, 1976\.
  * Kovenock and Roberson [2011] Dan Kovenock and Brian Roberson.  A Blotto game with multi-dimensional incomplete information.  _Economics Letters_ , 113:273–275, 2011.
  * Kovenock and Roberson [2021] Dan Kovenock and Brian Roberson.  Generalizations of the General Lotto and Colonel Blotto games.  _Economic Theory_ , 71:997–1032, 2021.
  * Krishna [2002] Vijay Krishna.  _Auction theory_.  Academic Press, 2002.
  * Kroer and Sandholm [2015] Christian Kroer and Tuomas Sandholm.  Discretization of continuous action spaces in extensive-form games.  In _International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS)_ , 2015.
  * Kroupa and Votroubek [2021] T. Kroupa and T. Votroubek.  Multiple oracle algorithm for general-sum continuous games, 2021.
  * LeCun et al. [1989] Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel.  Backpropagation applied to handwritten zip code recognition.  _Neural Computation_ , 1:541–551, 1989.
  * LeCun et al. [1998] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86:2278–2324, 1998.
  * Leshno et al. [1993] Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken.  Multilayer feedforward networks with a nonpolynomial activation function can approximate any function.  _Neural Networks_ , 6:861–867, 1993.
  * Letcher et al. [2019] Alistair Letcher, David Balduzzi, Sébastien Racanière, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel.  Differentiable game mechanics.  _Journal of Machine Learning Research_ , 20:3032–3071, 2019\.
  * Li and Wellman [2021] Zun Li and Michael P. Wellman.  Evolution strategies for approximate solution of Bayesian games.  _AAAI Conference on Artificial Intelligence (AAAI)_ , 35:5531–5540, 2021.
  * Lisý and Bowling [2017] Viliam Lisý and Michael Bowling.  Eqilibrium approximation quality of current no-limit poker bots.  In _AAAI Computer Poker Workshop_ , 2017.
  * Lockhart et al. [2019] Edward Lockhart, Marc Lanctot, Julien Pérolat, Jean-Baptiste Lespiau, Dustin Morrill, Finbarr Timbers, and Karl Tuyls.  Computing approximate equilibria in sequential adversarial games by exploitability descent.  In _Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)_ , pages 464–470, 2019.
  * Lotker et al. [2008] Zvi Lotker, Boaz Patt-Shamir, and Mark R. Tuttle.  A game of timing and visibility.  _Games and Economic Behavior_ , 62:643–660, 2008.
  * Marchesi et al. [2020] Alberto Marchesi, Francesco Trovò, and Nicola Gatti.  Learning probably approximately correct maximin strategies in simulation-based games with infinite strategy spaces.  In _Autonomous Agents and Multi-Agent Systems_ , pages 834–842, 2020\.
  * Mazumdar et al. [2020] Eric Mazumdar, Lillian J. Ratliff, and S. Shankar Sastry.  On gradient-based learning in continuous games.  _SIAM Journal on Mathematics of Data Science_ , 2:103–131, 2020.
  * Mazumdar et al. [2019] Eric V. Mazumdar, Michael I. Jordan, and S. Shankar Sastry.  On finding local Nash equilibria (and only local Nash equilibria) in zero-sum games, 2019.
  * McCulloch and Pitts [1943] Warren S. McCulloch and Walter Pitts.  A logical calculus of the ideas immanent in nervous activity.  _The bulletin of mathematical biophysics_ , 5:115–133, 1943\.
  * McMahan et al. [2003] H. Brendan McMahan, Geoffrey J. Gordon, and Avrim Blum.  Planning in the presence of cost functions controlled by an adversary.  In _International Conference on Machine Learning (ICML)_ , pages 536–543, 2003.
  * Mertikopoulos and Zhou [2019] Panayotis Mertikopoulos and Zhengyuan Zhou.  Learning in games with continuous action sets and unknown payoff functions.  _Mathematical Programming_ , 173:465–507, 2019.
  * Mescheder et al. [2017] Lars Mescheder, Sebastian Nowozin, and Andreas Geiger.  The numerics of GANs.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , pages 1823–1833, 2017.
  * Milgrom and Segal [2014] Paul Milgrom and Ilya Segal.  Deferred-acceptance auctions and radio spectrum reallocation.  In _Proceedings of the ACM Conference on Economics and Computation (EC)_ , 2014.
  * Milgrom and Segal [2020] Paul Milgrom and Ilya Segal.  Clock auctions and radio spectrum reallocation.  _Journal of Political Economy_ , 128:1–31, 2020.
  * Milgrom and Weber [1985] Paul Milgrom and Robert Weber.  Distributional strategies for games with incomplete infromation.  _Mathematics of Operations Research_ , 10:619–632, 1985\.
  * Mokhtari et al. [2020] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil.  A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: proximal point approach.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , volume 108, pages 1497–1507, 2020.
  * Nesterov and Spokoiny [2017] Yurii Nesterov and Vladimir Spokoiny.  Random gradient-free minimization of convex functions.  _Foundations of Computational Mathematics_ , 17:527–566, 2017.
  * Padala et al. [2021] Manisha Padala, Debojit Das, and Sujit Gujar.  Effect of input noise dimension in GANs.  In _Neural Information Processing_ , pages 558–569, 2021.
  * Petersen [2006] Peter Petersen.  _Riemannian geometry_.  Springer, 2 edition, 2006.
  * Pinkus [1999] Allan Pinkus.  Approximation theory of the MLP model in neural networks.  _Acta Numerica_ , 8:143–195, 1999.
  * Rechenberg [1978] Ingo Rechenberg.  Evolutionsstrategien.  In _Simulationsmethoden in der medizin und biologie_ , pages 83–114. Springer, 1978.
  * Rechenberg and Eigen [1973] Ingo Rechenberg and M Eigen.  _Evolutionsstrategie: optimierung technischer systeme nach prinzipien der biologischen evolution_.  Frommann-Holzboog Stuttgart, 1973.
  * Rosen [1965] J. B. Rosen.  Existence and uniqueness of equilibrium points for concave n-person games.  _Econometrica_ , 33:520–534, 1965.
  * Rosenblatt [1958] F. Rosenblatt.  The perceptron: a probabilistic model for information storage and organization in the brain.  _Psychological Review_ , 65:386–408, 1958.
  * Rumelhart et al. [1986] David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams.  Learning representations by back-propagating errors.  _Nature_ , 323:533–536, 1986.
  * Salimans et al. [2017] Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever.  Evolution strategies as a scalable alternative to reinforcement learning, 2017.
  * Sandholm [2013] Tuomas Sandholm.  Very-large-scale generalized combinatorial multi-attribute auctions: Lessons from conducting $60 billion of sourcing.  In Zvika Neeman, Alvin Roth, and Nir Vulkan, editors, _Handbook of Market Design_. Oxford University Press, 2013.
  * Sard [1942] Arthur Sard.  The measure of the critical values of differentiable maps.  _Bulletin of the American Mathematical Society_ , 48:883–890, 1942.
  * Schwefel [1977] Hans-Paul Schwefel.  _Numerische optimierung von computer-modellen mittels der evolutionsstrategie_.  Birkhäuser Basel, 1977.
  * Shamir [2017] Ohad Shamir.  An optimal algorithm for bandit and zero-order convex optimization with two-point feedback.  _Journal of Machine Learning Research_ , 18:1–11, 2017\.
  * Smith [1974] John Maynard Smith.  The theory of games and evolution in animal conflict.  _Journal of Theoretical Biology_ , 47:209–221, 1974.
  * Spall [1992] James C. Spall.  Multivariate stochastic approximation using a simultaneous perturbation gradient approximation.  _IEEE Transactions on Automatic Control_ , 37:332–341, 1992\.
  * Spall [1997] James C. Spall.  A one-measurement form of simultaneous perturbation stochastic approximation.  _Automatica_ , 33:109–112, 1997.
  * Szentes and Rosenthal [2003a] Balazs Szentes and Robert W. Rosenthal.  Beyond chopsticks: symmetric equilibria in majority auction games.  _Games and Economic Behavior_ , 45(2):278–295, 2003a.
  * Szentes and Rosenthal [2003b] Balázs Szentes and Robert W. Rosenthal.  Three-object two-bidder simultaneous auctions: chopsticks and tetrahedra.  _Games and Economic Behavior_ , 44:114–133, 2003b.
  * Timbers et al. [2022] Finbarr Timbers, Nolan Bard, Edward Lockhart, Marc Lanctot, Martin Schmid, Neil Burch, Julian Schrittwieser, Thomas Hubert, and Michael Bowling.  Approximate exploitability: learning a best response.  In _Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)_ , pages 3487–3493, 2022.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , volume 30, 2017.
  * Vinyals et al. [2015] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly.  Pointer networks.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , volume 28, 2015.
  * Vinyals et al. [2019] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al.  Grandmaster level in StarCraft II using multi-agent reinforcement learning.  _Nature_ , 575(7782):350–354, 2019.
  * Washburn [2013] Alan Washburn.  OR forum - Blotto politics.  _Operations Research_ , 61:532–543, 2013.
  * Werbos [1988] Paul J. Werbos.  Generalization of backpropagation with application to a recurrent gas market model.  _Neural networks_ , 1:339–356, 1988.
  * Wierstra et al. [2008] Daan Wierstra, Tom Schaul, Jan Peters, and Juergen Schmidhuber.  Natural evolution strategies.  In _2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence)_ , pages 3381–3387, 2008.
  * Wierstra et al. [2014] Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber.  Natural evolution strategies.  _Journal of Machine Learning Research_ , 15:949–980, 2014\.
  * Yi et al. [2009] Sun Yi, Daan Wierstra, Tom Schaul, and Jürgen Schmidhuber.  Stochastic search using the natural gradient.  In _International Conference on Machine Learning (ICML)_ , pages 1161–1168, 2009.
  * Zinkevich et al. [2007] Martin Zinkevich, Michael Bowling, Michael Johanson, and Carmelo Piccione.  Regret minimization in games with incomplete information.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2007.

##  Appendix A Best response computation for continuous Colonel Blotto game

Approximate best responses can be computed for the continuous Colonel Blotto
game without discretizing the action space [Ganzfried, 2021]. By sampling $K$
batches of actions from other players’ strategies, we can obtain an
approximate best response $a_{i}$ for player $i$ using a mixed-integer linear
program (MILP). More precisely, let $h_{jk}$ be the highest bid for $j$ from
other players in batch $k$. Solve the following MILP:

maximize
$\displaystyle\textstyle\sum_{j}v_{ij}\tfrac{1}{K}\textstyle\sum_{k}z_{jk}$
(3) over $\displaystyle a_{i}\in\mathbb{R}^{J}$ (4) $\displaystyle
z\in\\{0,1\\}^{J\times K}$ (5) subject to $\displaystyle a_{ij}\geq
0\quad\forall j$ (6) $\displaystyle\textstyle\sum_{j}a_{ij}=b_{i}$ (7)
$\displaystyle z_{jk}=[a_{ij}\geq h_{jk}]\quad\forall j,k$ (8)

We can use the Big M method to represent the last constraint:

$\displaystyle a_{ij}-h_{jk}+M(1-z_{jk})\geq 0$ (9)

where $M\gg 0$, which forces $z_{jk}$ to be 0 when $a_{ij}-h_{jk}$ is
negative.

##  Appendix B Additional information about auctions

Table 1 describes the independent private values, common values, affiliated
values, complete information, and asymmetric information auctions, in that
order.

$\Omega$ | $\tau_{i}(\omega)$ | $v_{i}(\omega)$
---|---|---
$[0,1]^{n}$ | $\omega_{i}$ | $\omega_{i}$
$[0,1]^{n+1}$ | $\omega_{i}\omega_{n+1}$ | $\omega_{n+1}$
$[0,1]^{n+1}$ | $\omega_{i}+\omega_{n+1}$ | $\omega_{n+1}+\tfrac{1}{n}\textstyle\sum_{i=1}^{n}\omega_{i}$
$[0,1]$ | $\omega$ | $\omega$
$[0,1]$ | $\omega[i=1]$ | $\omega$
Table 1: Auction descriptions. All use $\mu=\mathcal{U}(\Omega)$.

For the common values auction, also known as the “mineral rights” model
[Krishna, 2002, example 6.1], the following procedure can be used to sample
$\omega\mid o_{i}$:

$\displaystyle z$ $\displaystyle\sim\mathcal{U}([0,1])$ (10)
$\displaystyle\omega_{n+1}$ $\displaystyle=o_{i}^{z}$ (11)
$\displaystyle\omega_{i}$ $\displaystyle=o_{i}\mathbin{/}\omega_{n+1}$ (12)
$\displaystyle\omega_{j}$ $\displaystyle\sim\mathcal{U}([0,1])\qquad j\neq i$
(13)

For the affiliated values auction [Krishna, 2002, example 6.2], the following
procedure can be used to sample $\omega\mid o_{i}$:

$\displaystyle\omega_{n+1}$
$\displaystyle\sim\mathcal{U}(\max\\{0,o_{i}-1\\},\min\\{1,o_{i}\\})$ (14)
$\displaystyle\omega_{i}$ $\displaystyle=o_{i}-\omega_{n+1}$ (15)
$\displaystyle\omega_{j}$ $\displaystyle\sim\mathcal{U}([0,1])\qquad j\neq i$
(16)

The all-pay auction with independent private values has a pure symmetric
equilibrium generated by:

$\displaystyle a_{i}$ $\displaystyle=\tfrac{n-1}{n}(o_{i})^{n}$ (17)

The $k$th-price winner-pay auction with independent private values has a pure
symmetric equilibrium generated by [Kagel and Levin, 1993, p. 878]:

$\displaystyle a_{i}$ $\displaystyle=\tfrac{n-1}{n+1-k}o_{i}$ (18)

The 3-player 2nd-price winner-pay auction with common values has a pure
symmetric equilibrium generated by [Bichler et al., 2021]:

$\displaystyle a_{i}$ $\displaystyle=\tfrac{o_{i}}{2+\tfrac{1}{2}o_{i}}$ (19)

The 2-player 1st- and 2nd-price winner-pay auction with affiliated values have
pure symmetric equilibria generated by, respectively [Bichler et al., 2021]:

$\displaystyle a_{i}$ $\displaystyle=\tfrac{2}{3}o_{i}$ (20) $\displaystyle
a_{i}$ $\displaystyle=o_{i}$ (21)

##  Appendix C Other equilibrium-finding dynamics

We tested a broad set of equilibrium-finding dynamics. This section describes
those dynamics. Let $\xi$ denote the _simultaneous gradient_ of the utilities
with respect to the parameters of the respective players only:
$\xi_{i}=\nabla_{i}u_{i}$. This is a vector field on the strategy profile
space. In general, it is not conservative (the gradient of some potential).
This is the primary source of difficulties in applying standard gradient-based
optimization methods, since trajectories can cycle around fixed points rather
than converge to them. Various algorithms have been proposed in the literature
to address this. These include the following:

  1. 1.

Simultaneous gradient:

$\displaystyle x^{t+1}=x^{t}+\alpha\xi(x^{t})$ (22)

  2. 2.

Extragradient [Korpelevich, 1976]:

$\displaystyle x^{t+1}=x^{t}+\alpha\xi(x^{t}+\beta\xi(x^{t}))$ (23)

  3. 3.

Optimistic gradient [Daskalakis et al., 2018, Mokhtari et al., 2020]:

$\displaystyle x^{t+1}=x^{t}+\alpha\xi(x^{t})+\beta(\xi(x^{t})-\xi(x^{t-1}))$
(24)

  4. 4.

_Consensus optimization (CO)_ [Mescheder et al., 2017]:

$\displaystyle x^{t+1}$
$\displaystyle=x^{t}+\alpha(\xi-\beta\nabla\tfrac{1}{2}\|\xi\|^{2})(x^{t})$
(25) $\displaystyle=x^{t}+\alpha(\xi-\beta\xi\cdot\nabla\xi)(x^{t})$ (26)

  5. 5.

_Symplectic gradient adjustment (SGA)_ [Balduzzi et al., 2018, Gemp and
Mahadevan, 2018, Letcher et al., 2019]:

$\displaystyle x^{t+1}$
$\displaystyle=x^{t}+\alpha(\xi-\beta\xi\cdot(\nabla\xi)_{\mathrm{A}})(x^{t})$
(27)

where $M_{\mathrm{A}}=\tfrac{1}{2}(M-M^{\top})$ is the antisymmetric part of
$M$. CO and SGA are second-order methods, meaning they require access to the
second derivatives of the utility functions. CO can converge to bad critical
points even in simple cases where the ‘game’ is to minimize a single function.
Thus it cannot be considered a candidate algorithm for finding stable fixed
points in general games, since it fails in the basic case of potential games
[Letcher et al., 2019, p. 13]. SGA was created to address some of the
shortcomings of CO.

##  Appendix D Analytically-derived equilibria of the benchmark games

We carefully selected the benchmark games to be ones for which an
analytically-derived equilibrium exists, so that we can compare the
computationally-derived equilibria to the analytical one. In this section, we
illustrate the analytical equilibria to support that comparison.

Figure 13 illustrates the analytical solution for the continuous Colonel
Blotto game with fixed homogeneous budgets and valuations. This game was
analyzed by Gross and Wagner [1950], who also analyzed the game for various
special cases of heterogeneous budgets and valuations. They give the following
geometric description of the equilibrium strategy: “[The player] inscribes a
circle within [the triangle] and erects a hemisphere upon this circle. He next
chooses a point from a density uniformly distributed over the surface of the
hemisphere and projects this point straight down into the plane of the
triangle… He then divides his forces in respective proportion to the
triangular areas subtended by [this point] and the sides.”

Figure 13: Continuous Colonel Blotto game solution.

Figure 14 illustrates the analytical solution for the all-pay complete
information auction. This game was analyzed by Baye et al. [1996]. They show
that with homogeneous valuations ($v_{1}=v_{2}=\ldots=v_{n}$) there exists a
unique symmetric equilibrium and a continuum of asymmetric equilibria. All of
these equilibria are payoff equivalent, as is the expected sum of the bids
(revenue to the auctioneer). In the symmetric equilibrium, each player
randomizes uniformly on $[0,v_{1}]$.

Figure 14: Complete-information auction solution.

Figure 15 illustrates the analytical solution for the 2-player 1st-price
winner-pay asymmetric-information auction. This game was analyzed by Krishna
[2002, section 8.3]. Bidder 1 bids according to the strategy
$\beta(v)=\operatorname{E}[V\mid V\leq v]$. In our case,
$V\sim\mathcal{U}([0,1])$, so $\beta(v)=\tfrac{v}{2}$. Bidder 2 chooses a bid
at random from the interval $[0,\operatorname{E}[V]]$ according to the
distribution defined by $H(b)=\operatorname{P}[\beta(V)\leq b]$. In our case,
this reduces to the distribution $\mathcal{U}([0,\tfrac{1}{2}])$.

Figure 15: Asymmetric-information auction solution.

Figure 16 illustrates the analytical solution for the chopstick auction. This
game was analyzed by Szentes and Rosenthal [2003b, a], who state the
following: “The supports of the mixtures that generate the symmetric
equilibria in both the first- and second-price cases, turn out to be the
surfaces of regular tetrahedra, and the distributions themselves turn out to
be uniform on these surfaces. In addition, in each case all the points inside
the tetrahedron are pure best responses to the equilibrium mixture.”

Figure 16: Chopstick auction solution.

Figure 17 illustrates the analytical solution for the 2-player visibility
game. This game was analyzed by Lotker et al. [2008]. Up to a set of measure
zero, it has a unique equilibrium whose strategies have probability densities
$p(x)=1/(1-x)$ when $0\leq x\leq 1-1/\mathrm{e}$ and 0 otherwise. Each
player’s expected payoff is $1/\mathrm{e}$.

Figure 17: Visibility game solution.