# Sampling Equilibria: Fast No-Regret Learning in Structured Games

Daniel Beaglehole Department of Computer Science and Engineering, UCSD, CA
92092. Email<EMAIL_ADDRESS>Max Hopkins Department of Computer Science
and Engineering, UCSD, CA 92092. Email<EMAIL_ADDRESS>Supported by
NSF Award DGE-1650112. Daniel Kane Department of Computer Science and
Engineering / Department of Mathematics, UCSD, California, CA 92092. Email:
<EMAIL_ADDRESS>Supported by NSF Award CCF-1553288 (CAREER) and a Sloan
Research Fellowship. Sihan Liu Department of Computer Science and Engineering,
UCSD, CA 92092. Email<EMAIL_ADDRESS>Shachar Lovett Department of Computer
Science and Engineering, UCSD, CA 92092. Email<EMAIL_ADDRESS>Supported
by NSF Award CCF-1953928.

###### Abstract

Learning and equilibrium computation in games are fundamental problems across
computer science and economics, with applications ranging from politics to
machine learning. Much of the work in this area revolves around a simple
algorithm termed _randomized weighted majority_ (RWM), also known as “Hedge”
or “Multiplicative Weights Update,” which is well known to achieve
statistically optimal rates in adversarial settings (Littlestone and Warmuth
’94, Freund and Schapire ’99). Unfortunately, RWM comes with an inherent
computational barrier: it requires maintaining and sampling from a
distribution over all possible actions. In typical settings of interest the
action space is exponentially large, seemingly rendering RWM useless in
practice.

In this work, we refute this notion for a broad variety of _structured_ games,
showing it is possible to efficiently (approximately) sample the action space
in RWM in _polylogarithmic_ time. This gives the first efficient no-regret
algorithms for problems such as the _(discrete) Colonel Blotto game_ ,
_matroid congestion_ , _matroid security_ , and basic _dueling games_. As an
immediate corollary, we give a polylogarithmic time meta-algorithm to compute
approximate Nash Equilibria for these games that is exponentially faster than
prior methods in several important settings. Further, our algorithm is the
first to efficiently compute equilibria for more involved variants of these
games with general sums, more than two players, and, for Colonel Blotto,
multiple resource types.

###### Contents

  1. 1 Introduction
    1. 1.1 Results
      1. 1.1.1 The Colonel Blotto Game
      2. 1.1.2 Congestion Games
      3. 1.1.3 Security Games
      4. 1.1.4 Dueling Games
    2. 1.2 Techniques
      1. 1.2.1 Sampling via Dynamic Programming
      2. 1.2.2 MCMC-methods
    3. 1.3 Discussion
      1. 1.3.1 Dynamic Programming vs MCMC-sampling
      2. 1.3.2 Further Open Problems
    4. 1.4 Further Related Work
      1. 1.4.1 No-regret learning with structured loss
      2. 1.4.2 Computing equilibra for Colonel Blotto
  2. 2 Preliminaries
    1. 2.1 Game Theory
    2. 2.2 Linear Hypergraph Game
    3. 2.3 No-Regret Learning in Games
    4. 2.4 Randomized Weighted Majority Algorithm
  3. 3 Playing Games via MCMC-Sampling
    1. 3.1 Glauber Dynamics and Fractionally Log-Concave Games
    2. 3.2 Dueling Games and the JSV Chain
  4. 4 Playing Games via DP-Sampling
    1. 4.1 Sampling via estimation of partition function
    2. 4.2 Computing the Partition Function
    3. 4.3 Applications of the meta algorithm
    4. 4.4 Multi-resource allocation games
  5. A No-regret Learning and Equilibrium Computation
  6. B Bit-complexity and Stability of Numeric Operations
  7. C Implementing Glauber Dynamics

##  1 Introduction

Online learning and equilibrium computation in games has long played a major
role in our understanding of human behavior and general multi-agent systems,
with applications ranging all the way from politics [15, 48] and national
defense [69] to complexity theory [30, 65] and machine learning [34, 35, 2].
Perhaps the most celebrated line of work in this area is the introduction and
analysis of randomized weighted-majority (RWM) and its ‘mixed’ variant
(Optimistic) Hedge [54, 34, 64, 28]. These powerful algorithms allow players
to engage in repeated gameplay _without regret_ , in the sense that the
overall loss experienced by any player is not much more than that of the best
fixed strategy, even against an arbitrary, adaptive adversary. Such a
guarantee is not only powerful in its own right, but is also known to converge
quickly to equilibria when performed by all players in repeated rounds of play
[22].

Randomized weighted majority is a surprisingly simple algorithm given its
powerful guarantees. In each round of a repeated game, a player following RWM
samples a strategy $s$ with probability proportional to its (exponentiated)
historical loss $\ell(s)$:

$\Pr[\text{Player chooses $s$}]\propto\beta^{\ell(s)}$ (1)

for some specified ‘learning rate’ $\beta\in(0,1)$. RWM is also well studied
in the setting where the player ‘plays’ the distribution itself (typically
called a mixed strategy), and experiences its expected loss. This variant,
called Hedge, is perhaps the best studied algorithm in all of learning in
games [34, 22].

Unfortunately, while RWM and Hedge are _statistically_ optimal [54, 34], they
come with an inherent computational barrier: both techniques crucially rely on
tracking a distribution over all possible actions. Since the number of actions
is typically exponential in the relevant parameters of the game (e.g. in the
famous Colonel Blotto problem), this seems to render both Hedge and RWM
completely infeasible.

It turns out, however, that this intuition is not entirely correct. In many
important settings the distributions that arise from RWM are highly
structured, and while it still may not be possible to efficiently output the
distribution itself as in Hedge, it is sometimes possible to efficiently
sample from it. It is known, for instance, that RWM can be implemented in
polylogarithmic time when actions are given by the $k$-edges of a complete
hypergraph and rewards decompose linearly over vertices [76]. This raises an
important question:

_When is it possible to efficiently sample in Randomized Weighted Majority?_

Toward this end, we introduce a natural generalization of the complete
hypergraph setting we call _linear hypergraph games_ , where actions are given
by $k$-edges of an arbitrary hypergraph, and the reward of any edge similarly
decomposes as a sum over individual reward functions on its vertices (see
Section 2.2 for more detail). This simple definition captures a surprising
number of settings studied in the literature including resource allocation
problems like Colonel Blotto [18], along with other widely-studied settings
such as congestion [63], security [69, 5, 68, 14], and basic dueling games
[41, 5].

In this work, we show it is indeed possible to efficiently (approximately)
sample from RWM over several important subclasses of linear hypergraph games
including Colonel Blotto and its variants, matroid congestion [72], matroid
security [69, 5, 68, 14], and basic dueling games [41, 5]. This leads to the
first algorithms for no-regret learning in these settings that are
_polylogarithmic_ in the size of the state space, and thereby the first
polylogarithmic time algorithms for (approximate) equilibrium computation. On
top of giving an exponential improvement over prior results, this also
constitutes the first efficient algorithm for equilibrium computation
whatsoever in several more involved settings such as dice games, Colonel
Blotto with multiple resources, and for multiplayer and general-sum variants
of all games we consider. These results are (informally) summarized in Table
1.

Our techniques are largely based on two main paradigms: dynamic programming,
and Monte Carlo Markov Chains (MCMC). Generalizing seminal work on learning
$k$-sets and other structured concepts [76, 51], we show that the
distributions arising from RWM on linear hypergraph games correspond to well-
studied structure in approximate sampling and statistical physics called
_external fields_. In resource allocation games like Colonel Blotto that are
played over (ordered) fixed-size partitions of $n$, we exploit this structure
to build a dynamic program that approximately computes the normalization
factor of Equation 1 (often called the partition function). On the other hand,
in settings like matroid congestion and security, we rely on deep results from
the MCMC-sampling literature showing that any hypergraph that is a
sufficiently good high dimensional expander can be sampled under arbitrary
external fields [9, 1, 6]. To the authors’ knowledge, these are the first
applications of approximate sampling techniques to game theory.

Game | Known runtime (exact) | Our runtime (apx.)
---|---|---
(Discrete) Colonel Blotto |  $n^{13}k^{14}$ [5] | $k^{4}\log^{4}(n)$
Dice | NA | $k^{4}\log^{4}(n)$
Matroid Security |  $n^{4}k^{2}$ [14] | $k^{3}\log^{3}(n)$
Matroid Congestion |  $nk$ [11] | $k^{4}\log^{3}(n)$
Ranking Duel |  $n^{12}$ [41] 111This work did not give a runtime for their linear program. Here we naïvely apply the bound for ellipsoid method from [56]. The work of [5] can also be applied in this setting, but is largely geared towards being more general than more efficient (and also does not list a runtime). | $n^{9}$
Table 1: Rough asymptotic runtimes for equilibrium computation in contrast to
previous methods with two players. Approximation factor and maximum reward are
set to $O(1)$ along with some other game specific parameters (See Definition
3.7 for details).

###  1.1 Results

We briefly review the theory of games, equilibria, and no-regret learning
before discussing our results in more formality. Games are mathematical
objects that model (possibly non-cooperative) interaction between rational
agents. A (simultaneous) game consists of a set of actions $A_{i}$ for each
player, and reward functions $R_{i}$ mapping action tuples to rewards (real
numbers). Players seek to maximize their own reward, and optimal play is
typically characterized by Nash equilibria: randomized strategies such that no
player can improve by deviating. By the historic result of [59], every finite
game has at least one NE. As they are not always efficiently computable [29],
one often instead hopes to understand weaker notions such as Coarse Correlated
Equilibria (CCE), where the strategies of different players are chosen in
coordination with one another (see Section 2.1).

There is a deep connection between equilibrium computation and no-regret
learning in games. We consider the typical adaptive online setting in which,
in each round, a learner chooses an action and receives an adversarially
selected loss that may depend on the learner’s previous actions (see [22,
Chapter 4]). An algorithm is said to have “no-regret” when the expected loss
suffered by the learner in sequential rounds grows sublinearly compared to the
loss of the best fixed action in hindsight. No-regret learning is itself a
powerful tool, as it allows for optimal play against sub-optimal opponents
(unlike equilibria which only model the setting where all agents play
optimally). Furthermore, it is well known that any no-regret
algorithm222Formally we may need to require that a players strategy depends
only on the opponents history and not their own [22]. This is satisfied by all
algorithms considered in this work. leads to approximate equilibrium
computation with similar runtime simply by simulating the algorithm for all
players for sufficiently many rounds. RWM, for instance, is well-known to
satisfy the following (optimal) regret guarantee.

######  Lemma 1.1 (RWM is No-Regret [22, Lemma 4.1]).

The regret of RWM over $T$ rounds, $N$ actions, and with rewards in
$[-L_{\max},L_{\max}]$, satisfies

$\operatorname{Reg}_{T}\leq O\left(L_{\max}\sqrt{T\log(N)}\right),$

against any adaptive adversary (with high probability).

In fact, it is important to note in our setting that essentially all
guarantees of RWM also hold in the approximate regime, where the learner only
$\delta$-approximately samples from the distribution in Equation 1 in each
round (in Total Variation distance). We call such algorithms
$\delta$-approximate RWM ($\delta$-RWM). It is not hard to show that
$\delta$-RWM also satisfies the above regret guarantees for small enough
$\delta$ (see Lemma 2.10). We now cover four of the main settings in which we
give new algorithms for no-regret learning and equilibrium computation through
efficient implementatin of $\delta$-RWM: Colonel Blotto, Matroid Security,
Matroid Congestion, and Dueling games. We note that all results are given in
the algebraic computation model for simplicity (where algebraic operations
such as addition and subtraction are considered to be unit time), but can
easily be moved to the standard bit model with no substantial loss in running
time (see Appendix B).

####  1.1.1 The Colonel Blotto Game

The Colonel Blotto game was originally described by Borel in 1921 [18] and
formalizes how warring colonels should distribute soldiers over different
battlefields. In the most general version of this game, two colonels have
$n_{1}$ and $n_{2}$ soldiers that they must assign to $k$ different
battlefields, each with a non-negative integer weight. A colonel wins a battle
(receiving its weight in reward) if they assign more armies to that battle
than their opponent. Each colonel seeks to maximize the total weight of
battles won in a single assignment.

Despite its breadth of applications and simplicity to state, the first
polynomial time algorithm to compute optimal strategies for this game was only
developed recently in [5]. This breakthrough result deservedly received
significant media attention [42, 57], but struggled to see any practical use
due to an infeasible $O(n^{13}k^{14})$ running time (where
$n=\max\\{n_{1},n_{2}\\}$). To this day, this is the only known algorithm to
provably compute exact optimal strategies for the (discrete) Colonel Blotto
game with arbitrary parameters in polynomial time. Though some progress has
been made towards more practical algorithms in different settings [16], even
these methods cannot handle parameters beyond a few hundred troops [74].

Indeed, solving the Colonel Blotto problem is now only more relevant than it
was in 1921, with practical applications in a large swath of market
competitions including advertising and auctions [62], budget allocation [50],
elections [53], and even ecological modeling [36]. We give the first no-regret
learning algorithm for the Colonel Blotto games under the most general setting
[49], where rewards are heterogeneous across battles and players and different
players are allowed different troop capacities. Moreover, our algorithm runs
in time polylogarithmic in the state space, making it extremely efficient in
the regime where $n\gg k$ (i.e. there are many more troops than battlefields).

######  Theorem 1.2 (Blotto without Regret (Informal Corollary 4.9)).

In a Colonel Blotto game, for a player with $n$ soldiers, $k$ battlefields,
and maximum reward bounded by $L_{\max}$, $\delta$-RWM can be implemented over
$T$ rounds of play in time:

$\widetilde{O}\left(T^{3}L_{\max}k\log(n)\delta^{-1}\right),$

and is no-regret. In the regime where $n=O(k^{2})$, we give a faster algorithm
running in time $\widetilde{O}(Tnk)$.

Theorem 1.2 is the first no-regret algorithm for Colonel Blotto in online
adaptive settings, and also gives the fastest known algorithms to compute
(approximate) Nash equilibria provided the game is zero-sum, and approximate
coarse correlated equilibrium in general sum settings with many players. We
state the theorem for the two-player zero-sum setting here.

######  Corollary 1.3 (Equilibrium Computation for Blotto (informal Corollary
4.10)).

Let $n=\max(n_{1},n_{2})$, where $n_{1},n_{2}$ are the soldier counts for the
two player Colonel Blotto game. Let $L_{\max}$ be maximum reward of the game.
There exists an algorithm to compute an $\varepsilon$-approximate Nash
equilibrium for the two-player Colonel Blotto Game in time

$\widetilde{O}\left(L_{\max}^{7}k^{4}\log^{4}(n)\varepsilon^{-6}\right)$

with high probability. When $n=O(k^{2})$, we give a faster algorithm running
in time $\widetilde{O}(nk^{2}L_{\max}^{2}\varepsilon^{-2})$.

Not only is this algorithm exponentially faster than any prior work in most
relevant scenarios (namely when $n\gg k$), it is also the first known method
for computing CCE for multiplayer Blotto at all. Even more generally, our
algorithm extends to a number of other variants of Blotto (or ‘resource
allocation’ problems) such as Dice games and settings with multiple types of
troops known as the Multi-resource Colonel Blotto problem [16] (though in this
latter setting we lose the logarithmic dependence on $n$). We cover these
further applications in Section 4.3 and Section 4.4.

####  1.1.2 Congestion Games

Another natural example is a congestion game, a class introduced by Rosenthal
[63] to model resource competition among greedy players. In a congestion game,
$m$ players compete to select from a set of $n$ resources and receive rewards
depending on how many players chose a particular resource. Classical examples
of congestion games include routing traffic (pick the least congested route)
and variants of the famed El Farol Bar Problem [10] (players aim to choose a
bar that is neither too under nor over-crowded).

Unlike Blotto, equilibrium computation is known to be hard for congestion
games, namely (PPAD $\cap$ PLS)-complete [19]. However, this can be
circumvented when the underlying strategy spaces are sufficiently
combinatorially structured. It has long been known, for instance, that a Nash
equilibrium can be found in time $\widetilde{O}(m^{2}nqk)$ via iterated best-
response when all strategies are given by the bases of a rank-$k$
matroid333Matroid bases can be thought of as a generalization of the
combinatorial properties enjoyed by spanning trees, see Section 3.1 for
details. over $n$ resources of $q$ types [11]. We show matroid congestion
games are similarly well-behaved under RWM, and provide a near-optimal no-
regret algorithm in both a computational and statistical sense.

######  Theorem 1.4 (Congestion without Regret (informal Corollary 3.10)).

Let $\mathcal{I}=\\{\\{A_{i}\\}_{i=1}^{m},c\\}$ be a congestion game over a
size-$n$ ground set $\Omega$ with $q$ resource types where each $A_{i}$ is the
set of bases of a rank-$k$ matroid. Then $\delta$-RWM can be implemented for
$T$ rounds in time

$\widetilde{O}\left(kT\log(n)\log(\delta^{-1})(q+kmT)\right),$

and is no-regret.

To our knowledge, this is the first efficient no-regret algorithm for matroid
congestion. Moreover, in the setting where there are $\text{polylog}(n)$
resource types, the algorithm leads to exponentially faster (approximate)
equilibrium computation than the typical best response strategy (albeit for
CCE rather than Nash).

######  Corollary 1.5 (Equilibrium Computation for Congestion (informal
Corollary 3.11)).

Let $\mathcal{I}=\\{(A_{i},R_{i})_{i=1}^{m}\\}$ be a congestion game over a
size-$n$ ground set $\Omega$ with $q$ resource types where each $A_{i}$ is the
set of bases of a rank-$k$ matroid. Then there exists an algorithm to compute
an $\varepsilon$-CCE in time

$\widetilde{O}\left(m^{2}L_{\max}^{4}k^{4}\log^{3}(n)\varepsilon^{-4}+qmL_{\max}^{2}k^{2}\log^{2}(n)\varepsilon^{-2}\right)$

with high probability.

####  1.1.3 Security Games

While slightly less intuitive, games modeling security also fit within the
resource allocation paradigm. Security games are a basic two-player setting
modeling the behavior of a limited-resource player defending $n$ targets, and
an adversarial attacker. Each target in the game has a cost to defend, and a
“$k$-resource” defender may choose a (possibly restricted) $k$-set to defend.
Similarly, each target has a cost to attack, and the attacker chooses a single
element, receiving a reward depending on whether or not the selected target
was defended by the opponent. Depending on the cost/reward structure, security
games model several real-world scenarios, ranging from allocating defensive
resources at military checkpoints to choosing a path to transmit critical
resources (in the latter the attacker actually wins if they attack a
‘defended’ node). Indeed, security games have actually seen significant use in
critical real-life infrastructure such as checkpoint placements at LAX and US
Coast Guard and Federal Air Marshal Service patrol schedules [69].

Given their practical importance, it is no surprise equilibrium computation is
well-studied in the security game setting [69, 5, 68, 14], and polynomial time
algorithms are known in several settings, notably including when allocation
constraints are given by matroid bases [68, 14]. Unfortunately, as is the case
in previous work on Blotto, known algorithms are not practically useful and
have large polynomial factors in the number of targets. We take a major step
toward resolving this issue by showing $\delta$-RMW can be implemented in time
polylogarithmic in $n$, an exponential improvement over prior techniques [69,
68, 14].

######  Theorem 1.6 (Security without Regret (Informal Corollary 3.13)).

Let $\mathcal{I}$ a security game over the bases of a rank-$k$ matroid over
$n$ targets with $q$ distinct defender costs. Then $\delta$-RMW can be
implemented for $T$ rounds in time

$\widetilde{O}(kT\log(n)\log(\delta^{-1})(q+T)),$

and is no-regret.

######  Corollary 1.7 (Equilibrium Computation for Security (Informal
Corollary 3.14)).

Let $\mathcal{I}$ be a security game over the bases of a rank-$k$ matroid over
$n$ targets with $q$ distinct attacker and defender costs. Then it is possible
to compute an $\varepsilon$-CCE in time

$\widetilde{O}\left(L_{\max}^{4}k^{3}\log^{3}(n)\varepsilon^{-4}+qL_{\max}^{2}k^{2}\log^{2}(n)\varepsilon^{-2}\right).$

If the game is zero-sum, the resulting strategy is $\varepsilon$-Nash.

####  1.1.4 Dueling Games

Finally, we make a slight departure from the resource allocation framework to
consider the popular class of dueling games studied in [41, 5]. Dueling games
model competitive optimization between two players over a randomized set of
events. We will focus our attention on one of the simplest dueling games
called ranking duel (also known as the ‘Search Engine game’) where two players
compete to rank $n$ elements over a known distribution $\mu$, and win a round
if they rank $x\sim\mu$ higher than the opponent. This classically models the
problem of search engines competing to optimize a page ranking given a known
distribution over searches.

Equilibrium computation is well-studied in dueling games, and algorithms are
known in a few settings via a mix of bilinear embedding techniques and
reduction to non-competitive optimization [41, 5]. As in previous settings,
however, the algorithms are too slow to be of practical use. In contrast, we
focus our attention only on the basic ranking duel, but give both a faster
algorithm and a novel no-regret guarantee over the original space.

######  Theorem 1.8 (Dueling without Regret (Informal Corollary 3.19)).

Let $\mathcal{I}$ be an instance of ranking duel. Then $\delta$-RMW can be
implemented for $T$ rounds in time

$\widetilde{O}(T^{2}n^{7}\log(\delta^{-1})),$

and is no-regret.

######  Corollary 1.9 (Equilibrium Computation for Ranking Duel (Informal
Corollary 3.20)).

Let $\mathcal{I}$ be an instance of ranking duel. Then it is possible to
compute an $\varepsilon$-CCE in time

$\widetilde{O}(n^{9}\varepsilon^{-4}).$

If the game is zero-sum, the resulting strategy is $\varepsilon$-Nash.

While a running time of $O(n^{9})$ can hardly be claimed as practical, the
broader technique used in this result has the eventual possibility of running
in near-linear time. We discuss this further in Section 1.3.

###  1.2 Techniques

At their core, our results all stem from the ability to approximately sample
distributions arising from randomized weighted majority on various linear
hypergraph games. Recall that RWM maintains a mixed strategy, which we denote
as the RWM distribution, whose probabilities are proportional to their
(exponentiated) total historical loss (negative reward):

$\forall x\in A_{i}:\Pr(x)\propto\beta^{\ell^{T}(x)}$ (2)

where $\ell^{T}(x)$ is the total loss experienced by pure strategy $x$ up to
round $T$. As discussed earlier in the section, we typically cannot hope to
maintain this distribution explicitly, but it may still be possible to sample
from it in polylogarithmic time. Furthermore, while sampling such a
distribution exactly is a challenging task (and very few such algorithms are
known), _approximate_ sampling is perfectly sufficient in our setting. Indeed,
our approximate variant $\delta$-RWM satisfies essentially the same guarantees
as RWM itself.

######  Lemma 1.10 ($\delta$-RWM is No-Regret (Lemma 2.10)).

$\delta$-RWM over $N$ actions has

$Reg(T)\leq O\left(L_{\max}\sqrt{T\log N}+\delta L_{\max}T\right)$

expected regret, where $L_{\max}$ is the maximum loss experienced by any
action.

As discussed at the start of Section 1, no-regret algorithms like RWM are
classically used to compute equilibria of the base game by simulating repeated
play across all players. While much of the current literature centers around
the Hedge algorithm that ‘plays’ an entire mixed strategy in each round,
classical (and therefore approximate) RWM still leads to equilibrium
computation with high probability, by the classic result that no-regret
implies equilibrium computation [35].

######  Lemma 1.11 (Approximate RWM $\to$ Equilibria (Informal Corollary
2.11)).

Let $\mathcal{I}$ be an $m$-player game where each player has at most $N$
strategies. Let $\\{(x_{1}^{(t)},\ldots,x_{m}^{(t)})\\}_{t=1}^{T}$ be the
strategies arising from $T$ rounds of $\delta$-approximate RWM. There exist
universal constants $C>0$ such that for
$T=C\cdot{L_{\max}^{2}\varepsilon^{-2}\cdot\log(N)}$ rounds, and approximation
parameter $\delta\leq{\varepsilon}/{(CL_{\max})}$, these strategies constitute
an $\varepsilon$-CCE with high probability (Nash if the game is two-player
zero-sum).

As a result, efficient no-regret learning and equilibrium computation truly
reduces to the existence of an efficient approximate sampling scheme for
distributions arising in the execution of ($\delta$-approximate) RWM. Of
course, this is easier said than done. While approximate sampling is easier
than its exact variant, it is still a challenging problem, even over
structured domains. Using a mixture of novel sampling techniques and
reductions to known methods in the literature, we show it is indeed possible
to efficiently sample from RWM across a wide variety of structured games. Our
strategies fall into two main paradigms: dynamic programming (DP), and Monte
Carlo Markov Chains (MCMC).

####  1.2.1 Sampling via Dynamic Programming

We start with the former: sampling in basic resource allocation settings via
dynamic programming. At its most general, resource allocation problems are
played over (possibly constrained) fixed size partitions of $n$. The discrete
Colonel Blotto game on $n$ troops and $k$ battlefields is the simplest example
of this problem, where the strategy space corresponds to the set of all
$k$-size (ordered) partitions of $n$ (i.e. assignments $x_{1},\ldots,x_{k}$
such that $\sum x_{i}=n$). In this section, we will focus only on the Colonel
Blotto problem—general resource allocation follows from very similar arguments
(see Section 4 for details).

Our goal is now to design an algorithm for approximately sampling
distributions over strategies of the Colonel Blotto game that arise from RWM.
In this setting, it will actually be easier to solve an equivalent problem,
computing the normalizing factor of Equation 2, otherwise known as the
partition function:

$f_{k}(n)=\sum\limits_{x_{1}+\ldots+x_{k}=n}\beta^{\ell(x)}=\sum\limits_{x_{1}+\ldots+x_{k}=n}\prod\limits_{h=1}^{k}\beta^{\ell_{h}(x_{h})},$

where $\ell_{h}(x_{h})$ is the historical losses from the $h$-th battlefield
over previous rounds of play if one were to place $x_{h}$ soldiers on that
battlefield. Notice that once we know the value of
$f_{k^{\prime}}(n^{\prime})$ for all $k^{\prime}\leq k$ and $n^{\prime}\leq
n$, it is actually possible to exactly sample from Equation 2 (and therefore
implement RWM). In particular, one does this simply by sequentially sampling
the number of troops to put in each battlefield conditional on prior choices
in the following manner:

$\displaystyle\Pr[x_{1}=y]$ $\displaystyle\propto\beta^{\ell_{1}(y)}\cdot
f_{k-1}(n-y)\text{ for the first battlefield, }$
$\displaystyle\Pr\left[x_{h+1}=y|x_{1\cdots h}\right]$
$\displaystyle\propto\beta^{\ell_{h+1}(y)}\cdot
f_{k-h-1}\left(n-\left(\sum_{j=1}^{h}x_{j}\right)-y\right)\text{ for the
remaining battlefields}.$

One can easily check the joint distribution arising from this procedure is
exactly the RWM distribution.

Thus we have reduced our problem to computing the partition functions
$f_{k^{\prime}}(n^{\prime})$. This can be done by a simple dynamic programming
argument, and in particular by noticing that:

$\displaystyle
f_{k^{\prime}}(n^{\prime})=\sum_{i=0}^{n^{\prime}}\beta^{\ell_{k^{\prime}}(i)}\cdot
f_{k^{\prime}-1}\left(n^{\prime}-i\right).$ (3)

Since filling each entry $f_{k^{\prime}}(n^{\prime})$ takes time at most
$O(n)$ given that $f_{h-1}$ is pre-computed, we can fill the entire DP table
in time $O(n^{2}k)$.444We note that this can actually be improved to near-
linear in $n$ using the Fast Fourier Transform.

While this procedure already gives the first no-regret learning algorithm for
Blotto in the adversarial setting and by far the fastest known equilibrium
computation, one can still hope to do much better. Indeed, it is known that
there exist $\varepsilon$-Nash Equilibrium with support that is _logarithmic_
in the size of the state-space [55], so there is hope in building a
_polylogarithmic_ time algorithm (equivalently, a polynomial time algorithm in
the description complexity of the equilibria). We show this is indeed possible
by building an approximation scheme for the above DP. The key is to observe
that the partition functions $f_{k^{\prime}}(n^{\prime})$ are bounded and
monotonic. Roughly speaking, this means $f$ can be approximated within
multiplicative $(1\pm\varepsilon)$ factors by a piece-wise function with only
$\text{poly}({k\log(n)}/{\varepsilon})$ pieces (which is polylogarithmic in
the size of the state space).

By carefully computing and maintaining approximate versions of the partition
function, we can run a modified variant of the same dynamic program that
computes approximations for all $nk$ partition functions
$f_{k^{\prime}}(n^{\prime})$ (despite their sizes, these can indeed be
presented in only $\text{poly}(k\log(n))$ bits due to being piece-wise). Once
we have approximately computed the partition functions, it is easy to show
that a similar sampling scheme as discussed for the exact case gives an
efficient approximate sampling scheme for RWM running in
$\text{poly}({k\log(n)}/{\varepsilon})$ time. Combined with Lemma 1.10 and
Lemma 1.11, this results in the first polylogarithmic time algorithm for no-
regret learning and (approximate) equilibrium computation for Colonel Blotto
(Theorem 1.2 and Corollary 1.3), as well as for a number of related resource
allocation variants discussed later in the paper (e.g. multi-resource Blotto
and Dice games).

####  1.2.2 MCMC-methods

While dynamic programming is a powerful algorithmic method for structured
computation, there are many combinatorial settings common to games we cannot
hope to handle via such techniques. Building an analogous exact-counting based
DP for games over bipartite matchings or matroids, for instance, would give
efficient algorithms for classical #P-hard problems such as the permanent and
counting matroid bases [27]. On the other hand, we do actually know of
approximation algorithms for these problems based on a powerful tool called
MCMC-sampling [43, 9].

MCMC-sampling is an elegant method for approximately sampling from a
distribution $\mu$ with exponential size support usually traced back to Ulam
and Von Neumann in the 1940s (see e.g. [33]). The idea is simple. Imagine we
can construct a Markov chain (random process) $M$ satisfying the following
three conditions:

  1. 1.

The stationary distribution of $M$ is $\mu$

  2. 2.

A single step of $M$ can be implemented efficiently

  3. 3.

$M$ converges quickly to its stationary distribution.

Approximate sampling would then simply boil down to finding a starting
configuration and running the chain until it is within $\delta$ of stationary
(this typically takes around $O(\log(N/\delta))$ samples for a good chain).

Unsurprisingly, while MCMC-sampling itself is a simple technique, the design
and analysis of Markov chains is a difficult task, and general recipes for
their construction are known in very few scenarios. One particularly well-
studied setting in the literature that arises from simulation problems in
statistical physics are external fields. Given a hypergraph
$\Omega\subset{[n]\choose k}$, the distribution arising from external field
$w\in\mathbb{R}_{+}^{n}$ simply assigns each $k$-set a probability
proportional to the product of its fields:

$\Omega^{w}(s)\ \propto\ \prod\limits_{v\in s}w(v).$

External fields often correspond to particularly natural problems, and are
well-studied in the literature. In a recent breakthrough series of works, for
instance, it was shown that approximate sampling under external fields is
possible whenever the underlying state-space is a good enough high dimensional
expander [46, 7, 9, 6].555More formally, when the space satisfies a property
known as ‘fractional log-concavity.’

This is particularly relevant to our setting since it is a simple observation
that the distributions arising from RWM on a linear hypergraph game are
exactly given by the application of an external field over the action space.

######  Observation 1.12 (RWM $\to$ External Fields (Informal 3.3)).

Let $\mathcal{I}=\\{(A_{i},R_{i})_{i=1}^{m}\\}$ be an $m$-player linear
hypergraph game. Then for any $A_{i}$ and any round of play, Player $i$’s RWM
distribution can be written as the application of an external field $w$ to
$A_{i}$.

As a result, no-regret learning and equilibrium computation are possible in
any linear hypergraph game whose state space can be sampled under arbitrary
external fields. As a short detour, it is worth noting that the result in the
previous section can be phrased as a slight refinement of this statement. At a
technical level, our resource allocation algorithm simply corresponds to an
efficient approximate sampling scheme for fixed-size partitions of $n$ under
monotonic external fields (corresponding to the fact that assigning more
troops to a battlefield always results in at least as many victories).

Many well-studied games in the literature have state spaces where efficient
approximate sampling schemes under external fields exist. In this work we
focus mostly on games played on matroids (e.g. matroid congestion, security),
and dueling games arising from bipartite matchings such as ranking duel. Both
settings have well-known sampling schemes over external fields [9, 24, 43],
which leads to our results for Congestion, Security, and Dueling games
(Theorems 1.4,1.6, 1.8 and Corollaries 1.5,1.7, 1.9 respectively).

###  1.3 Discussion

In this work, we present two potential paradigms for learning in games via
approximate sampling. In this section we touch on the pros and cons of each
method, their likelihood to generalize beyond the settings considered in this
work, and natural open problems.

####  1.3.1 Dynamic Programming vs MCMC-sampling

Broadly speaking, the DP and MCMC approaches we develop in this work seem to
be largely incomparable. Dynamic programming works well in relatively
unconstrained resource allocation problems, where recursive structure allows
for inductive computation of the partition function. On the other hand,
typical MCMC methods (which are usually local in nature) actually fail
drastically in this sort of setting due to the need for global coordination.
One natural example of this issue appears in the Colonel Blotto game. Imagine
a scenario where Colonel $A$ has $k$ more troops than Colonel $B$, then there
always exists a configuration where $A$ wins every battle by assigning one
more troop in each battlefield than $B$. Finding this sort of optimum,
however, requires coordinated planning across battlefields. Typical MCMC
methods like Glauber dynamics (see Section 3) only look at a few battlefields
at a time, and therefore struggle to converge to such solutions. Simulations
confirm this intuition—even for small $n$ and $k$ Glauber dynamics seem to
exhibit very poor mixing on distributions arising in RWM.

On the other hand, as we mentioned in the previous section, our dynamic
programming approach has a significant issue in any setting with non-trivial
combinatorial structure. In particular, because the underlying method relies
on exactly computing the partition function, constructing any such method for
a problem like matroid games is #P-hard. On the other hand, local chains such
as the Glauber Dynamics mix extremely fast in these settings, providing near-
optimal algorithms.

Of course, neither of these arguments rules out either approach. It is
possible there exist successful MCMC methods for Blotto that are more global
in nature—indeed the main insight leading to the resolution of approximate
permanent was exactly such a Markov chain that avoided these issues [43]. On
the other hand, there may exist DP-based approaches that do not go through
computing the partition function. Understanding in which scenarios these two
or other potential sampling methods may apply remains an interesting and
important open problem if we wish to extend efficient learnability in games
beyond the few structured settings considered in this work.

####  1.3.2 Further Open Problems

Our work gives the first no-regret learning guarantees and polylogarithmic
equilibrium computation for several well-studied settings in game theory, but
there is still much to be done. Perhaps the most obvious open directions
involve improving the computational efficiency (and therefore practicality) of
our algorithms. The polynomial dependencies of our algorithm would be
universally improved if we can show that the $\delta$-approximate optimistic
variant of RWM achieves $\widetilde{O}(1)$ regret in games like its
deterministic counter-part, Optimistic Hedge [28], even for polynomial
approximation $\delta$.

######  Question 1.13 (Optimistic-RWM).

Does $\delta$-RWM with weights $\\{w_{i}^{(t)}\\}_{i,t}$ and optimistic
updates
${w_{i}^{(t+1)}\leftarrow
w_{i}^{(t)}\cdot\beta^{2\ell^{(t)}_{i}-\ell^{(t-1)}_{i}}}$ achieve
$\operatorname{polylog}(T)$ regret in games (even for
$\delta=(\operatorname{polylog}N)^{-1}$)?

These techniques are well known to give a substantial improvement in the exact
setting [28], but their analysis is subtle and may be nontrivial to adapt to
the $\delta$-approximate sampling variant we need for efficient computation.

Similarly, our algorithm for dueling games (while faster than prior work in
the worst-case), is not practical at $O(n^{9})$ running time. One interesting
question is whether the MCMC-sampling technique can be improved in this
setting using the fact that the weights arising from RWM are not arbitrary,
but exhibit monotonic structure (in the sense that ranking a page higher is
always better). This actually corresponds to a well-studied problem in the
sampling and geometry of polynomials literature (monotone permanent [17]), but
giving an improved sampling algorithm over the JSV-chain [43] remains an
interesting open problem.

######  Question 1.14 (Sampling with Monotone Weights).

Can a perfect matching in a complete bipartite graph with $n$ nodes under
monotone external fields be sampled in faster than $O(n^{7})$ time? In near-
linear time?

There is certainly hope in this direction, as recent years have seen many
breakthroughs towards near-optimal MCMC methods, including similar linear time
guarantees on problems that once seemed infeasible [9, 24, 26].

Another natural direction is to try to strengthen the type of equilibria we
compute in multiplayer and general-sum games. Foremost in this direction are
the so-called Correlated Equilibria (CE), a substantially stronger notion than
CCE which allows a player to switch strategies even after they receive
instructions from the coordinator. It was recently shown that a variant of
Optimistic Hedge converges quickly to CE in multiplayer, general-sum games
[4]. It is an open question whether an approximate, sampled variant could do
the same. We pose this as the following,

######  Question 1.15 (Correlated Equilibria with RWM).

Is there a variant of $\delta$-approximate RWM that converges to CE and
remains efficiently samplable? A variant that achieves $\widetilde{O}(T^{-1})$
convergence rate?

Finally, we end with a concrete direction toward answering our original
question: _when can one efficiently sample from RWM?_ We rely in part of this
work on a series of breakthroughs in the approximate sampling and high
dimensional expansion literatures [46, 7, 9, 6] leading to a sufficient
condition called fractional log-concavity [1, 6] for sampling hypergraphs
under arbitrary external fields (generalizing an earlier result for matroids
[9]). This is in fact a stronger guarantee than we actually need to ensure
efficient sampling for RWM. Not only are the fields we study typically
additionally structured (e.g. monotonic), but we are also okay with some
amount of decay in the mixing time depending (logarithmically) on the field
size. Is there a characterization of such objects in terms of geometry of
polynomials or high dimensional expansion?

######  Question 1.16.

Is there a general condition on hypergraphs (e.g. in terms of high dimensional
expansion, geometry of polynomials) that allows for approximate sampling under
external fields with polylogarithmic dependence on the worst field size? What
about under structural constraints (e.g. monotonicity)?

###  1.4 Further Related Work

####  1.4.1 No-regret learning with structured loss

Online learning over exponentially large classes with structured losses has
been considered previously in other contexts (e.g. [45, 25, 40, 51, 3, 75]).
Much of this work considers the combinatorial bandit setting [23], which
typically competes against a non-adaptive adversary, but has restricted
information. This is an interesting setting in its own right, but differs
substantially from the challenges seen in this work and does not lead to
equilibrium computation. On the other hand, there are two works which also
consider efficient implementation of RWM [76, 40], but only for the very
special settings of $k$-sets and permutations (which are generalized by our
framework). Also of note is the later work of [51], who built a new hedge-
based algorithm for these settings called component-hedge that also gives
efficient online learning in a few additional cases (e.g. for spanning trees).

####  1.4.2 Computing equilibra for Colonel Blotto

The Colonel Blotto game is one of the most well studied problems in
algorithmic game theory—we restrict our attention here to some of the most
notable and relevant results. As mentioned previously, the first known
algorithm to compute exact Nash equilibria strategies for discrete Colonel
Blotto was introduced in [5], who consider games that are asymmetric across
battles and across players (allowing different troop capacity and rewards
across battles and players). This work remains the only known algorithm for
exact equilibrium computation that is polynomial in the number of troops and
battlefields, though follow-up work gave a more practical (but potentially
exponential time) algorithm [16].

Due to the difficulty of understanding the discrete version, a number of works
have also considered Colonel Blotto’s continuous relaxation. It should be
noted that the equilibria in the continuous version do not apply to the
discrete case [61]. The works by [37, 38, 52, 71, 49] consider the case that
troop counts are identical (symmetric) for both players. Later, the symmetric
case was also studied when Colonels have different values for battles [49]. On
the other hand, when the troop counts of the two players differ,
constructing/computing equilibria becomes more complicated. In [62], the
author constructs equilibrium strategies explicitly in the case that the
rewards for each battlefield are the same (homogeneous). The authors of [58]
consider Blotto with heterogeneous rewards and asymmetric troops counts (but
with only two battles). In [67], they consider more than two battles but with
strict assumptions on the battle weights. More recently, the authors in [61]
present an efficient algorithm to compute approximate Nash equilibria in the
two-player continuous Colonel Blotto game with asymmetric troop and battle
values.

There is also a breadth of work that constructs strategies for approximate and
exact equilibrium under constrained parameter settings of Borel’s two-player
discrete version. Beginning with [39], the author constructs optimal
strategies explicitly when the troop counts and battle rewards are identical.
In [74], the authors give an algorithm to compute equilibria with fixed
approximation (decaying with the number of battles). They also give an
algorithm to compute the best-response strategy to a given distribution over
soldiers in each battlefield using dynamic programming. In [13, 70], the
authors describe equilibria in the symmetric case where the number of soldiers
is the same for both players. Moreover, [13] introduces the multiplayer
variant. In [73], the authors construct equilbria under particular conditions
for an extension of the Colonel Blotto game that accounts for pre-allocations
and resource effectiveness.

##  2 Preliminaries

All throughout the paper, for integers $a\leq b$ we denote by $[a,b]$ the set
$\\{a,\ldots,b\\}$ and shorthand $[n]=[1,n]$. We use the notations
$\widetilde{O}(f)$ to hide polylogarithmic dependencies on the argument. Given
a finite set $\Omega$, we denote by $\Delta(\Omega)$ the (convex) polytope of
all distributions defined on $\Omega$. We denote by $2^{\Omega}$ as the power
set of $\Omega$, i.e. the set of all subsets of $\Omega$. Given two finite
sets $\Omega_{1},\Omega_{2}$, we denote by $\Omega_{1}\times\Omega_{2}$ as the
Cartesian product of the two sets, i.e. $(x,y)\in\Omega_{1}\times\Omega_{2}$
if $x\in\Omega_{1}$ and $y\in\Omega_{2}$. We will use ${\Omega\choose k}$ to
denote all size-$k$ subsets of the ground set $\Omega$. Given two integers
$k,n\in\mathbb{Z}^{+}$, we will use $P_{k}(n)$ to represent the set of ordered
size-$k$ partition of $n$.

###  2.1 Game Theory

######  Definition 2.1 (Multiplayer Simultaneous Game).

An $m$-player Simultaneous Game is a tuple
$\\{\\{A_{i}\\}_{i=1}^{m},\\{R_{i}\\}_{i=1}^{m}\\}$ where $A_{i}$ denotes the
finite set of actions available for the $i$-th player and
$R_{i}:A_{1}\times\cdots\times A_{m}\mapsto\mathbb{R}$ denotes the reward
function for the $i$-th player.

Given a set of actions $a_{1},\ldots,a_{m}$, we often write $a_{-i}$ to
represent the combined action tuples without $a_{i}$, i.e.
$(a_{1},\ldots,a_{i-1},a_{i+1},\ldots,a_{m})$, and
$R_{i}(a_{i},a_{-i})=R_{i}(a_{1},\ldots,a_{m})$ where we have abused notation
in the input ordering to $R_{i}$ for simplicity of notation.

In a game, a player can choose to play an action, often called a pure
strategy, or to draw randomly from a _mixed strategy_ given by a probability
distribution over the set of available actions.

######  Definition 2.2 (Mixed Strategy).

Let $\\{\\{A_{i}\\}_{i=1}^{m},\\{R_{i}\\}_{i=1}^{m}\\}$ be an $m$-player
simultaneous game. For the $i$-th player, the set of mixed strategies are all
possible probability distributions over the actions $A_{i}$. Let
$\mathbf{s}_{i}\in\Delta\left(A_{i}\right)$ be the mixed strategy chosen by
the $i$-th player. Then, the expected reward received by the $i$-th player is
given by
$\mathbb{E}_{a_{1}\sim\mathbf{s}_{1},\ldots,a_{m}\sim\mathbf{s}_{m}}\left[R_{i}(a_{1},\ldots,a_{i},\ldots,a_{m})\right]$.

We will also make use of the following notion of a joint strategy.

######  Definition 2.3 (Joint Strategy).

A joint strategy is a distribution
$\sigma\in\Delta\left(A_{1}\times\cdots\times A_{m}\right)$. If players were
to participate in a joint strategy, then a central coordinator samples an
action tuple $a=(a_{1},\ldots,a_{m})\sim\sigma$, and each player then plays
the action $a_{i}$ correspondingly. As a result, the expected reward of the
$i$-th player is given by $\mathbb{E}_{a\sim\sigma}R_{i}(a)$.

For a set of actions $a_{i}^{(t)}$ for $i\in[m]$, and $t\in[T]$, we will often
write $\frac{1}{T}\sum_{t=1}^{T}a_{i}^{(t)}$ as the mixed strategy of player
$i$ such that action $a_{i}^{(t)}$ is played with probability $1/T$, and
$\frac{1}{T}\sum_{t=1}^{T}a_{1}^{(t)}\otimes\cdots\otimes a_{m}^{(t)}$ as the
joint mixed strategy such that the action tuple
$(a_{1}^{(t)},\ldots,a_{m}^{(t)})$ is played with probability $1/T$.

It is well known that if all players play a game optimally, the resulting
strategy tuples compose of a _Nash Equilibrium_ of the game.

######  Definition 2.4 (Nash Equilibrium).

In an $m$-player game $\\{\\{A_{i}\\}_{i=1}^{m},\\{R_{i}\\}_{i=1}^{m}\\}$, a
tuple of mixed strategies $\left(s_{1},\ldots,s_{m}\right)$ composes an
$\varepsilon$-Nash Equilibria ($\varepsilon$-NE) if for all $i\in[m]$ it
satisfies:

$\mathbb{E}_{s_{1},\ldots,s_{m}}\left[R_{i}(s_{1},\ldots,s_{i},\ldots,s_{m})\right]\geq\sup_{s^{\prime}\in\Delta\left(A_{i}\right)}\mathbb{E}_{s_{1},\ldots,s_{m}}\left[R_{i}(s_{1},\ldots,s^{\prime},\ldots,s_{m})\right]-\varepsilon,$

where the mixed strategies $s_{i}$ for $i\in[m]$ are mutually independent.

In multiplayer and general-sum games, computating Nash equilibria is
challenging. In fact, this problem is known to be complete for PPAD [29], a
complexity class containing many other computationally hard problems. A
standard and arguably more realistic goal is to find the so-called Coarse
Correlated Equilibria (CCEs) of the multi-player game, a relaxation of Nash
Equilibrium introduced by Aumann [12].

In a CCE, all players together sample from a joint mixed strategy (in contrast
to NE where players independently sample from their own mixed strategy).
Although a player $i$ cannot benefit from switching to any single action
$s_{i}^{\prime}$ before the joint strategy is sampled, once a strategy $s_{i}$
is sampled from a CCE distribution (becoming known to each player), a player
may improve their outcome by deviating (using the fact that her strategy is
correlated with other players’). Thus, CCE apply to situations where a player
must commit to their strategy up front and are unable to deviate after
sampling.

######  Definition 2.5.

Let $\mathcal{I}=\\{(A_{i},R_{i})_{i=1}^{m}\\}$ be an $m$-player game. An
$\varepsilon$-approximate coarse correlated equilibrium ($\varepsilon$-CCE) is
a joint mixed strategy $\mathbf{\sigma}\in\Delta(A_{1}\times\cdots\times
A_{m})$ that satisfies:

$\displaystyle\forall i\in[m],\text{ and actions $a_{i}^{\prime}\in
A_{i}$}:\quad\mathbb{E}_{a\sim\mathbf{\sigma}}R_{i}(a)\geq\mathbb{E}_{a\sim\mathbf{\sigma}}R_{i}(a_{i}^{\prime},a_{-i})-\varepsilon.$

###  2.2 Linear Hypergraph Game

Given a ground set of vertices $\Omega$, a hypergraph $H$ is a collection of
subsets of $\Omega$ called hyperedges. If all hyperedges of $H$ are in
${\Omega\choose k}$, the graph is called $k$-uniform. In this work we study a
special class of games whose reward functions can be ‘decomposed’ based on the
underlying structure of the game’s action space. More formally, we consider
games played over $k$-uniform hypergraphs whose rewards _decompose linearly_
over vertices. We denote this class of games as Linear Hypergraph Games.

######  Definition 2.6 (Linear Hypergraph Games).

Let $\mathcal{I}=\\{(A_{i},R_{i})_{i=1}^{m}\\}$ be an $m$-player game. We call
$\mathcal{I}$ a linear hypergraph game if for all $i\in[m]$ there is a
groundset $\Omega_{i}$ and parameter $k_{i}\in\mathbb{N}$ such that
$A_{i}\subset{\Omega_{i}\choose k_{i}}$ and a ‘vertex-wise’ reward function
$R_{i}^{\Omega_{i}}:\Omega_{i}\times A_{-i}$ such that for all
$t_{1},\ldots,t_{n}\in A_{1}\times\ldots\times A_{n}$

$R_{i}(t_{i},t_{-i})=\sum\limits_{v\in t_{i}}R^{\Omega}_{i}(v,t_{-i}).$

In other words, each element $v$ in the ground set $\Omega_{i}$ has a certain
reward with respect to any choice of the opponents, and the reward of a
$k$-set is simply the sum of its individual rewards. Many important games that
are well-studied in the game theory literature falls under this category, e.g.
Colonel Blotto Games, Security Games, Congestion Games, Dueling Games, etc. In
fact, it should be noted a similar notion has been studied in the online
learning setting in [51], who develop an efficient no-regret algorithm called
Component Hedge for linear losses over basic structures such as the complete
hypergraph, truncated permutations, and spanning trees.

###  2.3 No-Regret Learning in Games

We consider the framework of No-Regret Learning in Games (see [22, 28] and
references therein). In this framework, a game is iterated with one or more
players implementing a no-regret learning algorithm to adaptively choose
strategies. At the $t$-th round of the game, each player selects a mixed
strategy $\mathbf{s}_{i}^{(t)}$, and samples the action
$a_{i}^{(t)}\sim\mathbf{s}_{i}^{(t)}$, where the choice of
$\mathbf{s}_{i}^{(t)}$ depends only on $a_{j}^{(t^{\prime})}$ for $j\in[m]$
and $t^{\prime}<t$.

The goal for each player is to optimize her regret, defined as the following.

######  Definition 2.7 (Regret).

At the $T$-th round of the game, the regret for the $i$-th player is defined
as

$\operatorname{Reg}_{T,i}:=\max_{a^{*}\in
A_{i}}\sum_{t=1}^{T}R_{i}(a_{1}^{(t)},\cdots,a_{i-1}^{(t)},a^{*},a_{i+1}^{(t)},\cdots,a_{m}^{(t)})-\sum_{t=1}^{T}R_{i}(a_{1}^{(t)},\cdots,a_{m}^{(t)}).$

It is classical result that if all players follow no-regret learning
strategies, the overall dynamics quickly converge to a Nash or Coarse-
Correlated Equilibria (CCEs) of the game (see e.g. [35, 22, 60]).

######  Theorem 2.8 (No-Regret Implies Equilibrium Computation [35]).

Suppose $m$ players are playing under the No-Regret Learning in Games
framework. Let
$\mathbf{\sigma}^{*}:=\frac{1}{T}\sum_{t=1}^{T}a_{1}^{(t)}\otimes\cdots\otimes
a_{m}^{(t)}$ be the average mixed joint strategies played by the $i$-th player
over $T$ rounds. Then, $\mathbf{\sigma}^{*}$ forms an
$T^{-1}\max\left(\operatorname{Reg}_{T,1},\cdots,\operatorname{Reg}_{T,m}\right)$-approximate
CCE of the game, where $R_{i}^{(T)}$ is the regret for the $i$-th player at
the $T$-th round. When $m=2$ and the game is zero-sum, the mixed strategies
$\left(\frac{1}{T}\sum_{t=1}^{T}a_{1}^{(t)},\frac{1}{T}\sum_{t=1}^{T}a_{2}^{(t)}\right)$
constitute a
$T^{-1}\max\left(\operatorname{Reg}_{T,1},\operatorname{Reg}_{T,2}\right)$-approximate
Nash Equilibrium.

###  2.4 Randomized Weighted Majority Algorithm

As in online learning, no-regret learning in games studies the regret of a
player against the opponents’ strategies in repeated play with respect to the
best single strategy in hindsight.

One of the most frequently used tools in no-regret learning is the randomized
weighted majority (RWM) algorithm. For player $i\in[m]$, RWM maintains the
mixed strategies from $\Delta\left(A_{i}\right)$ as follows: at the first
round, it chooses uniformly among the actions.

At the $(T+1)$-st round, a cumulative reward is computed for each action $x\in
A_{i}$

$r^{(T+1)}(x)=\sum_{t=1}^{T}R_{i}(s_{1}^{(t)},\cdots,s_{i-1}^{(t)},x,s_{i+1}^{(t)},\cdots,s_{m}^{(t)}),$

and RWM chooses the mixed strategy $RM^{(T+1)}\left(\beta\right)$ (which we
refer to as the RWM distribution) such that

$\displaystyle\Pr\left[RM^{(T+1)}\left(\beta\right)=x\right]\propto\beta^{-r^{(T+1)}(x)}.$
(4)

It is well known that if any player samples according to
$RM^{(T+1)}\left(\beta\right)$ in each round, her expected regret will be
bounded in the worst case by $O_{\beta,N}(\sqrt{T})$.

In games whose action sets are exponentially large, exactly sampling from the
the RWM distribution may be intractable in relevant cases. Nonetheless, we
show that similar regret bounds hold even when one _approximately_ samples the
RWM distributions in each round (the proof is given in Appendix).

######  Definition 2.9 (Approximate Sampling).

We say a randomized algorithm $\mathcal{A}$ with output space $\Omega$
$\delta$-approximately samples a distribution $\mu$ over $\Omega$ if the
output of $\mathcal{A}$ is $\delta$-close to $\mu$ in TV-distance.

We call any strategy that $\delta$-approximately samples from
$RM^{(t)}\left(\beta\right)$ in each of $T$ rounds of repeated play
$\delta$-approximate RWM, and denote this class of algorithms by
$\delta$-RWM${}^{T}_{\beta}$. It is not hard to show that $\delta$-RWM has
near-optimal regret in the adversarial setting (see Appendix A).

######  Lemma 2.10 ($\delta$-RWM is No-Regret).

Let $\mathcal{I}$ be an $m$-player game with at most $N$ actions and
$L_{\max}$ reward. If the $i$-th player follows $\delta$-RWM${}^{T}_{\beta}$
in $T$ rounds of play with learning rate $\beta=1-\sqrt{\log(N)/T}$ and
approximation factor $\delta\leq\sqrt{\log(N)/T}$,666We are assuming $T\gg\log
N$. Otherwise, the regret bound becomes $L_{\max}T$, which can be achieved by
any arbitrary sequence of choices.  then for any $\eta>0$ they experience
regret at most

$\operatorname{Reg}_{T,i}\leq O\left(L_{\max}\sqrt{T}\left(\sqrt{\log
N}+\sqrt{\log(1/\eta)}\right)\right)$

with probability at least $1-\eta$.

As an immediate corollary, for any game, if we can approximate sample from the
RWM distribution efficiently, we immediately get an efficient no-regret
learner. In addition, connecting it with Theorem 2.8, we also obtain the
following corollary for equilibrium computation with RWM.

######  Corollary 2.11 (Equilibrium Computation with $\delta$-RWM).

Let $\mathcal{I}=\\{(A_{i},R_{i})_{i=1}^{m}\\}$ be an $m$-player where
$|A_{i}|\leq N$ for each $i\in[m]$ and reward bounded by $L_{\max}$. Suppose
the game is played repeatedly for $T$ rounds. If there is an algorithm which
can perform $\delta$-RWM${}^{T}_{\beta}$ for each player $i$ in time
$f_{\mathcal{I}}(T,\delta)$, then there exists an algorithm which computes an
$\varepsilon$-CCE of $\mathcal{I}$ (Nash if the game is $2$-player zero-sum)
with probability at least $1-\eta$. Moreover, the algorithm runs in time

$O\left(m\cdot f_{\mathcal{I}}\left(C\cdot
L_{\max}\varepsilon^{-2}\log(Nm/\eta),\frac{\varepsilon}{C\cdot
L_{\max}}\right)\right).$

for some universal constant $C>0$.

In Sections 3 and 4, we develop two different types of methods of approximate
sampling from the RWM distribution in many well-studied games and discuss
their implications. Before moving on, however, it is convenient to briefly
discuss one computational consideration that frequently occurs in efficient
implementation of RWM. In particular, it will often be the case that our
algorithm needs to deal with piece-wise constant functions that map from
$[0,n]$ to $\mathbb{R}$ (e.g. reward functions in Blotto for each battlefield
are $2$-piecewise in this sense). To represent such functions, we will use the
following data structure that we refer as a _succinct representation_.

######  Definition 2.12 (Succinct Descriptions of piecewise constant
functions).

Let $f:[0,n]\mapsto\mathbb{R}$ be a $q$-piecewise constant function. The
succinct description of $f$, denoted as $D_{f}$, consists of $q$ tuples of the
form $(a_{i},b_{i},y_{i})\in(\mathbb{Z}^{+},\mathbb{Z}^{+},\mathbb{R})$ such
that for all $x\in[a_{i},b_{i}]$, $f(x)=y_{i}$ and the intervals
$\\{[a_{1},b_{1}]\cdots[a_{q},b_{q}]\\}$ partition $[0,n]$.

We will often write $|D_{f}|$ to denote the number of intervals contained in
the succinct description. Finally, note that assuming access to succinct
descriptions does not lose much generality, as given query access to a
standard representation for the monotonic piece-wise function in question
(e.g. in the RAM model), it is easy to build a succinct description in time
$q\log(n)$ by binary search.

##  3 Playing Games via MCMC-Sampling

In this section, we develop the connections between linear hypergraph games,
the RWM distribution, and efficient sampling. In doing so, we unlock access to
powerful tools from the sampling literature for the first time in the context
of games. This allows for a number of immediate applications including the
first no-regret algorithms for well-studied settings such as matroids.

With this in mind, let’s first recall the basic framework of Monte Carlo
Markov Chains: a powerful tool for approximately sampling from large spaces
like the RWM distribution. More formally, consider the following problem:
given a distribution $\pi$ over a large state space $A$, we’d like to
approximately sample a state from $\pi$ in $\text{polylog}(|A|)$ time. MCMC-
sampling is an elegant approach to this problem in which one defines a Markov
chain $M$ on $A$ satisfying the following three conditions:

  1. 1.

The stationary distribution of $M$ is $\pi$

  2. 2.

A single step of $M$ can be implemented efficiently

  3. 3.

$M$ converges quickly to its stationary distribution.

As long as these three conditions hold, it is possible to efficiently sample
from $\pi$ up to any desired accuracy simply by running the Markov chain from
any starting position a few steps and outputting the resulting state. More
formally, recall that the mixing time of a Markov chain $M$ is the number of
steps until the resulting distribution is close in TV-distance to $\pi$:

######  Definition 3.1 (Mixing Time).

The mixing time of a Markov chain $M$ is the worst-case number of steps until
the total variation distance of $M$ is close to its stationary measure:

$T(M,\delta)\coloneqq\min_{t\in\mathbb{N}}:\forall\pi_{s},\
TV(M^{t}\pi_{s},\pi)\leq\delta.$

Thus one only needs to run the chain $T(M,\delta)$ times (from any starting
position) in order to $\delta$-approximately sample from $\pi$.

While MCMC-sampling is a promising approach, designing efficient Markov chains
is typically a challenging task. However, in structured settings such as
linear hypergraph games, the distributions arising from RWM seem to be more
conducive to the approach. In fact, they correspond to well-studied structure
in the approximate sampling literature called external fields.

######  Definition 3.2 (External Field).

Let $\pi$ be a distribution over a $k$-uniform hypergraph
$H\subset{\Omega\choose k}$. The distribution given by $\pi$ ‘under external
field $w$’ for $w\in\mathbb{R}_{+}^{\Omega}$ has measure proportional to the
product of w across each k-set:

$\pi^{w}(s)\ \propto\ \pi(s)\prod\limits_{v\in s}w(v).$

When $\pi$ is uniform over $H$, we often just write $H^{w}$ for $\pi^{w}$.

It is a simple observation that the distribution arising from RWM (or indeed
any reasonable variant) is exactly given by the application of an external
field to the state space.

######  Observation 3.3 (RWM $\to$ External Fields).

Let $\mathcal{I}=\\{(A_{i},R_{i})_{i=1}^{m}\\}$ be an $m$-player linear
hypergraph game. Then for any $i\in[m]$, $RM^{(T)}\left(\beta\right)$ can be
written as the application of an external field $w$ to $A_{i}$ such that
$A_{i}^{w}$ has minimum probability at most
$\frac{\beta^{-2L_{\max}T}}{|A_{i}|}$.

###### Proof.

Assume $i=1$ without loss of generality (for simplicity of notation). Recall
that RWM operates at round $T+1$ by exponentiating the total loss over the
previous $T$ rounds:

$\Pr\left[RM^{(T)}\left(\beta\right)=a\right]\propto\beta^{-\sum\limits_{j=1}^{T}R_{1}(a,s^{(j)})}$

where $s^{(1)},\ldots,s^{(T)}\in A_{-1}$ are the historical strategies played
by players $\\{2,\ldots,n\\}$ in rounds one through $T$. For simplicity of
notation, let $\ell^{(T)}(a)\coloneqq-\sum\limits_{t=1}^{T}R(a,s^{(t)})$ be
the total loss. We can similarly define this quantity for any element of the
ground set $v\in\Omega$ as:

$\ell^{(T)}(v)=-\sum\limits_{t=1}^{T}R_{1}^{\Omega}(v,s^{(t)}).$

Switching the summations, linearity promises we can express $\ell_{T}(s)$ as a
sum over $\ell_{T}(v)$:

$\ell_{T}(a)=\sum\limits_{v\in a}\ell_{T}(v).$

As a result, the RWM distribution is proportional to the product of
(exponentiated) total loss for each vertex:

$\Pr(a)\ \propto\ \prod\limits_{v\in a}\beta^{\ell^{(T)}(v)}.$

This is exactly $A_{1}$ under the external field $w\in\mathbb{R}_{+}^{\Omega}$
where $w(v)=\beta^{\ell^{(T)}(v)}$. Since the distribution started uniformly
over $A_{1}$ and is update by at most $\beta^{L_{\max}}$ in each step, the
minimum probability is at worst $\frac{\beta^{-2L_{\max}}}{|A_{1}|}$. ∎

As an immediate corollary, we get an efficient no-regret algorithm for any
linear hypergraph game whose state space can be approximately sampled under
arbitrary external fields, a well-studied problem in approximate sampling. In
the remainder of the section, we’ll show how such results lead to new
efficient no-regret learning algorithms for many well-studied settings in game
theory.

###  3.1 Glauber Dynamics and Fractionally Log-Concave Games

The past few years have seen major advances in approximate sampling various
combinatorial objects under external fields [9, 8, 1, 6]. The recent
breakthroughs have largely been driven by new analysis techniques for a simple
local Markov chain arising from the study of Ising models in statistical
physics called the Glauber Dynamics. Starting from a state $\sigma\in
H\subset{\Omega\choose k}$, the (single-site) Glauber Dynamics for a
distribution $\pi$ over $A_{i}$ are given by the following two-stage
procedure:

  1. 1.

“Down-Step:” Remove a vertex $v$ uniformly at random from $\sigma$.

  2. 2.

“Up-Step:” Sample from $\pi$ conditional on $\sigma\setminus v$.

It is not hard to show that $\pi$ is the stationary distribution of this
process. The first major breakthrough towards rapid mixing of Glauber Dynamics
was due to Anari, Liu, Oveis-Gharan, and Vinzant [9], who used tools developed
in the high dimensional expansion literature [46] to prove rapid-mixing of
Glauber Dynamics on a broad class of combinatorial objects called matroids.

######  Definition 3.4 (Matroids).

Let $\Omega$ be a ground set and $\mathcal{J}$ a family of subsets of
$\Omega$. $(\Omega,\mathcal{J})$ is called a matroid if it satisfies

  1. 1.

Non-emptiness: $\mathcal{J}$ contains at least one subset.

  2. 2.

Downward-closure: For all $S\in\mathcal{J}$ and $S^{\prime}\subset S$,
$S^{\prime}\in\mathcal{J}$

  3. 3.

Exchange-property: For all $S,S^{\prime}\in\mathcal{J}$ s.t.
$|S|>|S^{\prime}|$, there exists $x\in S$ s.t. $S^{\prime}\cup
x\in\mathcal{J}$.

An element $S\in I$ is a basis if it is maximal, and the rank of the matroid
(denoted $r(\mathcal{J})$) is the size of its largest basis.

Note that the bases of a matroid make up an $r(\mathcal{J})$-uniform
hypergraph over vertex set $\Omega$. These objects are perhaps best thought of
as generalizing the combinatorial structure seen in spanning trees (which form
the bases of a ‘graphic’ matroid). ALOV’s [9] major breakthrough was to prove
rapid mixing of Glauber Dynamics on matroid bases, a problem known as the
Mihail-Vazirani Conjecture (this result was later optimized by Cryan, Guo, and
Mousa [24]). Since matroids maintain their structure under external fields
(see e.g. [6]), this leads to the following MCMC-algorithm for sampling
matroid bases under arbitrary external fields.

######  Theorem 3.5 (Glauber Dynamics on Matroids [6, Theorem 5]).

Let $H$ be the set of bases of a rank-$k$ matroid $(\Omega,\mathcal{J})$. Let
$w\in\mathbb{R}_{+}^{\Omega}$ be any external field. Then, the single-step
Glauber Dynamics on $H^{w}$ has mixing time

$T(GD,\delta)\leq
O\left(k\log\left(\frac{\log(|\Omega|/w_{*})}{\delta}\right)\right).$

A substantial amount of progress has been made since ALOV and CGM’s works. In
fact, recently Anari, Jain, Koehler, Pham, and Vuong [6] introduced an even
more general class of hypergraphs that can be sampled under arbitrary external
fields called fractionally log-concave hypergraphs.777Formally this requires a
slight generalization known as the $q$-step Glauber Dynamics. All of our
results extend to this setting, but to our knowledge matroids already capture
most settings of interest in game theory so we focus just on this case for
concreteness.

Since matroids are typically exponential size in their rank, we will need
implicit access in order to build efficient algorithms. This is typically done
through various types of oracle access to the independent sets. For simplicity
of presentation, we will assume access to a contraction oracle, a standard
operation on matroids that restricts the object to independent sets containing
some fixed $S\in\mathcal{J}$.

######  Definition 3.6 (Contraction Oracle).

Let $(\Omega,\mathcal{J})$ be a rank-$k$ matroid. A rank-$r$ contraction
oracle inputs an independent set $S\in\mathcal{J}$ of size $r$, and outputs
(query access to) the contracted matroid $(\Omega,\mathcal{J}_{S})$, where

$\mathcal{J}_{S}=\\{T:T\cup S\in\mathcal{J}\\}.$

Crucially we will only use rank-$(k-1)$ contraction oracles on matroids with
rank $k$ (and thus drop rank from the notation below). This can always be
implemented in $|\Omega|$ applications of a standard independence oracle
(which decides given $S\subseteq\Omega$ whether $S\in\mathcal{J}$), but can
often be implemented much more efficiently. For instance, it is easy to see in
the case of uniform (unconstrainted) matroids, this can be implemented in
$O(k)$ time simply by removing each element of $S$ from the list.

Before stating the main guarantees for no-regret learning and equilibrium
computation, it will be useful to discuss a few finer-grained properties
typical to games on matroids that help parameterize related computation
complexities. First, while not strictly necessary, it will be convenient to
restrict our attention to games where the action sets of all players are given
by $k_{i}$-uniform hypergraphs on some shared groundset $\Omega$, i.e.
$A_{i}\subseteq{\Omega\choose k_{i}}$ for all $i$. Given such a game
$\mathcal{I}=\\{(A_{i},R_{i})_{i=1}^{m}\\}$, we will typically write
$k_{-i}=\max_{j\neq i}k_{j}$ to denote the maximum support of any viable
opponent strategy.

Second, it will be useful to introduce an important property of congestion and
security games we call collision-sensitivity: the vertex-wise reward of an
element $v\in\Omega$ only changes if $v$ is also selected by another opponent.

######  Definition 3.7 (Collision-sensitive Games).

Let $\mathcal{I}=\\{(A_{i},R_{i})_{i=1}^{m}\\}$ be an $m$-player linear
hypergraph game where $A_{i}\subseteq 2^{\Omega}$. We call the rewards of
player $i$ ‘collision-sensitive’ if for all $v\in\Omega$, the vertex-wise
reward of $v$ only changes if another opponent also selects $v$:

$\forall v\in\Omega\text{ and }s,s^{\prime}\in A_{-i}\text{ s.t. }v\notin
s,s^{\prime}:R_{i}^{\Omega}(v,s)=R_{i}^{\Omega}(v,s^{\prime}).$

We will write $\operatorname{NC}_{i}:\Omega\mapsto\mathbb{R}$ as the function
specifying the $i$-th player’s no-collision reward function for each vertex,
i.e. $\operatorname{NC}_{i}(x)=R_{i}^{\Omega}(x,s)$ for $x\notin s$. We say a
collision-sensitive reward has support $q$ if the no-collision reward function
$\operatorname{NC}_{i}$ for each player takes on at most $q$ values across all
vertices $v\in\Omega$.

In a sense, collision-sensitivity can be thought of as an independence
criterion on the vertices: roughly speaking, actions taken on $v$ do not
effect actions taken on $w$ for $w\neq v$. With these definitions out of the
way, we can now state our main guarantees for no-regret learning on matroids.

######  Theorem 3.8 (RWM on Matroids).

Let $\mathcal{I}=\\{(A_{i},R_{i})_{i=1}^{m}\\}$ be an $m$-player linear
hypergraph game on a size-$n$ ground set $\Omega$. If $A_{i}$ is collision-
sensitive with support $q$, then it is possible to implement
$\delta$-RWM${}^{T}_{\beta}$ in time

$O\left(k_{i}T(CO+q\log(n)+mk_{-i}T\log(n))\log\left(\frac{k_{i}\log(n)+L_{\max}T\log(\beta^{-1})}{\delta}\right)\right),$

assuming access to a $q$-piecewise succinct description of
$\operatorname{NC}_{i}$ encoded under an ordering of $\Omega$ and a
contraction oracle matching the same ordering.

The proof of Theorem 3.8 is not particularly interesting beyond combining 3.3
and Theorem 3.5 and involves mostly tedious implementation details of Glauber
Dynamics on matroids. We give these details in Appendix C for completeness.

Before moving on, we briefly note this result is nearly tight in many of the
main parameters. For instance, the dependence on $k$,$m$, and $n$ is
$\tilde{O}(mk\log(n))$,888This may increase when the support of other players
is non-constant. E.g. if all players are playing bases of $k$-uniform
matroids, we require $mk^{2}\log(n)$ which in many cases (e.g. uniform
matroid) is the number of bits required even to express a set of pure
strategies for each player. The bound is also linear in $q$, which is easily
seen to be necessary since one needs to know the $q$ distinct values in order
to sample.

Many games in the literature satisfy the conditions of Theorem 3.8. We’ll end
this subsection by giving a few concrete examples. Perhaps the most well-
studied variant of these games is a popular setting called congestion games.
Congestion games are a natural model for resource competition where
$m$-players compete to share $n$ resources and receive rewards dependent on
the number of players sharing the same resource.

######  Definition 3.9 (Congestion Game).

Given a ground set $\Omega$, an $m$-player congestion game on $\Omega$
consists of a collection $\\{A_{i}\\}_{i=1}^{m}$ and a reward function
$c:\Omega\times[m]\to\mathbb{R}$ where each $A_{i}\subseteq 2^{\Omega}$ are
the strategies of player $i$, and the reward on the actions
$(s_{1},\ldots,s_{n})$ is given by:

$R_{i}(s_{i},s_{-i})=\sum\limits_{e\in s_{i}}c(e,|e(s)|)$

where $e(s)=\\{s_{i}:e\in s_{i}\\}$.

Congestion games are particularly well-studied on matroid bases, which are the
only structure on which best response is known to converge to Nash in
polynomial time. However, to our knowledge Theorem 3.8 provides the first no-
regret algorithm for congestion games.

######  Corollary 3.10 (Matroid Congestion without Regret).

Let $\mathcal{I}=\\{\\{A_{i}\\}_{i=1}^{m},c\\}$ be a congestion game where
each $A_{i}$ is the set of bases of a rank-$k_{i}$ matroid on a ground set
$\Omega$ of size $n$ satisfying $\max_{i\in[m]}k_{i}=k$. Suppose
$\operatorname{NC}(e)=c(e,1)$, the no collision reward function, is
$q$-piecewise under some ordering of $\Omega$. Then there is a no-regret
learning algorithm for $\mathcal{I}$ with regret:

$\operatorname{Reg}_{T}\leq
O\left(L_{\max}\sqrt{T}\cdot\left(\sqrt{k\log(n)}+\sqrt{\log(1/\eta)}\right)\right)$

with probability at least $1-\eta$ that runs in time

$O\left(kT(CO+q\log(n)+Tmk\log(n))\log\left(L_{\max}Tk\log(n)\right)\right)$

assuming access to a $q$-piecewise succinct description of $\operatorname{NC}$
encoded in some ordering of $\Omega$ and a contraction oracle matching this
ordering.

###### Proof.

It is enough to argue the game is linear, as the result then follows
immediately from Theorem 3.8. Denote by $s$ be the strategy tuples chosen by
the players. Recall that the reward of any strategy $s_{i}\in
A_{i}\subset{\Omega\choose k_{i}}$ in the congestion game is given by:

$R(s_{i},s_{-i})=\sum\limits_{e\in s_{i}}c(e,|e(s)|).$

$c$ can easily be extended into the desired vertex-wise reward function, so we
are done. ∎

######  Corollary 3.11 (Equilibrium Computation for Matroid Congestion).

Let $\mathcal{I}=\\{\\{A_{i}\\}_{i=1}^{m},c\\}$ be a congestion game where
each $A_{i}$ is the set of bases of a rank-$k_{i}$ matroid on a shared ground
set $\Omega$ of size $n$ satisfying $\max_{i\in[m]}k_{i}=k$. Suppose
$\operatorname{NC}(e)=c(e,1)$ is $q$-piecewise under some ordering of
$\Omega$. Then it is possible to compute an $\varepsilon$-CCE with probability
at least $1-\eta$ in time

$O\left(mL_{\max}^{2}k^{2}\log(mn/\eta)\varepsilon^{-2}(CO+q\log(n)+mL_{\max}^{2}k^{2}\log^{2}(mn/\eta)\varepsilon^{-2})\log\left(L_{\max}k\log(mn/\eta)/\varepsilon\right)\right).$

We note that these results also easily generalizes matroid congestion over any
FLC, unlike the best response strategy for computing Nash. Furthermore, we
note that Hedge is actually known to converge to better equilibria [47] than
original techniques based on best response, which gives this approach an
additional potential advantage.

Another setting particularly well-suited to matroids are security games, which
model a variety of attack/defense scenarios.

######  Definition 3.12 (Security Game).

A security game $\mathcal{I}=(A_{d},A_{a},\\{r,\zeta,c,\rho\\})$ over ground
set $\Omega$ consists of defender actions $A_{d}\subseteq 2^{\Omega}$,
attacker actions $A_{a}=\Omega$, and reward/cost functions
$r,\zeta,c,\rho:\Omega\to\mathbb{R}$. Let $S\in A_{d}$, $i\in A_{a}$ be the
actions taken by the defender and the attacker respectively. The reward
matrices are given by:

$R_{d}(S,i)=\begin{cases}r(i)&\text{if }i\in S\\\
c(i)&\text{else,}\end{cases}\ \ \ \ \text{and}\ \ \ \
R_{a}(S,i)=\begin{cases}\zeta(i)&\text{if }i\in S\\\
\rho(i)&\text{else.}\end{cases}$

Security games can model a couple natural settings dependent on the choice of
parameters. One basic setting is where the defender has $k$ security resources
to defend a set of $n$ targets, and ‘wins’ if the attacker chooses a defended
target. On the other hand, the model also captures the complement of this game
where the defender chooses $k$ targets to distribute key resources, and the
attacker wins if they intercept this distribution (pick one of the $k$ marked
targets). Security games have broad applicability in practice, and indeed have
been used in cases such as assigning security checkpoints at LAX [69].

Security games are inherently linear in their natural representation and thus
admit efficient no-regret algorithms when the defender’s state-space is a
matroid (simulating RWM for the attacker is trivial as it corresponds to a
size-$|\Omega|$ multinomial distribution).

######  Corollary 3.13 (Security without Regret).

Let $\mathcal{I}=(A_{d},A_{a},\\{r,\zeta,c,\rho\\})$ be a security game where
$A_{d}$ are the bases of a rank-$k$ matroid on the ground set $\Omega$ and
$A_{a}=\Omega$. Suppose $c,\rho:\Omega\mapsto\mathbb{R}$ are $q$-piecewise
under some ordering of $\Omega$. Then there exists a no-regret learning
algorithm for $\mathcal{I}$ with regret:

$\operatorname{Reg}_{T}\leq
O\left(L_{\max}\sqrt{T}\cdot\left(\sqrt{k\log(n)}+\sqrt{\log(1/\eta)}\right)\right)$

with probability at least $1-\eta$ that runs in time

$O\left(kT(CO+q\log(n)+T\log(n))\log\left(k\log(n)TL_{\max}\right)\right),$

assuming access to $q$-piecewise succinct descriptions for $c$ and $\rho$
encoded in some ordering of $\Omega$ and a contraction oracle matching this
ordering.

###### Proof.

Note that the attacker’s strategy consists of bases of just rank-$1$ matroid
so implementing RWM for her is trivial. We focus on the implementation for the
defender side. Again it is enough to show the game is linear. By definition,
we have

$R_{D}(S,i)=\sum\limits_{j\in S}R_{D}^{\Omega}(j,i)$

where $R_{D}^{\Omega}:[n]\times[n]\to\mathbb{R}$ is

$R_{D}^{\Omega}(i,j)=\begin{cases}r(i)&\text{if }i=j\\\
c(i)&\text{else}.\end{cases}$

∎

As an immediate corollary, we also get fast equilibrium computation.

######  Corollary 3.14 (Equilibrium Computation for Security).

Let $\mathcal{I}=(A_{d},A_{a},\\{r,\zeta,c,\rho\\})$ be a security game where
$A_{d}$ are the bases of a rank-$k$ matroid on the ground set $\Omega$ and
$A_{a}=\Omega$. Suppose $c,\rho:\Omega\mapsto\mathbb{R}$ are $q$-piecewise
under some ordering of $\Omega$. Then it is possible to compute an
$\varepsilon$-CCE (Nash if the game is zero-sum) with probability at least
$1-\eta$ in time

$O\left(L_{\max}^{2}k^{2}\log(n/\eta)\varepsilon^{-2}(CO+q\log(n)+L_{\max}^{2}k\varepsilon^{-2}\log^{2}(n/\eta))\log\left(k\log(n/\eta)\varepsilon^{-1}L_{\max}\right)\right),$

assuming access to an $q$-piecewise succinct description for $c$ and $\rho$
encoded under some ordering of $\Omega$ and a contraction oracle matching this
ordering.

We note that this result easily generalizes to settings with multiple
attackers or an attacker who chooses targets corresponding to a matroid basis.

###  3.2 Dueling Games and the JSV Chain

Matroids (or more generally FLC’s) are not the only type of constrained state
space that can be sampled under arbitrary external fields. Indeed, long before
these results Jerrum, Sinclair, and Vigoda [43] famously proved (in work on
approximating the permanent) that bipartite matchings have this property as
well. We give an improved version of their result due to Bezáková,
Štefankovič, Vazirani, and Vigoda [21].

######  Theorem 3.15 (JSV Chain).

Let $(K_{n,n},w)$ be an edge-weighted complete bipartite graph, and consider
the distribution over perfect matchings given by:

$Pr(M)\propto\prod\limits_{e\in M}w_{e}.$

It is possible to $\delta$-approximately sample from this distribution in
$\widetilde{O}(n^{7}\log\frac{1}{\delta w_{\min}})$ time, where $w_{\min}$ is
the minimum weight.

Note one can phrase this result as a sampling algorithm for permutations over
external fields, where the state-space is viewed as a subset of $[n]^{n}$.
Like matroids, bipartite matchings are very natural objects and underlie a
fair number of well-studied games. In this section, we focus on the setting of
dueling games. Dueling games model two player competitive optimization over a
shared ground set.

######  Definition 3.16 (Dueling Games).

A dueling game $\mathcal{I}=(\Omega,\mu,A_{1},A_{2})$ consists of a set
$\Omega$, a distribution $\mu$ over $\Omega$, and strategy spaces
$A_{1},A_{2}\subset\mathbb{R}_{+}^{\Omega}$. The reward matrices are given by
the probability of ranking $x\sim\mu$ higher than the opponent:

$R_{1}(s,t)=Pr_{x\sim\mu}[s(x)>t(x)]-Pr_{x\sim\mu}[t(x)>s(x)],$

and likewise:

$R_{2}(s,t)=Pr_{x\sim\mu}[t(x)>s(x)]-Pr_{x\sim\mu}[s(x)>t(x)].$

There is no known polynomial time algorithm for computing equilibria of
general dueling games. We will give a general algorithm for a class of dueling
games we call unrestricted.

######  Definition 3.17 (Unrestricted Dueling Games).

A dueling game $\mathcal{I}=(\Omega,\mu,A_{1},A_{2})$ is called un-restricted
if there exist subsets $S_{1},S_{2}\subset\mathbb{R}$ with
$|S_{1}|=|S_{2}|=|\Omega|$ such that $A_{1}$ (respectively $A_{2}$) consists
of all possible assignments of $\Omega$ to $S_{1}$ (respectively $S_{2}$).

It is not hard to see that unrestricted dueling games are linear over perfect
matchings in a complete bipartite graph. As a result, we can use the JSV-chain
to simulate optimistic hedge in polynomial time.

######  Theorem 3.18 (Sampling Unrestricted Dueling Games).

Let $\mathcal{I}=(\Omega,\mu,A_{1},A_{2})$ be an unrestricted dueling game
where $|\Omega|=n$. Then it is possible to implement
$\delta$-RMW${}^{T}_{\beta}$ in time
$\widetilde{O}(T^{2}n^{7}\log(1/\delta))$.

###### Proof.

We focus on player $1$. The result is analogous for player $2$. Strategies in
an unrestricted dueling game correspond to perfect matchings in the complete
bipartite graph $K_{n,n}$, where the LHS corresponds to elements of $\Omega$,
and the RHS corresponds to elements in $S_{1}$. To fit into our prior
framework of linearity and external fields, one may view these perfect
matchings as elements of $E^{n}$ (where $E$ is the edge set of $K_{n,n}$).
Recall that the reward is given by:

$R_{1}(s,t)=Pr_{x\sim\mu}[s(x)>t(x)]-Pr_{x\sim\mu}[t(x)>s(x)]$

It is not hard to see this is linear over the edges of matching:

$R_{1}(s,t)=\sum\limits_{e\in s}R_{1}^{\Omega}(e,t)$

where $R_{1}^{\Omega}:E\times A_{2}\to\mathbb{R}$ is given by:

$R_{1}^{\Omega}(\\{v,w\\},t)=\begin{cases}\mu(v)&\text{if }w>t(v)\\\
-\mu(v)&\text{if }w<t(v)\\\ 0&\text{else}\end{cases}$

As a result, 3.3 implies that RWM is given by the application of an external
field over the edges of perfect bipartite matchings, which is exactly the
distribution considered in Theorem 3.15. All that is left is to efficiently
build access to the weights of the underlying bipartite graph, which is a
small onetime cost that is asymptotically dominated by even the mixing time of
the JSV chain. As a result, it is enough to run Theorem 3.15 $T$ times, which
gives the resulting runtime bound. ∎

We note that this result can easily be generalized to a slightly larger class
of games where $|S_{1}|$ and $|S_{2}|$ may be larger than $\Omega$, and
specific edges in the bipartite representation may be disallowed (i.e. we
might add the constraint that $x\in\Omega$ can never be given rank $1$). Such
strategies correspond to sampling matchings on a generic bipartite graph
(rather than $K_{n,n}$), and no-regret learning can can also be performed by
the JSV-chain.

Finally, we’ll look at a classic dueling game that fit into the unrestricted
framework: ranking duel. Ranking duel (or the ‘search engine game’) is a game
where two players compete to choose the best ranking of $n$ items. One of
these items is pulled from a known distribution, and the player who ranked it
higher wins.

Ranking duel is an unrestricted game where $S_{1},S_{2}=[n]$ and the action
spaces $A_{1},A_{2}=\mathcal{S}_{n}$, i.e. permutations of $n$. As a result
Theorem 3.18 immediately implies an efficient algorithm for sampling in
$\delta$-RWM.

######  Corollary 3.19 (Ranking Duel without Regret).

Let $\mathcal{I}=([n],\mu,\mathcal{S}_{n},\mathcal{S}_{n})$ be an instance of
ranking duel. Then there exists an algorithm with regret:

$\operatorname{Reg}_{T}\leq
O\left(\sqrt{T}\cdot\left(\sqrt{k\log(n)}+\sqrt{\log(1/\eta)}\right)\right)$

with probability at least $1-\eta$ that runs in time
$\widetilde{O}(T^{2}n^{7})$.

As a corollary we get the fastest known equilibrium computation for ranking
duel,

######  Corollary 3.20 (Equilibrium Computation for Ranking Duel).

Let $\mathcal{I}=([n],\mu,S_{n},S_{n})$ be an instance of ranking duel. Then
there exists an algorithm computing an $\varepsilon$-CCE (Nash if the game is
zero-sum) with probability at least $1-\eta$ in time
$\tilde{O}(n^{9}\log(1/\eta)/\varepsilon^{4})$

Unfortunately, while the JSV-chain is an improvement over previous extended
linear programming approaches to dueling games [41, 5], $n^{9}$ can hardly be
called a practical running time. In fact, it should be noted there is a faster
known no-regret algorithm for perfect bipartite matchings called PermELearn
that runs in $O(Tn^{4})$ time.

Thus Theorem 3.18 is perhaps more interesting from the perspective of the
method than the result itself. Designing faster and simpler Markov chains for
sampling bipartite matchings has long been a favorite open problem in the
sampling community. Our setting gives a nice intermediate version of this
problem, as the matching problems arising from unrestricted dueling games have
particularly nice structure. In particular, they correspond to monotonic
weightings, in the sense that for every fixed vertex $v$ on the LHS on the
graph, the edge weight of $w(v,i)\geq w(v,j)$ if $i\geq j$. Matchings with
monotonic weights are actually well-studied in the literature, including the
resolution of the monotone column permanent conjecture [17] and rapid mixing
of the switch chain999The switch chain is in essence the $2$-step Glauber
Dynamics on the view of matchings as a subset of $E^{n}$. for binary monotonic
weights [31]. However despite these related results, a fast algorithm for
sampling general bipartite matchings with monotonic weights remains an
interesting open problem, and the application to practical no-regret
algorithms for dueling games gives yet another motivation for its study.

##  4 Playing Games via DP-Sampling

While MCMC-sampling is a powerful tool, standard techniques like Glauber
Dynamics may not perform well in settings that require global coordination
across coordinates. In this section, we develop a new sampling technique
toward this end based on Dynamic Programming, taking advantage of the fact
that many settings of interest, such as Colonel Blotto, additionally exhibit
certain recursive structure. In particular, we consider a large class of
problems called _Resource Allocation Games_ that broadly generalize the
Colonel Blotto game.

##### Resource Allocation Game.

In a resource allocation game, each player assigns fungible items to some
number of battlefields. Namely, for the $i$-th player, the action space
$A_{i}$ is the set of ordered size $k_{i}$ partition of $n_{i}$ for
$k_{i},n_{i}\in\mathbb{Z}^{+}$. 101010While we define actions as all
$k$-partitions of $[n]$, our algorithm also applies to action spaces that are
subsets of these partitions with arbitrary assignment constraints on each
battlefield (i.e., of the form, at most $m$ items can be assigned to battle
$j$). One can see the action space is indeed a hypergraph where the vertices
correspond to pairs $(h,x)$ interpreted as “assigning $x$ items to the $h$-th
battlefield”, and a strategy is simply a subset of vertices
$(1,x_{1}),\cdots,(k,x_{k})$ satisfying $\sum_{h=1}^{k}x_{h}=n$. Let the
variables $x_{i,h}$ denote the number of items assigned by the $i$-th player
to the $h$-th battlefields and $A_{-i}:=A_{1}\times\cdots\times A_{i-1}\times
A_{i+1}\times\cdots\times A_{m}$ denote the set of action tuples from players
other than player $i$. The reward structure of a resource allocation game is
defined by a set of battlefield reward functions $r_{i,h}:[0,n]\times
A_{-i}\mapsto\mathbb{\mathbb{R}}$ for each player $i\in[m]$ and battlefield
$h\in[k_{i}]$. Let $\mathbf{a}_{-i}\in A_{-i}$ be the actions picked by
players other than player $i$. The total reward received by the $i$-th player
is given by the sum of rewards over individual battles:

$R_{i}(x_{i,1},\cdots,x_{i,h},\mathbf{a}_{-i})=\sum_{h=1}^{k_{i}}r_{i,h}(x_{i,h},\mathbf{a}_{-i}).$

Additionally, let $r_{i,h,\mathbf{a}_{-i}}:[0,n]\mapsto\mathbb{\mathbb{R}}$ be
the restriction of $r_{i,h}$ after fixing the strategies of the other players
i.e. $r_{i,h,\mathbf{a}_{-i}}(x)=r_{i,h}(x,\mathbf{a}_{-i})$. We say the
resource allocation game is $q$-piecewise and monotonic if for every
$i\in[m],h\in[k_{i}]$, and $\mathbf{a}_{-i}\in A_{-i}$,
$r_{i,h,\mathbf{a}_{-i}}$ is a $q$-piecewise constant and monotonically
increasing function.

In the remainder of this section, we discuss how one achieves no-regret
learning for the first player (the algorithm for the other players is
analogous). For this purpose, we will drop the subscript indicating the player
number and let $n=n_{1},k=k_{1},r_{h}=r_{1,h},\mathbf{a}=\mathbf{a}_{-1}$.

##### RWM Distributions.

To achieve no-regret learning, we will need to approximately sample from the
distributions arising from running the RWM algorithm on Resource Allocation
Games. Assume that the players have played the game for $T$ rounds. Let
$a^{(t)}\in A_{-1}$ be the action tuples observed from all but the first
player at the $t$-th round. For an action $x\in A_{1}$ that assigns $x_{h}$
items to the $h$-th battlefield, RWM will set its weight $w_{T}(x)$ as

$\displaystyle
w_{T}(x)=\beta^{\sum_{h=1}^{k}\sum_{t=1}^{T}r_{h}(x_{h},a^{(t)})}\,,$ (5)

where $\beta\in[1/2,1)$ is the learning rate. For simplicity, we will define
the cumulative battlefield reward function (negated to simplify the syntax
appearing after)

$\displaystyle\ell_{h}^{(T+1)}(x_{h})=-\sum_{t=1}^{T}r_{j}(x_{h};a^{(t)}),$
(6)

so the weight for strategy $x$ can alternatively be written as
$\prod_{h=1}^{k}\beta^{\ell_{h}^{(t+1)}(x_{h})}.$ We remark that, if the
resource allocation game is monotonic and $q$ piecewise,
$\ell_{j}^{(T+1)}(\cdot)$ is also monotonically increasing and a $((q-1)\cdot
t+1)$-piecewise constant function. Though the domain of $\ell_{j}$ is of size
$n+1$, the property allows us to represent it succinctly in space $O(qt)$,
which is critical when we try to design algorithms whose runtime depends on
$n$ polylogarithmically. In this section, we focus on how one could design
algorithms to efficiently sample from $RM^{(T)}\left(\beta\right)$
approximately given succinct descriptions of the functions
$r_{h,\mathbf{a}^{(t)}}$ for all $h\in[k]$ and $t\in T$ (recall that
$r_{h,\mathbf{a}^{(t)}}$ is the restriction of the battlefield reward function
$r_{h}$ after fixing the other players’ actions). This allows us to implement
$\delta$-RWM in polylogarithmic time.

######  Theorem 4.1 (RWM in Resource Allocation Game).

Let $\mathcal{I}=\\{(A_{i},R_{i})_{i=1}^{m}\\}$ be an $m$-player monotonic,
$q$-piecewise resource allocation game where $A_{1}=P_{k}(n)$ for
$n,k\in\mathbb{Z}^{+}$. Suppose the reward of the first player is bounded by
$L_{\max}$. Then it is possible to implement $\delta$-RWM${}^{T}_{\beta}$ in
time

$\displaystyle O(Tk)\cdot\Bigg{(}$
$\displaystyle\min\bigg{(}T^{2}L_{\max}\log(1/\beta)/\delta\cdot\zeta_{1}\left(\log
T+\log\zeta_{2}\right)\cdot\log n\,,n\log n\bigg{)}+\min(Tq,n)\Bigg{)}.$

where
$\zeta_{1}:=\min\left(L_{\max}\log(1/\beta)/\delta,q\right),\zeta_{2}:=\max\left(L_{\max}\log(1/\beta)/\delta,q\right)$,
assuming access to a $Tq$-piecewise succinct description of $\ell_{h}^{(t)}$
defined in Equation 6 for all $h\in[k],t\in[T]$.

As corollaries of the above theorem, we obtain efficient no-regret learners
and algorithms for computing CCEs in Resource Allocation Games.

In the remainder of this section, we present the sampling algorithm whose
analysis leads to the proof of Theorem 4.1, and discuss a number of
applications to games in the literature including Colonel Blotto and its
variants.

###  4.1 Sampling via estimation of partition function

We will focus for the moment on how one could sample from the RWM distribution
just in round $T$. For that purpose, we often omit the superscript $T$ for the
function $\ell_{h}^{(T)}$ (Equation (6)) for simplicity. To sample with a
dynamic program, we define the partition function for an RWM distribution in
resource allocation.

##### Partition Function

The partition function $f_{h}:[0]\cup\mathbb{Z}^{+}\mapsto\mathbb{R}^{+}$ for
$h\in[k]$ is defined as the sum of partial weights of all strategies that
allocate $y$ soldiers in the subgame induced on the first $h$ battles. Namely,

$\displaystyle
f_{h}(y)=\sum_{x_{1}+\cdots+x_{h}=y}\prod_{i=1}^{h}\beta^{\ell_{i}(x_{i})}.$
(7)

It has long been known that efficient algorithms for computing the partition
function of a self-reducible problem imply efficient (approximate) samplers
for the problem’s solution space [44]. As one can see, computing the partition
function $f_{h}$ in our setting simply corresponds to counting the number of
(weighted) size $h$ partitions of $y$, which is exactly such a self-reducible
problem. Consequently, if one has the values for the partition functions
precomputed, one can use them to sample from the RWM distribution efficiently.
We provide the detailed sampling procedure below for completeness.

In particular, this is done by sampling the number of items to put in each
battlefield sequentially, conditioned appropriately on prior choices. One puts
$x_{1}\in\\{0,\ldots,n\\}$ soldier to the first battlefield with probability

$\displaystyle\Pr[x_{1}=y]\propto\beta^{\ell_{1}(y)}\cdot f_{k-1}(n-y).$ (8)

To sample from the $(h+1)$-th battlefield conditioned on the fact that one has
put $x_{1},\ldots,x_{h}$ soldiers in battles $1\ldots h$, it is enough to
sample according to the distribution

$\displaystyle\Pr\left[x_{h+1}=y|x_{1\ldots
h}\right]\propto\beta^{\ell_{h+1}(y)}\cdot
f_{k-h-1}\left(n-\left(\sum_{j=1}^{h}x_{j}\right)-y\right).$ (9)

The probabilities defined according to Equations (8), (9) yields exactly the
RWM distribution, but computing the partition function exactly can be quite
costly. For this purpose, we consider the notion of _$\delta$ -approximations_
(multiplicative) of functions.

######  Definition 4.2 ($\delta$-approximation).

Given $f:[0,n]\mapsto\mathbb{R}^{+}$ and $\hat{f}:[0,n]\mapsto\mathbb{R}^{+}$,
we say $\hat{f}$ is a $\delta$-approximation of $f$ if for all $x\in[0,n]$ we
have

$\bigg{(}1-\delta\bigg{)}f(x)\leq\hat{f}(x)\leq\bigg{(}1+\delta\bigg{)}f(x).$

Fortunately, with $\delta/(Ck)$-approximations of the partition functions for
some sufficiently large constant $C$, one can still perform
$\delta$-approximate sampling from the RWM distribution (See proof of Lemma
4.3).

Another important observation for achieving efficient (approximate) sampling
is that $\ell_{h}$, the reward function for each battlefield, is a piece-wise
constant function. Hence, further optimization is possible if the
approximations used for each partition function is also piece-wise constant
(and this is indeed the case as we will see shortly). The pseudo-code for the
sampling algorithm that takes as input the succinct descriptions of the
(approximate) partition functions and the reward functions is given below.

1:Succinct descriptions $D_{\hat{f}_{h}}$ for $h\in[k]$ ; succinct description
$D_{g_{h}}$ of the function $g_{h}(x)=\beta^{\ell_{h}(x)}$.

2:Initialize the number of unused soldiers $u=n$.

3:Initialize an empty assignment description $S$.

4:for $h=1\ldots k$ do

5: Compute the succinct description $D_{\kappa_{h}}$ of the function
$\kappa_{h}:[0,u]\mapsto\mathbb{R}^{+}$ defined as
$\displaystyle\kappa_{h}(i):=g_{h}(i)\cdot\hat{f}_{k-h}\left(u-i\right).$ (10)
$\triangleright$ $|D_{\kappa_{h}}|=|D_{g_{h}}|+|D_{\hat{f}_{h}}|$ and
$D_{\kappa_{h}}$ can be computed in time linear with respect to the
description length.

6:

7: {_Compute intervals_}

8: for $(a_{i},b_{i},y_{i})\in D_{\kappa_{h}}$ do

9: Compute the cumulative weight of constant intervals.
$\displaystyle\nu_{i}$ $\displaystyle:=y_{i}\cdot(b_{i}-a_{i}+1).$ (11)

10: {_Sample an interval_}

11: Sample $j\in 1\ldots|D_{\kappa_{h}}|$ according to the weight vector
$\nu$.

12:

13: {_Sample soldiers used in battle $h$_}

14: Sample $z_{h}$ uniformly for $\\{a_{j},a_{j}+1,\ldots b_{j}-1,b_{j}\\}$
where $[a_{j},b_{j}]$ is the $j$-th constant interval in $D_{\kappa_{h}}$.

15:

16: Add $z_{h}$ to the strategy $S$ description.

17: $u\leftarrow u-z_{h}$.

18:return $S$.

######  Lemma 4.3.

Let $\mathcal{I}=\\{(A_{i},R_{i})_{i=1}^{m}\\}$ be an $m$-player monotonic,
$q$-piecewise resource allocation game where $A_{i}=P_{k_{i}}(n_{i})$ for
$n_{i},k_{i}\in\mathbb{Z}^{+}$. At the $t$-th round, for each $h\in[k]$, let
$\hat{f}_{h}$ be $\delta/(2k)$-approximations of the partition function
defined in Equation (7), and let $g_{h}(x)=\beta^{\ell_{h}(x)}$. Assume one is
given the succinct descriptions $D_{\hat{f}_{h}}$ and $D_{g_{h}}$. Then, there
exists an algorithm Partition-Sampling which performs $\delta$-approximate
sampling from $RM^{(T)}\left(\beta\right)$ in time

$k\cdot O\left(p+\min\left(Tq,n\right)+\log n\right)$

where $p:=\max|D_{\hat{f}_{h}}|$.

###### Proof.

If we were to perform the sampling process with $f_{h}$ instead of
$\hat{f}_{h}$, we would get exactly the distribution
$RM^{(t)}\left(\beta\right)$. This follows from repeated applications of
Bayes’ rule and that we are sampling the correct conditional distribution.
Namely,

$\displaystyle\Pr\left[x_{1}=y_{1},\ldots,x_{k}=y_{k}\right]=\prod_{h=1}^{k}\Pr\left[x_{h}=y_{h}\mid
x_{h^{\prime}}=y_{h^{\prime}},\forall h^{\prime}<h\right]$

To make sure that we are performing $\delta$-approximate sampling overall, it
suffices if we perform $\delta/k$ approximate sampling for each conditional
distribution (each battlefield). To perform exact sampling, one needs to
compute the weight

$\kappa_{h}^{*}(i):=g_{h}(i)\cdot f_{k-h-1}(u-i).$

Since for every $h\in[k]$ we have $\hat{f}_{h}$ are $\delta/(2k)$
approximations of $f_{h}$, we also have $\kappa_{h}$ is $\delta/(2k)$
approximations of $\kappa_{h}^{*}$, which implies that

$(1-\delta/(2k))\sum_{i=0}^{n}\kappa_{h}^{*}(i)\leq\sum_{i=0}^{n}\kappa_{h}(i)\leq(1+\delta/(2k))\sum_{i=0}^{n}\kappa_{h}^{*}(i).$

It then follows that the distribution defined by $\kappa_{h}^{*}$ and
$\kappa_{h}$ differs by at most $\delta$ in total variation distance.

To analyze the runtime, we note that for each battlefield, we first compute
the succinct description $D_{\kappa_{h}}$ defined in Equation (10). Since it
is the point-wise multiplication between $g_{h}$, which is
$\min(Tq,n)$-piecewise constant, and $\hat{f}_{k-h-1}$, which is $p$-piecewise
constant, $\kappa_{h}$ will be $p+\min(Tq,n)$ piecewise constant. To construct
the succinct description of $D_{\kappa_{h}}$, one maintains two pointers
$a=0,b=u$ and keeps track of the interval from $D_{g_{h}}$ that $a$ is in and
the interval from $D_{\hat{f}_{h}}$ that $b$ is in. Then, one shifts $a$
forward and $b$ backward to seek for constant intervals of $D_{\kappa_{h}}$.
It is easy to see the runtime of the construction is linear with respect to
$|D_{\kappa_{h}}|$. Then, computing $\nu_{i}$ requires scanning through the
succinct description of $D_{\kappa_{h}}$ once. After that, we first sample
from a multinomial distribution with support at most $p$, which takes time
$O(p)$. Then, we sample from a uniform distribution with support at most $n$,
which takes time $O(\log n)$. Adding everything together then gives our final
runtime. ∎

###  4.2 Computing the Partition Function

We now move to showing how to (approximately) compute the partition function.
As a warmup, we will first show how this can be done exactly via dynamic
programming. In particular, we want to fill a $k\times n$ table such that the
$(h,y)$ entry corresponds to the value $f_{h}(y)$.

######  Proposition 4.4.

The values $f_{h}(y)$ for all $h\in[k]$ and $y\in[0,n]$ can be computed in
time $O\left(nk\log n\right)$.

###### Proof.

Notice that we have the following recursion

$\displaystyle f_{h}(y)=\sum_{x=0}^{y}\beta^{\ell_{h}(x)}\cdot
f_{h-1}\left(y-x\right).$ (12)

$f_{h}$ is exactly the convolution of $\beta^{\ell_{h}(\cdot)}$ and $f_{h-1}$.
Using Discrete Fast Fourier Transform, $f_{h}$ can be evaluated in time
$O(n\log n)$ ([20]). Hence, in total, the entire DP table can be filled in
time $O(nk\log n)$.

∎

Next, we will discuss how one can develop faster algorithms when $n$ is
substantially larger than $k,T$, and $L_{\max}$. Our main technical result is
an algorithm to pre-compute the partition functions “approximately” whose
runtime depends on $n$ _polylogarithmically_.

######  Proposition 4.5.

There exists an algorithm Approx-DP which constructs
$\hat{f}_{1},\cdots,\hat{f}_{k}$ such that $\hat{f}_{i}$ is a
$\delta$-approximation of the partition function $f_{i}$ pointwisely, and runs
in time

$O\left(kT^{2}L_{\max}\log(1/\beta)/\delta\cdot\zeta_{1}\left(\log
T+\log\zeta_{2}\right)\cdot\log n\right).$

where
$\zeta_{1}:=\min\left(L_{\max}\log(1/\beta)/\delta,q\right),\zeta_{2}:=\max\left(L_{\max}\log(1/\beta)/\delta,q\right)$.

This seems a bit surprising as there are in total $k\cdot(n+1)$ values that we
need to pre-compute ($f_{h}(y)$ for all $h\in[k]$ and $y\in[0,n]$). However,
notice that we are only interested in computing approximations to these
values. And, as each $f_{h}$ is itself a monotonically increasing function, we
can approximate it with a sufficiently simple piece-wise function.

######  Fact 4.6.

Given a monotonically increasing function $f:[0,n]\mapsto\mathbb{R}^{+}$, it
can be $\delta$-approximated by a function that is $d$-piecewise constant
where $d=\Theta(\log(\max_{x}f(x)/\min_{x}f(x))/\delta)$.

Hence, the algorithm Approx-DP does not need to output the entire
$k\times(n+1)$ tables specifying the partition functions. Rather it can just
construct the succinct descriptions of a series of functions
$\hat{f}_{1},\cdots,\hat{f}_{k}$ such that $\hat{f}_{i}$ is a
$\delta$-approximation of $f_{i}$. By 4.6, we can indeed find such
$\hat{f}_{i}$ that are
$\Theta(\log(\beta^{TL_{\max}})/\delta)=\Theta(TL_{\max}\log(1/\beta)/\delta)$
piecewise constant. As the first building block of the Approx-DP, we
demonstrate the routine which, given query access to an unknown monotonically
increasing function, constructs a piecewise constant approximation of the
function.

######  Lemma 4.7.

Given a monotonically increasing function $f:[0,n]\mapsto\mathbb{R}^{+}$ and
query access to $f$, there exists an algorithm Piecewise-Approximate which
outputs a piecewise function $\hat{f}$ satisfying that

  * •

$\hat{f}$ is $d$-piecewise constant for
$d=\Theta(\log(\max_{x}f(x)/\min_{x}f(x))/\delta)$.

  * •

$(1-\delta)\cdot f(x)\leq\hat{f}(x)\leq f(x)$.

  * •

the algorithm runs in time $O\left(\log n\cdot d\cdot Q\right)$.

where $Q$ is the cost of making a single query to $f$.

###### Proof.

The algorithm proceeds by iteratively finding the longest interval from a
starting point such that the function values at the endpoints are within a
$(1+\delta)$-factor of each other, and then letting $\hat{f}$ on this interval
be the constant function given by the value of $f$ on the right endpoint. By
the monotonicity of $f$, it is easy to see that $\hat{f}$ is indeed a
$\delta$-approximation of $f$ on this interval. The algorithm then repeats
this process starting from the next value on which $\hat{f}$ is not yet
defined and repeats until $\hat{f}$ has been defined on the entire domain.

Since the function values of $f$ increase by at least a factor of $(1+\delta)$
between each interval and the last, the total number of intervals is at most
$d=\Theta(\log(\max_{x}f(x)/\min_{x}f(x))/\delta)$. ∎

Algorithm 1 Piecewise-Approximate

1:Query access to $f:[0,n]\mapsto\mathbb{R}^{+}$; Approximation accuracy
$\delta$.

2:$D\leftarrow\\{\\},a\leftarrow 0$.

3:while $a\leq n$ do

4: Binary Search to find the largest $b$ such that $f(b)\leq
f(a)\cdot(1+\delta)$.

5: Add $(a,b,f(a))$ to $D$. (setting $\hat{f}(x)$ to $f(a)$ for all $a\leq
x\leq b.$)

6: $a\leftarrow b+1$.

7:return $D$.

With this in mind the construction of the series of piecewise constant
approximation functions $\hat{f}_{1},\cdots,\hat{f}_{k}$ becomes clear: one
initializes $\hat{f}_{1}=\textbf{Piecewise-Approximate}(f_{1})$ and then
defines $\hat{f}_{h}$ recursively as $\hat{f}_{h}=\textbf{Piecewise-
Approximate}(f_{h}^{\prime})$ where
$f_{h}^{\prime}(y)=\sum_{x=0}^{y}\hat{f}_{h-1}(x)\cdot g_{h}(y-x)$. Recall
that the routine Piecewise-Approximate requires query access to the input
function. Hence, we need to show how one could implement query access to
$f_{1}$ and $f_{h}^{\prime}$ for $h\in[k]$ efficiently (independent of $n$).
The former is easy given the succinct description of $f_{1}$ since
$f_{1}=\beta^{\ell_{1}(x)}$ is a $T\cdot q$ piecewise constant function. To
realize the latter, we use the fact that $f_{h}^{\prime}$ is the convolution
of $\hat{f}_{h}$ and $g_{h}$ which are both piecewise constant functions. In
particular, we give the following routine which efficiently implements query
access to convolutions of piecewise constant functions.

Algorithm 2 Convolution-Query

1:Succinct descriptions $D_{f}$,$D_{g}$ of two piece-wise constant functions
$f$, $g$; Query point $x$.

2:Preprocess $D_{f}$ to extend each tuple into the form
$(a_{i},b_{i},y_{i},s_{i})$ where $s_{i}:=\sum_{j<i}(b_{j}-a_{j}+1)\cdot
y_{j}$.

3:Let  $\displaystyle F(z)=\begin{cases}\sum_{i=0}^{z}f(i)\text{ for }i\geq
0\,,\\\ 0\text{ otherwise.}\\\ \end{cases}$

4:$res\leftarrow 0$.

5:for each interval $(a_{i},b_{i},y_{i})\in D_{g}$ do

6: $res\mathrel{+}=(F(x-a_{i})-F(x-b_{i}-1))\cdot y_{i}$.

7:return $res$.

We note that the pre-processing incurs a one-time cost for each new function
$f$ and does not need to be performed for different queries with respect to
the same function $f$. We also note $F(z)$ can be evaluated by first binary
search the first index $j$ such that for $(a_{j},b_{j},y_{j},s_{j})\in D_{f}$
we have $b_{j}\geq z$. Then use the equality $F(z)=s_{j}+(z-a_{j})\cdot
y_{j}$.

######  Lemma 4.8.

Assume one is given the succinct description $D_{f},D_{g}$ of two functions
$f,g:[0,n]\mapsto\mathbb{R}^{+}$. Let $(f\star g)(x)=\sum_{i=0}^{x}f(i)\cdot
g(x-i)$. Suppose $|D_{f}|=p_{f}$ and $|D_{g}|=p_{g}$ with $p_{f}<p_{g}$. There
exists an algorithm Convolution-Query that takes $O(p_{f}+p_{g})$ time to
preprocess $D_{f},D_{g}$ and then takes $O\left(p_{f}\cdot\log p_{g}\right)$
time to return query access $(f\star g)(x)$ for each $x\in[0,n]$.

###### Proof.

In the pre-processing step, for each tuple $(a_{i},b_{i},y_{i})\in D_{f}$, we
add an extra number $s_{i}$ which denotes the prefix-sum of all elements
before the interval $[a_{i},b_{i}]$. This can be done easily by scanning
through the tuples of succinct description in order in one pass. Then, if one
want to query the prefix sum $F(z)$, one can just find out which interval $z$
falls into by binary search and then computes in constant time with $s_{i}$.

Then, using the fact that $g$ is piecewise constant, we can rewrite the
convolution query $(f\star g)(x)$ as

$\sum_{i=0}^{x}f(x-i)\cdot
g(i)=\sum_{i=1}^{|D_{g}|}y_{i}\cdot\left(\sum_{j=x-b_{i}-1}^{x-a_{i}}f(j)\right)=\sum_{i=1}^{|D_{g}|}y_{i}\cdot\bigg{(}F(x-a_{i})-F(x-b_{i}-1)\bigg{)}.$

where $(a_{i},b_{i},y_{i})$ are tuples in $D_{g}$. Since evaluating each query
to $F$ takes at most $O(\log|D_{f}|)$ time (for binary search), the above
expression can be evaluated in time $O\left(|D_{g}|\log|D_{f}|\right)$. ∎

We are now ready to present the pseudocode and analysis of Approx-DP, whose
analysis then lead to the proof of Proposition 4.5.

Algorithm 3 Approx-DP

1:For each $h\in[k]$, succinct description $D_{g_{h}}$ of the function
$g_{h}(x)=\beta^{-\ell_{h}(x)}$; number of goods $n$; number of battlefields
$k$; approximation error $\delta$.

2:Initialize $\hat{f}_{1}$ as $g_{1}$.
$D_{\hat{f}_{1}}\leftarrow\textbf{Piecewise-
Approximate}\left(g_{1},\delta/(4k)\right).$

3:for $h=2\cdots k$ do

4: Consider the function  $\displaystyle
f_{h}^{\prime}(y)=\sum_{x=0}^{y}\hat{f}_{h-1}(x)\cdot
g_{h}(y-x)=\sum_{x=0}^{y}\hat{f}_{h-1}(x)\cdot\beta^{\ell_{h}(y-x)}.$ (13)

5: Set $\hat{f}_{h}$ to be the piecewise approximation of $f_{h}^{\prime}$.
$\displaystyle D_{\hat{f}_{h}}\leftarrow\textbf{Piecewise-
Approximate}\left(f_{h}^{\prime},\delta/(4k)\right).$

6:return $D_{\hat{f}_{h}}$ for $h\in[k]$.

We note that the query access to $g_{1}$ is by simply reading from the
succinct description $D_{g_{1}}$. Further, query access to $f_{h}^{\prime}(y)$
is implemented by routine $\textbf{Convolution-
Query}(D_{\hat{f}_{h-1}},D_{g_{h}},y)$ (see the Appendix for its pseudocode
and runtime).

###### Proof of Proposition 4.5.

We will show via induction that each $\hat{f}_{h}$ is monotonically increasing
and $\hat{f}_{h}$ an $(h\cdot\delta/k)$-approximation of the original function
$f_{h}$. Consider the function $f_{h}^{\prime}$ defined in Equation (13).
Since both $\hat{f}_{h-1}(x)$ and $\beta^{-\ell_{h}(x)}$ are monotonically
increasing, their convolution $f_{h}^{\prime}$ is also monotonically
increasing. Besides, by our inductive hypothesis, $\hat{f}_{h-1}$ is an
$((h-1)\cdot\delta/k)$-approximation of $f_{h-1}$, implying that
$f_{h}^{\prime}$ is an $((h-1)\cdot\delta/k)$-approximation of $f_{h}$. By
Lemma 4.7, $\hat{f}_{h}$ is a $(\delta/k)$-approximation of $f_{h}^{\prime}$,
and consequently a $(h\cdot\delta/k)$-approximation of $f_{h}$.

The runtime of the algorithm is dominated by the $(k-1)$ times we call the
routine Piecewise-Approximate in Line 5. Notice that
$\max_{x}f_{h}(x)/\min_{x}f_{h}(y)$ can be at most $\beta^{-\ell(x)}$ where
$\ell(x)$ is at most $TL_{\max}$. As we have argued, each $f_{h}^{\prime}$ is
always a $\delta$-approximation of $f_{h}$, which implies that
$\max_{x}f_{h}^{\prime}(x)/\min_{x}f_{h}^{\prime}(y)$ is at most
$\exp(2\cdot\log(1/\beta)TL_{\max})$. Therefore, each $\hat{f}_{h}$ is a
$O(\log(1/\beta)TL_{\max})$ constant function.

Piecewise-Approximate uses the routine Convolution-Query as its query access
to the input function $f_{h}^{\prime}$. By Lemma 4.8, Convolution-Query incurs
a one-time cost of $O(TL_{\max}\log(1/\beta)/\delta+Tq)$ to preprocess the
succinct descriptions of $g_{h}(x)=\beta^{\ell_{h}(x)}$ and $\hat{f}_{h-1}$.
Then, each query takes time $O\left(T\cdot\zeta_{1}\cdot\left(\log
T+\log\zeta_{2}\right)\right).$ where
$\zeta_{1}:=\min\left(L_{\max}\log(1/\beta)/\delta,q\right),\zeta_{2}:=\max\left(L_{\max}\log(1/\beta)/\delta,q\right)$.
By Lemma 4.7, each call to Piecewise-Approximate then takes time

$O\left(T^{2}L_{\max}\log(1/\beta)/\delta\cdot\zeta_{1}\left(\log
T+\log\zeta_{2}\right)\cdot\log n\right).$

The overall runtime just multiplies the entire expression by $k$. ∎

Combining Lemmas 4.3,4.4, and Proposition 4.5, we then obtain an efficient
algorithm for $\delta$-RWM in Resource Allocation Games, which concludes the
proof of Theorem 4.1.

###  4.3 Applications of the meta algorithm

In this section, we describe the main applications of our sampling algorithm.

##### Colonel Blotto Game

A well-studied example of the resource allocation game is the Colonel Blotto
Game. In the game, $m$ players try to assign $\\{n_{i}\\}_{i=1}^{m}$ troops to
$k$ different battlefields. For the $i$-th battlefield, the player who places
more soldiers wins the battle and earn a reward of $w_{i}\in\mathbb{Z}^{+}$
(ties are broken e.g. lexicographically).111111In the zero-sum variant the
other player also loses $w_{i}$. This can be viewed as a resource allocation
game where the reward function $r_{j}$ is simply the threshold function
$r_{j}(x)=w_{j}\cdot\mathbbm{1}(x>y)$ where $y$ is the maximum number of
soldiers placed by the other players. It is easy to see that $r_{j}$ is
monotonically increasing and $2$-piecewise constant. Hence, Theorem 4.1
immediately gives an efficient no-regret learning algorithm for the Colonel
Blotto Game.

######  Corollary 4.9 (Colonel Blotto without Regret).

Let $\mathcal{I}$ be an $m$-player Colonel Blotto Game where the $i$-th player
tries to assign $n_{i}$ soldiers to $k$ battlefields satisfying $n_{i}\leq n$.
Then there is a no-regret learning algorithm for $\mathcal{I}$ with regret:

$\operatorname{Reg}_{T}\leq
O\left(L_{\max}\sqrt{T}\cdot\left(\sqrt{k\log(n)}+\sqrt{\log(1/\eta)}\right)\right)$

with probability at least $1-\eta$ that runs in time

$Tk\cdot O\Bigg{(}\min\left(n\log n,T^{2}L_{\max}\log(TL_{\max})\log
n\right)+m\Bigg{)}.$

###### Proof.

By Lemma 2.10, to achieve no-regret learning in $T$ rounds, we simply need to
perform $\delta$-approximate sampling from the RWM distributions with learning
rate $\log(1/\beta)$, where $\delta=\sqrt{k\log n/T}$ and $\beta=1-\sqrt{k\log
n/T}$. For $T\geq C\cdot k\log n$ for a sufficiently large constant, we have
$\log(1/\beta)=O(\sqrt{k\log n/T})$. Hence, $\log(1/\beta)/\delta=O(1)$. To
show that we can perform the sampling process efficiently, we will apply
Theorem 4.1 with $q=2$ since Colonel Blotto is a resource allocation game
whose reward function is always $2$-piecewise. To do so, we need to construct
and maintain the succinct descriptions of the cumulative battlefield reward
function $\ell_{h}^{(t)}$ required by the sampling algorithm. Let
$a_{j,h}^{(t)}$ be the number of soldiers that the $j$-th player assigns to
the $h$-th battlefield at the $t$-th round. Then, for the first player, we
essentially have

$\ell_{h}^{(t)}(x)=w_{h}\cdot\sum_{t^{\prime}=1}^{t-1}\mathbbm{1}\left\\{x>\max_{j=2\cdots
m}a_{j,h}^{(t^{\prime})}\right\\}.$

After observing the assignments from other players at round $t$, one first
computes the maximum $\nu_{h}^{(t)}=\max_{j=2\cdots m}a_{j,h}^{(t)}$, which
can be done in $O(m)$ time. After that, one essentially adds
$\ell_{h}^{(t-1)}$ with the threshold function
$\mathbbm{1}\left\\{x>\nu_{h}^{(t)}\right\\}$, which takes time
$O(\min(T,n))$, which is strictly dominated by the sampling time. Overall, the
update just adds an additive factor of $O(Tkm)$ in total. ∎

This immediately gives an algorithm for computing $\varepsilon$-approximate
CCEs in the Colonel Blotto Game (or Nash Equilibria when $m=2$). Namely, we
simulate no-regret playing for all $m$ players simultaneously for $T=C\cdot
kL_{\max}^{2}\varepsilon^{-2}\log(mn/\eta)$ many rounds.

######  Corollary 4.10 (Equilibrium Computation for Colonel Blotto Games).

Let $\mathcal{I}$ be an $m$-player Colonel Blotto Game where the $i$-th player
tries to assign $n_{i}$ soldiers to $k$ battlefields satisfying $n_{i}\leq n$.
There exists an algorithm to compute an $\varepsilon$-approximate CCE (Nash if
the game is two-player zero-sum) with probability at least $1-\eta$ in time

$\displaystyle m\cdot O\Bigg{(}$
$\displaystyle\min\bigg{(}nk^{2}L_{\max}^{2}\varepsilon^{-2}\log(m/\eta)\cdot\log^{2}n\,,\,k^{4}L_{\max}^{7}\varepsilon^{-6}\log^{4}(n)\cdot\log^{3}(m/\eta)\cdot\log\left(kL_{\max}\varepsilon^{-1}\log(mn/\eta)\right)\bigg{)}$
$\displaystyle+mk^{2}\varepsilon^{-2}L_{\max}^{2}\log(mn/\eta)\Bigg{)}.$

In the regime where $n$ is far greater than $k,\varepsilon$, and $L_{\max}$,
this gives an exponential improvement over prior algorithms [5] (at the cost
of being approximate rather than exact).

##### Dice Game

Dice Games are a randomized variant of Blotto first proposed in [32] where
$m$-players121212The original dice game is defined for two players. This can
be nonetheless generalized naturally to an $m$-player setting. construct and
roll dice, with the highest roller winning the game. These games are another
natural instance of resource allocation. More formally, in the dice game each
of $m$-playes has a $k_{i}$-sided die and $n_{i}$ points to distribute. The
$i$-th player builds their die by assigning a number of dots to each face such
that the sum is exactly $n_{i}$ (where $k_{i},n_{i}\in\mathbb{Z}^{+}$). Note
that the action space $A_{i}$ is then exactly the set of ordered partitions
$P_{k_{i}}(n_{i})$. The rewards are determined by “rolling” the $m$ dice
simultaneously; the player with the highest roll wins. In other words, for
each player a face is selected uniformly at random and independently, and the
player with more dots on the chosen faces wins and earns a reward of $1$. The
reward function is given by the expected reward of this process.

Let $x_{i,h}$ be the number of dots that the $i$-th player placed on the
$h$-th face of her die for $i\in[m]$ and $h\in k_{i}$, and denote by $X_{i}$
the random variable representing the number of dots obtained by player $i$
after rolling. The expected utility for the first player is given by

$\displaystyle\Pr[X_{1}>\max(X_{2},\cdots,X_{m})]$
$\displaystyle=\frac{1}{k_{1}}\sum_{h=1}^{k_{1}}\Pr[x_{1,h}>\max(X_{2},\cdots,X_{m})]$
$\displaystyle=\frac{1}{k_{1}}\sum_{h=1}^{k_{1}}\prod_{i=2}^{m}\Pr[x_{1,h}>X_{i}].$
$\displaystyle=\frac{1}{k_{1}}\sum_{h=1}^{k_{1}}\prod_{i=2}^{m}\frac{1}{k_{i}}\sum_{h^{\prime}=1}^{k_{i}}\mathbbm{1}(x_{1,h}>x_{i,h^{\prime}}).$

Let $k=\max_{i}k_{i}$. It is not hard to see that
$\frac{1}{k_{i}}\sum_{h^{\prime}=1}^{k_{i}}\mathbbm{1}(x_{1,h}>x_{i,h^{\prime}})$
is an $O(k)$-piecewise monotonic function and
$\prod_{i=2}^{m}\frac{1}{k_{i}}\sum_{h^{\prime}=1}^{k_{i}}\mathbbm{1}(x_{1,h}>x_{i,h^{\prime}})$
is an $O(mk)$ piecewise monotonic function. Hence, this is indeed a
$O(mk)$-piecewise monotonic resource allocation game. Applying our meta-
algorithm immediately gives the following results on no-regret learning and
equilibrium computation in dice games.

######  Corollary 4.11 (No-regret Learning in Dice Games).

Let $\mathcal{I}=\\{(A_{i},R_{i})_{i=1}^{m}\\}$ be an $m$ player dice game
such that $\max_{i}k_{i}\leq k$ and $\max n_{i}\leq n$. Then there is a no-
regret learning algorithm for $\mathcal{I}$ with regret

$\operatorname{Reg}_{T}\leq
O\left(L_{\max}\sqrt{T}\cdot\left(\sqrt{k\log(n)}+\sqrt{\log(1/\eta)}\right)\right)$

with probability at least $1-\eta$, and runs in time

$Tk\cdot O\Bigg{(}\min\bigg{(}T^{2}\cdot\log(Tm)\cdot\log n,n\log
n\bigg{)}+Tkm\Bigg{)}.$

###### Proof.

Similar to the proof of Corollary 4.9, we will apply Theorem 4.1 with $q:=mk$
and $L_{\max}=1$. The main step is to maintain the succinct description of
$\ell_{h}^{(t)}$. In dice games, the cumulative reward functions
$\ell_{h}^{(t)}$ for all faces are identical and take the form

$\ell^{(t)}(x)=\sum_{t^{\prime}=1}^{t-1}\frac{1}{k_{1}}\prod_{i=2}^{m}\frac{1}{k_{i}}\sum_{h=1}^{k_{i}}\mathbbm{1}(x>x_{i,h}^{(t^{\prime})}).$

After observing the actions $x_{i,h}^{(t)}$ for $i\in[m]$, $h\in[k_{i}]$ at
the $t$-th round, we first compute the functions
$\nu_{i}^{(t)}(x)=\frac{1}{k_{i}}\sum_{h=1}^{k_{i}}\mathbbm{1}(x>x_{i,h}^{(t)})$,
which are all at most $k$-piecewise. This requires sorting
$x_{i,1}^{(t)},\cdots x_{i,k_{i}}^{(t)}$, which takes time at most $O(k\log
k)$. As a result, constructing all $\nu_{2}^{(t)},\cdots\nu_{m}^{(t)}$ takes
time in total $O(mk\log k)$. Then, we will point-wisely multiply all
$\nu_{i}^{(t)}$ together. One can proceed in a divide and conquer manner: in
the first pass, multiply together $\nu_{i}^{(t)}$ in groups of two, in the
second pass, multiply together $\nu_{i}^{(t)}$ in groups of four and continues
until all $\nu_{i}^{(t)}$ are multiplied together. There will be $\log m$
passes and the computation cost for each pass is at most $O(mk)$. Hence, the
process takes time $O(mk\log m)$ in total. Then, we add the resulting function
to $\ell^{(t-1)}$, which incurs another cost of $O(Tkm)$. Hence, in total,
(assuming $\log m<T$), it takes time $O(Tkm)$ to update $\ell^{(t)}$ at one
round. ∎

######  Corollary 4.12 (Equilibrium for Dice Games).

Let $\mathcal{I}=\\{(A_{i},R_{i})_{i=1}^{m}\\}$ be a dice game with
$n=\max(n_{1},\ldots,n_{m})$, and $k=\max(k_{1},\ldots,k_{m})$. There exists
an algorithm to compute an $\varepsilon$-CCE (Nash if the game is two-player
zero-sum) with probability at least $1-\eta$ in time

$\displaystyle m\cdot O\Bigg{(}$
$\displaystyle\min\big{(}nk^{2}\varepsilon^{-2}\log(m/\eta)\cdot\log^{2}n,k^{4}\varepsilon^{-6}\log^{4}(n)\cdot\log^{3}(m/\eta)\cdot\log(k\varepsilon^{-1}m\log(n/\eta))\big{)}$
$\displaystyle+$ $\displaystyle
mk^{4}\varepsilon^{-4}\log^{2}(mn/\eta)\Bigg{)}.$

###  4.4 Multi-resource allocation games

A natural generalization of the resource allocation game is when each player
has multiple resource types. This occurs naturally in many settings: a Colonel
in Blotto, for instance, might have access to multiple unit types including
troops, tanks, and planes (this variant was introduced in [16]). One would
expect that the reward functions should vary depending on which types of units
the Colonel chooses.

More formally, in the multi-resource allocation game, the $i$-th player has
$B_{i}$ types of fungible items. We denote by $n_{i,b}$ the number of type-$b$
items that the $i$-th player possesses. Her strategy is an allocation of these
items to $k_{i}$ battlefields. We denote $X_{i,b,h}$ as the number of type $b$
items that the $i$-th player assigns to the $h$-th battlefield. Similar to the
single-resource allocation game, for each player $i$ and each battlefield $h$,
there is a battlefield reward function

$r_{i,h}:([0,n_{i,1}])\times\cdots\times([0,n_{i,B}])\times
A_{-i}\mapsto\mathbb{R}\,,$

where we recall $A_{-i}$ is the set of strategy tuples from the players other
than $i$. Let $S\in A_{-i}$ be the strategies used by the other players, the
total reward for the $i$-th player on strategy $X=\\{X_{i,b,h}\\}$ is given by
summing over the rewards on each individual battlefield:

$R_{i}(X,S)=\sum_{h=1}^{k_{i}}r_{i,h}\left(X_{i,1,h},\cdots,X_{i,b,h},S\right).$

We now prove a variant of Theorem 4.1 for the multi-resource setting.

######  Theorem 4.13 (RWM in Multi-Resource Allocation Game).

Let $\mathcal{I}=\\{(A_{i},R_{i})_{i=1}^{m}\\}$ be an $m$-player multi-
resource allocation game where $A_{i}=P_{k_{i}}(n_{i,1})\times\cdots\times
P_{k_{i}}(n_{i,B})$ for $n_{1},\cdots n_{B},k\in\mathbb{Z}^{+}$. Suppose the
reward of the first player is bounded by $L_{\max}$,
$\max_{i\in[m],b\in[B]}n_{i,b}=n$, $\max_{i\in[m]}k_{i}=k$. Then it is
possible to implement (exact) RMW${}^{T}_{\beta}$ in time

$\displaystyle O\left(TkB(n+1)^{2B}+mTk^{2}B\cdot(n+1)^{B}\right).$

assuming query access to
$r_{i,h}:([0,n_{i,1}])\times\cdots\times([0,n_{i,B}])\times
A_{-i}\mapsto\mathbb{R}$.

###### Proof.

We proceed to analyze the partition function of the RWM distribution. As
usual, we will conduct the analysis from the first player’s perspective and
drop the subscript used to index the player. Suppose the game is played for
$T$ rounds and the observed actions from the other players’ are
$S^{(1)},\cdots,S^{(T)}$. Then, similar to Equation (6), for an assignment
$x\in A_{i}$, we will define the cumulative reward

$\ell^{(T+1)}_{h}(X_{1,h},\cdots,X_{b,h})=\sum_{t=1}^{T}r_{h}\left(X_{1,h},\cdots,X_{B,h},S^{(t)}\right).$

For simplicity, we will abbreviate $(X_{1,h},\cdots,X_{b,h})$ as $X_{*,h}$.
Then, we have the weight for the action $x$ is simply

$w_{T}(X)=\prod_{h=1}^{k}\beta^{\ell_{h}^{(T+1)}(X_{*,h})}.$

After dropping the superscript marking the rounds, accordingly, the partition
function is now $f_{h}:\left([0,n]\right)^{B}\mapsto\mathbb{R}^{+}$ for
$h\in[k]$ defined as

$\displaystyle
f_{h}(y)=\sum_{X\in\mathcal{X}_{y}}\prod_{h=1}^{k}\beta^{\ell_{h}(X_{*,h})}\,,$

where $\mathcal{X}_{y}=\\{X\in(\mathbb{Z}^{+})^{B\times k}|\forall
b\in[B]\,,\sum_{h=1}^{k}X_{b,h}=y_{b}\\}$. We still have the recursion

$\displaystyle
f_{h}(y)=\sum_{z\in{\mathcal{Z}_{y}}}f_{h}(y-z)\cdot\beta^{\ell_{h}(z)}\,,$
(14)

where $\mathcal{Z}_{y}=\\{z\in([0,n])^{B}|\forall b\,,z_{b}\leq y_{b}\\}$.

Compared to the single-resource allocation game, there are
$O\left(k\cdot(n+1)^{B}\right)$ partition function values we need to compute.
Using dynamic programming and the recursion stated in Equation (14), each of
them now takes time at most $O\left(B(n+1)^{B}\right)$. Hence, filling the
entire DP table takes time $O\left(kB\cdot(n+1)^{2B}\right)$.

After that, we likewise sample the assignment for each battlefield
sequentially. We will write $\mathbf{n}=(n_{1},\cdots,n_{B})$. For the first
battlefield, we sample

$\Pr[X_{*,1}=y]\propto\beta^{\ell_{1}(y)}\cdot
f_{k-1}\left(\mathbf{n}-y\right).$

To sample from the $(h+1)$-st battlefield, one sample according to the
distribution

$\displaystyle\Pr\left[X_{*,h+1}=y|X_{*,1\cdots
h}\right]\propto\beta^{\ell_{h+1}(y)}\cdot
f_{k-h-1}\left(\mathbf{n}-\left(\sum_{j=1}^{h}X_{*,j}\right)-y\right).$

The domain size of the distributions we sample from is
$O\left((n+1)^{B}\right)$. To compute the probabilities of each element takes
$O(B)$ times. Hence, the sampling time for one battlefield is
$O\left(B\cdot(n+1)^{B}\right)$. Hence, the runtime of the sampling process is
dominated by that of computing the partition functions.

Finally, we discuss how we maintain the function $\ell_{h}^{(t)}$ at round
$t$. To do that, we gather the strategy $S^{(t)}$ observed at the $t$-th round
from other players and then query $r_{h}(z,S^{(t)})$ for each
$z\in\left([0,n]\right)^{B}$, and add that to $\ell_{h}^{(t-1)}(z)$. Each
query takes time $O(mBk)$ (to write down the input). In total, maintaining
$\ell_{h}^{(t)}$ in $T$ rounds takes time $O(mTk^{2}B(n+1)^{B})$. Adding this
together with the time for computing the partition function then gives our
final runtime. ∎

As an immediate application, we get no-regret learning and equilibrium
computation for the multi-resource allocation games such as the multi-resource
Colonel Blotto problem.