where $\mathbf{H}$ is the orthogonal projection matrix onto
$\mathcal{H}=\\{\mathbf{x}\in\mathbb{R}^{k}\mid\mathbf{e}^{\prime}\mathbf{x}=0\\}$.

###### Proof.

Denote $\hat{\mathbf{p}}=\pi_{\Delta}(\mathbf{p+x})$, and suppose, by way of
contradiction, that there exists some $\mathbf{q}\in\Delta$ that is closer
than $\hat{\mathbf{p}}$ to $\mathbf{p+Hx}$, so that

$\|\mathbf{p+Hx-q}\|^{2}<\|\mathbf{p+Hx}-\hat{\mathbf{p}}\|^{2}.$

Note, since $\mathbf{p},\mathbf{q},\hat{\mathbf{p}}\in\Delta$, that
$\mathbf{p-q}\in\mathcal{H}$ and $\mathbf{p}-\hat{\mathbf{p}}\in\mathcal{H}$,
so that both $\mathbf{p-q}$ and $\mathbf{p}-\hat{\mathbf{p}}$ are orthogonal
to $\mathbf{x-Hx}$. Using the (generalized) Pythagorean theorem, together with
the above inequality we therefore have

$\|\mathbf{p+x-q}\|^{2}=\|\mathbf{x-Hx}\|^{2}+\|\mathbf{p+Hx-q}\|^{2}<\|\mathbf{x-Hx}\|^{2}+\|\mathbf{p+Hx}-\hat{\mathbf{p}}\|^{2}=\|\mathbf{p+x}-\hat{\mathbf{p}}\|^{2},$

which is in contradiction to the definition of $\hat{\mathbf{p}}$. ∎

To define the corresponding ODE, let $\mathbf{p}\in\Delta$, and let the set-
valued map $\mathcal{C}:\Delta\to 2^{\Delta}$ be defined as follows: For an
interior point $\mathbf{p}\in\Delta^{\mathrm{o}}$, let
$\mathcal{C}=\\{\mathbf{0}\\}$; for a boundary point
$\mathbf{p}\in\Delta\setminus\Delta^{\mathrm{o}}$, let $\mathcal{C}$ be the
infinite convex cone generated by the outer normals of the faces of $\Delta$
that contain $\mathbf{p}$. Adopted to our framework, the projected ODE takes
the form:

$\mathbf{\dot{p}=Hu(p)+z},\quad\text{and}\quad-\mathbf{z}(t)\in\mathcal{C}(\mathbf{p}(t)),\>\forall
t\geq 0,$ (17)

where $\dot{\mathbf{p}}(\cdot)$ is the vector of time derivatives of
$\mathbf{p}(\cdot)$; $\dot{\mathbf{p}}=(dp_{1}/dt,\dots,dp_{k}/dt)$. The value
of $\mathbf{z}(\cdot)$ at each point in time is interpreted as the ‘minimum
force’ needed to prevent the path ${\mathbf{p}}(\cdot)$ from leaving $\Delta$.
A stationary point of (17) is a point $\mathbf{p}^{e}\in\Delta$ such that
$\mathbf{Hu}(\mathbf{p}^{e})+\mathbf{z}=\mathbf{0}$ for some $\mathbf{z}$ such
that $-\mathbf{z}\in\mathcal{C}(\mathbf{p}^{e})$, meaning that the minimum
force needed to push $\mathbf{p}^{e}+\mathbf{Hu}(\mathbf{p}^{e})$ into
$\Delta$ is given by $-\mathbf{Hu}(\mathbf{p}^{e})$. Hence, if
$\mathbf{p}^{e}$ is stationary,

$\pi_{\Delta}(\mathbf{p}^{e}+\mathbf{Hu}(\mathbf{p}^{e}))=\mathbf{p}+\mathbf{Hu}(\mathbf{p}^{e})-\mathbf{Hu}(\mathbf{p}^{e})=\mathbf{p}^{e},$

and in light of Lemma 11, $\mathbf{p}^{e}=\mathbf{f}(\mathbf{p}^{e})$,
implying by Lemma 2 that $\mathbf{p}^{e}$ is an equilibrium.

Define the limit set of the ODE in (17) as

$\mathcal{L}=\bigcup_{\mathbf{p}^{0}\in\Delta}\>\bigcap_{t\geq
0}\left\\{\mathbf{p}(s)\mid s\geq t,\>\mathbf{p}(0)=\mathbf{p}^{0}\right\\},$

that is, if we consider a solution path of (17) starting at an initial point
$\mathbf{p}^{0}$ and pick all points visited infinitely many times on this
path, then $\mathcal{L}$ includes all such points for all possible initial
values $\mathbf{p}^{0}\in\Delta$. Theorems 2.1 and 2.4 in [49, Ch. 5.2]
provide sufficient conditions under which the stochastic iterate
$\mathbf{p}^{(n)}$ converges (almost surely) to some subset of $\mathcal{L}$
as $n\to\infty$.

Clearly, if $\mathbf{p}^{e}$ is stationary, then a path starting at
$\mathbf{p}^{e}$ will forever remain there, thus
$\mathbf{p}^{e}\in\mathcal{L}$. However, in general $\mathcal{L}$ may include
points that are not stationary, specifically when there are solutions of (17)
that do no converge to a unique point (e.g., circles). It is therefore of
interest to introduce conditions under which such circular paths do not exist,
and Assumption A3 is one such condition. This is formulated in the lemma
below:

######  Lemma 12.

Let $\mathcal{S}^{*}$ be the set of stationary points of (17). If Assumption
A3 holds, then $\mathcal{S}^{*}=\mathcal{L}$, hence, every point in
$\mathcal{L}$ is an equilibrium.

###### Proof.

That $\mathcal{S}^{*}\subseteq\mathcal{L}$ holds trivially, therefore it is
suffices to show that Assumption A3 implies
$\mathcal{L}\subseteq\mathcal{S}^{*}$. Let
$\nabla_{\mathbf{p}}u^{*}=-\mathbf{Hu}$, and let $\mathbf{p}(\cdot)$ be a
(continuous) trajectory of (17) starting at some $\mathbf{p}^{0}\in\Delta$.
Our goal is to show that $\mathbf{p}(\cdot)$ converges to some set of
stationary points, using $u^{*}(\cdot)$ as a Lyapunov function. Note that
$u^{*}(\cdot)$ is continuous and therefore attains a finite minimum on
$\Delta$, hence we can assume w.l.o.g that $u^{*}(\cdot)$ is positive on
$\Delta$ (otherwise it can be increased by a constant without affecting the
assumptions). For any $t\geq 0$, the term
$\mathbf{p}(t)+\mathbf{Hu(p}(t))+\mathbf{z}(t)$ is the projection of
$\mathbf{p}(t)+\mathbf{Hu(p}(t))$ onto $\Delta$, hence

$\displaystyle\|\mathbf{z}(t)\|$
$\displaystyle=\|\mathbf{p}(t)+\mathbf{Hu(p}(t))-(\mathbf{p}(t)+\mathbf{Hu(p}(t))+\mathbf{z}(t))\|$
$\displaystyle\leq\|\mathbf{p}(t)+\mathbf{Hu(p}(t))-\mathbf{p}(t)\|=\|\mathbf{Hu(p}(t))\|.$

Note that the inequality is strict in the case that $\mathbf{p}(t)$ is non-
stationary. This, together with the Cauchy–Schwarz inequality implies, for any
non-stationary $\mathbf{p}(t)$,

$-\|\mathbf{Hu(p}(t))\|^{2}<-\|\mathbf{Hu(p}(t))\|\cdot\|\mathbf{z}(t)\|\leq\big{(}\mathbf{Hu(p}(t))\big{)}^{\prime}\mathbf{z}(t).$

Denote $w(\mathbf{p}(t))=-(d/dt)u^{*}(\mathbf{p}(t))$. Using the gradient
chain rule we therefore have, for non-stationary $\mathbf{p}(t)$,

$-w(\mathbf{p}(t))=\frac{d}{dt}u^{*}(\mathbf{p}(t))={\nabla_{\mathbf{p}}u^{*}(\mathbf{p}(t))}^{\prime}\dot{\mathbf{p}}(t)=-\big{(}\mathbf{Hu(p}(t))\big{)}^{\prime}(\mathbf{Hu(p}(t))+\mathbf{z}(t))<0.$

Following the continuity of $\mathbf{Hu}(\cdot)$, $w(\cdot)$ is continuous on
$\Delta$, and it can be seen from the above that for any
$\mathbf{p}\in\Delta$, $w(\mathbf{p})=0$ if and only if $\mathbf{p}$ is
stationary. Furthermore, for all $t\geq 0$,

$0\leq\int_{0}^{t}w(\mathbf{p}(s))ds=u^{*}(\mathbf{p}^{0})-u^{*}(\mathbf{p}(t))\leq
u^{*}(\mathbf{p}^{0}),$

where the last inequality is due to $u^{*}$ being positive. It follows that
$\int_{0}^{t}w(\mathbf{p}(s))ds<\infty$, thus, as $t\to\infty$,
$w(\mathbf{p}(t))\to 0$, and by continuity of $w(\cdot)$ and
$\mathbf{p}(\cdot)$,

$\mathbf{p}(t)\to\\{\mathbf{p}^{e}\mid w(\mathbf{p}^{e})=0\\},$

i.e., $\mathbf{p}(\cdot)$ converges to a set of stationary points, as desired.
∎

######  Remark 5.

There are cases in which Assumptions A3 can be easily verified. For example,
if $k=2$, then each strategy $\mathbf{p}=(p,1-p)\in\Delta$ is uniquely
characterized by a single value $p\in[0,1]$ which parametrizes the whole
simplex, and the matrix $\mathbf{H}$ is given by

$\mathbf{H}=\frac{1}{2}\cdot\begin{pmatrix}1&-1\\\ -1&1\end{pmatrix}.$

Then for any $\mathbf{p}=(p,1-p)\in\Delta$, denoting $\mathbf{s}=(s,1-s)$ and
$\tilde{\mathbf{e}}=\mathbf{e}_{1}-\mathbf{e}_{2}=(1,-1)$, we can simply
define $u^{*}(\cdot)$ by

$u^{*}(\mathbf{p})=\int_{0}^{p}\mathbf{-\left(Hu(s)\right)}^{\prime}\tilde{\mathbf{e}}\cdot
ds=-\int_{0}^{p}\left(u_{1}(\mathbf{s})-u_{2}(\mathbf{s})\right)ds=\int_{0}^{p}\left(u_{2}(s,1-s)-u_{1}(s,1-s)\right)ds.$

A similar approach can be taken to show the existence of some $u^{*}(\cdot)$
if $k>2$ and $\mathbf{u}(\cdot)$ itself is known to be conservative. In this
case, for every parameterized curve
$\mathbf{r}(s),s\in[a,b]\subseteq\mathbb{R}$, that lies entirely in $\Delta$,
any tangential vector at a point along $\mathbf{r}$ must lie in $\mathcal{H}$;
that is, $\dot{\mathbf{r}}(s)\in\mathcal{H}$ for all $s\in[a,b]$. Assuming
$-\mathbf{u}=\nabla_{\mathbf{p}}v^{*}$ for some $v^{*}:\Delta\to\mathbb{R}$,
the line integral of $-\mathbf{Hu}(\cdot)$ along the curve $\mathbf{r}(\cdot)$
is given by

$\int_{a}^{b}-\big{(}\mathbf{Hu(r}(s))\big{)}^{\prime}\dot{\mathbf{r}}(s)ds=\int_{a}^{b}-\mathbf{u(r}(s))^{\prime}\mathbf{H}\dot{\mathbf{r}}(s)ds=\int_{a}^{b}-\mathbf{u(r}(s))^{\prime}\dot{\mathbf{r}}(s)ds=v^{*}(\mathbf{r}(b))-v^{*}(\mathbf{r}(a)),$

where the first transition follows from the symmetry of $\mathbf{H}$, the
second follows from $\dot{\mathbf{r}}(s)\in\mathcal{H}$, and the third is due
to $\mathbf{u}(\cdot)$ being conservative. This shows that the integral of
$\mathbf{-Hu}(\cdot)$ along any curve in $\Delta$ depends only on its
endpoints, hence $\mathbf{-Hu}(\cdot)$ is conservative.

We next proceed to the proof of the theorem.

#### Proof of Theorem 5

###### Proof.

Let $\epsilon_{n}=\gamma_{n}\ell(\mathbf{p}^{(n)})$, then the algorithm in (5)
can be written as

$\mathbf{p}^{(n+1)}=\pi_{\Delta}\left(\mathbf{p}^{(n)}+\epsilon_{n}\frac{\mathbf{G}^{(n)}}{\ell(\mathbf{p}^{(n)})}\right)=\pi_{\Delta}\left(\mathbf{p}^{(n)}+\epsilon_{n}\frac{\mathbf{H}\mathbf{G}^{(n)}}{\ell(\mathbf{p}^{(n)})}\right),$
(18)

where the second equality is due to Lemma 11. Note that $\ell(\mathbf{p})\geq
1$, thus
$\sum_{n=1}^{\infty}\epsilon_{n}\geq\sum_{n=1}^{\infty}\gamma_{n}=\infty$, in
accordance with Equation (1.1) of [49, Ch. 5.1]. Assumption A1 implies that
$\ell(\mathbf{p})\leq M<\infty$ for all $\mathbf{p}\in\Delta$, hence by
Assumption A4 and the compactness of $\Delta$ we have that
$\sum_{n=1}^{\infty}\epsilon_{n}^{2}\leq
M^{2}\sum_{n=1}^{\infty}\gamma_{n}^{2}<\infty$ almost surely. Therefore,
condition (2.14) of Theorem 2.4 in [49, Ch. 5.2] is satisfied.

Next observe that the iterate $\mathbf{p}^{(n)}$ in (18) is confined to the
simplex, which is a compact and non-empty polyhedron. Therefore, Assumption
(A4.3.2) of [49, Ch. 5.2] is satisfied. Assumptions A3 and A2 imply
Assumptions (A2.1), (A2.3) of [49, Ch. 5.2]. By Lemma 4 and the linearity of
expectation we have that

$\displaystyle\mathrm{E}_{\mathbf{p}}\left[\frac{\mathbf{H}\mathbf{G}^{(n)}}{\ell(\mathbf{p}^{(n)})}\right]=\mathbf{H}\mathbf{u}(\mathbf{p}^{(n)}),$

hence Assumption (A2.7) of [49, Ch. 5.2] is satisfied.

Combining the above yields the conclusion of Theorem 2.4 in [49, Ch. 5.2] that
$\mathbf{p}^{(n)}$ as defined in (18) converges to a set of limit points in
$\mathcal{L}$, and together with Assumption A3 we have, by Lemma 12, that all
points in $\mathcal{L}$ are equilibria, which concludes the proof of the
theorem. ∎

###  A.3 Proof of Proposition 7

###### Proof.

Assume without loss that $\mathbf{u}$ is non-negative in all its coordinates
and that $\min_{\mathbf{p}\in\Delta}\|\mathbf{u(p)}\|>0$. This is possible
since $\|\mathbf{u}(\cdot)\|_{\infty}$ admits a minimum on $\Delta$, and
shifting all coordinates of $\mathbf{u}$ by the same constant neither affects
the game nor the algorithm’s progression. We first note that if $\mathbf{u}$
is Lipschitz, then $\mathbf{u(p)^{\prime}p}$ is also (locally) Lipschitz (as a
function of $\mathbf{p}$) on $\Delta$: Let $K_{\mathbf{u}}$ be a Lipschitz
constant for $\mathbf{u}$ and let $M_{\mathbf{u}}$ be an upper bound on
$\|\mathbf{u}(\cdot)\|$ over $\Delta$. Then for all $\mathbf{p,q}\in\Delta$

$\displaystyle|\mathbf{u(p)^{\prime}p}-\mathbf{u(q)^{\prime}q}|$
$\displaystyle=|\mathbf{(u(p)-u(q))^{\prime}p}+\mathbf{u(q)^{\prime}(p-q)}|$
$\displaystyle\leq\|\mathbf{u(p)-u(q)}\|\cdot\|\mathbf{p}\|+\mathbf{\|u(q)\|\cdot\|p-q\|}$
$\displaystyle\leq\|\mathbf{u(p)-u(q)}\|+M_{\mathbf{u}}\mathbf{\|p-q\|}$
$\displaystyle\leq(K_{\mathbf{u}}+M_{\mathbf{u}})\|\mathbf{p-q}\|.$

Thus, $K=K_{\mathbf{u}}+M_{\mathbf{u}}$ is a Lipschitz constant for both
$\mathbf{u(p)^{\prime}p}$ and $\mathbf{u(p)}$. Note that $u^{*}$ is strongly
convex, therefore there exists a unique equilibrium $\mathbf{p}^{e}$.
Furthermore, $\mathbf{p}^{e}$ is a best response to itself, i.e.,
$p_{i}^{e}=0$ for any $i$ such that
$u_{i}(\mathbf{p}^{e})<\|\mathbf{u}(\mathbf{p}^{e})\|_{\infty}$, therefore
$\mathbf{u}(\mathbf{p}^{e})^{\prime}\mathbf{p}^{e}=\|\mathbf{u}(\mathbf{p}^{e})\|_{\infty}$.
Thus, for all $\mathbf{p}\in\Delta$,

$\displaystyle\|\mathbf{u}(\mathbf{p}^{e})\|_{\infty}-\mathbf{u(p)^{\prime}p}=\mathbf{u}(\mathbf{p}^{e})^{\prime}\mathbf{p}^{e}-\mathbf{u(p)^{\prime}p}\leq|\mathbf{u}(\mathbf{p}^{e})^{\prime}\mathbf{p}^{e}-\mathbf{u(p)^{\prime}p}|\leq
K\|\mathbf{p-p}^{e}\|,$

hence,
$\|\mathbf{u}(\mathbf{p}^{e})\|_{\infty}-K\|\mathbf{p-p}^{e}\|\leq\mathbf{u(p)^{\prime}p}$.
For all $\mathbf{x}\in\mathbb{R}^{k}$,
$\|\mathbf{x}\|_{\infty}\leq\|\mathbf{x}\|$, and using the triangle inequality
together with the above yields, for all $\mathbf{p,q}\in\Delta$,

$\begin{split}\mathbf{u(p)^{\prime}q}&\leq\|\mathbf{u(p)}\|_{\infty}=\|\mathbf{u(p)}-\mathbf{u}(\mathbf{p}^{e})+\mathbf{u}(\mathbf{p}^{e})\|_{\infty}\leq\|\mathbf{u}(\mathbf{p}^{e})\|_{\infty}+\|\mathbf{u(p)}-\mathbf{u}(\mathbf{p}^{e})\|_{\infty}\\\
&\leq\|\mathbf{u}(\mathbf{p}^{e})\|_{\infty}+\|\mathbf{u(p)}-\mathbf{u}(\mathbf{p}^{e})\|\leq\|\mathbf{u}(\mathbf{p}^{e})\|_{\infty}+K\|\mathbf{p}-\mathbf{p}^{e}\|\\\
&=\|\mathbf{u}(\mathbf{p}^{e})\|_{\infty}-K\|\mathbf{p}-\mathbf{p}^{e}\|+2K\|\mathbf{p}-\mathbf{p}^{e}\|\leq\mathbf{u(p)^{\prime}p}+2K\|\mathbf{p}-\mathbf{p}^{e}\|.\end{split}$
(19)

Following Assumptions A1, for all $\mathbf{p\in\Delta}$, by Lemma 4,
$\mathrm{E}_{\mathbf{p}}\mathbf{G}=\ell(\mathbf{p})\mathbf{u(p)}$. Since
$\ell$ is a positive real function and $\|\mathbf{u}(\cdot)\|$ is bounded away
from $0$, using Jensen’s inequality,

$\ell(\mathbf{p})=\frac{\|\mathrm{E}_{\mathbf{p}}\mathbf{G}\|}{\|\mathbf{u(p)}\|}\leq\frac{\mathrm{E}_{\mathbf{p}}\|\mathbf{G}\|}{\|\mathbf{u(p)}\|}\leq\frac{\mathrm{E}_{\mathbf{p}}\|\mathbf{G}\|}{\min_{\mathbf{q}\in\Delta}\|\mathbf{u(q)}\|}.$

Therefore, by Assumption A2, we can choose constants $M_{0},M_{1}>0$ such that
$\mathrm{E}_{\mathbf{p}}\|\mathbf{G}\|^{2}\leq M_{0}^{2}$ and
$\ell(\mathbf{p})\leq M_{1}$ for all $\mathbf{p}\in\Delta$. Setting
$\gamma_{n}=\eta/n$, we rewrite the iterate $\mathbf{p}^{(n)}$ as in (18) with
the corresponding step size $\eta\ell(\mathbf{p}^{(n)})/n$, where we note that
$\mathbf{H}\mathbf{G}^{(n)}/\ell(\mathbf{p}^{(n)})$ is unbiased for
$\mathbf{Hu}(\mathbf{p}^{(n)})$ and that
$\eta\ell(\mathbf{p}^{(n)})/n\geq\eta/n$ (almost surely). Suppose that
$\eta>1/(2C)$, then under the strong convexity assumption (11), we can invoke
the result in [60, Eq. (2.8)], by which we have for all $n\geq 1$ that

$\displaystyle\mathrm{E}\|\mathbf{p}^{(n+1)}-\mathbf{p}^{e}\|^{2}$
$\displaystyle\leq\left(1-\frac{\eta\ell(\mathbf{p}^{(n)})}{n}\cdot
2C\right)2\mathrm{E}\|\mathbf{p}^{(n)}-\mathbf{p}^{e}\|^{2}+\left(\frac{\eta\ell(\mathbf{p}^{(n)})}{n}\cdot
M_{0}\right)^{2}$
$\displaystyle\leq\left(1-\frac{2C\eta}{n}\right)2\mathrm{E}\|\mathbf{p}^{(n)}-\mathbf{p}^{e}\|^{2}+\left(\frac{\eta
M_{0}M_{1}}{n}\right)^{2}.$

Define $M_{\eta}=\max\\{(\eta M_{0}M_{1})^{2}/(2C\eta-1),1\\}$. Then,
similarly to [60, Eq. (2.9)], by induction we have for all $n\geq 1$ that

$\displaystyle\mathrm{E}\|\mathbf{p}^{(n)}-\mathbf{p}^{e}\|^{2}\leq\frac{M_{\eta}}{n}.$

For any $\delta\in(0,1)$, using Markov’s inequality we then get

$\displaystyle\mathrm{P}\left(2K\|\mathbf{p}^{(n)}-\mathbf{p}^{e}\|>\sqrt{n^{-\delta}}\right)=\mathrm{P}\left(\|\mathbf{p}^{(n)}-\mathbf{p}^{e}\|^{2}>\frac{n^{-\delta}}{4K^{2}}\right)\leq\frac{4K^{2}\mathrm{E}\|\mathbf{p}^{(n)}-\mathbf{p}^{e}\|^{2}}{n^{-\delta}}\leq
4K^{2}M_{\eta}\cdot n^{\delta-1}.$

From (19), for all $\mathbf{q}\in\Delta$,

$\mathbf{u}(\mathbf{p}^{(n)})^{\prime}\mathbf{p}^{(n)}\geq\mathbf{u}(\mathbf{p}^{(n)})^{\prime}\mathbf{q}-2K\|\mathbf{p}^{(n)}-\mathbf{p}^{e}\|,$

hence, if $2K\|\mathbf{p}^{(n)}-\mathbf{p}^{e}\|\leq\sqrt{n^{-\delta}}$, then
$\mathbf{p}^{(n)}$ is a $\sqrt{n^{-\delta}}$-equilibrium, and we conclude that

$\displaystyle\mathrm{P}\left(\mathbf{u}(\mathbf{p}^{(n)})^{\prime}\mathbf{p}^{(n)}\geq\max_{\mathbf{q}\in\Delta}\mathbf{u}(\mathbf{p}^{(n)})^{\prime}\mathbf{q}-\sqrt{n^{-\delta}}\right)\geq
1-4\cdot K^{2}M_{\eta}\cdot n^{\delta-1},$

which completes the proof. ∎

##  Appendix B Proofs for applications and examples

###  B.1 Proof of Lemma 1

Recall that $1/\mu_{m}$ is the expected service time in queue $m$ and that
$\mu_{2}\geq\mu_{1}$. For any strategy $\mathbf{p}=(p_{1},p_{2},p_{3})$ the
arrival rate to queue $m=1,2$ is $\lambda p_{i}$. Let $w_{m}(p_{m})$ denote
the expected stationary waiting time (service inclusive) in queue $m=1,2$ when
strategy $\mathbf{p}=(p_{1},p_{2},1-p_{1}-p_{2})$ is played by all customers,
where we define $w_{m}(p_{m})=\infty$ for any strategy such that $\lambda
p_{m}>\mu_{m}$. Clearly, if $R-C/\mu_{2}<0$ then in equilibrium no customer
will join either queue, hence $\mathbf{p}^{e}=(0,0,1)$ is the unique Nash
equilibrium.

If $R-C/\mu_{2}>0>R-C/\mu_{1}$, then in equilibrium, customers never join
queue 1, but a positive fraction of them join queue 2. The function
$w_{2}(p_{2})$ is continuous and increasing with respect to $p_{2}$ (see [73])
such that $w_{2}(0)=1/\mu_{2}$. Therefore, if $R-Cw_{2}(1)\geq 0$ then
$\mathbf{p}^{e}=(0,1,0)$ is the unique equilibrium, and if $R-Cw_{2}(1)<0$
then there exists some $p_{2}\in(0,1)$ such that $R-Cw_{2}(p_{2})=0$, i.e.,
$\mathbf{p}^{e}=(0,p_{2},1-p_{2})$ is the unique equilibrium.

Finally, we address the case $R-C/\mu_{2}>R-C/\mu_{1}>0$. If
$R-C/w_{2}(1)>R-C/\mu_{1}$, then in equilibrium all customers join queue 2 and
$\mathbf{p}^{e}=(0,1,0)$ is the unique equilibrium. If $R-C/w_{2}(1)\leq
R-C/\mu_{1}$ then an equilibrium strategy must satisfy $p_{1},p_{2}>0$ and
$w_{1}(p_{1})=w_{2}(p_{2})$. As before, $w_{m}(p_{m})$ is continuous and
increasing in $p_{m}$, $m=1,2$, hence there are two possible cases, (a) There
exists a pair $p_{1}+p_{2}<1$ such that $R-C/w_{2}(p_{2})=R-Cw_{1}(p_{1})=0$
and $\mathbf{p}^{e}=(p_{1},p_{2},1-p_{1}-p_{2})$ is the unique Nash
equilibrium; (b) There exists a pair $p_{1}+p_{2}=1$ such that
$R-C/w_{2}(p_{2})=R-Cw_{1}(p_{1})>0$ and $\mathbf{p}^{e}=(p_{1},p_{2},0)$.
This solution is unique because of the monotonicity of the waiting times
implies that there is at most one solution $p_{1}$ to the equation
$w_{1}(p_{1})=w_{2}(1-p_{1})$. ∎

###  B.2 Proof of Proposition 8

###### Proof.

In light of Theorem 5, to prove our Proposition 8, it suffices to verify that
Assumptions A1–A3 are satisfied in the underlying model.

First, we note that $\mathbf{u}(\mathbf{p})$ is a separable function, in the
sense that $u_{i}(\mathbf{p})$ is only a function of $p_{i}$ for every
$i=1,\ldots,k$. By [73], $\mathbf{u}(\cdot)$ is continuous, and can be further
expressed as the gradient of the sum of the antiderivatives,

$\mathbf{u}(\mathbf{p})=\nabla_{\mathbf{p}}\left(\sum_{i=1}^{k}\int
u_{i}(p_{i})dp_{i}\right).$

Thus, Assumption A3 holds. In what follows, we verify that Assumptions A1 and
A2 also hold. To this aim, we construct a coupling between the original system
and a single-server queue, which we describe next.

Given a strategy $\mathbf{p}=(p_{1},\dots,p_{k})$, consider a single-server,
FCFS queue, which we call the _coupled system_ , with identical arrival
process $\\{T_{n}\\}_{n\geq 1}$ as in the original system. Consider the $j$-th
arriving customer, whose arrival time (in both the original and the coupled
systems) is $T_{j}$. We assume that if this customer chooses to join queue $m$
in original system (which occurs with probability $p_{m}$) with service demand
$Y_{m}$, then customer $j$ in the coupled system with equal service demand
$Y_{m}$ joins at the same time. If customer $j$ in the original system balks,
then we say that in the coupled system, customer $j$ joins with 0 service
demand.

Recall our notation
$X_{j}(\mathbf{p})=(X_{j}^{[1]}(\mathbf{p}),\dots,X_{j}^{[k-1]}(\mathbf{p}))$
for the vector of workloads in the original system observed by customer $j$,
and let the (univariate) r.v. $\tilde{X}_{j}(\mathbf{p})$ represent its
coupled counterpart, namely the workload observed by the $j$-th arriving
customer in the coupled system. We assume both the original and the coupled
system start empty, $X_{1}^{[m]}(\mathbf{p})=\tilde{X}_{1}(\mathbf{p})=0$ for
all $m\in\\{1,\dots,k-1\\}$. It can be seen from the construction that
$X_{j}^{[m]}(\mathbf{p})\leq\tilde{X}_{j}(\mathbf{p})$ with probability one,
for all $m\in\\{1,\dots,k-1\\}$ and $j\geq 0$. Furthermore, recall that
$L(\mathbf{p})=\inf\\{n\geq 1:\ X_{n+1}(\mathbf{p})=0^{k-1}(\mathbf{p})\\}$
denotes the length of a random regenerative cycle in the original system and
let $\tilde{L}(\mathbf{p})=\inf\\{n\geq 1:\ \tilde{X}_{n+1}(\mathbf{p})=0\\}$
be its coupled counterpart. Then $L(\mathbf{p})\leq\tilde{L}(\mathbf{p})$ with
probability one. Denoting by $\tau(\mathbf{p})$ the departure time of the
$L(\mathbf{p})$-th customer in the original system and by
$\tilde{\tau}(\mathbf{p})$ the departure time of the
$\tilde{L}(\mathbf{p})$-th customer in the coupled system, it is immediate
that the busy period in the original system,
$B(\mathbf{p})=\tau(\mathbf{p})-T_{1}$, and the busy period in the coupled
system, $\tilde{B}(\mathbf{p})=\tilde{\tau}(\mathbf{p})-T_{1}$, satisfy
$B(\mathbf{p})\leq\tilde{B}(\mathbf{p})$ almost surely. Since for all
$m\in\\{1,\dots,k-1\\}$ and $j\in\\{1,\dots,L(\mathbf{p})\\}$ we know that
$X_{j}^{[m]}(\mathbf{p})\leq B(\mathbf{p})$, we conclude that
$X_{j}^{[m]}(\mathbf{p})\leq\tilde{B}(\mathbf{p})$ with probability one.

For convenience, assume without loss that
$\mu_{1}\leq\mu_{2}\leq\dots\leq\mu_{k-1}$. For any strategy
$\mathbf{p}=(p_{1},\dots,p_{k})$, let $\tilde{Y}(\mathbf{p})$ be a random
variable that with probability $p_{m}$ is a random draw from the distribution
$F_{m}$, $m\in\\{1,\dots,k-1\\}$, and with probability $p_{k}$ takes the value
0. Hence, given $\mathbf{p}$, the coupled system forms a GI/G/1 queue in which
service time is distributed similarly to $\tilde{Y}(\mathbf{p})$. Moreover,
this queue is stable due to $\lambda<\mu_{1}$. By assumption,
$\mathrm{E}[Y_{m}^{4}]<\infty$, and it follows that
$\mathrm{E}[\tilde{Y}(\mathbf{p})^{4}]<\infty$. It is known (see [71]) that
this implies $\mathrm{E}_{\mathbf{p}}\tilde{L}(\mathbf{p})^{4}<\infty$ as well
as $\mathrm{E}_{\mathbf{p}}\tilde{B}(\mathbf{p})^{4}<\infty$. Thus,
$\ell^{2}(\mathbf{p})\leq\mathrm{E}_{\mathbf{p}}\tilde{L}(\mathbf{p})^{2}<\infty$
and Assumption A1 follows.

Let $\kappa>0$ be a constant such that $\nu_{m}$ is $\kappa$-Lipschitz for all
$m\in\\{1,\dots,k-1\\}$, and let
$\xi=\max_{m=1,\dots,k-1}\nu_{m}(0)+\kappa\mathrm{E}[Y_{m}]$. We have, for
every $m\in\\{1,\dots,k-1\\}$ and $j\in\\{1,\dots,L(\mathbf{p})\\}$,

$\displaystyle\overline{v}_{m}(X_{j}(\mathbf{p}))$
$\displaystyle=\mathrm{E}[\nu_{m}(X_{j}^{[m]}(\mathbf{p})+Y_{m})\mid
X_{j}^{[m]}(\mathbf{p})]$ $\displaystyle\leq\nu_{m}(0)+\kappa
X_{j}^{[m]}(\mathbf{p})+\kappa\mathrm{E}[Y_{m}]\leq\xi+\kappa
X_{j}^{[m]}(\mathbf{p})\leq\xi+\kappa\tilde{B}(\mathbf{p})$

almost surely. Thus,

$\|\mathbf{G}\|^{2}=\Bigg{\|}\sum_{j=1}^{L(\mathbf{p})}\mathbf{\overline{v}}(X_{j}(\mathbf{p}))\Bigg{\|}^{2}\leq\Bigg{\|}\sum_{j=1}^{L(\mathbf{p})}(\xi+\kappa\tilde{B}(\mathbf{p}))\mathbf{e}\Bigg{\|}^{2}=k\cdot{L}(\mathbf{p})^{2}(\xi+\kappa\tilde{B})^{2}\leq
k\cdot\tilde{L}(\mathbf{p})^{2}(\xi+\kappa\tilde{B}(\mathbf{p}))^{2},$

and together with Hölder’s inequality,

$\displaystyle\mathrm{E}_{\mathbf{p}}\|\mathbf{G}\|^{2}\leq
k\mathrm{E}_{\mathbf{p}}[\tilde{L}(\mathbf{p})^{2}(\xi+\kappa\tilde{B}(\mathbf{p}))^{2}]\leq
k\cdot(\mathrm{E}_{\mathbf{p}}[\tilde{L}(\mathbf{p})^{4}])^{\frac{1}{2}}(\mathrm{E}_{\mathbf{p}}[(\xi+\kappa\tilde{B}(\mathbf{p}))^{4}])^{\frac{1}{2}}<\infty,$

where the last inequality follows from the finiteness of the first four
moments of $\tilde{L}(\mathbf{p})$ and $\tilde{B}(\mathbf{p})$. To prove that
Assumption A2 holds, it suffices to show that the first four moments of
$\tilde{L}(\mathbf{p})$ and $\tilde{B}(\mathbf{p})$ are continuous functions
of $\mathbf{p}$, which will imply that
$\mathrm{E}_{\mathbf{p}}\|\mathbf{G}\|^{2}$ is uniformly bounded on $\Delta$.
The remainder of the proof is therefore dedicated to proving the continuity of
the moments.

Let $\mathbf{p}^{(n)}$ be a convergent sequence of strategies, and denote
$\mathbf{p}=\lim_{n\to\infty}\mathbf{p}^{(n)}$. Our goal is to prove
$\mathrm{E}_{\mathbf{p}^{(n)}}\tilde{L}(\mathbf{p}^{(n)})^{r}\to\mathrm{E}_{\mathbf{p}}\tilde{L}(\mathbf{p})^{r}$
and
$\mathrm{E}_{\mathbf{p}^{(n)}}\tilde{B}(\mathbf{p}^{(n)})^{r}\to\mathrm{E}_{\mathbf{p}}\tilde{B}(\mathbf{p})^{r}$
for $r\leq 4$. The convergence of $\mathbf{p}^{(n)}$ to $\mathbf{p}$ implies
that $\tilde{Y}(\mathbf{p}^{(n)})\>\to_{\rm d}\>\tilde{Y}(\mathbf{p})$ as
$n\to\infty$. Since the cycle length and busy period are continuous maps of
the queue-length process and workload process, respectively, and since $H$ is
a continuous distribution, we have by [73] that
$\tilde{L}(\mathbf{p}^{(n)})^{r}\>\to_{\rm d}\>\tilde{L}(\mathbf{p})^{r}$ and
$\tilde{B}(\mathbf{p}^{(n)})^{r}\>\to_{\rm d}\>\tilde{B}(\mathbf{p})^{r}$. To
show convergence of the means we shall use the dominated-convergence theorem
based on the following construction:

Define $Z=\max_{m\in\\{1,\dots,k-1\\}}Y_{m}$. Since
$\mathrm{E}Y_{m}^{4}<\infty$, we have $\mathrm{E}Z^{4}<\infty$, and clearly,
$\mathrm{E}Z\geq 1/\mu_{1}$. For every $\epsilon\in(0,1)$ there exists some
$N_{\epsilon}$ such that for all $n\geq N_{\epsilon}$ and
$i\in\\{1,\dots,k\\}$

${p}^{(n)}_{i}\leq(1-\epsilon)p_{i}+\epsilon.$

Assume $\epsilon\leq(1/\lambda-1/\mu_{1})/(\mathrm{E}Z-1/\mu_{1})$. Define
$\bar{Y}(\mathbf{p})$ as a random variable taking the value
$\tilde{Y}(\mathbf{p})$ w.p. $1-\epsilon$ and $Z$ otherwise. Hence
$\mathrm{E}\bar{Y}(\mathbf{p})^{4}<\infty$, and

$\mathrm{E}\bar{Y}(\mathbf{p})=(1-\epsilon)\mathrm{E}\tilde{Y}(\mathbf{p})+\epsilon\mathrm{E}Z\leq(1-\epsilon)\frac{1}{\mu_{1}}+\epsilon\mathrm{E}Z=\epsilon\cdot(\mathrm{E}Z-1/\mu_{1})+1/\mu_{1}\leq
1/\lambda.$

Furthermore, for $n\geq N_{\epsilon}$ and $i\in\\{1,\dots,k-1\\}$, we note
that $\tilde{Y}(\mathbf{p}^{(n)})$ takes the (random) value $Y_{i}$ with
probability $p^{(n)}_{i}$, whereas $\bar{Y}(\mathbf{p})$ takes a value equal
or larger than $Y_{i}$ with probability $(1-\epsilon)p_{i}+\epsilon\geq
p^{(n)}_{i}$. Hence,

$\tilde{Y}(\mathbf{p}^{(n)})\leq_{\mathrm{st}}\bar{Y}(\mathbf{p}).$

Define $\bar{L}$ and $\bar{B}$ as the cycle length and busy period of a GI/G/1
queue with interarrival distribution $H$ and service distribution similar to
that of $\bar{Y}(\mathbf{p})$. Thus,
$\tilde{L}(\mathbf{p}^{(n)})\leq_{\mathrm{st}}\bar{L}$ and
$\tilde{B}(\mathbf{p}^{(n)})\leq_{\mathrm{st}}\bar{B}$. Because
$\mathrm{E}\bar{Y}(\mathbf{p})<1/\lambda$ and
$\mathrm{E}\bar{Y}(\mathbf{p})^{4}<\infty$, it follows that
$\mathrm{E}\bar{L}^{r}<\infty$ and $\mathrm{E}\bar{B}^{r}<\infty$ for any
integer $r\leq 4$. Since for all $n\geq N_{\epsilon}$,
$\tilde{L}(\mathbf{p}^{(n)})^{r}\leq_{\mathrm{st}}\bar{L}^{r}$ and
$\tilde{B}(\mathbf{p}^{(n)})^{r}\leq_{\mathrm{st}}\bar{B}^{r}$, we conclude,
using the dominated-convergence theorem, that

$\lim_{n\to\infty}\mathrm{E}_{\mathbf{p}^{(n)}}\tilde{L}(\mathbf{p}^{(n)})^{r}=\mathrm{E}_{\mathbf{p}}\tilde{L}(\mathbf{p})^{r}\qquad\text{and}\qquad\lim_{n\to\infty}\mathrm{E}_{\mathbf{p}^{(n)}}\tilde{B}(\mathbf{p}^{(n)})^{r}=\mathrm{E}_{\mathbf{p}}\tilde{B}(\mathbf{p})^{r},$

hence, we have proven that $\mathrm{E}_{\mathbf{p}}\tilde{L}(\mathbf{p})^{r}$
and $\mathrm{E}_{\mathbf{p}}\tilde{B}(\mathbf{p})^{r}$ are continuous in
$\mathbf{p}$. ∎

###  B.3 Proof of Proposition 9

###### Proof.

As a special case of the model in 4.2, by setting $\mathbf{p}=\mathbf{e}_{2}$,
we have that all customers join the queue of server 2, hence it can be modeled
as an M/G/1 queue, which is stable due to $\lambda<\mu$. Then, by a coupling
argument, for every $\mathbf{p}\in\Delta$, the total workload process
$X^{[1]}(t)+X^{[2]}(t)$ is dominated by that of the corresponding M/G/1 queue
of $\mathbf{p}=\mathbf{e}_{2}$, which, under the assumption
$\mathrm{E}[Y^{4}]<\infty$, has finite cycle-length second moment, as
explained in Example 1 in Section 3.2. Hence, Assumption A1 holds.
Furthermore, $\mathbf{u}$ is continuous in $\mathbf{p}$ (see [38]) and
following an explanation similar to that in Example 1 in Section 3.2, we
conclude that Assumptions A1–A2 are satisfied. Furthermore, we have in this
example that $k=2$, hence Assumption A3 holds, and together with the step size
assumption A4 the conclusion of Theorem 5 holds. ∎

##  Appendix C Unknown stability region

In strategic-queueing literature, it is often claimed, in a rather loose
sense, that customer rationality imposes system stability, even when some
strategies in the strategy space force the system out of its stability region.
However, the current literature is lacking a rigorous mathematical formulation
of a queueing game that reifies this intuitive argument. The framework
presented in Section 2 does not formally cover models in which some strategies
induce system instability, because customer utility is not well defined when
the system is non-regenerative. In this section we suggest a heuristic
modification of the algorithm that attempts to deal with cases where some
strategies render the system unstable, and the stability region of the system
is not known a-priori. While we believe this method to be useful in practice,
some important theoretical questions revolving stability in queueing games are
left unsettled. Hopefully the results presented in this paper will motivate
future research on this subject.

Suppose that the underlying system is positive recurrent only for strategies
in some non-empty connected subset of the strategy space
$\mathcal{S}\subset\Delta$. For the sake of the discussion here we will assume
that $\mathcal{S}$ itself is unknown, but that $\Delta\setminus\mathcal{S}$ is
compact, and that $\mathcal{S}$ contains an equilibrium point. Note that when
$\mathcal{S}\neq\Delta$, the existence of an equilibrium in $\mathcal{S}$ does
not follow directly from our Assumption A3. This can be easily seen through a
degenerate variation of the Unobservable M/G/1 in Example 1, by setting
$\lambda>\mu$, hence $\mathcal{S}=\\{\mathbf{p}=(p,1-p)\mid
p\in[0,\mu/\lambda)\\}$, and letting $C<0$ (namely, customers profit from
waiting). Then, although $\mathbf{u}$ is a smooth conservative vector field on
$\mathcal{S}$, any strategy in $\mathcal{S}$ must prescribe balking with some
positive probability, while its best response is to join with probability 1.
Furthermore, $\mathcal{S}$ is non-compact (as is often the case for stability
regions of queueing systems), and in this example an equilibrium does not
exist even if customers are restricted to choose a strategy in $\mathcal{S}$.

For our Definition 2 of an equilibrium strategy to be valid, $\mathbf{u}$ has
to be defined in the extended sense as

$\mathbf{u(p)}=\lim_{n\to\infty}\mathrm{E}\big{[}\overline{\mathbf{v}}(X_{n}(\mathbf{p}))\big{]}$

for all $\mathbf{p}\in\Delta$, including those strategies in
$\Delta\setminus\mathcal{S}$. Moreover, this definition has to coincide with
the stationary utility whenever a limiting distribution exists, i.e.,
$\overline{\mathbf{v}}$ has to be a function such that for all
$\mathbf{p}\in\mathcal{S}$, if there exists a random variable $X(\mathbf{p})$
such that $X_{n}(\mathbf{p})\>\to_{\rm d}\>X(\mathbf{p})$ as $n\to\infty$,
then it must also hold that

$\mathbf{u(p)}=\lim_{n\to\infty}\mathrm{E}\big{[}\overline{\mathbf{v}}(X_{n}(\mathbf{p}))\big{]}=\mathrm{E}\big{[}\overline{\mathbf{v}}(X(\mathbf{p}))\big{]}.$

Furthermore, to use our method, appropriate assumptions have to be introduced
on the primitives that rule out the existence of equilibria in
$\Delta\setminus\mathcal{S}$, and prevent the iterate from “drifting” outside
$\mathcal{S}$. Such conditions should imply that after finitely many
iterations, the iterate is absorbed in a compact subset $\tilde{\mathcal{S}}$
of $\mathcal{S}$ containing an equilibrium point. Rigorously formulating such
conditions exceeds the scope of this paper. However, we conjecture that the
following condition, which indeed holds in Example 1 (with strictly positive
waiting cost), is sufficient: For all $\mathbf{p}\notin\mathcal{S}$,
$\mathbf{u(p)}^{\prime}\mathbf{p}=-\infty$ and, additionally, for any sequence
$\\{\mathbf{p}_{m}\\}_{m\geq 1}$ such that
$\min_{\mathbf{q}\in\Delta\setminus\mathcal{S}}\|\mathbf{p}_{m}-\mathbf{q}\|\to
0$, $\lim_{m\to\infty}\mathbf{u(p}_{m})^{\prime}\mathbf{p}_{m}=-\infty$. We
next present a modified version of the SA algorithm that terminates busy
cycles when they exceed a threshold that increases as the number of iteration
grows.

At iteration $n\geq 1$, given a strategy $\mathbf{p}^{(n)}$, let

$\tilde{\mathbf{G}}^{(n)}=\sum_{j=1}^{L\wedge\beta_{n}}\mathbf{\overline{v}}(X_{j}),$
(20)

where $L\wedge\beta=\min\\{L,\beta\\}$ and $\\{\beta_{n}\\}_{n\geq 1}$ is an
increasing sequence of integers such that $\lim_{n\to\infty}\beta_{n}=\infty$.
The modified SA algorithm is defined as

$\mathbf{p}^{(n+1)}=\pi_{\Delta}\left(\mathbf{p}^{(n)}+\gamma_{n}\tilde{\mathbf{G}}^{(n)}\right).$
(21)

Clearly $\tilde{\mathbf{G}}^{(n)}$ is in general not an unbiased estimator of
$\mathbf{g}(\mathbf{p}^{(n)})$, even if $\mathbf{p}^{(n)}\in\mathcal{S}$.
However, we next argue that by carefully choosing the threshold sequence
$\\{\beta_{n}\\}$, $\tilde{\mathbf{G}}^{(n)}$ can be made asymptotically
unbiased to $\mathbf{g}(\mathbf{p}^{(n)})$. Note that the number of summands
in (20) is finite for all $n$, thus, under natural conditions on
$\overline{\mathbf{v}}$, $\tilde{\mathbf{G}}^{(n)}$ is integrable for all
$\mathbf{p}\in\Delta$, and we define
$\mathbf{g}_{n}(\mathbf{p})=\mathrm{E}_{\mathbf{p}}\tilde{\mathbf{G}}^{(n)}$.

Our goal therefore is to find an appropriate threshold sequence
$\\{\beta_{n}\\}$. In our suggested heuristic we attempt to choose
$\\{\beta_{n}\\}$ such that for every $\mathbf{p}\in\mathcal{S}$, the sequence
$\\{\mathbf{g}_{n}(\mathbf{p})\\}_{n\geq 1}$ converges sufficiently fast to
$\mathbf{g}(\mathbf{p})$ as $n\to\infty$. Note that for all
$\mathbf{p}\in\mathcal{S}$, $\mathbf{g}_{n}(\mathbf{p})$ can be written as

$\displaystyle\mathbf{g}_{n}(\mathbf{p})$
$\displaystyle=\mathrm{E}_{\mathbf{p}}\tilde{\mathbf{G}}^{(n)}=\mathrm{E}_{\mathbf{p}}\left[\sum_{j=1}^{L}\mathbf{\overline{v}}(X_{j})\right]-\mathrm{E}_{\mathbf{p}}\left[\sum_{j=\beta_{n}+1}^{L}\mathbf{\overline{v}}(X_{j})\mathbf{1}_{\\{L>\beta_{n}\\}}\right]$
$\displaystyle=\mathbf{g}(\mathbf{p})-\mathrm{E}_{\mathbf{p}}\left[\sum_{j=\beta_{n}+1}^{L}\mathbf{\overline{v}}(X_{j})\mathbf{1}_{\\{L>\beta_{n}\\}}\right]$
$\displaystyle=\mathbf{g}(\mathbf{p})-\mathrm{P}_{\mathbf{p}}(L>\beta_{n})\cdot\sum_{j=\beta_{n}+1}^{L}\mathrm{E}_{\mathbf{p}}\big{[}\mathbf{\overline{v}}(X_{j})\mid
L>\beta_{n}\big{]}=\mathbf{g}(\mathbf{p})-\xi_{n}(\mathcal{\mathbf{p}}),$

where

$\xi_{n}(\mathcal{\mathbf{p}})=\mathrm{P}_{\mathbf{p}}(L>\beta_{n})\cdot\sum_{j=\beta_{n}+1}^{L}\mathrm{E}_{\mathbf{p}}\big{[}\mathbf{\overline{v}}(X_{j})\mid
L>\beta_{n}\big{]}.$

Assume that $\mathbf{u}$ is continuous and conservative on $\mathcal{S}$ (as
in A3) and that $\\{\gamma_{n}\\}$ satisfies A4. Let
$\tilde{\mathcal{S}}\subset\mathcal{S}$ be a compact subset of $\mathcal{S}$
in which an equilibrium lies, such that
$\sup_{\mathbf{p}\in\mathcal{S}}\mathrm{E}_{\mathbf{p}}\|\mathbf{G}\|^{2}<\infty$
(as in A2), and in addition, for all $\mathbf{p}\in\tilde{\mathcal{S}}$,

$\sum_{n=1}^{\infty}\gamma_{n}\ell(\mathbf{p})\cdot|\xi_{n}({\mathbf{p}})|<\infty.$
(22)

If for all sufficiently large $n$, the iterate remains (with probability 1) in
$\tilde{\mathcal{S}}\subset\mathcal{S}$, then, we conjecture that the
conclusion of Theorem 5 holds. Rigorous results for iteration-dependent
functions can be found in [49, Ch. 6].

Noticeably, there is an inherent trade-off in the choice of the sequence
$\\{\beta_{n}\\}$: if $\\{\beta_{n}\\}$ diverges too slowly,
$|\xi_{n}({\mathbf{p}})|$ diminishes slowly and may fail to satisfy the
condition in (22), whereas if $\\{\beta_{n}\\}$ diverges very fast, there is a
risk that the algorithm will spend long periods of time simulating arrivals to
an unstable system. A reasonable choice for $\beta_{n}$ should satisfy, as an
example, for all sufficiently large $n$ and $\mathbf{p}\in\mathcal{S}$,

$\mathrm{P}_{\mathbf{p}}(L>\beta_{n})\leq z(\mathbf{p})^{n}\ ,$ (23)

for some function $z:\mathcal{S}\to(0,1)$. If $z$ is bounded over the compact
set $\tilde{\mathcal{S}}$, then this choice of $\\{\beta_{n}\\}$, by the
Borel-Cantelli lemma, ensures that the cycle length hits the threshold
$\beta_{n}$ only finitely many times. This can be done, for example, if the
cycle-length distribution has a light tail, i.e., if for all
$\mathbf{p}\in\tilde{\mathcal{S}}$ there exists an $\alpha$ such that
$\mathrm{P}(L>x)\leq\alpha^{x}$ (the latter is implied, for example, in the
M/G/1 queue, assuming that the service-time distribution is light tailed; cf.
[24]). Then taking $\beta_{n}=\kappa n$ for some constant $\kappa>0$ yields
$\mathrm{P}_{\mathbf{p}}(L>\beta_{n})\leq\alpha^{\kappa n}$.

In Figure 5 below we present results from a simulation of the Unobservable
M/G/1 queue of Example 1, which demonstrate the convergence of the iterate to
the true equilibrium depicted by the red dashed line. In this example,
service-time are exponentially distributed with mean $1/\mu=1$ (thus, the
queue is an M/M/1), and the (potential) arrival rate $\lambda$ is $2$, hence,
$\lambda>\mu$ and $\mathcal{S}=\\{\mathbf{p}=(p,1-p)\mid p\in[0,1/2)\\}$. The
utility parameters are $R=5$ and $C=1$, implying that the equilibrium joining
probability is given by $p^{e}=0.4$. We implement the modified algorithm, for
$n=1,\dots,10^{6}$, using $\tilde{\mathbf{G}}^{(n)}$ as the estimator at
iteration $n$, with $\beta_{n}=n$, step size $\gamma_{n}=1/n$ and initial
strategy $\mathbf{p}^{(1)}=(1/2,1/2)$. In our experimentation, over the
simulation horizon, the cycle length hits the threshold $\beta_{n}$ a few
dozens times, with $n=6,175$ being the last iteration index for which the
threshold was hit. The last iteration $n$ for which the the iterate exists the
stability region is $n=5,059$, where we have
$\mathbf{p}^{(n)}=(0.53,0.47)\notin\mathcal{S}$. This provides a strong
empirical evidence that iterate is absorbed in a compact set in the domain of
attraction of the equilibrium point $\mathbf{p}^{e}$.

Figure 5: Convergence of the modified SA algorithm as $n\to\infty$. The first
coordinate of $\mathbf{p}^{(n)}=({p}^{(n)},1-{p}^{(n)})$, i.e., the joining
probability at stage $n$, is plotted (in blued) vs. $n$ on a square-root
scale. The red dashed line depicts the correct equilibrium joining
probability, which is given by $p^{e}=0.4$.

##  Appendix D Extension to games with state information

In this section we extend our concept of the surrogate best-response function
to the model with state information. Theorem 10 follows directly from this
construction.

First, we redefine the surrogate best-response function as

$\mathbf{f}(\mathbf{p})=\operatorname*{arg\,min}_{\mathbf{q}\in\mathcal{P}}\sum_{s\in\mathcal{I}}\left\|\mathbf{p}(s)+\xi_{\mathbf{p}}(s)\cdot\mathbf{Hu}(\mathbf{p}\mid
s)-\mathbf{q}(s)\right\|^{2}.$ (24)

Similar to (14), the optimization problem in (24) is also separable,
motivating the following definition, for all $s\in\mathcal{I}$:

$\mathbf{f}(\mathbf{p}\mid
s)=\pi_{\Delta}\left(\mathbf{p}(s)+\xi_{\mathbf{p}}(s)\cdot\mathbf{Hu}(\mathbf{p}\mid
s)\right)=\pi_{\Delta}\left(\mathbf{p}(s)+\xi_{\mathbf{p}}(s)\cdot\mathbf{u}(\mathbf{p}\mid
s)\right)$ (25)

which is a real function from $\Delta$ to itself. The second transition in
(25) follows Lemma 11. We can therefore think of $\mathbf{f}$ as a vector
valued function, $\mathbf{f}:\mathcal{P}\to\mathcal{P}$ (as opposed to
$\mathcal{BR}$, which is a correspondence, $\mathcal{BR}:\mathcal{P}\to
2^{\mathcal{P}}$), and in addition, $\mathbf{p}=\mathbf{f(p)}$ if and only if
$\mathbf{p}(s)=\mathbf{f(p}\mid s)$ for all $s\in\mathcal{I}$.

######  Lemma 13.

Suppose for every $s\in\mathcal{I}$,
$\xi_{\mathbf{p}}(s)\cdot\mathbf{Hu}(\mathbf{p}\mid s)$ is continuous on
$\mathcal{P}$ (as a function of $\mathbf{p}$). Then $\mathbf{f}(\cdot)$ is
continuous on $\mathcal{P}$, and therefore admits a fixed point. In addition,
any strategy is a fixed point for $\mathbf{f}$ if and only if it is an
equilibrium, i.e., $\mathbf{p}=\mathbf{f}(\mathbf{p})$ if and only if
$\mathbf{p}\in\mathcal{BR}(\mathbf{p})$, hence, an equilibrium exists.

###### Proof.

Under the conditions of Lemma 13, the objective function in the LHS of (24) is
continuous in $(\mathbf{p},\mathbf{q})$ on the product space
$\mathcal{P}\times\mathcal{P}$, and $\mathcal{P}$ is compact, thus by the
maximum theorem $\mathbf{f}$ is continuous over $\mathcal{P}$. As a result, by
Brouwer’s fixed-point theorem, $\mathbf{f}$ admits a fixed point in
$\mathcal{P}$. The rest of the proof is similar to that of Lemma 2:

Suppose $\mathbf{p}$ is an equilibrium, i.e.,
$\mathbf{p}\in\mathcal{BR}(\mathbf{p})$. Then for all $s\in\mathcal{I}$, the
expression $\xi_{\mathbf{p}}(s)\mathbf{u}(\mathbf{p}\mid
s)^{\prime}\mathbf{r}$ is maximized at $\mathbf{r}=\mathbf{p}(s)$, hence
$\xi_{\mathbf{p}}(s)\mathbf{u}(\mathbf{p}\mid
s)^{\prime}(\mathbf{p}(s)-\mathbf{q}(s))\geq 0$ for all
$\mathbf{q}\in\mathcal{P}$. Consider a strategy $\mathbf{q}\neq\mathbf{p}$,
thus, for any $s\in\mathcal{I}$ such that $\mathbf{q}(s)\neq\mathbf{p}(s)$,

$\displaystyle\|\mathbf{p}(s)+\xi_{\mathbf{p}}(s)\mathbf{u}(\mathbf{p}\mid
s)-\mathbf{q}(s)\|^{2}$
$\displaystyle=\|\mathbf{p}(s)-\mathbf{q}(s)\|^{2}+2\xi_{\mathbf{p}}(s)\mathbf{u}(\mathbf{p}\mid
s)^{\prime}(\mathbf{p}(s)-\mathbf{q}(s))+\|\xi_{\mathbf{p}}(s)\mathbf{u}(\mathbf{p}\mid
s)\|^{2}$ $\displaystyle>\|\xi_{\mathbf{p}}(s)\mathbf{u}(\mathbf{p}\mid
s)\|^{2}=\|\mathbf{p}(s)+\xi_{\mathbf{p}}(s)\mathbf{u}(\mathbf{p}\mid
s)-\mathbf{p}(s)\|^{2}.$

Hence, $\mathbf{p}(s)=\mathbf{f}(\mathbf{p}\mid s)$, meaning that
$\mathbf{p}=\mathbf{f}(\mathbf{p})$. Assume on the contrary that $\mathbf{p}$
is not an equilibrium, thus we can choose $\mathbf{q}\in\mathcal{P}$ and
$s\in\mathcal{I}(\mathbf{p})$, $\xi_{\mathbf{p}}(s)>0$, such that
$\mathbf{u}(\mathbf{p}\mid s)^{\prime}\mathbf{q}(s)>\mathbf{u}(\mathbf{p}\mid
s)^{\prime}\mathbf{p}(s)$. Then a parameter $\theta\in(0,1)$ can be chosen
such that

$\theta<\min\left\\{\frac{2\xi_{\mathbf{p}}(s)\mathbf{u(p}\mid
s)^{\prime}(\mathbf{q}(s)-\mathbf{p}(s))}{\|\mathbf{q}(s)-\mathbf{p}(s)\|^{2}},1\right\\},$

noting from the assumptions that the right-hand side is strictly positive. We
then define $\tilde{\mathbf{q}}=\mathbf{p}+\theta(\mathbf{q-p})$ to obtain,
after rearrangement,

$\begin{split}&\left\|\mathbf{p}(s)+\xi_{\mathbf{p}}(s)\cdot\mathbf{u}(\mathbf{p}\mid
s)-\tilde{\mathbf{q}}(s)\right\|^{2}\\\
&\qquad=\theta\left(\|\mathbf{q}(s)-\mathbf{p}(s)\|^{2}+2\xi_{\mathbf{p}}(s)\mathbf{u(p}\mid
s)^{\prime}(\mathbf{q}(s)-\mathbf{p}(s))\right)+\|\xi_{\mathbf{p}}(s)\mathbf{u}(\mathbf{p}\mid
s)\|^{2}\\\ &\qquad<\|\xi_{\mathbf{p}}(s)\mathbf{u}(\mathbf{p}\mid
s)\|^{2}=\left\|\mathbf{p}(s)+\xi_{\mathbf{p}}(s)\cdot\mathbf{u}(\mathbf{p}\mid
s)-\mathbf{p}(s)\right\|^{2},\end{split}$

and therefore $\mathbf{p}(s)\neq\mathbf{f}(\mathbf{p}\mid s)$, implying that
$\mathbf{p}\neq\mathbf{f}(\mathbf{p})$. ∎

#### Proof of Theorem 10

###### Proof.

Denote $|\mathcal{I}|=l$. With slight abuse of notation, we treat a strategy
$\mathbf{p}\in\mathcal{P}$ hereafter as a real $k\times l$ matrix, whose
$s$-th column, $(p_{1,s},\dots p_{k,s})$, is given by the vector
$\mathbf{p}(s)$ defined previously. Define the mapping
$\bar{\mathbf{u}}:\mathcal{P}\to\mathbf{R}^{k\times l}$ such that
$\bar{\mathbf{u}}(\mathbf{p})$ is a matrix whose $s$-th column,
$(\bar{u}_{1,s}(\mathbf{p}),\dots,\bar{u}_{k,s}(\mathbf{p}))$, is given by
$\xi_{\mathbf{p}}(s)\mathbf{Hu(p}\mid s)$. Note that the strategy space
$\mathcal{P}$ is the product space of $l$ copies of $\Delta$, hence it is a
compact polyhedron in $\mathbf{R}^{k\times l}$. Furthermore, the projection of
an element in $\mathbf{x}\in\mathbf{R}^{k\times l}$ onto $\mathcal{P}$ is
computed simply by projecting each column of $\mathbf{x}$ onto $\Delta$. Then
the corresponding ODE for the algorithm in (16) is

$\mathbf{\dot{p}=\bar{u}(p)+z},\quad-(z_{1,s}(t),\dots
z_{k,s}(t))\in\mathcal{C}((p_{1,s}(t),\dots p_{k,s}(t))),\>\forall t\geq
0,1\leq s\leq l,$ (26)

where $(z_{1,s}(t),\dots z_{k,s}(t))$ is the $s$-th column vector of
$\mathbf{z}$, and $\mathcal{C}$ is the set-valued map defined in Section A.2.
Let $u^{*}:\mathcal{P}\to\mathbb{R}$ be the potential function, and let
$\nabla u^{*}(\mathbf{p})$ be its gradient at $\mathbf{p}$, i.e., a real
$k\times l$ matrix whose element at the $i$-th row and $s$-th column is
$(\partial/\partial p_{i,s})u^{*}(\mathbf{p})$. Then Assumption B3 implies
that $\nabla u^{*}(\mathbf{p})=-\bar{\mathbf{u}}(\mathbf{p})$. By repeating
the same steps as in the proof of Lemma 12, we have that each point
$\mathbf{p}$ in the limit set of (26) is stationary, i.e., satisfies
$\mathbf{p}=\pi_{\mathcal{P}}(\mathbf{p}+\mathbf{\bar{u}(p)})$, and therefore
is an equilibrium strategy.

Similarly to the proof of Theorem 5, we define
$\epsilon_{n}=\gamma_{n}\ell(\mathbf{p}^{(n)})$, observing that
$\sum_{n=1}^{\infty}\epsilon_{n}=\infty$ and
$\sum_{n=1}^{\infty}\epsilon_{n}^{2}<\infty$ due to Assumptions B1 and A4. The
algorithm in (16) can be therefore written as

$\mathbf{p}^{(n+1)}=\pi_{\mathcal{S}}\left(\mathbf{p}^{(n)}+\epsilon_{n}\frac{\mathbf{H}\mathbf{G}^{(n)}}{\ell(\mathbf{p}^{(n)})}\right),$
(27)

where $\mathbf{G}$ is a $k\times l$ matrix with $\mathbf{G}(s)$ as its $s$-th
column. From (15) we have that

$\displaystyle\mathrm{E}_{\mathbf{p}}\left[\frac{\mathbf{H}\mathbf{G}^{(n)}}{\ell(\mathbf{p}^{(n)})}\right]=\bar{\mathbf{u}}(\mathbf{p}^{(n)}).$

Thus, as in the proof of Theorem 5, we invoke Theorem 2.4 in [49, Ch. 5.2], to
conclude that $\mathbf{p}^{(n)}$ converges to a set of limit points of (26),
and since every limit point is an equilibrium strategy, we obtain the result.
∎