# Sampling from the Gibbs Distribution in Congestion Games111Most of this work
has been carried out while the author was a postdoctoral fellow at the Max
Planck Institute for Informatics in Saarbrücken, Germany.

Pieter Kleer
Tilburg University
Tilburg, The Netherlands
<EMAIL_ADDRESS>
###### Abstract

Logit dynamics is a form of randomized game dynamics where players have a bias
towards strategic deviations that give a higher improvement in cost. It is
used extensively in practice. In congestion (or potential) games, the dynamics
converges to the so-called Gibbs distribution over the set of all strategy
profiles, when interpreted as a Markov chain. In general, logit dynamics might
converge slowly to the Gibbs distribution, but beyond that, not much is known
about their algorithmic aspects, nor that of the Gibbs distribution. In this
work, we are interested in the following two questions for congestion games:
i) Is there an efficient algorithm for _sampling_ from the Gibbs distribution?
ii) If yes, do there also exist natural randomized dynamics that converges
quickly to the Gibbs distribution?

We first study these questions in extension parallel congestion games, a well-
studied special case of symmetric network congestion games. As our main
result, we show that there is a simple variation on the logit dynamics (in
which we in addition are also allowed to randomly interchange the strategies
of two players) that converges quickly to the Gibbs distribution in such
games. This answers both questions above affirmatively. We also address the
first question for the class of so-called capacitated $k$-uniform congestion
games.

To prove our results, we rely on the recent breakthrough work of Anari, Liu,
Oveis-Gharan and Vinzant (2019) concerning the approximate sampling of the
base of a matroid according to strongly log-concave probability distribution.

##  1 Introduction

Congestion games constitute a rich class of games that have been studied
extensively since their introduction by Rosenthal [45]. An (unweighted)
_congestion game_ $\Gamma=(N,E,(\mathcal{S}_{i})_{i\in N},(c_{e})_{e\in E})$
consists of a set of players $N=\\{1,\dots,n\\}$ and a set of resources
$E=\\{1,\dots,m\\}$. Every player $i$ has a strategy set $S_{i}\subseteq
2^{E}$, where each strategy is a subset of resources. Furthermore, every
resource $e\in E$ is equipped with a cost function $c_{e}:\mathbb{R}_{\geq
0}\rightarrow\mathbb{R}$ that we assume to be non-negative and non-decreasing.
The goal of a player is to choose a strategy that minimizes her total cost
$C_{i}(s)=\sum_{e\in s_{i}}c_{e}(\ell_{e}(s))$, where $\ell_{e}(s)$ is the
number of players using resource $e$ in profile
$s\in\times_{i}\mathcal{S}_{i}=\mathcal{S}$. A well-known example is the class
of symmetric network congestion games, in which we are given a directed graph
$G=(V,E)$ with origin $o\in V$ and destination $d\in V$. The common strategy
set of all players is given by the set of all $o,d$-paths in $G$.

Rosenthal [45] proved that congestion games are _(exact) potential games_. He
showed that the function $\Phi:\times_{i}\mathcal{S}_{i}\rightarrow\mathbb{R}$
given by

$\Phi(s)=\sum_{e\in E}\sum_{k=1}^{\ell_{e}(s)}c_{e}(k),$

satisfies

$C_{i}(s)-C_{i}(s_{i}^{\prime},s_{-i})=\Phi(s)-\Phi(s_{i}^{\prime},s_{-i})$
(1)

for every $s\in\times_{i}\mathcal{S}_{i}$ and
$s_{i}^{\prime}\in\mathcal{S}_{i}$. Here $C_{i}(s_{i}^{\prime},s_{-i})$ is
used to denote the cost of player $i$ in the strategy profile where $i$
chooses $s_{i}^{\prime}$, and all other players choose their strategy in $s$.
The function $\Phi$ is often referred to as _Rosenthal’s potential_. The main
implication of (1) is the existence of a _pure Nash equilibrium (PNE)_ : A
strategy profile in which no player can deviate to another strategy and obtain
an improved cost [45]. This follows directly from the observation that any
sequence of _better (or best) response dynamics_ converges to a PNE in a
finite number of steps. Better response dynamics is defined as the procedure
where in every step precisely one player deviates to another strategy that
yields an improved cost (until a pure Nash equilibrium is reached). For best
response dynamics, the deviating player always deviates to a strategy that
yields the greatest possible improvement in cost.

In the last two decades, the algorithmic aspects of (pure) Nash equilibria
have been studied extensively, in both general and special classes of
congestion games; see, e.g., [19, 29, 1, 16, 33]. Two of the most prominent
questions concerning pure Nash equilibria are the following.

  1. 1.

Do (natural) player dynamics, such as better or best response dynamics,
converge to a PNE in polynomial time?

  2. 2.

If not, can one compute a PNE in polynomial time by other means?

Player dynamics, roughly speaking, come in two flavors: Either one deviates to
another strategy profile according to a deterministic rule, or a probabilistic
one. A well-known example of the latter case is _noisy (randomized) best
response dynamics_ that has received a lot of attention in practice, but seems
hard to analyze from a theoretical perspective. Here, instead of making a
deviation to another strategy according to a deterministic rule, a player
chooses a strategy from her set according to a probability distribution that
usually puts relatively more weight on strategies that will result in a lower
cost.222Such methods are special cases of what is more broadly known as
_simulated annealing_. Randomized dynamics can be studied from multiple
perspectives: Either as a randomized alternative for deterministic dynamics
converging to a pure Nash equilibrium or as a dynamical system on its one.

One well-known example of player dynamics that can be studied as a dynamical
system, and which is the topic of this paper, is the _logit dynamics_. It has
received a lot of attention in various communities, such as evolutionary game
theory (see, e.g., [46]) and experimental economics (see, e.g., [14]). The
procedure was introduced by Blume [10] as a form of randomized game dynamics
in which players update their strategy according to a _logit update rule_
[38]. The logit dynamics for congestion games can be formulated as follows.
For a given strategy profile $s$ and fixed _rationality level_ (or
_temperature_ 333The notion of temperature comes from the physics literature.)
parameter $T\geq 0$, first choose a player $i\in N$ uniformly at random, and
then have player $i$ choose a strategy $s_{i}^{\prime}\in\mathcal{S}_{i}$ with
probability

$\frac{e^{-T\Phi(s_{i}^{\prime},s_{-i})}}{\sum_{t\in\mathcal{S}_{i}}e^{-T\Phi(t,s_{-i})}}.$
(2)

Note that the denominator in (2) is a normalizing constant. The rationality
level $T\geq 0$ is used to model the amount of noise players believe there to
be in the system. When $T\rightarrow\infty$, players effectively only assign
positive probability to best responses, whereas when $T\rightarrow 0$, the
distribution in (2) approaches the uniform distribution over
$\mathcal{S}_{i}$. Also note that the dynamics indeed puts relatively more
probability mass on strategies that give a greater improvement in cost.

The logit dynamics gives rise to an _irreducible, time-reversible Markov
chain_ on the set $\mathcal{S}$ of all strategy profiles that has the _Gibbs
distribution_ $\pi$, given by

$\pi(s)=\frac{e^{-T\Phi(s)}}{\sum_{t\in\times_{i}\mathcal{S}_{i}}e^{-T\Phi(t)}}$

for $s\in\mathcal{S}$, as its unique stationary distribution. This simply
means that if one runs the logit dynamics for a sufficiently long time, the
distribution over $\mathcal{S}$ converges to the Gibbs distribution.

In fact, Auletta et al. [8] interpret the Gibbs distribution as a dynamic
equilibrium concept, which they dubbed the _logit equilibrium_ (this concept
is well-defined for general games in [8]). The goal of this work is to study
algorithmic aspects of the logit equilibrium/Gibbs distribution in congestion
games. Unfortunately, in general the logit dynamics converge slowly to the
Gibbs distribution [8], in particular, the number steps needed might be
$\Omega(e^{T\Phi_{\max}})$, where $\Phi_{\max}$ is the maximum value attained
by Rosenthal’s potential. We next give a simple example illustrating this
fact.

######  Example 1.1.

Consider the congestion game with players $N=\\{1,2\\}$ and two resources
$E=\\{a,b\\}$. Both resources $e\in\\{a,b\\}$ can be used by both players,
i.e., $\mathcal{S}_{1}=\mathcal{S}_{2}=\\{\\{a\\},\\{b\\}\\}$, and have a cost
function satisfying $c_{e}(1)=0$ and $c_{e}(2)=\phi$ for some $\phi\geq 0$.

If $\phi$ is large, the Gibbs distribution assigns weight close to $1/2$ to
the strategy profiles $(s_{1},s_{2})\in\\{(a,b),(b,a)\\}$, and weight close to
$\frac{1}{2}e^{-T\phi}\approx 0$ to $(s_{1},s_{2})\in\\{(a,a),(b,b)\\}$. Now,
informally speaking, if we consider the logit dynamics with starting profile
$(a,b)$, then the number of steps we need to run the dynamics before we see
the profile $(b,a)$ is $\Omega(e^{T\phi})$. As both profiles appear with
probability close to $1/2$ in the Gibbs distribution, this also means that we
need to run the dynamics for at least $\Omega(e^{T\phi})$ steps before the
resulting distribution over all strategy profiles is close to the Gibbs
distribution.

What is causing the slow convergence in Example 1.1? The problem is that we
need to use either the profile $(a,a)$ or $(b,b)$, both having very small
probability in the Gibbs distribution, to move from $(a,b)$ to $(b,a)$.
However, as it turns out, if one in addition with some probability is allowed
to interchange the strategies of players $1$ and $2$, then the resulting
dynamics converges quickly to the Gibbs distribution.555This is a special case
of Theorem 6. Note that this enables the possibility to directly transition
between $(a,b)$ and $(b,a)$. This motivates the following question:

Is there a (simple) Markov chain on $\mathcal{S}$ that converges rapidly to
the Gibbs distribution over $\mathcal{S}$ at any temperature $T$?

This question may be interpreted as the natural analogue of looking for other
local search procedures converging quickly to a PNE, when best/better response
dynamics does not have this property.

When the answer to the above question is not directly obvious, one can take
another step back and first ask whether it is at all possible to efficiently
_sample_ from the Gibbs distribution. Informally speaking, can we take
‘snapshots’ (according to the Gibbs distribution) from the system in
equilibrium in polynomial time? More formally speaking:

Does there exist an efficient algorithm to sample (approximately) a strategy
profile $s\in\mathcal{S}$ according to the Gibbs distribution over
$\mathcal{S}$ at any temperature $T$?

This question can be interpreted as a dynamic analogue of the second question
posed earlier for the computation of pure Nash equilibria. That is, although
(deterministic) better/best response dynamics might take a long time to
converge to a pure Nash equilibrium, one still wants to know whether a PNE can
be computed efficiently by other means. Similarly, although logit (or other
natural) dynamics might take a long time to converge to the Gibbs
distribution, we may still ask whether, by means of sampling, we can get an
impression of what the Gibbs distribution over $\mathcal{S}$ looks like.

The questions above will be made precise in Section 2. We remark that one of
the aspects that makes them non-trivial is the fact that we require the
questions to hold for _any_ temperature $T$, i.e., $T$ is considered part of
the input. (For example, in Example 1.1 we could set $T=\Theta(1/\phi)$ to
circumvent the problem arising there.)

###  1.1 Our contributions and techniques

We first address the questions from the introduction for _extension parallel
(EP)_ congestion games, a well-studied special case of symmetric network
congestion games, see, e.g., [28, 21, 22]. Here, the common strategy set of
all players is given by the set of $o,d$-paths $\mathcal{P}$ of an _extension
parallel graph_ (see Section 4 for a definition and example). Our main result
is that there is a simple Markov chain converging quickly to the Gibbs
distribution over $\mathcal{S}$ (also implying that we can sample
approximately from the Gibbs distribution).

We show that if one, in addition to the logit dynamics transitions, is allowed
to randomly interchange the strategies of two players (akin to the explanation
given after Example 1.1), the resulting Markov chain converges quickly to the
Gibbs distribution. We call this dynamics the _relaxed logit dynamics_ (see
Section 4.2 for a formal definition). Note that Theorem 6 gives a doubly
exponential improvement w.r.t. the dependence on $T\Phi_{\max}$ compared to
the lower bound as given in Example 1.1.

######  Theorem 1.2 (Informal).

The _relaxed logit dynamics_ for extension parallel (EP) congestion games, at
temperature $T$, converges to a distribution “$\epsilon$-close” to the Gibbs
distribution in at most

$n^{3}\left(\log
n+\log\log|\mathcal{P}|+\log\left(\frac{2T\Phi_{\max}}{\epsilon^{2}}\right)\right)$

steps, where $n$ is the number of players, $\mathcal{P}$ the number of paths
in the EP graph and $\Phi_{\max}$ the maximum value attained by Rosenthal’s
potential.666If one would drop the assumption that the cost functions are non-
negative (see Section 2), the parameter $\Phi_{\max}$ can be replaced by
$\Delta\Phi:=\Phi_{\max}-\Phi_{\min}$ where $\Phi_{\min}$ is the minimum value
attained by Rosenthal’s potential. This also holds for all subsequent results.

The notion of “$\epsilon$-close” refers to the fact that the distribution seen
after the indicated number of steps differs from the Gibbs distribution at
most $\epsilon$ in _total variation distance_ (see Section 2.4), a well-known
distance measure for comparing probability distributions in Markov chain
theory.

In a nutshell, Theorem 6 follows from the fact that in EP congestion games
Rosenthal’s potential is _M-convex_ , as was shown by Fujishige et al. [22].
M-convexity is a property defined in the area of discrete convex analysis [41]
(see Section 2.2).777In fact, the result above generalizes directly to
“symmetric congestion games for which Rosenthal’s potential is M-convex”, but
we are not aware of any other interesting class of congestion games for which
this is true (and therefore choose to formulate our results in terms of EP
congestion games). M-convexity of Rosenthal’s potential already fails to hold
for the smallest non-extension parallel network congestion game (the ”Figure
8” graph that has two graphs, both consisting of two parallel edges, in
series). The link between M-convexity and sampling has, roughly speaking, been
established in a series of papers by Anari et al. [2, 4, 5] through the theory
of strongly log-concave polynomials, which in turn is also largely developed
by Brändén and Huh [13] (under the name Lorentzian polynomials). In
particular, Anari et al. [4] give the first polynomial time algorithm for
approximately sampling and counting the number of bases of a given matroid,
resolving also an old conjecture by Mihail and Vazirani [40]. In this work, we
rely on the sampling result from [4], albeit for relatively simple matroid
structures.

Before proving the result above, we also give another way of sampling from the
Gibbs distribution in Section 4.1, that essentially is a more direct approach
than the sampler induced by the Markov chain result given above. The high-
level approach used for this more direct sampler (and for the additional
application given in the next paragraph) is given in Section 3. Finally, we
give an application of our results to the problem of (almost) uniformly
sampling pure Nash equilibria in EP congestion games in Section 4.3, which is,
to the best of our knowledge, the first of its kind.

Furthermore, we also study the class of so-called _$u$ -capacitated
$k$-uniform congestion games_ for given $k=(k_{1},\dots,k_{n})$ and
$u=(u_{1},\dots,u_{m})$. In such a game the strategy set of player $i\in N$ is
given by all subsets of $E$ of size $k_{i}$. Furthermore, for every $e\in E$
we are given a _capacity_ $u_{e}$ so that $c_{e}(x)=\infty$ whenever
$x>u_{e}$.

The motivation for studying these games comes from the class of _base-matroid_
congestion games, where the strategy set of every player is the set of bases
$\mathcal{B}_{i}$ of a given matroid $\mathcal{M}_{i}$ over the ground set of
resources $E$. It is well-known that best response dynamics converges to a PNE
in a polynomial number of steps in this class of games [1], and so, in
particular, a PNE can be computed in polynomial time. Given the base matroid
sampling result of Anari et al. [4], a natural question that comes to mind is
if a similar result exists for sampling from the Gibbs distribution in base
matroid congestion games. Here, we give a first result addressing this
question. (Note that in our setting the strategies of player $i\in N$ are the
bases of the $k_{i}$-uniform matroid.)

We next explain why there is a need for capacity constraints in our results. A
strategy profile $s$ can be seen as a bipartite graph where the nodes on one
side correspond to the players, having degrees $k_{i}$, and the nodes on the
other side correspond to the resources, having degrees $\ell_{e}(s)$ (the
resource load on $e$ in profile $s$). For a given profile $s$ with resource
load profile $\ell(s)$, the bipartite graph is obtained in the natural way:
There is an edge between player $i$ and resource $e$ if player $i$ uses
resource $e$ in profile $s$. Very roughly speaking, in order to apply the
sampling result in [4], we establish strong log-concavity of a certain
polynomial associated to the vectors $k$ and $u$. For this we rely on an
asymptotic enumeration formula888Asymptotic enumeration of graphs with given
degrees has been studied extensively in the area of combinatorics. for the
number of bipartite graphs with a given degree sequence, which, in terms of
congestion games, gives the number of strategy profiles that have a given
resource load profile $\ell$. The formula that we use is only valid for the
range of $k=(k_{1},\dots,k_{n})$ and resource load profiles
$\ell(s)=(\ell_{e}(s))$ satisfying the imposed capacity constraints as given
in Theorem 9. Our main result is as follows.

######  Theorem 1.3 (Informal).

There is an (almost)999See Remark 5.4. polynomial time algorithm for
approximately sampling from the Gibbs distribution in $u$-capacitated
$k$-uniform congestion games assuming that $1\leq
k_{\max}u_{\max}=o\left(U^{1/4}\right)$ when $n\rightarrow\infty$, where
$k_{\max}=\max_{i}k_{i}$, $u_{\max}=\max_{j}u_{j}$ and $U=\sum_{j}u_{j}$.

The proof of Theorem 9 reveals an interesting connection between M-convexity
and asymptotic enumeration formulas, that might be of independent interest.

To the best of our knowledge, ours are the first sampling results for the
Gibbs distribution in congestion games, beyond the well-studied case of
Glauber dynamics for the Ising model (see Section 1.2). Given the extensive
attention that logit dynamics has received in various communities, we believe
this to be an interesting line of work, at the intersection of algorithmic
game theory, combinatorics and approximate sampling, to pursue further.

In particular, for special cases of congestion games with a positive answer to
questions $(1)$ and $(2)$ as in the introduction, do there also exist positive
answers for their dynamic analogues? As a concrete open question, we ask
whether it is always possible to efficiently sample from the Gibbs
distribution in general base matroid congestion games [1]. If true, this would
provide an interesting (qualitative) game-theoretical generalization of the
sampling result of Anari et al. [4].

###  1.2 Further related work

For an exposition of the notion of logit equilibrium, and more related work,
we refer to the survey article of Ferraioli [20] and references therein. There
are also various results addressing the inefficiency of ‘long-term’ equilibria
in the context of logit dynamics, see, e.g., the works of Asadpour and Saberi
[7], Mamageishvili and Penna [36] and Penna [44].

A special case of potential games for which logit-like dynamics have been
studied extensively is the Glauber dynamics for the Ising model, which, in
game-theoretical terms, can be seen as logit dynamics in so-called _max cut
games_ , see, e.g., [24].101010There exist many generalizations of max cut
games, see, e.g., [34] and references therein, for which it might also be
interesting to study the logit dynamics. Here, we are given a graph $G=(V,E)$
of which its nodes $V$ are players that all have strategy set $\\{-1,+1\\}$.
The potential function in this case is given by $\Phi(s)=\sum_{\\{i,j\\}\in
E}s_{i}s_{j}$ for a strategy profile $s=(s_{1},\dots,s_{n})$. Whether or not
the logit dynamics are rapidly mixing in this case depends on the parameter
$T\geq 0$ and graph topology $G$, see, e.g., the work of Levin, Luczak and
Peres [35] and references therein. Jerrum and Sinclair [30] show that,
nevertheless, there exists a polynomial time algorithm to sample from the
Gibbs distribution for any parameter $T\geq 0$ and graph topology. The first
question posed in the introduction essentially aims at investigating to what
extent a similar result is possible for (special classes of) congestion games.

##  2 Preliminaries

In this section we will give all the necessary preliminaries regarding
resource allocation (or congestion) games, strongly log-concave polynomials
and the relevant Markov chain notions and results. We start with some general
notation.

All logarithms in this work have Euler’s number $e$ as their base, unless
specified otherwise. For $k\in\mathbb{Z}_{>0}$, we write
$[k]=\\{1,\dots,k\\}$. For two vectors $x,y\in\mathbb{Z}^{n}$, we write $x\leq
y$ if $x_{i}\leq y_{i}$ for $i=1,\dots,n$, and $x<y$ if strict inequality
holds for at least one $i$. Furthermore, with $|x|=\sum_{i=1}^{n}|x_{i}|$ we
denote the modulus of $x$. We use $(e_{i})_{i=1,\dots,n}$ to denote the
standard basis of $\mathbb{R}^{n}$, i.e., $e_{i}(k)=1$ if $k=i$ and
$e_{i}(k)=0$ otherwise.

###  2.1 Congestion games

A _capacitated congestion game_ $\Gamma$ is given by a tuple
$(N,E,(\mathcal{S}_{i})_{i\in N},(c_{e})_{e\in E},(u_{e})_{e\in E})$, where
$N=[n]$ is a finite set of players, $E=[m]$ a finite set of resources (or
facilities), $\mathcal{S}_{i}\subseteq 2^{E}$ is a set of strategies of player
$i\in N$, and $c_{e}:\mathbb{Z}_{\geq 0}\rightarrow\mathbb{Q}$ the cost
function of resource $e\in E$ that satisfies $c_{e}(x)=W$ whenever $x>u_{e}$
for $e\in E$ with $W$ a (sufficiently) large number.111111Think of $W$ as
being $\infty$. Unless stated otherwise, the cost functions are assumed to be
non-negative and non-decreasing. Finally, $u_{e}$ is non-negative integer
modeling the capacity on resource $e\in E$. If $u_{e}=n$ for every resource
$e\in E$, we simply call $\Gamma$ a _congestion game_.121212Extension parallel
and capacitated uniform congestion games are defined in Sections 4 and 5,
respectively. For a strategy profile
$s=(s_{1},\dots,s_{n})\in\times_{i}\mathcal{S}_{i}=\mathcal{S}$, we define
$\ell_{e}(s)$ as the number of players using resource $e$, i.e.,
$\ell_{e}(s)=|\\{i\in N:e\in s_{i}\\}|$. A game is called _symmetric_ if
$\mathcal{S}_{i}=\mathcal{S}_{j}$ for all $i,j\in[n]$. We then write
$\mathcal{P}$ to denote the common strategy set of all players.

We call $\ell(s)=(\ell_{e}(s))_{e\in E}$ the _resource load profile
corresponding to strategy profile $s$_. We say that a strategy
$s\in\mathcal{S}$ is _feasible_ if $\ell_{e}(s)\leq u_{e}$ for every $e\in E$
and write $\mathcal{S}_{f}$ to denote the set of all feasible strategy
profiles.131313We only consider games in which the set of feasible strategy
profiles is non-empty. More generally, we say that $y\in\mathbb{N}^{m}$ is a
_(feasible) resource load profile_ for $(N,E,(\mathcal{S}_{i})_{i\in
N},(u_{e})_{e\in E})$ if there is some (feasible) strategy profile $s$ such
that $y=\ell(s)$. We write $\mathcal{S}(y)$ for the set of strategy profiles
$s\in\times_{i}\mathcal{S}_{i}$ whose resource load profile is $y$.

Similarly, for symmetric congestion games we define the notion of a _strategy
load profile_ that models how many players are using a strategy
$p\in\mathcal{P}$ in a given strategy profile $s\in\mathcal{P}^{n}$. More
precisely, given a strategy profile $s\in\mathcal{P}^{n}$, we define
$z_{p}(s)=|\\{i\in N:s_{i}=p\\}|$ as the number of players choosing strategy
$p\in\mathcal{P}$ in strategy profile $s$. The vector
$z(s)=(z_{p}(s))_{p\in\mathcal{P}}$ is called the strategy load profile of
$s$. Similarly as for resource load profiles, we define (with a slight abuse
of notation) $\mathcal{S}(x)$ as the set of strategy profiles $s$ for which
$x=z(s)$.

The cost of player $i\in N$ under a strategy profile
$s=(s_{1},\dots,s_{n})\in\times_{i}\mathcal{S}_{i}$ is given by
$C_{i}(s)=\sum_{e\in s_{i}}c_{e}(\ell_{e}(s)).$ A strategy profile
$s\in\mathcal{S}$ is called a _(pure) Nash equilibrium_ if for every $i\in N$
and every $s_{i}^{\prime}\in\mathcal{S}_{i}$ it holds that $C_{i}(s)\leq
C_{i}(s_{i}^{\prime},s_{-i})$, where $(s_{i}^{\prime},s_{-i})$ denotes the
strategy profile in which player $i$ plays $s_{i}^{\prime}$ and every other
player $j\neq i$ plays $s_{j}$. We write $\text{NE}(\Gamma)$ to denote the set
of all pure Nash equilibria of $\Gamma$.

We say that $\Phi:\times_{i}\mathcal{S}_{i}\rightarrow\mathbb{R}$ is an exact
potential function for a congestion game $\Gamma$ if for every strategy
profile $s\in\times_{i}\mathcal{S}_{i}$, for every player $i\in N$ and every
unilateral deviation $s^{\prime}_{i}\in\mathcal{S}_{i}$ of $i$ it holds:
$\Phi(s)-\Phi(s_{-i},s_{i}^{\prime})=C_{i}(s)-C_{i}(s_{-i},s_{i}^{\prime}).$
Rosenthal [45] shows that

$\Phi(s)=\sum_{e\in E}\sum_{k=1}^{\ell_{e}(s)}c_{e}(k)$ (3)

is an exact potential function for any congestion game). Subsequently, we
refer to this potential function as _Rosenthal’s potential_.

A function $\phi:\\{0,\dots,n\\}\rightarrow\mathbb{R}$, is called _convex_ if
$\phi(i)-\phi(i-1)\leq\phi(i+1)-\phi(i)$ for all $i=1,\dots,n-1$. A function
$\psi:\\{0,\dots,n\\}^{m}\rightarrow\mathbb{R}$ is called _separable convex_
if it is of the form $(x_{1},\dots,x_{m})\mapsto\sum_{j=1}^{m}\psi_{j}(x_{j})$
where the $\psi_{j}$, given by $x_{j}\mapsto\psi_{j}(x_{j})$, are convex. We
say that $\phi$ is _concave_ if $-\phi$ is convex, and, similarly, $\psi$ is
_separable concave_ if $-\psi$ is separable convex. A simple, but important,
observation that we will use in this work is the fact that Rosenthal’s
potential is a separable convex function when seen as a function from resource
load profiles to the reals. That is, the function $\bar{\Phi}:\mathbb{Z}_{\geq
0}^{m}\rightarrow\mathbb{R}$, given by

$\bar{\Phi}(\alpha)=\sum_{e\in E}\sum_{k=1}^{\alpha_{e}}c_{e}(k)$ (4)

for $\alpha\in\mathbb{Z}_{\geq 0}^{m}$ is separable convex.

######  Proposition 2.1.

If the cost functions $(c_{e})_{e\in E}$ are non-decreasing, then Rosenthal’s
potential $\bar{\Phi}$ is a separable convex function.

#### The Gibbs distribution and logit dynamics.

The Gibbs distribution $\pi:\mathcal{S}\rightarrow\mathbb{R}_{\geq 0}$ over
the strategy profiles of a congestion game $\Gamma$ is given by

$\pi(s)=\frac{e^{-T\Phi(s)}}{Z}$

where $\Phi$ is Rosenthal’s potential, $T\geq 0$ a so-called temperature
parameter, and $Z$ the normalizing constant (or partition function)

$Z=\sum_{t\in\mathcal{S}_{f}}e^{-T\Phi(t)}.$

The _logit dynamics Markov chain_ 141414Formal Markov chain definitions are
given in Section 2.4. with current state $s\in\mathcal{S}$ proceeds by:

  * •

Select a player $i\in N$ uniformly at random.

  * •

For $s_{i}^{\prime}\in\mathcal{S}_{i}$, transition to
$(s_{i}^{\prime},s_{-i})$ with probability
$e^{-T\Phi(s_{i}^{\prime},s_{-i})}/Z_{i}^{\prime}$ with normalizing constant

$Z_{i}^{\prime}=\sum_{r\in\mathcal{S}_{i}}e^{-T\Phi(r,s_{-i})}.$

It is a standard fact, which can be shown by using (1), that this Markov chain
is reversible with respect to the Gibbs distribution.

###  2.2 Matroids and $M$-concavity

Let $E=[n]$ be a finite set called the _ground set_ and $\mathcal{I}\subseteq
2^{E}=\\{X:X\subseteq E\\}$ a collection of subsets of $E$ (called
_independent sets_). The pair $\mathcal{N}=(E,\mathcal{I})$ is a _matroid_ if
i) $\emptyset\in\mathcal{I}$; ii) $A\in\mathcal{I}$ and $B\subseteq A$, then
$B\in\mathcal{I}$; iii) $A,B\in\mathcal{I}$ and $|A|>|B|$, then there exists
an $a\in A\setminus B$ such that $B+a\in\mathcal{I}$.151515For $A,B,C\subseteq
E$ with $|B|,|C|\leq 1$, we use the notation $A-B+C$ to denote the set
$(A\setminus B)\cup C$. An independent set $B\in\mathcal{I}$ of maximum size
is called a _basis_. We use $\mathcal{B}$ to denote the set of all bases of
$\mathcal{N}$. The set of bases $\mathcal{B}$ satisfies the so-called _base-
exchange property_ : If $B,B^{\prime}\in\mathcal{B}$ and $e\in B\setminus
B^{\prime}$, then there exists an $e^{\prime}\in B^{\prime}\setminus B$ such
that $B+e^{\prime}-e\in B$. It safisfies the _strong base-exchange property_
if both $B+e^{\prime}-e,\ B^{\prime}-e^{\prime}+e\in B$. The _rank_ of a
matroid is the common cardinality $r$ of all bases in $\mathcal{B}$. The
$\ell$-truncation $\mathcal{M}_{\ell}=(E,\mathcal{I}_{\ell})$ of a matroid
$\mathcal{M}$ is the matroid with $A\in\mathcal{I}_{\ell}$ if and only if
$A\in\mathcal{I}$ and $|A|\leq\ell$. The _partition matroid_ is given by a
disjoint partition $E=E_{1}\cup\dots\cup E_{q}$ of the ground set $E$, and
upper bounds $u_{i}$ for $i=1,\dots,q$. A set $A\subseteq E$ is independent if
and only if $|A\cap E_{i}|\leq u_{i}$ for all $i=1,\dots,q$. The _$k$ -uniform
matroid_ is the matroid in which $A\subseteq E$ is independent if and only if
$|A|\leq k$.

A _discrete polymatroid_ (which can be seen as a multi-set generalization of a
matroid) is a finite set of vectors $R\subset\mathbb{Z}_{\geq 0}^{n}$ with the
properties that i) $\mathbf{0}\in R$; ii) if $y\in R$ and $x\leq y$, then
$x\in R$; and iii) if $x,y\in R$ with $|y|>|x|$, then there is a vector $w\in
R$ such that $x<w<\max\\{u,v\\}$ (where the maximum is taken coordinate-wise).
The set of bases $\mathcal{B}_{R}$ is given by all maximal vectors in $R$ that
have a common modulus $r$. A polymatroid satsifies the _base-exchange
property_ : if $x,y\in\mathcal{B}_{R}$ and $x_{i}>y_{i}$, then there exists an
index $j$ with $y_{j}>x_{j}$ and $x-e_{i}+e_{j}\in R$.

Finally, as a generalization of discrete polymatroids, we describe the notion
of _$M$ -convexity_ for functions [41, 43]. As we will mostly work with its
negated counterpart of _$M$ -concavity_, we will describe this first. Let
$\nu:\mathbb{Z}_{\geq 0}^{n}\rightarrow\mathbb{R}\cup\\{-\infty\\}$ be a
function.161616In particular, we set $\log(0)=-\infty$. The _effective domain_
of $\nu$ is given by

$\text{dom}(\nu)=\\{\alpha\in\mathbb{Z}_{\geq 0}^{n}:v(\alpha)>-\infty\\}.$

The function $\nu$ is called _$M^{\sharp}$ -concave_ if it satisfies the
_(symmetric) exchange property_ : For any $\alpha,\beta\in\text{dom}(\nu)$ and
any $i\in[n]$ satisfying $\alpha_{i}>\beta_{i}$, there exists a $j\in[n]$ such
that $\alpha_{j}<\beta_{j}$ and

$\nu(\alpha)+\nu(\beta)\leq\nu(\alpha-e_{i}+e_{j})+\nu(\beta+e_{i}-e_{j}).$
(5)

It is well known that a separable concave function is $M^{\sharp}$-concave
[42]. The function $\nu$ is called _$M$ -concave_ if it is
$M^{\sharp}$-concave and, in addition, there is an $r\in\mathbb{Z}_{\geq 0}$
such that $\text{dom}(\nu)\subseteq\\{\alpha:\sum_{i}\alpha_{i}=r\\}$. A
function $\nu:\mathbb{Z}_{\geq 0}^{n}\rightarrow\mathbb{R}\cup\\{\infty\\}$ is
called _$M$ -convex_ if $-\nu$ is $M$-concave.

###  2.3 Strongly log-concave polynomials

We consider polynomials $p\in\mathbb{R}[x_{1},\dots,x_{n}]$ with non-negative
coefficients. For a vector
$\beta=(\beta_{1},\dots,\beta_{n})\in\mathbb{Z}_{\geq 0}^{n}$, we write

$\partial^{\beta}=\prod_{i=1}^{n}\partial_{x_{i}}^{\beta_{i}}$

to denote the partial differential operator that differentiates a function
$\beta_{i}$ times with respect to $x_{i}$ for $i=1,\dots,n$. For
$\alpha\in\mathbb{Z}_{\geq 0}^{n}$, we write $x^{\alpha}$ to denote
$\prod_{i=1}^{n}x_{i}^{\alpha_{i}}$. Furthermore, we write
$\alpha!=\prod_{i}\alpha_{i}!$, and for $\alpha,\kappa\in\mathbb{Z}_{\geq
0}^{n}$ with $\alpha_{i}\leq\kappa_{i}$ for all $i$, we write

$\binom{\kappa}{\alpha}=\prod_{i=1}^{n}\binom{\kappa_{i}}{\alpha_{i}}.$

For a constant $t\in\mathbb{Z}_{\geq 0}$ with $t\geq\max_{i}\alpha_{i}$, we
write $\binom{t}{\alpha}=\prod_{i=1}^{n}\binom{t}{\alpha_{i}}$. Let
$\kappa\in\mathbb{Z}_{\geq 0}^{n}$ and $K=\times_{i}\\{0,\dots,\kappa_{i}\\}$.
Let $w:K\rightarrow\mathbb{R}_{\geq 0}$ be a weight function. The _generating
polynomial_ of $w$ is given by

$g_{\kappa}(x)=\sum_{\alpha\in K}w(\alpha)x^{\alpha}.$

The _support_ of $g_{\kappa}$ is the set $\text{supp}(g_{\kappa})=\\{\alpha\in
K:w(\alpha)>0\\}$. The generating polynomial $g$ is called $d$-homogeneous if
$|\alpha|=\sum_{i}\alpha_{i}=d$ for all $\alpha\in\\{0,\dots,k\\}^{m}$ with
$w_{\alpha}>0$. It is called _multi-affine_ if every variable $x_{i}$ appears
with at most multiplicity one in every monomial of $p$. For example,
$q(x_{1},x_{2})=x_{1}x_{2}$ is multi-affine, but
$r(x_{1},x_{2})=x_{1}^{2}+x_{1}x_{2}$ is not, as the multiplicity of $x_{1}$
in the first monomial is two. Finally, the _elementary symmetric polynomial of
degree $d$_, for $\kappa=(1,1,\dots,1)$, is given by

$h_{\kappa}(x)=\sum_{\alpha\in\\{0,1\\}^{n}:|\alpha|=d}x^{\alpha}.$

######  Definition 2.2 (Strong log-concavity [25]).

A polynomial $p\in\mathbb{R}[x_{1},\dots,x_{n}]$ with non-negative
coefficients is called _log-concave_ on a subset
$S\subseteq\mathbb{R}^{n}_{\geq 0}$ if its Hessian $\triangledown^{2}\log(p)$
is negative semidefinite on $S$. A polynomial $p$ is called _strongly log-
concave (SLC)_ on $S$ if for any $\beta\in\mathbb{Z}_{\geq 0}^{n}$, we have
that $\partial^{\beta}p$ is log-concave.

For convenience, the zero polynomial is defined to be strongly log-concave
always. It is interesting to note that if a $d$-homogeneous multi-affine
polynomial $p$ is SLC, then the support of $p$ must form the collection of
bases of a matroid, and, more general, if a (not multi-affine) homogeneous
polynomial is SLC, its support forms an $M$-convex set [13].

Finally, if the generating polynomial $g_{\kappa}$ is strongly log-concave,
then the probability distribution $\pi(\alpha)\propto w(\alpha)$ is called
strongly log-concave.

######  Remark 2.3.

The definition of strong log-concavity is (in this work) is not really needed,
but included for completeness. In our proofs we essentially only rely on
properties of SLC polynomials from the literature that are reviewed below. For
homogeneous generating polynomials the notion of strong log-concavity is
equivalent to that of a polynomial being _Lorentzian_ [13], or _completely
log-concave_ [3]. These equivalences are shown in [12].

We next state all properties of SLC polynomials that will be used in this
work. First of all, it is easy to check that the SLC property is preserved
under multiplication with a non-negative scalar, which we state below for sake
of reference.

######  Proposition 2.4 (Brändén and Huh [13]).

If $p\in\mathbb{R}[x_{1},\dots,x_{n}]$ is SLC and $\gamma\in\mathbb{R}_{\geq
0}$, then $\gamma p$ is SLC.

We continue with the _polarization operator_ defined by Brändén and Huh [13].
The polarization operator introduces auxiliary variables in order to turn $p$
into a multi-affine polynomial over a larger set of variables.171717We
elaborate on polarization in Section 3.1. Formally, following [13], for
$\kappa\in\mathbb{Z}_{\geq 0}^{n}$ let

$\mathbb{R}_{\kappa}[x_{i}]=\Big{\\{}\text{polynomials in
}\mathbb{R}[x_{i}]_{1\leq i\leq n}\text{ of degree at most }\kappa_{i}\text{
in }x_{i}\text{ for every }i\Big{\\}},$

and $\mathbb{R}^{a}_{\kappa}[x_{ij}]=\left\\{\text{multi-affine polynomials in
}\mathbb{R}[x_{ij}]_{1\leq i\leq n,1\leq j\leq\kappa_{i}}\right\\}.$ The
polarization operator
$\Pi_{\kappa}:\mathbb{R}_{\kappa}[x_{i}]\rightarrow\mathbb{R}^{a}_{\kappa}[x_{ij}]$
replaces every factor $x^{\alpha}$ by

$\frac{1}{\binom{\kappa}{\alpha}}\prod_{i=1}^{n}\Big{(}\text{elementary
symmetric polynomial of degree }\alpha_{i}\text{ in the variables
}\\{x_{ij}\\}_{1\leq j\leq\kappa_{i}}\Big{)}.$

######  Proposition 2.5 (Brändén and Huh [13]).

If $p$ is $d$-homogeneous and SLC over $\mathbb{R}_{\kappa}[x_{i}]$, then
$\Pi_{\kappa}(p)$ is $d$-homogeneous and SLC over
$\mathbb{R}^{a}_{\kappa}[x_{ij}]$.

We conclude this section by stating a large class of homogeneous polynomials
that are known to be strongly log-concave.

######  Proposition 2.6 (Brändén and Huh [13]).

For $\kappa\in\mathbb{Z}_{\geq 0}^{n}$ and $w:K\rightarrow\mathbb{R}_{\geq 0}$
a non-negative weight function, consider

$g_{\kappa}(x)=\sum_{\alpha\in K}\frac{w(\alpha)}{\alpha!}x^{\alpha},$ (6)

and assume that $g_{\kappa}$ is $d$-homogeneous. Let $\nu:\mathbb{Z}_{\geq
0}^{n}\rightarrow\mathbb{R}\cup\\{-\infty\\}$ be defined by
$\nu(\alpha)=\log(w(\alpha))$ for $\alpha\in K$ and $\nu(\alpha)=-\infty$
otherwise. If $\nu$ is $M$-concave, then $g_{\kappa}$ is SLC.

###  2.4 Markov chains

Let $\mathcal{M}=(\Omega,P)$ be an aperiodic, irreducible and time-reversible
Markov chain with state space $\Omega$, transition matrix $P$, and stationary
distribution $\pi$. Reversibility means that $\pi(x)P(x,y)=\pi(y)P(y,x)$ for
any $x,y\in\Omega$. We write $P^{t}(x,\cdot)$ for the distribution over
$\Omega$ at time step $t$ with initial state $x\in\Omega$. The _total
variation distance_ $d_{TV}(\pi,\sigma)$ of two distributions $\pi$ and
$\sigma$ over $\Omega$ is defined as
$d_{TV}(\pi,\sigma)=\max_{S\subseteq\Omega}|\pi(S)-\sigma(S)|=\frac{1}{2}\sum_{x\in\Omega}|\pi(x)-\sigma(x)|,$
where for a distribution $\sigma$ over $\Omega$, we write
$\sigma(S)=\sum_{x\in S}\sigma(x)$. We say that two distributions $\pi$ and
$\sigma$ are _$\epsilon$ -close_ if $d_{TV}(\pi,\sigma)\leq\epsilon$. The
total variation distance of the distribution $P^{t}(x,\cdot)$ from $\pi$ at
time $t$ with initial state $x$ is denoted by $\Delta_{x}(t)$. The _mixing
time_ of $\mathcal{M}$ with initial state $x\in\Omega$ is
$\tau_{x}(\epsilon)=\min\\{t:\Delta_{x}(t^{\prime})\leq\epsilon\text{ for all
}t^{\prime}\geq t\\}.$ Informally, $\tau_{x}(\epsilon)$ is the number of steps
until the Markov chain is $\epsilon$-close to its stationary distribution,
given that it is starting in $x$. A treaty of some more advanced Markov chain
notions is given in Appendix A, including the definition of the _modified log-
Sobolev constant $\rho=\rho(P)$_ which can be used to bound the mixing time of
a Markov chain.181818The definition of $\rho$ is deferred to Appendix A as we
actually do not need it in this work; we only rely on lower bounds on this
constant obtained by other authors. In particular, it holds that

$\tau_{x}(\epsilon)\leq\frac{1}{\rho(P)}\left(\log\log\pi(x)^{-1}+\log\left(\frac{1}{2\epsilon^{2}}\right)\right).$
(7)

#### Markov chain decomposition.

Let $\Omega=\Omega_{1}\cup\dots\cup\Omega_{m}$ be a disjoint partition of the
state space $\Omega$. Following [37], consider
$\bar{\pi}(i)=\pi(\Omega_{i})=\sum_{x\in\Omega}\pi(x)$ and let
$\bar{P}:[m]\times[m]\rightarrow[0,1]$ be defined by

$\bar{P}(i,j)=\bar{\pi}(i)^{-1}\sum_{x\in\Omega_{i},\
y\in\Omega_{j}}\pi(x)P(x,y).$

The Markov chain on $[m]$ with transition matrix $\bar{P}$ is called the
_projection chain_ on the partition $\\{\Omega_{i}\\}_{i=1,\dots,m}$. It is
time-reversible with respect to the distribution $\bar{\pi}$ over $[m]$. For
$i\in[m]$ the _restriction chain_ on $\Omega_{i}$ has transition matrix
$P_{i}:\Omega_{i}\times\Omega_{i}\rightarrow[0,1]$ given by

$P_{i}(x,y)=\left\\{\begin{array}[]{ll}P(x,y)&\text{ if }x\neq y,\\\
1-\sum_{z\in\Omega_{i}\setminus\\{x\\}}P(x,z)&\text{ if
}x=y.\end{array}\right.$

Its stationary distribution $\pi_{i}$ is given by
$\pi_{i}(x)=\pi(x)/\bar{\pi}(i)$ for $x\in\Omega_{i}$. In Appendix A.1 we give
a Markov chain decomposition result based on the modified log-Sobolev constant
$\rho$.

#### Base-exchange Markov chain.

Let $\mathcal{N}$ be a matroid and let $\pi$ be an SLC probability
distribution over the set of bases $\mathcal{B}$ given by $\pi(\alpha)\propto
w(\alpha)$ for some non-negative weight function $w:K\rightarrow\mathbb{R}$.
Here $\pi(\alpha)\propto w(\alpha)$ means that
$\pi(\alpha)=w(\alpha)/(\sum_{\alpha\in K}w(\alpha))$. The _base-exchange
Markov chain on $\mathcal{B}$_ is defined by the following transitions, where
$B\in\mathcal{B}$ is the current state of the Markov chain:

  * •

Select an element $e\in B$ uniformly at random and remove it.

  * •

Pick a base $B^{\prime}\in\mathcal{B}$ with $B^{\prime}\supset B-e$ with
probability $\propto w(B^{\prime})$ among all such bases $B^{\prime}$.

It is not hard to see, using the base-exchange property, that this procedure
defines an ergodic, time-reversible Markov chain with stationary distribution
$\pi$. Anari et al. [3] show that this chain is rapidly mixing for any matroid
$\mathcal{N}$. In particular, in a recent follow-up work, they give a (tight)
mixing time bound [5].

######  Theorem 2.7 (Anari et al. [5]).

Let $\mathcal{N}$ be matroid of rank $r$, and let $\pi$ be an SLC probability
distribution over the set of bases $\mathcal{B}$ given by $\pi(\alpha)\propto
w(\alpha)$ for some weight function $w:K\rightarrow\mathbb{R}_{\geq 0}$. Then
the mixing time of the base-exchange random walk, satisfies
$\tau(\epsilon)\leq O(r\log(r/\epsilon)).$

We note that the mixing time is independent of the size $n$ of the ground set
$E$ of the matroid $\mathcal{N}$, as well as the stationary distribution
$\pi$. In this work Theorem 2.7 is essentially only applied to partition and
uniform matroids. Furthermore, Cryan, Guo and Mousa [15] show that the
modified log-Sobolev of the base-exchange random walk satisfies $\rho\geq
1/r$, where $r$ is the rank of the matroid.

###  2.5 Sampling algorithms

Consider a class of (capacitated) congestion games
$\Gamma=(N,E,(\mathcal{S}_{i})_{i\in N},(c_{e})_{e\in E},(u_{e})_{e\in E})$
with $n$ players and $m$ resources, and cost functions $c_{e}:\mathbb{Z}_{\geq
0}\rightarrow\mathbb{Q}$ for $e\in E$. Let
$w:\mathcal{S}\rightarrow\mathbb{Q}_{\geq 0}$ be a weight function. In this
work, an algorithm for sampling $s\in\mathcal{S}$ according to a distribution
$\epsilon$-close to $\pi$ with $\pi(s)\propto w(s)$ is said to run in
_(randomized) polynomial time_ if the number of arithmetic operations can be
upper bounded by a polynomial in $n,\ m,\ \log(1/\epsilon),\
\max_{e,j}\log(c_{e}(j))$191919Assuming that the strategy sets can be
described in a “compact” form, like in the case of (symmetric) network
congestion games. Alternatively, one could replace $m$ by
$\max_{i}|\mathcal{S}_{i}|$ in case the strategy sets are assumed to be given
explicitly. and $\max_{s}\log(w(s))$. The generation of a uniform random $0/1$
bit is considered to be one arithmetic operation.

######  Remark 2.8 (Real numbers).

In this work we use Markov chains whose transition probabilities are, in
general, not rational numbers (in particular for the Gibbs distribution).
Whenever we use real numbers, it is implicitly assumed that we use
sufficiently accurate approximations to these numbers. All our results remain
valid when (real-valued) transition probabilities are replaced by sufficiently
accurate rational approximations. We note that, roughly speaking, whenever we
want to generate Markov chain transitions with probabilities proportional to
$e^{-T\Phi(s)}$ for $s\in\mathcal{S}$, our algorithms run in pseudo-polynomial
time in terms of the values of the cost functions of the congestion game under
consideration.

All our results algorithmic results are based on running Markov chains for a
sufficiently long time. We will usually write our running time bounds as the
product of two factors: The number of steps that we need to run the Markov
chain (before it’s close to stationarity), and the complexity of implementing
one such step. In particular, in all cases, the transitions probabilities of
one step are determined by a sequence of rational numbers
$a=(a_{1},\dots,a_{z})$ and $q=(q_{1},\dots,q_{z})$, and we want to sample an
index $i\in[z]$ with probability

$\frac{q_{i}e^{a_{i}}}{\sum_{i}q_{i}e^{a_{i}}}.$ (8)

Here $z$, as well as the encoding size of the $q_{i}$, will be
$\text{poly}(n,m)$. We will refer to $C=C(n,m,a)$ as the computational
complexity of sampling an index $i$ according to (approximations of) the above
probabilities in order not to overload our theorem statements. We say that
probabilities of the form (8) are _suitable_.

###  2.6 Bipartite graphs

An (undirected) bipartite graph $G=(A\cup B,F)$ is given by two disjoint sets
of nodes $A=\\{a_{1},\dots,a_{n}\\}$ and $B=\\{b_{1},\dots,b_{m}\\}$ with
$F\subseteq\\{\\{a,b\\}:a\in A,b\in B\\}$. We say that $G$ has degree sequence
$(\mathbf{x},\mathbf{y})$ if $d(a_{i})=x_{i}$ for $i=1,\dots,n$ and
$d(b_{i})=y_{j}$ for $j=1,\dots,m$, where $d(v)$ denotes the degree of node
$v$ in $G$. We write $\mathcal{G}(\mathbf{x},\mathbf{y})$ for the set of all
bipartite graphs on $A\cup B$ with degree sequence $(\mathbf{x},\mathbf{y})$.

##  3 General approach

In Section 2.1, we gave two possible definitions for the load profile of a
strategy profile $s=(s_{1},\dots,s_{n})\in\times_{i}\mathcal{S}_{i}$. For
general congestion games, we defined the resource load profile
$\ell(s)=(\ell_{e}(s))$ that keeps track of how many players use a particular
resource $e$ in $s$. For symmetric congestion games, we may in addition
consider the strategy load profile $z(s)=(z_{t}(s))_{t\in\mathcal{S}_{0}}$
that keeps track of how many player use a particular strategy $t$ from the
common strategy set $\mathcal{P}$.

A general approach for sampling a strategy profile according to the Gibbs
distribution in Section 4.1 and 5.1 will be to first sample a (resource or
strategy) load profile $\alpha$ according to approximately the right
probability, and then sample a strategy profile $s\in\mathcal{S}(\alpha)$
uniformly at random. Remember that the set $\mathcal{S}(\alpha)$ was used to
denote all strategy profiles with the given (resource or strategy) load
profile. The approach is summarized in Algorithm 1, in which we essentially
give the formulation for resource load profiles, since we use Rosenthal’s
potential $\bar{\Phi}:\times_{i}\mathcal{S}_{i}\rightarrow\mathbb{R}$ as given
in (4). The formulation for strategy load profiles is exactly the same, with
$\bar{\Phi}$ replaced by $\Phi$ as given in (3). We note that, in order to
sample a strategy load profile $s\in\mathcal{S}(\alpha)$ uniformly at random
in symmetric games, it suffices to generate a random permutation of the
players in $N=\\{1,\dots,n\\}$.

Sampling a load profile with the correct probability in our applications
corresponds to sampling a base of a discrete polymatroid according to a
strongly log-concave distribution. In order to do this, we present a reduction
of this problem to that of sampling a base of a matroid according to a
strongly log-concave distribution in Section 3.1 (after which we can rely on
Theorem 2.7).

Input : Congestion game $\Gamma$, temperature $T\geq 0$ and $\epsilon\geq 0$.

Output : Strategy profile $s\in\mathcal{S}$ according to distribution
$\bar{\pi}$ that is $\epsilon$-close to Gibbs distribution $\pi$ at
temperature $T$.

Step I: Sample load profile $\alpha$ according to a distribution
$\sigma^{\prime}$ that is $\epsilon$-close to $\pi^{\prime}$ given by
$\pi^{\prime}(\alpha)=|\mathcal{S}(\alpha)|e^{-T\bar{\Phi}(\alpha)}.$

Step II: Sample strategy profile $s\in\mathcal{S}(\alpha)$ (approximate)
uniformly at random.

ALGORITHM 1 Gibbs sampler for congestion game $\Gamma$.

###  3.1 Sampling bases of discrete polymatroids

In this section we describe how to generate a discrete polymatroid base,
according to a strongly log-concave distribution over the set of all
polymatroid bases, by reducing it to the problem of generating a base of a
matroid.202020This is a special case of sampling an element from an M-convex
set under a strongly log-concave distribution. This follows more or less
directly from Theorem 2.7 by using the notion of polarization. Polarization
can be seen as a functional version of the classical reduction from discrete
polymatroids to matroids, as given by Helgason [26].212121See also Chapter
44.6b in [47] for this reduction.

For a polymatroid $R\subset\mathbb{Z}_{\geq 0}^{n}$, consider a
$d$-homogeneous strongly log-concave polynomial
$g_{R}(x_{1},\dots,x_{n})=\sum_{\alpha\in\mathcal{B}_{R}}w(\alpha)x^{\alpha}.$
with positive coefficients and support the set of bases $\mathcal{B}_{R}$.
Consider the matroid $\mathcal{N}_{R}=(E,\mathcal{I})$ on ground set
$E=\\{(i,j):1\leq i\leq n,\ 1\leq j\leq d\\}$, where $I\in\mathcal{I}$ if and
only if the vector $\alpha(I)\in\mathbb{Z}_{\geq 0}^{n}$ given by
$\alpha_{e}=|\\{f:(e,f)\in I\\}|$ satisfies $\alpha(I)\in R$. The fact that
$\mathcal{N}_{R}$ is indeed a matroid follows directly from the fact that $R$
is a polymatroid. Note that, for a given $\alpha\in R$, we have

$|\\{I:\alpha(I)=\alpha\\}|=\binom{d}{\alpha}$ (9)

We slightly abuse notation here and write $d=(d,\dots,d)$ for the all
$d$-vector in $\mathbb{Z}^{n}$.

Then, with $\Pi(\mathcal{B}_{R})$ the set of bases of $\mathcal{N}_{R}$, the
polarization $\Pi(g)$ of $g$ can be written as

$\displaystyle\Pi(g)(y_{11},\dots,y_{1d},\dots,y_{n1},\dots,y_{nd})$
$\displaystyle=\sum_{B\in\Pi(\mathcal{B}_{R})}\binom{d}{\alpha(B)}^{-1}w(\alpha(B))\cdot
y^{B}$ $\displaystyle=\sum_{B\in\Pi(\mathcal{B}_{R})}w_{\Pi}(\alpha(B))\cdot
y^{B}$

where, for $B\in\Pi(\mathcal{B}_{R})$, we define

$w_{\Pi}(\alpha(B))=\binom{d}{\alpha(B)}^{-1}w(\alpha(B)).$ (10)

Polarization should be interpreted as spreading out the weight $w(\alpha)$ for
$\alpha\in R$ equally over all bases
$B\in\\{A:\alpha(A)=\alpha\\}\subseteq\Pi(\mathcal{B}_{R})$. Proposition 2.5
implies that $\Pi(g)$ is also strongly log-concave.

######  Example 3.1.

Let $p(x_{1},x_{2})=x_{1}^{2}x_{2}+x_{1}x_{2}$, so that
$\text{supp}(p)=\\{(2,0),(1,1)\\}$, and take $d=(2,2)$. Then

$\displaystyle\Pi_{d}(p)$
$\displaystyle=\frac{1}{2}x_{11}x_{12}(x_{21}+x_{22})+\frac{1}{4}(x_{11}+x_{12})(x_{21}+x_{22})$
$\displaystyle=\frac{1}{2}x_{11}x_{12}x_{21}+\frac{1}{2}x_{11}x_{12}x_{22}+\frac{1}{4}x_{11}x_{21}+\frac{1}{4}x_{11}x_{22}+\frac{1}{4}x_{12}x_{21}+\frac{1}{4}x_{12}x_{22}.$

Note that, looking at the support of $p$, we have $\binom{d}{\alpha}=2$
monomials corresponding to $\alpha=(2,0)$ and $\binom{d}{\alpha}=4$ monomials
corresponding to $\alpha=(1,1)$.

Corollary 3.2 below now follows directly from Theorem 2.7. It simply says the
following. Suppose the current state of the base-exchange Markov chain after
$T$ steps, starting from any state $B_{0}\in\Pi(\mathcal{B}_{R})$, is the base
$B\in\Pi(\mathcal{B}_{R})$, and suppose we output the polymatroid base
$\alpha(B)$. If $T$ is large enough, such that we are in state $B$ with
probability close to $w_{\Pi}(\alpha(B))$ for every
$B\in\Pi(\mathcal{B}_{R})$, then $\alpha(B)$ will be outputted with
probability close to $w(\alpha(B))$, with $w_{\Pi}(\alpha(B))$ and
$w(\alpha(B))$ as in (10).

######  Corollary 3.2.

Let $\pi$ be the distribution over $\mathcal{B}_{R}$ with $\pi(\alpha)\propto
w(\alpha)$, and let $\Pi_{\pi}$ be the distribution over
$\Pi(\mathcal{B}_{R})$ with $\Pi_{\pi}(B)\propto w_{\Pi}(\alpha(B))$. Let
$B\in\Pi(\mathcal{B}_{R})$ and let $\Pi_{\sigma}^{T}=P^{T}(B,\cdot)$ be the
distribution over $\Pi(\mathcal{B}_{R})$ after $T$ steps of the base-exchange
Markov chain $\mathcal{M}=(\Pi(\mathcal{B}_{R}),P)$. Let $\sigma^{T}$ be the
induced distribution over $\mathcal{B}_{R}$ given by
$\sigma^{T}(\alpha)=\sum_{B:\alpha(B)=\alpha}\Pi_{\sigma}^{T}(B).$ If
$d_{TV}(\Pi_{\sigma}^{T},\Pi_{\pi})\leq\epsilon$, then also
$d_{TV}(\sigma^{T},\pi)\leq\epsilon$.

######  Remark 3.3.

It is possible to define a more direct Markov chain on the set of all bases of
a given discrete polymatroid, and prove that this chain is rapidly mixing
(also based Theorem 2.7), but this is not necessarily needed for our results
(and not of interest of this work).

##  4 Extension parallel congestion games

An _extension parallel congestion game_ is a symmetric congestion game in
which the common strategy set $\mathcal{P}$ of the players consists of the
$o,d$-paths in a (directed) extension-parallel network $G=(V,A)$ with source
$o$ and target $d$. For two given networks $G_{i}=(V_{i},A_{i})$ with source
$o_{i}$ and target $d_{i}$ for $i=1,2$, let $G^{\prime}=(V_{1}\cup
V_{2},A_{1}\cup A_{2})$ be the union of $G_{1}$ and $G_{2}$. The _parallel
composition_ of $G_{1}$ and $G_{2}$ is the network obtained by identifying
$o_{1}$ with $o_{2}$, and $d_{1}$ with $d_{2}$. These nodes are the source and
target of $G^{\prime}$, respectively. The _series composition_ of $G_{1}$ and
$G_{2}$ is obtained by identifying $d_{1}$ with $o_{2}$. The node $o_{1}$
becomes the source of $G^{\prime}$, and $d_{2}$ its target. An _extension
parallel network_ either consists of i) a single arc $(o,d)$, ii) two
extension-parallel networks in parallel, iii) a single arc in series with an
extension parallel network. An example is given in Figure 4.1. For a given
extension parallel graph $G$, we use $\mathcal{P}=\\{p_{1},\dots,p_{q}\\}$ to
denote all $o,d$-paths in $G$. Note that for an extension parallel network we
have $q\leq|A|=m$.

$o$$d$ Figure 4.1: Example of an extension parallel network

In this section we will always be working with strategy load profiles (and so
these are sometimes simply referred to as load profiles). The set of all
possible strategy load profiles will be denoted by
$\mathcal{L}=\\{\alpha\in\\{1,\dots,q\\}^{n}:|\alpha|=n\\}$. We consider the
potential $\Phi:\mathcal{L}\rightarrow\mathbb{Q}$ defined by
$\Phi(\alpha)=\Phi(s)$ for some $s\in\mathcal{S}(\alpha)$.222222This is well-
defined as the potential value is the same for any choice of
$s\in\mathcal{S}(\alpha)$. The main result that we will need in this section
is the M-convexity of Rosenthal’s potential for EP congestion games.

######  Proposition 4.1 (Fujishige et al. [22]).

Let $\Gamma$ be an extension parallel congestion game. Then the potential
$\Phi:\mathcal{L}\rightarrow\mathbb{Q}$ defined by $\Phi(\alpha)=\Phi(s)$ for
$s\in\mathcal{S}(\alpha)$, is $M$-convex.

Before giving our main result as sketched in Section 1.1, we first give a more
direct approach for sampling from the Gibbs distribution in EP congestion
games.

###  4.1 Sampling from the Gibbs distribution

As mentioned in Section 3, and sketched in Algorithm 1, the high-level
algorithmic idea for sampling a strategy profile according to the Gibbs
distribution consists of first sampling a load profile $\alpha$ with the
correct probability, and then a strategy profile from $\mathcal{S}(\alpha)$
uniformly at random. The main result of this section, based on this approach,
is stated in Theorem 4.2.

######  Theorem 4.2.

Let $\epsilon>0$ and $T\geq 0$, and let $\Gamma$ be an extension parallel
congestion game with $n$ players. There is a randomized algorithm
$\mathcal{A}$ with output distribution $\bar{\pi}$ over $\mathcal{P}^{n}$ that
is $\epsilon$-close to the Gibbs distribution $\pi$ at temperature $T$, and
runs in (expected) time $O(C\cdot n\log(n/\epsilon))$ with $C$ the complexity
of implementing one step of a base-exchange Markov chain with suitable
probabilities (see Section 2.5).

###### Proof.

Note that for an extension parallel congestion game, the number of strategy
profiles corresponding to a given load profile $\alpha$ is
$|\mathcal{S}(\alpha)|=\frac{n!}{\alpha!}$.232323This is the number of ways in
which we can assign $n$ labeled balls to bins $b_{1},\dots,b_{p}$, where
$b_{i}$ contains $\alpha_{i}$ balls.

######  Lemma 4.3.

The $n$-homogeneous generating polynomial

$g(x_{1},\dots,x_{n})=\sum_{\alpha\in[q]^{n}:|\alpha|=n}|\mathcal{S}(\alpha)|e^{-T\Phi(\alpha)}x^{\alpha}=\sum_{\alpha\in[q]^{n}:|\alpha|=n}\frac{n!}{\alpha!}e^{-T\Phi(\alpha)}x^{\alpha}$
(11)

is strongly log-concave. Hence, the distribution $\pi^{\prime}$ over
$\mathcal{L}$ given by
$\pi^{\prime}(\alpha)\propto\frac{n!}{\alpha!}e^{-T\Phi(\alpha)}$ for
$\alpha\in\mathcal{L}$ is strongly log-concave.

###### Proof.

Strong log-concavity is preserved under scalar multiplication by Proposition
2.4, so it suffices to show that

$\frac{1}{n!}g(x)=\sum_{\alpha\in[q]^{n}:|\alpha|=n}\frac{e^{-T\Phi(\alpha)}}{\alpha!}x^{\alpha}$

is strongly log-concave. In turn, by Proposition 2.6, it is sufficient to show
that $\log\left(e^{-T\Phi(\alpha)}\right)=-T\Phi(\alpha)$ is an $M$-concave
function on its effective domain. As $T\geq 0$, this is equivalent to showing
that $\Phi(\alpha)$ is $M$-convex on its effective domain
$\mathcal{L}=\\{\alpha\in[q]^{n}:|\alpha|=n\\}$. This follows from Proposition
4.1. ∎

Because of Lemma 4.3, the polarization $\Pi(g)$ of $g$ in (11) is also
strongly log-concave. The support of $\Pi(g)$ can be seen as the bases of the
$n$-uniform matroid $\mathcal{N}$ on ground set $\\{(i,j):1\leq i,j\leq n\\}$.
Our algorithm now consists of first running the base-exchange Markov chain for
$O(n\log(n/\epsilon))$ steps, starting from any initial base. We output
$\alpha(B)$, where $B$ is the state we are in after the $O(n\log(n/\epsilon))$
steps that were carried out. The resulting distribution
$\sigma^{\prime}(\alpha)$ over $\mathcal{L}$ satisfies
$d_{TV}(\sigma^{\prime},\pi^{\prime})\leq\epsilon$ by Corollary 3.2. We then
uniformly at random choose a strategy profile from $\mathcal{S}(\alpha)$. Let
$\bar{\pi}$ be the resulting output distribution over $\mathcal{S}$. It
remains to show that $d_{TV}(\pi,\bar{\pi})\leq\epsilon$, which can be done
using a simple calculation that is deferred to Appendix B.2.

We conclude with analysing the running time of the algorithm. One step of the
base-exchange Markov chain can be implemented in time $O(C)$ by definition.
Generating an $s\in\mathcal{S}(\alpha)$ uniformly at random can be done by
generating a uniform random permutation $\mu$ of $\\{1,\dots,n\\}$. We set
$s_{i}=p_{1}$ for players $i=\mu(1),\dots,\mu(\alpha_{1})$, $s_{i}=p_{2}$ for
players $\mu(\alpha_{1}+1),\dots,\mu(\alpha_{2}+1)$, and so on. Generating a
uniform random permutation can be done in time $O(n\log(n))$ using random
$0/1$ bits. ∎

###  4.2 Relaxed logit dynamics

In this section, we give the proof of Theorem 6, reformulated in Theorem 4.4
below. Formally, the _relaxed logit dynamics Markov chain_ with current state
$s\in\mathcal{P}^{n}$ proceeds by:

  * •

With probability $\frac{1}{2}$: Select two players $i,j\in N$ uniformly at
random and transition to $s^{\prime}$ given by

$s_{k}^{\prime}=\left\\{\begin{array}[]{ll}s_{i}&\text{ if }k=j\\\
s_{j}&\text{ if }k=i\\\ s_{k}&\text{ otherwise.}\end{array}\right.$

  * •

With probability $\frac{1}{2}$: Perform a transition according to the logit
dynamics (as in Section 2.1).

We note that for any symmetric congestion game, this is a well-defined
ergodic, time-reversible Markov chain with the Gibbs distribution as
stationary distribution.

######  Theorem 4.4.

For an extension parallel congestion game $\Gamma$ with common strategy set
$\mathcal{P}$ and initial state $s\in\mathcal{P}^{n}$, the mixing time of the
relaxed logit dynamics Markov chain at temperature $T\geq 0$ satisfies

$\displaystyle\tau_{s}(\epsilon)\leq n^{3}\left(\log
n+\log\log|\mathcal{P}|+\log\left(\frac{2T\Phi_{\max}}{\epsilon^{2}}\right)\right)$

where $\Phi_{max}=\max_{r\in\mathcal{S}}\Phi(r)$ is the maximum value attained
by Rosenthal’s potential over $\mathcal{P}^{n}$.

Compared to the mixing time of the (non-relaxed) logit dynamics for general
games, we get a doubly exponential improvement in terms of the dependence on
$T\Phi_{max}$ (at the cost of a small polynomial increase in the dependence on
$n$).

###### Proof of Theorem 4.4.

We will use a Markov chain decomposition argument based on the two operations
that define the relaxed logit dynamics Markov chain. We first partition the
state space $\mathcal{S}=\mathcal{P}^{n}$ naturally based on load profiles by
setting $\Omega_{\alpha}=\mathcal{S}(\alpha)$ for $\alpha\in\mathcal{L}$,
where as before we have $\mathcal{L}=\\{\alpha:\alpha\in[q]^{n}\text{ and
}|\alpha|=n\\}$. Our proof approach is to apply the Markov chain decomposition
theorem of Hermon and Salez [27] as given in Theorem A.1. In particular, for
this we will need to bound the modified log-Sobolev constants of the
projection and restriction chains. We start with the modified log-Sobolev
constant $\bar{\rho}$ of the projection chain.

The projection chain $\bar{P}$ has state space $\mathcal{L}$ and stationary
distribution $\bar{\pi}(\alpha)=|\mathcal{S}(\alpha)|e^{-T\Phi(\alpha)}$ for
$\alpha\in\mathcal{L}$. Let $\alpha,\beta\in\mathcal{L}$ such that
$\sum_{e}|\alpha_{e}-\beta_{e}|=2$, i.e., there exist paths $p$ and
$p^{\prime}$ such that

$\alpha_{e}=\left\\{\begin{array}[]{ll}\beta_{e}+1&\text{ if }e=p\\\
\beta_{e}-1&\text{ if }e=p^{\prime}\\\ \alpha_{e}&\text{ if }e\in
E\setminus\\{p,p^{\prime}\\}.\end{array}\right.$

In this case we say that $\alpha$ and $\beta$ are _adjacent load profiles
differing on paths $p$ and $p^{\prime}$_. Note that if
$s\in\mathcal{S}(\alpha)$ and $s^{\prime}\in\mathcal{S}(\beta)$ are such that
they differ by a deviation of some player $i$ from path $p$ to path
$p^{\prime}$, then
$P(s,s^{\prime})=\frac{1}{2n}\frac{\exp(-T\Phi(p^{\prime},s_{-i}))}{Z^{\prime}}$
and this expression is the same for every such player $i$ with $s_{i}=p$.
Moreover, note that $\pi(x)=\pi(y)$ for any two strategy profiles
$x,y\in\mathcal{S}(\alpha)$.

For some fixed choice of strategy profile $x\in\Omega_{\alpha}$ and player $i$
using path $p$, i.e., $s_{i}=p$, the transition probabilities for adjacent
load profiles can then be seen to equal242424Here $Z$ and $Z^{\prime}$ are the
normalizing constants as in Section 2.1

$\displaystyle
2\bar{P}(\alpha,\beta)=\frac{1}{\bar{\pi}(\alpha)}\sum_{x\in\Omega_{\alpha},y\in\Omega_{\beta}}\pi(x)P(x,y)$
$\displaystyle=\frac{\pi(x)}{\bar{\pi}(\alpha)}\frac{\alpha_{p}}{n}|\mathcal{S}(\alpha)|\frac{\exp(-T\Phi(\beta))}{Z^{\prime}}$
$\displaystyle=\frac{\exp(-T\Phi(\alpha))/Z}{|\mathcal{S}(\alpha)|\exp(-T\Phi(\alpha))/Z}\frac{\alpha_{p}}{n}|\mathcal{S}(\alpha)|\frac{\exp(-T\Phi(\beta))}{Z^{\prime}}$
$\displaystyle=\frac{\alpha_{p}}{n}\frac{\exp(-T\Phi(\beta))}{Z^{\prime}}$
$\displaystyle=2\alpha_{p}P(s,s^{\prime})$ (12)

where the last equality is true for any choice of $s\in\mathcal{S}(\alpha)$
and $s^{\prime}\in\mathcal{S}(\beta)$. Note that this implies that for any
$\alpha,\beta\in\mathcal{L}$, $s\in\mathcal{S}(\alpha)$ and
$s^{\prime}\in\mathcal{S}(\beta)$, we have

$\frac{P(s,s^{\prime})}{\bar{P}(\alpha,\beta)}=\frac{1}{\alpha_{p}}\geq\frac{1}{n}.$
(13)

The lower bound of $1/n$ will serve as our lower bound on $\chi$ as defined in
Appendix A.1. In order to bound the modified log-Sobolev constant of the
projection chain, one can use a comparison argument (as defined in Appendix
A.2) with the base-exchange Markov chain on the support of the polarization
$\Pi(g_{\Gamma})$ of $g_{\Gamma}$ as in (11). In this section the support
corresponds to the set of bases of an $n$-uniform matroid. In particular, it
holds that

$\bar{\rho}\geq\frac{1}{n}\cdot\rho(\Pi(\mathcal{L}))\geq\frac{1}{n^{2}},$
(14)

where $\rho(\Pi(\mathcal{L}))$ is the modified log-Sobolev constant of the
base-exchange Markov chain on the support of $\Pi(g)$ with $g$ as in (11). The
second inequality comes from the fact that $\rho(\Pi(\mathcal{L}))\geq 1/n$,
as was shown by Cryan, Guo and Mousa [15]. The first inequality is not hard to
see, but we defer it to Appendix B.3 as it requires a Markov chain comparison
argument between two Markov chains on different state spaces.

We continue with bounding the modified log-Sobolev constant of the restriction
chains. In order to do this, we will use a comparison argument with the
_random transposition Markov chain_ on the set $S_{k}$ of all permutations of
$\\{1,\dots,k\\}$. Given a permutation $\sigma$, this chain proceeds by
selecting two positions $a$ and $b$ uniformly at random, and interchanging the
positions of the elements $\sigma(a)$ and $\sigma(b)$. With $\rho_{rt}$
denoting the modified log-Sobolev constant of this chain, it follows that for
every $\alpha\in\mathcal{L}$, we have

$\rho_{\alpha}\geq\rho_{rt}\geq\frac{1}{n-1}$ (15)

using the fact that $\rho_{rt}\geq 1/(n-1)$, as shown by Goel [23]. This
comparison argument is also deferred to Appendix B.3. Now, applying Theorem
A.2, it follows that $\bar{\rho}\geq 1/n^{3}$. Plugging this into (7), it then
follows that

$\tau_{s}(\epsilon)\leq n^{3}\left(\log
n+\log\log|\mathcal{P}|+\log\left(\frac{2T\Phi_{\max}}{\epsilon^{2}}\right)\right)$

using that $\pi(s)^{-1}\leq|\mathcal{P}|^{n}e^{-T\Phi_{\max}}$ for every
$s\in\mathcal{S}$, because of the non-negativity of the cost functions. ∎

###  4.3 Uniform sampling of pure Nash equilibria

In Theorem 4.5 we show that the result in Theorem 4.2 also implies that, for
an extension parallel congestion game $\Gamma$, we can (approximate) uniformly
at random sample a pure Nash equilibrium from the set $\text{NE}(\Gamma)$ of
all pure Nash equilibria of $\Gamma$ in pseudo-polynomial time. That is, we
sample every $s\in\text{NE}(\Gamma)$ with probability approximately
$1/|\text{NE}(\Gamma)|$. The (approximate) uniform sampling of combinatorial
objects has received a lot of attention in the last thirty years, in
particular within the area of theoretical computer science. However, to the
best of our knowledge, no non-trivial results for (pure) Nash equilibria are
known, despite the fact that the problem of computing Nash equilibria has
received much attention.

For the proof of Theorem 4.5 we use the fact that Nash equilibria are
precisely the profiles minimizing Rosenthal’s potential in EP congestion
games. Furthermore, we will exploit the fact that Theorem 4.2 holds for any
temperature $T\geq 0$. In particular, if we set $T$ large enough, then most
weight in the stationary distribution will be assigned to profiles minimizing
Rosenthal’s potential (under the assumption that the cost functions are
integer-valued). This means that, with high probability, Algorithm 1 will
output a strategy profile minimizing Rosenthal’s potential with domain
$\mathcal{S}$.252525Whenever we refer to Algorithm 1, we mean the
implementation of the high-level approach as given in the previous section. We
will use the Gibbs distribution with base $2$ instead of $e$ to avoid having
to work with real numbers. The full proof of Theorem 4.5 is given in Appendix
B.4

######  Theorem 4.5.

Let $\epsilon>0$ and let $\Gamma$ be an extension parallel congestion game
with integer-valued cost functions and $n$ players. There is a randomized
algorithm $\mathcal{A}$ with output distribution $\bar{\pi}$ over
$\text{NE}(\Gamma)$ that is $\epsilon$-close to the uniform distribution over
$\text{NE}(\Gamma)$, and runs in (expected) time polynomial in
$n,m,\Phi_{\max}$ and $\log(1/\epsilon)$ where $\Phi_{\max}$ is the maximum
value attained by Rosenthal’s potential.

######  Remark 4.6.

The pseudo-polynomial dependence, coming from the polynomial dependence on
$\Phi_{\max}$ rather than $\log_{2}(\Phi_{\max})$, arises from the fact that
we have to compute transition probabilities of the form
$2^{a_{i}}/\sum_{i}2^{a_{i}}$, where the $a_{i}$ are integers, which requires
$\Omega(\sum_{i}a_{i})$ random $0/1$ bits (following the notion of suitable
probabilities in Section 2.5). However, there is no _a priori_ reason that the
problem of (approximately) sampling pure Nash equilibria according to the
uniform distribution requires pseudo-polynomial (in the input size of the
original congestion game) time, as opposed to sampling from the Gibbs
distribution. We leave open the question of finding a truly polynomial time
algorithm.

##  5 Capacitated uniform congestion games

In this section, we consider _$u$ -capacitated $k$-uniform congestion games_
for vectors $u=(u_{1},\dots,u_{m})$ and $k=(k_{1},\dots,k_{n})$. We write
$K=|k|=\sum_{i}k_{i}$ and $U=|u|=\sum_{e}u_{e}$. The vector $u$ models the
capacities of the resources $e\in E$, i.e., the variables $(u_{e})_{e\in E}$
as defined in Section 2.1. The strategy set of player $i\in N$ is given by all
subsets $S\subseteq E$ of cardinality $|S|=k_{i}$, i.e., the bases of the
$k_{i}$-uniform matroid on $E$. We write $\Gamma(u,k)$ for the collection of
all $u$-capacitated $k$-uniform congestion games. We remark that in this
section _load profiles_ will refer to resource load profiles as defined in
Section 2.1, and no longer to _path load_ profiles as considered in Section 4.

Note that we can naturally model a feasible strategy profile in
$s=(s_{1},\dots,s_{n})\in\mathcal{S}$ of a capacitated uniform congestion game
as a (simple) bipartite graph $G=(N\cup E,F)\in\mathcal{G}(u,k)$ on $N\cup E$:
There is an edge $\\{i,e\\}\in F$ if and only if player $i\in N$ uses resource
$e\in E$ in $s_{i}$.

The main result needed in this section is stated in Proposition 5.1 below. We
use the notation $[x]_{b}=x(x-1)\cdots(x-b+1)$ for $x,b\in\mathbb{Z}_{\geq
0}$. For a bipartite degree sequence $(k,\alpha)$, we then write
$K_{b}=\sum_{i=1}^{n}[k_{i}]_{b}$ and $A_{b}=\sum_{j=1}^{m}[\alpha_{j}]_{b}$.
Note that $K=A=K_{1}=A_{1}$.

######  Proposition 5.1 (McKay [39]).

Let $\mathcal{D}$ be the collection of all bipartite degree sequences
$(k,\alpha)$ for which $1\leq k_{\max}\alpha_{\max}=o\left(K^{1/4}\right)$.
Then

$|\mathcal{G}(k,\alpha)|=\frac{K!}{\prod_{i}k_{i}!\prod_{j}\alpha_{j}!}\exp\left(-\frac{K_{2}}{K^{2}}\cdot
A_{2}+O\left(\max\\{k_{\max},\alpha_{\max}\\}^{4}/K\right)\right)$

as $K\rightarrow\infty$.

###  5.1 Sampling from the Gibbs distribution

In this section we give an (almost polynomial time) sampling algorithm that
samples from a distribution which is close to the Gibbs distribution (provided
the game is sufficiently large). That is, we show that for a large class of
pairs $(u,k)$, we can sample from a distribution close to the Gibbs
distribution.

We follow again the high-level approach in Algorithm 1. The set of all
feasible load profiles is now given by $L(k,u)=\left\\{\alpha:0\leq\alpha\leq
u\text{ and }|\alpha|=\sum_{i}k_{i}\right\\}$ and
$\mathcal{S}(\alpha)=\mathcal{G}(k,\alpha)$ for any feasible load profile
$\alpha\in L(k,u)$. Recall that we want to sample an $\alpha\in L(k,u)$ with
probability proportional to (approximately)
$\approx|\mathcal{S}(\alpha)|e^{-T\Phi(\alpha)},$ and then sample a strategy
profile $s\in\mathcal{S}(\alpha)$ with probability $\approx
1/|\mathcal{S}(\alpha)|$.

A couple of problems arise here compared to the case of extension parallel
congestion games. First of all, there is no polynomial time algorithm known to
compute the numbers $w_{\alpha}=|\mathcal{S}(\alpha)|$.262626In fact, it is
still an open question whether or not this problem is $\\#$P-complete (see,
e.g., [31]). Instead, we will rely on a _fully-polynomial randomized
approximation scheme_ for computing approximations $\hat{w}_{\alpha}$ to the
numbers $w_{\alpha}$ up to arbitrary precision [9, 31]. Secondly, in this case
the polynomial

$g(x_{1},\dots,x_{n})=\sum_{\alpha\in
L(k,u)}|\mathcal{S}(\alpha)|e^{-T\Phi(\alpha)}x^{\alpha}$ (16)

is in general not strongly log-concave. We overcome this problem by showing
that we can restore strong log-concavity ‘approximately’ when the game becomes
large, and when there are, in addition, suitable capacity constraints. We do
this by using asymptotic enumeration formulas for the number of bipartite
graphs with a given degree sequence, an area that has received considerable
attention in combinatorics. It turns out that replacing
$|\mathcal{S}(\alpha)|$ by an asymptotic approximation $\phi(\alpha)$ in (16)
gives rise to a strongly log-concave polynomial.

Finally, the problem of sampling a strategy profile
$s\in\mathcal{S}(\alpha)=\mathcal{G}(k,\alpha)$ now corresponds to that of
sampling a bipartite graph with degree sequence $(k,\alpha)$ for which many
algorithms are known. The main result of this section is given in Theorem 5.2.

######  Theorem 5.2.

Let $\epsilon\geq 0$, let $\pi$ be the Gibbs distribution at temperature
$T\geq 0$, and let $\mathcal{D}$ be the the class of all congestion games
$\Gamma(k,u)$ satisfying

$1\leq k_{\max}u_{\max}=o\left(K^{1/4}\right).$ (17)

There is a randomized algorithm $\mathcal{A}$ for the class $\mathcal{D}$, and
a constant $K_{0}\geq 0$, such that the output distribution $\bar{\sigma}$
over $\mathcal{S}$ has the property that

$d_{TV}(\bar{\sigma},\pi)\leq\epsilon$

whenever $K\geq K_{0}$. The algorithm runs in (expected) time

$C\cdot n\left(\log
n+\log\log|\mathcal{P}|+\log\left(\frac{2T\Phi_{\max}}{\epsilon^{2}}\right)\right)$

with
$C(n,m,\epsilon,\Phi_{\max})=\text{\emph{poly}}(1/\epsilon,n,m,\Phi_{\max})$.

###### Proof.

Setting

$\phi(\alpha)=\frac{K!}{k!\alpha!}\exp\left(-\frac{K_{2}}{K^{2}}\cdot
A_{2}\right)$

it follows, assuming (17) holds, that for any $0\leq\alpha\leq u$, we have
$\phi(\alpha)=(1+o(1))|\mathcal{S}(\alpha)|$, where $o(1)$ is with respect to
$K\rightarrow\infty$. In particular if $K\geq K_{0}$ for $K_{0}$ large enough,
it follows that

$\frac{1}{2}|\mathcal{S}(\alpha)|\leq\phi(\alpha)\leq\frac{3}{2}|\mathcal{S}(\alpha)|.$
(18)

The next step is now to show that replacing $|\mathcal{S}(\alpha)|$ by
$\phi(\alpha)$ in (19) gives rise to a strongly log-concave polynomial. The
crucial observation here is to see that
$A_{2}=\sum_{j}\alpha_{j}(\alpha_{j}-1)$ is a separable convex function.

######  Lemma 5.3.

The $K$-homogeneous generating polynomial

$g(x_{1},\dots,x_{n})=\sum_{\alpha\in
L(k,u)}\frac{K!}{k!\alpha!}\cdot\exp\left(-\frac{K_{2}}{K^{2}}\cdot\sum_{j=1}^{m}\alpha_{j}(\alpha_{j}-1)\right)\exp\left(-T\Phi(\alpha)\right)\cdot
x^{\alpha}$ (19)

is strongly log-concave.

###### Proof.

Following the proof of Lemma 4.3, first observe that272727Note that $k$ and
all quantities involving $k$ are considered fixed.

$\frac{k!}{K!}g(x_{1},\dots,x_{n})=\sum_{\alpha\in
L(k,u)}\frac{1}{\alpha!}\exp\left(-\frac{K_{2}}{K^{2}}\cdot\sum_{j=1}^{m}\alpha_{j}(\alpha_{j}-1)\right)\exp\left(-T\Phi(\alpha)\right)x^{\alpha}$

is strongly log-concave as well because of Proposition 2.4. Then, in order to
apply Proposition 2.6, it suffices to show that

$-\left(\frac{K_{2}}{K^{2}}\cdot\sum_{j=1}^{m}\alpha_{j}(\alpha_{j}-1)+T\Phi(\alpha)\right)$

is $M$-concave over its domain $L(k,u)$.282828That is, formally speaking, we
define it to be $-\infty$ outside of $L(k,u)$ This follows directly from the
fact that both $\sum_{j=1}^{m}\alpha_{j}(\alpha_{j}-1)$ and $\Phi(\alpha)$ are
separable convex functions in $(\alpha_{1},\dots,\alpha_{m})$ over the
(effective) domain $L(k,u)$, and the fact that $K_{2},K,T\geq 0$. Separable
convex functions (over effective domain $L(k,u)$) are known to be $M$-convex
[42]. ∎

One can now carry out similar steps as in the proof of Theorem 4.2, albeit
with some modifications. Again, the polarization $\Pi(g)$ of $g$ as in (19) is
strongly log-concave as well. The support of $\Pi(g)$ is now the set of bases
of the $n$-truncation of a partition matroid $\mathcal{N}$ on ground set
$E=\cup_{j}E_{j}$ where $E_{j}=\\{(j,i):1\leq i\leq n\\}$ with $A\subseteq E$
is independent if and only if $|A\cap E_{j}|\leq u_{j}$ for $j=1,\dots,m$. It
follows that the modified log-Sobolev constant of this chain satisfies
$\rho_{\mathcal{N}}\geq 1/n$. A simple Markov chain comparison argument (as
described in Appendix A.2), in combination with (18), then yields that the
modified log-Solev constant $\rho$ of the Markov chain in which we use the
original quantities $|\mathcal{S}(\alpha)|$, instead of the approximation
$\phi(\alpha)$, satisfies $\rho\geq\frac{1}{2n}$.

Of course, the algorithmic problem is now that we cannot compute the
quantities $w_{\alpha}=|\mathcal{S}(\alpha)|$ exactly in polynomial time, so
one step of this base-exchange Markov chain cannot be implemented efficiently.
Nevertheless we can use the approximation scheme of Bezáková, Bhatnagar and
Vigoda [9] to compute approximations $\hat{w}_{\alpha}$ up to arbitrary
precision in time polynomial in $n,m$ and $1/\epsilon$ (this gives the
dependence of $1/\epsilon$ in $C$). A Markov chain comparison argument then
implies that the base-exchange Markov chain on $\mathcal{N}$ using these
approximation is also rapidly mixing, in particular, it is sufficient to run
the chain

$3n\left(\log
n+\log\log|\mathcal{P}|+\log\left(\frac{2T\Phi_{\max}}{\epsilon^{2}}\right)\right)$

steps and then output $\alpha(B)$ where $B$ is the current base after having
run the chain for the above-mentioned number of steps.

We conclude with the sampling of a strategy profile from the set
$\mathcal{S}(\alpha)$ uniformly at random, which now requires sampling a
bipartite graph from the set $\mathcal{G}(k,\alpha)$ uniformly at random. One
algorithm to do this for degree sequences satisfying the condition in
Proposition 5.1 is that of Arman, Gao and Wormald [6] that runs in expected
polynomial time.292929For an overview of algorithms that can be used to
(approximately) sample a bipartite graph with a given degree sequence, see,
e.g., [18]. ∎

######  Remark 5.4.

We remark here that the algorithm of Theorem 5.2 does not run in polynomial
time, as described in Section 2.5, because of the dependence of $C$ on
$1/\epsilon$ (as opposed to the required $\log(1/\epsilon)$). This dependence
arises because of the algorithmic approximations of the numbers
$|\mathcal{S}(\alpha)|$ used in the proof of Theorem 5.2. Alternatively, we
could just use the approximations $\phi(\alpha)$ straight away. However, these
predictions only become accurate when $K\rightarrow\infty$, so this gives a
weaker result in terms of closeness to the Gibbs distribution.

#### Acknowledgements.

The author is grateful to Prasad Tetali for pointing him to [27], and to the
anonymous reviewers of EC 2021 for their useful comments.

## References

  * [1] Heiner Ackermann, Heiko Röglin, and Berthold Vöcking.  On the impact of combinatorial structure on congestion games.  Journal of the ACM, 55(6):25:1–25:22, 2008.
  * [2] Nima Anari, Shayan Oveis Gharan, and Cynthia Vinzant.  Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 35–46. IEEE, 2018.
  * [3] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant.  Log-concave polynomials iii: Mason’s ultra-log-concavity conjecture for independent sets of matroids.  CoRR, abs/1807.00929, 2018.
  * [4] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant.  Log-concave polynomials ii: high-dimensional walks and an fpras for counting bases of a matroid.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1–12, 2019.
  * [5] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant.  Log-concave polynomials iv: Exchange properties, tight mixing times, and faster sampling of spanning trees.  CoRR, abs/2004.07220, 2020.
  * [6] Andrii Arman, Pu Gao, and Nicholas Wormald.  Fast uniform generation of random graphs with given degree sequences.  In IEEE Annual Symposium on Foundations of Computer Science, 2019, pages 1371–1379. IEEE Computer Society, 2019.
  * [7] Arash Asadpour and Amin Saberi.  On the inefficiency ratio of stable equilibria in congestion games.  In Internet and Network Economics, pages 545–552, 2009.
  * [8] Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, Paolo Penna, and Giuseppe Persiano.  Convergence to equilibrium of logit dynamics for strategic games.  Algorithmica, 76(1):110–142, 2016.
  * [9] Ivona Bezáková, Nayantara Bhatnagar, and Eric Vigoda.  Sampling binary contingency tables with a greedy start.  Random Structures & Algorithms, 30(1-2):168–205, 2007.
  * [10] Lawrence E Blume et al.  The statistical mechanics of strategic interaction.  Games and economic behavior, 5(3):387–424, 1993.
  * [11] Sergey G Bobkov and Prasad Tetali.  Modified logarithmic sobolev inequalities in discrete settings.  Journal of Theoretical Probability, 19(2):289–336, 2006.
  * [12] Petter Brändén and June Huh.  Hodge-riemann relations for potts model partition functions.  CoRR, abs/1811.01696, 2018.
  * [13] Petter Brändén and June Huh.  Lorentzian polynomials.  CoRR, abs/1902.03719, 2019.
  * [14] Colin F Camerer.  Behavioural game theory.  In Behavioural and Experimental Economics, pages 42–50. Springer, 2010.
  * [15] Mary Cryan, Heng Guo, and Giorgos Mousa.  Modified log-sobolev inequalities for strongly log-concave distributions.
  * [16] Alberto Del Pia, Michael Ferris, and Carla Michini.  Totally unimodular congestion games.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 577–588, 2017.
  * [17] Persi Diaconis and Laurent Saloff-Coste.  Logarithmic sobolev inequalities for finite markov chains.  The Annals of Applied Probability, 6(3):695–750, 1996.
  * [18] Martin Dyer, Catherine Greenhill, Pieter Kleer, James Ross, and Leen Stougie.  Sampling hypergraphs with given degrees.  CoRR, abs/2006.12021, 2020.
  * [19] Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar.  The complexity of pure nash equilibria.  In Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, pages 604–612, 2004.
  * [20] Diodato Ferraioli.  Logit dynamics: a model for bounded rationality.  ACM SIGecom Exchanges, 12(1):34–37, 2013.
  * [21] Dimitris Fotakis.  Congestion games with linearly independent paths: Convergence time and price of anarchy.  Theory of Computing Systems, 47(1):113–136, 2010.
  * [22] Satoru Fujishige, Michel Goemans, Tobias Harks, Britta Peis, and Rico Zenklusen.  Congestion games viewed from m-convexity.  Operations Research Letters, 43(3):329–333, 2015.
  * [23] Sharad Goel.  Modified logarithmic sobolev inequalities for some models of random walk.  Stochastic processes and their applications, 114(1):51–79, 2004\.
  * [24] Laurent Gourvès and Jérôme Monnot.  On strong equilibria in the max cut game.  In Proc. 5th International Workshop on Internet and Network Economics, pages 608–615, 2009.
  * [25] Leonid Gurvits.  On multivariate newton-like inequalities.  In Advances in Combinatorial Mathematics, pages 61–78, 2010.
  * [26] Thorkell Helgason.  Aspects of the theory of hypermatroids.  In Hypergraph Seminar, pages 191–213. Springer Berlin Heidelberg, 1974.
  * [27] Jonathan Hermon and Justin Salez.  Modified log-sobolev inequalities for strong-rayleigh measures.  CoRR, abs/1902.02775, 2019.
  * [28] Ron Holzman and Nissan Law-Yone.  Strong equilibrium in congestion games.  Games and economic behavior, 21(1-2):85–101, 1997.
  * [29] Samuel Ieong, Robert McGrew, Eugene Nudelman, Yoav Shoham, and Qixiang Sun.  Fast and compact: A simple class of congestion games.  In Proceedings of the 20th National Conference on Artificial Intelligence, pages 489–494, 2005.
  * [30] Mark Jerrum and Alistair Sinclair.  Polynomial-time approximation algorithms for the ising model.  SIAM Journal on computing, 22(5):1087–1116, 1993.
  * [31] Mark Jerrum, Alistair Sinclair, and Eric Vigoda.  A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.  Journal of the ACM, 51(4):671–697, 2004.
  * [32] Mark Jerrum, Jung-Bae Son, Prasad Tetali, Eric Vigoda, et al.  Elementary bounds on poincaré and log-sobolev constants for decomposable markov chains.  The Annals of Applied Probability, 14(4):1741–1765, 2004.
  * [33] Pieter Kleer and Guido Schäfer.  Potential function minimizers of combinatorial congestion games: Efficiency and computation.  In Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, pages 223–240. ACM, 2017.
  * [34] Pieter Kleer and Guido Schäfer.  Topological price of anarchy bounds for clustering games on networks.  In Proceedings of the 15th Conference on Web and Internet Economics, pages 241–255, 2019.
  * [35] David A Levin, Malwina J Luczak, and Yuval Peres.  Glauber dynamics for the mean-field ising model: cut-off, critical power law, and metastability.  Probability Theory and Related Fields, 146(1-2):223, 2010.
  * [36] Akaki Mamageishvili and Paolo Penna.  Tighter bounds on the inefficiency ratio of stable equilibria in load balancing games.  Operations Research Letters, 44(5):645–648, 2016.
  * [37] Russell A Martin and Dana Randall.  Sampling adsorbing staircase walks using a new markov chain decomposition method.  In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 492–502, 2000.
  * [38] Daniel McFadden.  Conditional logit analysis of qualitative choice behavior.  Frontiers in Econometrics, pages 105–142, 1973.
  * [39] Brendan D McKay.  Asymptotics for 0-1 matrices with prescribed line sums.  Enumeration and Design, Academic Press, pages 225–238, 1984.
  * [40] Milena Mihail and Umesh Vazirani.  On the expansion of 0-1 polytopes.  Journal of Combinatorial Theory, Series B, 1989.
  * [41] Kazuo Murota.  Discrete convex analysis.  Mathematical Programming, 83(1-3):313–371, 1998.
  * [42] Kazuo Murota.  Discrete convex analysis.  SIAM Monograph on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2003.
  * [43] Kazuo Murota.  Recent developments in discrete convex analysis.  In Research Trends in Combinatorial Optimization, pages 219–260, 2009.
  * [44] Paolo Penna.  The price of anarchy and stability in general noisy best-response dynamics.  International Journal of Game Theory, 47(3):839–855, 2018.
  * [45] Robert W. Rosenthal.  A class of games possessing pure-strategy Nash equilibria.  International Journal of Game Theory, 2:65–67, 1973.
  * [46] William H Sandholm.  Population games and evolutionary dynamics.  MIT press, 2010.
  * [47] Alexander Schrijver.  Combinatorial optimization: polyhedra and efficiency. Vol. B, Matroids, trees, stable sets. Chapters 39–69.  Algorithms and combinatorics. Springer-Verlag, 2003.

##  Appendix A Markov chains and functional inequalities

Let $\mathcal{M}=(\Omega,P)$ be a time-reversible Markov chain with stationary
distribution $\pi$, and $f,g:\Omega\rightarrow\mathbb{R}_{\geq 0}$. Let
$\mathbb{E}_{\pi}(f)=\sum_{x\in\Omega}\pi(x)f(x)$ and

$\text{Var}_{\pi}(f)=\sum_{x\in\Omega}\pi(x)(f(x)-\mathbb{E}_{\pi}(f))^{2}.$

Furthermore, define the entropy-like quantity

$\text{Ent}_{\pi}(f)=\mathbb{E}_{\pi}\left[f\log(f)-f\log(\mathbb{E}_{\pi}(f))\right]$

and the _Dirichlet form_

$\displaystyle\mathcal{E}_{P}(f,g)$
$\displaystyle=\frac{1}{2}\sum_{x\in\Omega}\sum_{y\in\Omega}\pi(x)P(x,y)[f(x)-f(y)][g(x)-g(y)].$

The Poincaré constant is defined by

$\lambda(P)=\inf\left\\{\frac{\mathcal{E}_{P}(f,f)}{\text{Var}_{\pi}(f)}\
\Big{|}\ f:\Omega\rightarrow\mathbb{R}_{\geq 0},\ \text{Var}_{\pi}(f)\neq
0\right\\},$

the _log-Sobolov constant_ by

$\alpha(P)=\inf\left\\{\frac{\mathcal{E}_{P}(\sqrt{f},\sqrt{f})}{\text{Ent}_{\pi}(f)}\
\Big{|}\ f:\Omega\rightarrow\mathbb{R}_{\geq 0},\ \text{Ent}_{\pi}(f)\neq
0\right\\},$

amd the _modified log-Sobolev constant_ of the Markov chain $\mathcal{M}$ is
defined by

$\rho(P)=\inf\left\\{\frac{\mathcal{E}_{P}(f,\log(f))}{\text{Ent}_{\pi}(f)}\
\Big{|}\ f:\Omega\rightarrow\mathbb{R}_{\geq 0},\ \text{Ent}_{\pi}(f)\neq
0\right\\}.$

These quantities satisfy (see Prop. 3.6 in [11])

$2\lambda(P)\geq\rho(P)\geq 4\alpha(P).$ (20)

It is well-known they can be used to upper bound the mixing time of a Markov
chain as

$\displaystyle\tau_{x}(\epsilon)\leq\frac{1}{2\lambda(P)}\left(\log\pi(x)^{-1}+2\log\left(\frac{1}{2\epsilon}\right)\right),\
\
\tau_{x}(\epsilon)\leq\frac{1}{\rho(P)}\left(\log\log\pi(x)^{-1}+\log\left(\frac{1}{2\epsilon^{2}}\right)\right),\
\text{and}$
$\displaystyle\tau_{x}(\epsilon)\leq\frac{1}{4\alpha(P)}\left(\log\log\pi(x)^{-1}+\log\left(\frac{1}{2\epsilon^{2}}\right)\right).\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $

###  A.1 Markov chain decomposition

Let $\mathcal{M}=(\Omega,P)$ be a time-reversible Markov chain with stationary
distribution $\pi$ and let $\Omega=\Omega_{1}\cup\dots\cup\Omega_{m}$ be a
disjoint partition of the state space. We write $\lambda$ for the Poincaré
constant of this chain, $\bar{\lambda}$ for the Poincaré constant of the
projection chain, and $\lambda_{i}$ for that of the restriction chain $P_{i}$
(and define $\lambda_{\min}=\min_{i}\lambda_{i}$). We define $\alpha,\
\bar{\alpha}$ and $\alpha_{\min}$ similarly for the log-Sobolev constant, as
well as $\rho,\ \bar{\rho}$ and $\rho_{\min}$ for the modified log-Sobolev
constant.

Hermon and Salez [27] recently gave a Markov chain decomposition theorem that
applies to the Poincaré constant, the log-Sobolev constant and the modified
log-Sobolev constant.303030For other Markov chain decomposition theorems, see,
e.g., the work of Jerrum et al. [32] (who, in particular, give stronger
theorems for the Poincaré and log-Sobolev constant). We next describe the
necessary objects to formulate their result.

Assume that for each $i,j\in[m]$ with $i\neq j$ and $\bar{P}(i,j)>0$, we are
given a coupling $\kappa_{ij}:\Omega_{i}\times\Omega_{j}\rightarrow[0,1]$ of
the probability distributions $\pi_{i}$ and $\pi_{j}$. That is, $\kappa_{ij}$
is such that

$\displaystyle\forall x\in\Omega_{i},\
\sum_{y\in\Omega_{j}}\kappa_{ij}(x,y)=\pi_{i}(x),$ $\displaystyle\forall
y\in\Omega_{j},\ \sum_{x\in\Omega_{i}}\kappa_{ij}(x,y)=\pi_{j}(y).$

Based on the couplings $\kappa_{ij}$, we define

$\chi=\min_{x\in\Omega_{i},y\in\Omega_{j},i,j\in[m]}\left\\{\frac{\pi(x)P(x,y)}{\bar{\pi}(i)\bar{P}(x,y)\kappa_{ij}(x,y)}\right\\},$

with the range taken over all combinations for which the denumerator in the
fraction is strictly positive. We state (a small variation of) the theorem of
Hermon and Salez [27] for the modified log-Sobolev constant (for the other
constants the statements are similar).

######  Theorem A.1 (Hermon and Salez [27]).

With the above notation, it holds that
$\rho\geq\min\\{\chi\bar{\rho},\rho_{min}\\}$ with

$\chi=\max_{x\in\Omega_{i},y\in\Omega_{j},i,j\in[m]:\bar{P(i,j)}>0}\left\\{\frac{P(x,y)}{\bar{P}(i,j)},\frac{P(y,x)}{\bar{P}(j,i)}\right\\}.$

###  A.2 Markov chain comparison

Another useful property of proving mixing time bounds through Poincaré and
(modified) log-Sobolev constants, is that it is easy to see that small
perturbations in the transition probabilities and the stationary distribution
only result in mild variations in these constants, by means of a Markov chain
comparison argument. Goel [23] states the following for the modified log-
Sobolev constant, based on similar results for the other constants by Diaconis
and Saloff-Coste [17].

######  Theorem A.2 (Lemma 4.1 [23]).

Let $\mathcal{M}=(\Omega,P)$ and
$\mathcal{M}^{\prime}=(\Omega^{\prime},P^{\prime})$ be two finite, reversible
Markov chains with stationary distributions $\pi$ and $\pi^{\prime}$,
respectively, and modified log-Sobolev constant $\rho$ and $\rho^{\prime}$,
respectively. Assume there is a mapping $\phi:W(\Omega,\pi)\rightarrow
W^{\prime}(\Omega^{\prime},\pi^{\prime})$ mapping $f\rightarrow f^{\prime}$
for $f:\Omega\rightarrow\mathbb{R}_{\geq 0}$, and constants $C,c>0$ and $B\geq
0$ such that for all $f\in W(\Omega,\pi)$, we have

$\mathcal{E}_{P^{\prime}}(f^{\prime},\log f^{\prime})\leq
C\cdot\mathcal{E}_{P}(f,\log f)\ \ \text{ and }\ \
c\cdot\text{Ent}_{\pi}(f)\leq\text{Ent}_{\pi^{\prime}}(f^{\prime})+B\cdot\mathcal{E}_{P}(f,\log
f).$

Then

$\frac{c\rho^{\prime}}{C+B\rho^{\prime}}\leq\rho.$

In particular, if $\Omega=\Omega^{\prime}$ and there exists a $\delta>0$ such
that $(1-\delta)P(x,y)\leq P^{\prime}(x,y)\leq(1+\delta)P(x,y)$ for all
$x,y\in\Omega$, and $(1-\delta)\pi(x)\leq\pi^{\prime}(x)\leq(1+\delta)\pi(x)$
for $x\in\Omega$, it directly follows that

$\frac{1}{\rho}\leq\frac{1+\delta}{1-\delta}\cdot\frac{1}{\rho^{\prime}}.$

##  Appendix B Omitted proofs

In this appendix we give all proofs missing from the main body. These result
are not very difficult to prove, but somewhat tedious to formally write down,
and, hence, were omitted.

###  B.1 Proof of Corollary 3.2

Corollary 3.2. Let $\pi$ be the distribution over $\mathcal{B}_{R}$ with
$\pi(\alpha)\propto w(\alpha)$, and let $\Pi_{\pi}$ be the distribution over
$\Pi(\mathcal{B}_{R})$ with $\Pi_{\pi}(B)\propto w_{\Pi}(\alpha(B))$. Let
$B\in\Pi(\mathcal{B}_{R})$ and let $\Pi_{\sigma}^{T}=P^{T}(B,\cdot)$ be the
distribution over $\Pi(\mathcal{B}_{R})$ after $T$ steps of the base-exchange
Markov chain $\mathcal{M}=(\Pi(\mathcal{B}_{R}),P)$. Let $\sigma^{T}$ be the
induced distribution over $\mathcal{B}_{R}$ given by
$\sigma^{T}(\alpha)=\sum_{B:\alpha(B)=\alpha}\Pi_{\sigma}^{T}(B).$

If $d_{TV}(\Pi_{\sigma}^{T},\Pi_{\pi})\leq\epsilon$, then also
$d_{TV}(\sigma^{T},\pi)\leq\epsilon$.

###### Proof.

We have that

$\displaystyle 2d_{TV}(\sigma,\pi)$
$\displaystyle=\sum_{\alpha\in\mathcal{B}_{R}}\left|\sum_{B:\alpha(B)=\alpha}\sigma^{\prime}(B)-w(\alpha)\right|$
$\displaystyle=\sum_{\alpha\in\mathcal{B}_{R}}\left|\sum_{B:\alpha(B)=\alpha}\left[\sigma^{\prime}(B)-\binom{d}{\alpha(B)}^{-1}w(\alpha)\right]\right|\
\ (\text{using }\eqref{eq:scaling})$
$\displaystyle\leq\sum_{B\in\mathcal{B}^{\prime}}|\sigma^{\prime}(B)-w^{\prime}(\alpha(B))|\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (\text{triangle
inequality})$ $\displaystyle=2d_{TV}(\sigma^{\prime},\pi^{\prime})\leq
2\epsilon.$

This gives the desired result. ∎

###  B.2 Calculation that $d_{TV}(\pi,\bar{\pi})\leq\epsilon$ in proof of
Theorem 4.2

Note that

$\bar{\pi}(s)=\frac{\alpha!}{n!}\sigma^{\prime}(\alpha)$

where $\alpha=\ell(s)$ is the load profile corresponding to strategy $s$. Then

$\displaystyle\sum_{s\in\mathcal{S}}|\bar{\pi}(s)-\pi(s)|$
$\displaystyle=\sum_{\alpha}\sum_{s\in\mathcal{S}:\ell(s)=\alpha}|\bar{\pi}(s)-\pi(s)|$
$\displaystyle=\sum_{\alpha}\sum_{s\in\mathcal{S}:\ell(s)=\alpha}\left|\frac{\alpha!}{n!}\sigma^{\prime}(\alpha)-e^{-T\Phi(\alpha)}\right|$
$\displaystyle=\sum_{\alpha}\frac{n!}{\alpha!}\left|\frac{\alpha!}{n!}\sigma^{\prime}(\alpha)-e^{-T\Phi(\alpha)}\right|$
$\displaystyle=\sum_{\alpha}\left|\sigma^{\prime}(\alpha)-\frac{n!}{\alpha!}e^{-T\Phi(\alpha)}\right|$
$\displaystyle\leq 2\epsilon.$

This shows that $d_{TV}(\pi,\bar{\pi})\leq\epsilon$ as desired.

###  B.3 Comparison arguments omitted in proof of Theorem 4.4

#### First inequality in (14).

We start with showing the first inequality in (14), which is

$\bar{\rho}\geq\frac{1}{n}\cdot\rho(\Pi(L)),$

by using Theorem A.2. We will heavily abuse notation and write $\Pi(\cdot)$
for many different objects in order not to overload the notation. Remember
that $\bar{\rho}$ is the modified log-Sobolev constant of the projection chain
$\mathcal{M}=(L,\bar{P})$, where $L=\\{\alpha\in[q]^{n}:|\alpha|=n\\}$, with
stationary distribution given by

$\bar{\pi}(\alpha)=|\mathcal{S}(\alpha)|e^{-T\Phi(\alpha)}.$

Furthermore, $\rho(\Pi(L))$ is the modified log-Sobolev constant of the base-
exchange Markov chain $\mathcal{M}_{\Pi}=(\Pi(L),P_{\Pi})$ on $\Pi(L)$ with
stationary distribution $\pi_{\Pi}$. Similar to what was explained in Section
3.1, we may write $\Pi(L)=\cup F_{i}$ where $F_{i}=\\{(i,j):1\leq j\leq n\\}$
for $i=1,\dots,n$, and $\Pi(L)$ is then the set of bases of the $n$-uniform
matroid on $\cup F_{i}$. Roughly speaking, for every path $p\in\mathcal{P}$ we
introduce $n$ auxiliary elements (corresponding to the $n$ auxiliary variables
introduced when polarizing).

For every $\alpha\in L$, there are $\binom{n}{\alpha}$ bases $B\in\Pi(L)$
corresponding to it (as in Section 3.1). We will denote this set of bases by

$\Pi(\alpha)=\\{A\in\Pi(L):\alpha(A)=\alpha\\},$

where $\alpha(A)$ is the vector given by $\alpha_{i}=|A\cap F_{i}|$ for
$i=1,\dots,n$.

We start with defining the required mapping $\phi$ needed in Theorem A.2. For
$f:L\rightarrow\mathbb{R}_{\geq 0}$, we define
$f^{\prime}:\Pi(L)\rightarrow\mathbb{R}_{\geq 0}$ simply by setting
$f^{\prime}(A)=f(\alpha(A))$ for $A\in\Pi(L)$. It can then easily be checked
that $\text{Ent}_{\pi}(f)=\text{Ent}_{\pi_{\Pi}}(f^{\prime})$ as
$\pi(\alpha)=\sum_{A\in\Pi(\alpha)}\pi_{\Pi}(A)$. This means that we can take
$c=1$ and $B=0$ in Theorem A.2. In order to show the desired Dirichlet form
inequality in the statement of Theorem A.2, it suffices to prove that for any
adjacent $\alpha,\beta\in L$, it holds that

$\sum_{A\in\Pi(\alpha)}\pi_{\Pi}(A)\sum_{B\in\Pi(\beta)}P_{\Pi}(A,B)\leq
C\cdot\bar{\pi}(\alpha)\bar{P}(\alpha,\beta).$ (21)

with $C=n$. The fact that this is sufficient follows from the observation that
summing up (21) for all ordered pairs $(\alpha,\beta)$ for $\alpha,\beta\in L$
gives the desired result (in combination with the definition of $f^{\prime}$).

Now, fix $\alpha,\beta\in L$ and assume that they are adjacent (the case
$\alpha=\beta$ can be dealt with similarly). Remember that $\gamma\in L$ is
adjacent to $\alpha$ if $\sum_{e}|\alpha_{e}-\gamma_{e}|=2$, i.e., there exist
paths $p$ and $p^{\prime}$ such that

$\alpha_{e}=\left\\{\begin{array}[]{ll}\gamma_{e}+1&\text{ if }e=p\\\
\gamma_{e}-1&\text{ if }e=p^{\prime}\\\ \alpha_{e}&\text{ if }e\in
E\setminus\\{p,p\\}.\end{array}\right.$

Let $r$ be the path for which $\alpha_{r}=\beta_{r}+1$ and write
$\mathcal{N}_{r}(\alpha)$ for all load profiles $\gamma$ adjacent to $\alpha$
for which $\alpha_{r}=\gamma_{r}+1$ (including $\beta$). Following the
definition of the base-exchange Markov chain, it then holds that for any
$A\in\Pi(\alpha)$ and $B\in\Pi(\beta)$, we have

$2\cdot\sum_{B\in\Pi(\beta)}P_{\Pi}(A,B)=\frac{\alpha_{p}}{n}\frac{(n-\beta_{p^{\prime}_{\beta}}+1)\binom{n}{\beta}^{-1}e^{-T\Phi(\beta)}}{\sum_{\gamma\in\mathcal{N}_{r}(\alpha)\cup\\{\alpha\\}}(n-\gamma_{p^{\prime}_{\gamma}}+1)\binom{n}{\gamma}^{-1}e^{-T\Phi(\gamma)}}=:Q$
(22)

where $p^{\prime}_{\gamma}$ is used to indicate the path
$p^{\prime}=p^{\prime}_{\gamma}$ for which
$\alpha_{p^{\prime}}=\gamma_{p^{\prime}}-1$ for
$\gamma\in\mathcal{N}_{p}(\alpha)$, and $p^{\prime}_{\alpha}=r$. With some
care, it can be shown that for $\gamma\in\mathcal{N}(\alpha)\cup\\{a\\}$, it
holds that

$\frac{(n-\gamma_{p^{\prime}_{\gamma}}+1)\binom{n}{\gamma}^{-1}}{(n-\beta_{p^{\prime}_{\beta}}+1)\binom{n}{\beta}^{-1}}=\frac{\gamma_{p^{\prime}_{\gamma}}}{\beta_{p^{\prime}_{\beta}}}=\frac{\beta_{p^{\prime}_{\gamma}}+1}{\beta_{p^{\prime}_{\beta}}}\geq\frac{1}{n}.$

Continuing the estimate in (22), we then get

$Q\leq
n\cdot\frac{\alpha_{p}}{n}\frac{e^{-T\Phi(\beta)}}{\sum_{\gamma\in\mathcal{N}_{r}(\alpha)\cup\\{\alpha\\}}e^{-T\Phi(\gamma)}}=2n\bar{P}(\alpha,\beta),$

using (12) for the final equality. This gives the desired result in (21).
Applying Theorem A.2 with $c=1,\ C=n$ and $B=0$ then gives the desired first
inequality in (14).

#### First inequality in (15).

In order to show the inequality in (15), we will again use a Markov chain
comparison between two chains on different state spaces. We want to show that

$\rho_{\alpha}\geq\rho_{rt}$

where $\rho_{\alpha}$ is the modified log-Sobolev constant of the restriction
chain on $\mathcal{S}(\alpha)$ for $a\in L$, in which we randomly interchange
the strategies of two players, and $\rho_{rt}$ the modified log-Sobolev
constant of the so-called random transposition walk. From now on, we fix some
$\alpha\in L$.

It is convenient to study these chains in terms of bipartite graphs with given
degrees on node partition $A\cup B$. For $\alpha\in L$ we consider the degree
sequence $x=(x_{1},\dots,x_{n})$ with $x_{i}=1$ for every $i\in B$, and the
sequence $y=(y_{1},\dots,y_{q})$ with $y_{p}=\alpha_{p}$ for $p\in A$, where
one should remember that $q$ is the number of strategies, i.e., paths,
available in the common strategy set (denoted by $A$ here) of all players. It
follows directly that there is a one-to-one correspondence between
$\mathcal{S}(\alpha)$ and $\mathcal{G}(x,y)$ where, for a given strategy
profile $s\in\mathcal{S}(\alpha)$, there is an edge $\\{i,p\\}$ if and only if
$s_{i}=p$. (This is similar to the setting we consider in Section 5.) Given
$s\in\mathcal{S}(\alpha)$, our restriction chain can be interpreted as
randomly selecting two edges from the bipartite graph $G_{s}$ corresponding to
the profile $s$ and switching them if possible. That is, if we select
$\\{i,p\\}$ and $\\{i^{\prime},p^{\prime}\\}$ with $p\neq p^{\prime}$, we
delete the edges $\\{i,p\\}$ and $\\{i^{\prime},p^{\prime}\\}$, and add the
edges $\\{i,p^{\prime}\\}$ and $\\{i^{\prime},p\\}$ (note that $i\neq
i^{\prime}$ always holds as the nodes in $B$ have degree one).

In order to introduce the random transposition Markov chain, we split up every
node $p_{j}\in A$ into nodes $p_{j1},\dots,p_{j\alpha_{j}}$, and consider
bipartite graphs on two sets of $n$ nodes $B=\\{1,\dots,n\\}$ and
$A^{*}=\cup_{j}A^{*}_{j}$, with
$A^{*}_{j}=\\{p_{j1},\dots,p_{j\alpha_{j}}\\}$, where every node has degree
one. That is, every such graph is a perfect matching between $A^{*}$ and $B$.
Note that there are precisely

$\prod_{j=1}^{q}\alpha_{j}!=\alpha!$

perfect matchings corresponding to the graph $G_{s}$ for
$s\in\mathcal{S}(\alpha)$ under the natural transformation in which, for a
given perfect matching, we consider the graph that we get by merging all the
nodes $p_{j1},\dots,p_{j\alpha_{j}}$ back into one node $p_{j}$ for every
$j=1,\dots,q$. We will denote this set of perfect matchings by $H(s)$ for
$s\in\mathcal{S}(\alpha)$. The random tranposition Markov chain
$\mathcal{M}=(\mathcal{H},P)$, with $\mathcal{H}=\cup_{s}H(s)$ denoting the
set of all perfect matchings on the bipartition $A^{*}\cup B$, proceeds by
selecting two edges (of the current perfect matching) uniformly at random, and
switching them. Note that this is always possible here as opposed to in the
case of our restriction chains on $\mathcal{S}(\alpha)$.

We can now use a similar type of comparison argument as for the first
inequality in (14) given above. We define the mapping $\phi$, for a given
function $f:\mathcal{S}(\alpha)\rightarrow\mathbb{R}_{\geq 0}$, by setting
$f^{\prime}(M)=f(s)$ whenever $M\in H(s)$ for $s\in\mathcal{S}(\alpha)$. Let
$\sigma$ be the uniform distribution over $\mathcal{S}(\alpha)$ and let
$\sigma_{\mathcal{H}}$ the uniform distribution over $\mathcal{H}$. Note that
$\sigma(s)=\sum_{M\in H(s)}\sigma_{\mathcal{H}}(M)$. It then follows that for
every $s,s^{\prime}\in\mathcal{S}(\alpha)$, we have

$\sum_{M\in H(s)}\sigma_{\mathcal{H}}(M)\sum_{M^{\prime}\in
H(s^{\prime})}P(M,M^{\prime})=\sigma(s)P_{\alpha}(s,s^{\prime})$ (23)

since $P_{\alpha}(s,s^{\prime})=\frac{1}{n(n-1)}=\sum_{M^{\prime}\in
H(s^{\prime})}P(M,M^{\prime})$ for all $M\in H(s)$ whenever $s\neq s^{\prime}$
and $P_{\alpha}(s,s^{\prime})>0$. Note that there is only one matching
$M^{\prime}\in H(s^{\prime})$ such that $P(M,M^{\prime})>0$. When
$s=s^{\prime}$, we also have

$\sum_{M^{\prime}\in H(s^{\prime})}P(M,M^{\prime})=P_{\alpha}(s,s^{\prime}).$

This implies that we can take $C=1$. As before, we can take $a=1$ and $B=0$.

###  B.4 Proof of Theorem 4.5

Theorem 4.5. Let $\epsilon>0$ and let $\Gamma$ be an extension parallel
congestion game with integer-valued cost functions and $n$ players. There is a
randomized algorithm $\mathcal{A}$ with output distribution $\bar{\pi}$ over
$\text{NE}(\Gamma)$ that is $\epsilon$-close to the uniform distribution over
$\text{NE}(\Gamma)$, and runs in (expected) time polynomial in
$n,m,\Phi_{\max}$ and $\log(1/\epsilon)$ where $\Phi_{\max}$ is the maximum
value attained by Rosenthal’s potential.

For the proof of Theorem 4.5 we will use the following correspondence between
Nash equilibria and strategy profiles minimizing Rosenthal’s potential.

######  Proposition B.1 (Holzman and Law-Yone [28]; Fotakis [21]).

The set of strategy profiles $\text{NE}(\Gamma)$ of an extension parallel
congestion game $\Gamma$ coincides with the set of strategy profiles that
minimize Rosenthal’s potential as in (3).

###### Proof of Theorem 4.5.

We first show that, for $T$ sufficiently large in the algorithm used to prove
Theorem 4.2, most weight will be assigned to strategy profiles minimizing
Rosenthal’s potential. We will apply the idea in Algorithm 1 used to prove
Theorem 4.2 with base $2$ instead of base $e$. Remember that $q$ is the number
of $(o,d)$-paths in the extension parallel network of the game $\Gamma$. Let
$\phi=\Phi(s)$ be the common potential value of all strategy profiles
$s\in\text{NE}(\Gamma)$. For any other strategy profile
$s^{\prime}\in\mathcal{S}\setminus\text{NE}(\Gamma)$, we have

$2^{-T\Phi(s^{\prime})}\leq 2^{-T(\phi+1)}=2^{-T}e^{-T\phi}$

by assumption that all cost functions are integer-valued. As there are $q$
strategies to choose from for every player, we have
$|\mathcal{S}|=q^{n}=2^{n\log_{2}(q)}$. This implies that the Gibbs
distribution $\pi$ over $\mathcal{S}$ with temperature $T=\lceil
n\log_{2}(q)+\log_{2}(2/\epsilon)\rceil$, satisfies

$\pi(\mathcal{S}\setminus\text{NE}(\Gamma))=\sum_{s\in\text{NE}(\Gamma)}2^{-T\Phi(s^{\prime})}\leq
2^{n\log(q)}2^{-T}2^{-T\phi}\leq\frac{\epsilon}{2}\cdot\pi(\text{NE}(\Gamma)).$
(24)

The algorithm for sampling an (almost) uniform sample from $\text{NE}(\Gamma)$
now works as follows. First compute a strategy profile minimizing Rosenthal’s
potential in order to determine $\phi$. This can be done efficiently, see,
e.g., [21]. Then run Algorithm 1 with $T=\lceil
n\log_{2}(q)+\log_{2}(2/\epsilon)\rceil$ and $\epsilon^{\prime}=\epsilon/2$.
If the resulting strategy profile has potential value $\phi$, output this
strategy profile, and, otherwise, rerun Algorithm 1 until it does. Note that
with probability at least $(1-\epsilon/2)$, Algorithm 1 will output a strategy
profile with potential value $\phi$ in one run. A simple argument then shows
that the output distribution is $\epsilon$-close to the uniform distribution
over $\text{NE}(\Gamma)$ as desired. ∎