Next, we analyze the loss caused by rounding. Let $y\in[0,1]^{n}$ be a vector,
and consider tossing $n$ independent coins with the $t$-th coin turning up
with probability $y_{i}$. Then, the _Poisson binomial distribution_ [8] with
respect to $y$, denoted $P(y)$, is the probability distribution of the number
of coins turning up. The following shows that this distribution plays an
important role in the analysis of the performance of the rounding.

######  Lemma 7.10.

Let $i^{\prime}\in\\{1,\dots,|U|\\}$. Then, $|\bm{C}_{\bm{p}(i^{\prime})}|-1$
follows the Poisson binomial distribution with respect to the vector
$(x_{1,\bm{p}(i^{\prime})},\dots,x_{i^{\prime}-1,\bm{p}(i^{\prime})},x_{i^{\prime}+1,\bm{p}(i^{\prime})},\dots,x_{|U|,\bm{p}(i^{\prime})})$.

###### Proof.

For each $i\in\\{1,\dots,|U|\\}$ and $j\in\\{1,\dots,|V|\\}$, we have
$\Pr\left[\bm{p}(i)=j\right]=\bm{x}_{i,j}$. Additionally,
$\bm{p}(i)\;(i\in\\{1,\dots,|U|\\})$ are pairwise independent. Therefore,
$|\bm{C}_{p(i^{\prime})}|-1$ can be regarded as the number of coins turning up
when we toss $|U|$ independent coins with turning-up probabilities of
$x_{1,\bm{p}(i^{\prime})},\ldots,x_{i^{\prime}-1,\bm{p}(i^{\prime})},x_{i^{\prime}+1,\bm{p}(i^{\prime})},\dots,x_{|U|,\bm{p}(i^{\prime})}$.
∎

Let

$\displaystyle Y=\inf_{n\in\mathbb{Z}_{\geq 1},\sum_{t=1}^{n}y_{t}\leq
1}\sum_{k=0}^{\infty}\left(\frac{1}{k+1}\Pr_{\bm{k}\sim
P(y)}\left[\bm{k}=k\right]\right).$

Then, the output matching size can be bounded by using $Y$ as can be seen in
the following:

######  Lemma 7.11.

Let $\bm{x}\in\mathbb{R}^{E}$ be the vector and $\bm{M}$ be the matching as
constructed in $\textsc{PLipMWBM}(G,w,\epsilon)$. Then, we have

$\displaystyle\mathop{\mathbb{E}}\left[\sum_{e\in\bm{M}}w(e)\right]\geq
Y\sum_{e\in E}w(e)\bm{x}_{e}.$

###### Proof.

We have

$\displaystyle\mathop{\mathbb{E}}\left[\sum_{e\in\bm{M}}w(e)\right]=\sum_{e\in
E}\left(w(e)\cdot\Pr[e\in\bm{M}]\right)=\sum_{i=1}^{|U|}\sum_{j=1}^{|V|}\left(w(i,j)\cdot\Pr\left[\bm{p}(i)=j\right]\cdot\Pr\left[\bm{q}(j)=i\mid\bm{p}(i)=j\right]\right)$
$\displaystyle=\sum_{i=1}^{|U|}\left(\Pr\left[\bm{q}(\bm{p}(i))=i\right]\cdot\sum_{j=1}^{|V|}\left(w(i,j)\cdot\Pr\left[\bm{p}(i)=j\right]\right)\right)=\sum_{i=1}^{|U|}\left(\mathop{\mathbb{E}}\left[\frac{1}{\left|\bm{C}_{\bm{p}(i)}\right|}\right]\cdot\sum_{j=1}^{|V|}w(i,j)\bm{x}_{i,j}\right)$
$\displaystyle=\sum_{i=1}^{|U|}\left(\sum_{k=0}^{\infty}\left(\frac{1}{k+1}\cdot\Pr\left[P((\bm{x}_{1,\bm{p}(i)},\dots,\bm{x}_{i-1,\bm{p}(i)},\bm{x}_{i+1,\bm{p}(i)}\dots,\bm{x}_{|U|,\bm{p}(i)}))=k\right]\right)\cdot\sum_{j=1}^{|V|}w(i,j)\bm{x}_{i,j}\right)$
$\displaystyle\geq Y\sum_{e\in E}w(e)\bm{x}_{e}.\qed$

Now we evaluate $Y$.

######  Lemma 7.12.

$Y=\frac{1}{2}$.

###### Proof.

For $y_{1},\ldots,y_{n}\in[0,1]$ with $\sum_{i=1}^{n}y_{i}\leq 1$, let

$\displaystyle
Y(y_{1},\dots,y_{n})=\sum_{k=0}^{\infty}\left(\frac{1}{k+1}\Pr_{\bm{k}\sim
P(y_{1},\ldots,y_{n})}\left[\bm{k}=k\right]\right).$

Suppose $n\geq 2$. We show that deleting two elements of
$(y_{1},\dots,y_{n})$, say $y_{1}$ and $y_{2}$, and appending their sum does
not increase the value. To show this, for $k\in\mathbb{Z}_{\geq 0}$, we let
$Q(k)=\Pr_{\bm{k}\sim P(y_{3},\ldots,y_{n})}\left[\bm{k}=k\right]$. We have

$\displaystyle Y(y_{1},y_{2},y_{3},\dots,y_{n})$
$\displaystyle=\sum_{k=0}^{\infty}\left(\left(\frac{1}{k+1}\cdot(1-y_{1})(1-y_{2})+\frac{1}{k+2}\cdot((1-y_{1})y_{2}+y_{1}(1-y_{2}))+\frac{1}{k+3}\cdot
y_{1}y_{2}\right)Q_{k}\right),$ $\displaystyle
Y(y_{1}+y_{2},y_{3},\dots,y_{n})$
$\displaystyle=\sum_{k=0}^{\infty}\left(\left(\frac{1}{k+1}\cdot(1-(y_{1}+y_{2}))+\frac{1}{k+2}\cdot(y_{1}+y_{2})\right)Q_{k}\right).$

Then, we have

$\displaystyle
Y(y_{1},y_{2},y_{3},\dots,y_{n})-Y(y_{1}+y_{2},y_{3},\dots,y_{n})$
$\displaystyle=\sum_{k=0}^{\infty}\left(\left(\frac{1}{k+1}\cdot
y_{1}y_{2}+\frac{1}{k+2}\cdot 2y_{1}y_{2}+\frac{1}{k+3}\cdot
y_{1}y_{2}\right)Q_{k}\right)$
$\displaystyle=y_{1}y_{2}\cdot\sum_{k=0}^{\infty}\left(\left(\frac{1}{k+1}-\frac{2}{k+2}+\frac{1}{k+3}\right)Q_{k}\right)\geq
0.$

Hence, the minimum of $Y(y_{1},\ldots,y_{n})$ is attained when $n=1$. We have

$\displaystyle Y(y_{1})=(1-y_{1})+\frac{1}{2}\cdot y_{1}\geq\frac{1}{2},$

where the equality holds when $y_{1}=1$, and hence the lemma holds. ∎

###### Proof of Lemma 7.8.

Combining Lemmas 7.9, 7.11 and 7.12 yields the claim. ∎

####  7.2.2 Stability of Entropy Regularization

In this section, we discuss the stability of the solution of the LP with
entropy regularization.

For a graph $G=(U\cup V,E)$, a weight vector $w\in\mathbb{R}_{\geq 0}^{E}$,
and $B>0$, let

$f(x)=\sum_{e\in E}w(e)x_{e}-B\sum_{e\in E}x_{e}\log x_{e}$

be the objective function of $\mathrm{LP}_{\mathrm{ent}}$ with a weight vector
$w\in\mathbb{R}_{\geq 0}^{E}$. We first discuss the following property of $f$.

######  Lemma 7.13.

For any $x,y\in\mathbb{R}^{E}$ with $\sum_{j\in V}x_{i,j}\leq 1$ and
$\sum_{j\in V}y_{i,j}\leq 1$, we have

$f(x)-f(y)\geq\nabla f(x)^{\top}(x-y)+\frac{B}{2}\sum_{i\in U}\left(\sum_{j\in
V}|x_{i,j}-y_{i,j}|\right)^{2}$

###### Proof.

Because $f$ is concave, for $z=x-y$, it suffices to show

$z^{\top}H(x)z\leq-B\sum_{i\in U}\left(\sum_{j\in V}|z_{i,j}|\right)^{2},$

where $H(x)$ is the Hessian of $f$ at $x$. Indeed, we have

$\displaystyle z^{\top}H(x)z=-B\sum_{e\in
E}\frac{z_{e}^{2}}{x_{e}}=-B\sum_{i\in U}\sum_{j\in
V}\frac{z_{i,j}^{2}}{x_{i,j}}$ $\displaystyle\leq-B\sum_{i\in
U}\left(\sum_{j\in V}\frac{z_{i,j}^{2}}{x_{i,j}}\cdot\sum_{j\in
V}x_{i,j}\right)\leq-B\sum_{i\in U}\left(\sum_{j\in
V}|z_{i,j}|\right)^{2}.\qed$

######  Lemma 7.14.

Let $G=(U\cup V,E)$ be a graph, $w\in\mathbb{R}_{\geq 0}^{E}$ be a weight
vector, $f\in E$, and $\delta>0$. Let $x,x^{\delta f}\in\mathbb{R}^{E}$ be the
optimal solutions to $\mathrm{LP}_{\mathrm{ent}}(G,w,B)$ and
$\mathrm{LP}_{\mathrm{ent}}(G,w+\delta\mathbf{1}_{f},B)$, respectively. Then,
we have

$\|x-x^{\delta f}\|_{1}=O\left(\frac{\delta\sqrt{|U|}}{B}\right).$

###### Proof.

Let

$\displaystyle f^{\delta f}(x)$ $\displaystyle=\sum_{e\in
E\setminus\\{f\\}}w(e)x_{e}+(w(f)+\delta)x_{f}-B\sum_{e\in E}x_{e}\log x_{e}.$

be the objective function of $\mathrm{LP}_{\mathrm{ent}}$ with the weight
vector $w+\delta\bm{1}_{f}$.

By Lemma 7.13, we have

$\displaystyle f(x)-f(x^{\delta f})\geq\nabla f(x)^{\top}(x-x^{\delta
f})+\frac{B}{2}\sum_{i\in U}\left(\sum_{j\in V}|x_{i,j}-x^{\delta
f}_{i,j}|\right)^{2}\geq\frac{B}{2}\sum_{i\in U}\left(\sum_{j\in
V}|x_{i,j}-x^{\delta f}_{i,j}|\right)^{2}.$

Similarly, we have

$\displaystyle f^{\delta f}(x^{\delta f})-f(x)\geq\frac{B}{2}\sum_{i\in
U}\left(\sum_{j\in V}|x_{i,j}-x^{\delta f}_{i,j}|\right)^{2}.$

Also, we have

$\displaystyle f(x)-f(x^{\delta f})+f^{\delta f}(x^{\delta f})-f^{\delta
f}(x)=\delta(x^{\delta f}_{f}-x_{f}).$

Combining the above three, we have

$\displaystyle B\sum_{i\in U}\left(\sum_{j\in V}|x_{i,j}-x^{\delta
f}_{i,j}|\right)^{2}\leq\delta(x^{\delta f}_{f}-x_{f}).$ (8)

In particular, this implies

$B(x^{\delta f}_{f}-x_{f})^{2}\leq\delta(x^{\delta f}_{f}-x_{f}),$

and hence we have $|x^{\delta f}_{f}-x_{f}|\leq\delta/B$. By substituting this
into (8), we obtain

$\sum_{i\in U}\left(\sum_{j\in V}|x_{i,j}-x^{\delta
f}_{i,j}|\right)^{2}\leq\frac{\delta^{2}}{B^{2}}.$

Then, we have

$\|x-x^{\delta f}\|_{1}=\sum_{i\in U}\sum_{j\in V}|x_{i,j}-x^{\delta
f}_{i,j}|\leq\sqrt{\sum_{i\in U}\left(\sum_{j\in V}|x_{i,j}-x^{\delta
f}_{i,j}|\right)^{2}}\cdot\sqrt{\sum_{i\in
U}1^{2}}=\frac{\sqrt{|U|}\delta}{B}.\qed$

####  7.2.3 Pointwise Lipschitzness

The goal of this section is to show the following:

######  Lemma 7.15.

For any bipartite graph $G=(U\cup V,E)$, a weight vector $w\in\mathbb{R}_{\geq
0}^{E}$, $\delta>0$, and $f\in E$, we have

$\displaystyle\mathrm{EM}_{\mathrm{u}}(\textsc{PLipMWBM}(G,w,\epsilon),\textsc{PLipMWBM}(G,w+\delta\mathbf{1}_{f},\epsilon))\leq
O\left(\frac{\delta\epsilon^{-1}|U|^{\frac{3}{2}}\log|V|}{\mathrm{opt}(G,w)}\right).$

To bound the earth mover’s distance between the output matchings for $(G,w)$
and $(G,w+\delta\bm{1}_{f})$, we consider the coupling $\mathcal{W}$ between
$(\bm{B},\bm{p},\bm{q})$ and $(\bm{B}^{\delta f},\bm{p}^{\delta
f},\bm{q}^{\delta f})$, defined as follows: For each number $B\in\mathbb{R}$,
we transport the probability mass for $\bm{B}=B$ to that for $\bm{B}^{\delta
f}=B$ as far as possible in such a way that

$\displaystyle\mathop{\mathbb{E}}_{((\bm{B},\bm{p},\bm{q}),(\bm{B}^{\delta
f},\bm{p}^{\delta f},\bm{q}^{\delta
f}))\sim\mathcal{W}}\left[\|\bm{q}-\bm{q}^{\delta
f}\|_{0}\mid\bm{B}=\bm{B}^{\delta f}=B\right],$

is minimized, where $\|\bm{q}-\bm{q}^{\delta f}\|_{0}$ is the number of
indices $j$ with $\bm{q}(j)\neq\bm{q}^{\delta f}(j)$. The remaining mass is
transported arbitrarily. Note that $\|\bm{q}-\bm{q}^{\delta f}\|_{0}$ is equal
to $d_{u}(\bm{M},\bm{M}^{\delta f})$, where $\bm{M}$ and $\bm{M}^{\delta f}$
are the matchings constructed using $\bm{q}$ and $\bm{q}^{\delta f}$,
respectively.

First, we evaluate the remaining mass.

######  Lemma 7.16.

We have

$\displaystyle\mathrm{TV}\left(\bm{B},\bm{B}^{\delta
f}\right)\leq\frac{2\delta}{\mathrm{opt}(G,w)}$

###### Proof.

We have

$\displaystyle\mathrm{TV}\left(\bm{B},\bm{B}^{\delta f}\right)$
$\displaystyle=\Pr\left[\bm{B}^{\delta
f}\in\left[\frac{2\mathrm{opt}(G,w)}{|U|\log|V|},\frac{2\mathrm{opt}(G,w+\delta\mathbf{1}_{f})}{|U|\log|V|}\right]\right]$
$\displaystyle=2\cdot\frac{\mathrm{opt}(G,w+\delta\mathbf{1}_{f})-\mathrm{opt}(G,w)}{\mathrm{opt}(G,w+\delta\mathbf{1}_{f})}$
$\displaystyle\leq\frac{2\delta}{\mathrm{opt}(G,w+\delta\mathbf{1}_{f})}\leq\frac{2\delta}{\mathrm{opt}(G,w)}.\qed$

Now we evaluate the distance between $\bm{p}$ and $\bm{p}^{\delta f}$.

######  Lemma 7.17.

Let $B\in\mathbb{R}_{\geq 0}$ and let $x,x^{\delta f}\in\mathbb{R}_{\geq
0}^{E}$ be the optimal solutions to $\mathrm{LP}_{\mathrm{ent}}(G,w)$ and
$\mathrm{LP}_{\mathrm{ent}}(G,w+\mathbf{1}_{\delta})$, respectively. Then, we
have

$\displaystyle\mathop{\mathbb{E}}_{((\bm{B},\bm{p},\bm{q}),(\bm{B}^{\delta
f},\bm{p}^{\delta f},\bm{q}^{\delta
f}))\sim\mathcal{W}}\left[\|\bm{p}-\bm{p}^{\delta
f}\|_{0}\mid\bm{B}=\bm{B}^{\delta f}=B\right]\leq\|x-x^{\delta f}\|_{1}.$

###### Proof.

First, we have

$\displaystyle\left|\Pr\left[\bm{p}(i)=j\right]-\Pr[\bm{p}^{\delta
f}(i)=j]\right|=\left|x_{i,j}-x^{\delta f}_{i,j}\right|$

for all $i\in\\{1,\dots,|U|\\}$ and $j\in\\{1,\dots,|V|\\}$. Because the
$\bm{p}(i)$ values are independent of each other when $\bm{B}=\bm{B}^{\delta
f}=B$, taking the product of the transportation for all
$i\in\\{1,\dots,|U|\\}$ yields the lemma. ∎

Now we evaluate the distance between $\bm{q}$ and $\bm{q}^{\delta f}$.

######  Lemma 7.18.

Let $B\in\mathbb{R}_{\geq 0}$ and let $x$ and $x^{\delta f}$ be the optimal
solutions to $\mathrm{LP}_{\mathrm{ent}}(G,w)$ and
$\mathrm{LP}_{\mathrm{ent}}(G,w+\mathbf{1}_{\delta})$, respectively. Then, we
have

$\displaystyle\mathop{\mathbb{E}}_{((\bm{B},\bm{p},\bm{q}),(\bm{B}^{\delta
f},\bm{p}^{\delta f},\bm{q}^{\delta
f}))\sim\mathcal{W}}\left[\|\bm{q}-\bm{q}^{\delta
f}\|_{0}\mid\bm{B}=\bm{B}^{\delta f}=B\right]\leq 2\cdot\|x-x^{\delta
f}\|_{1}.$

###### Proof.

Fix $B,p,p^{\delta f}\in\mathbb{R}_{\geq 0}$, and let $(\bm{q},\bm{q}^{\delta
f})$ be sampled from the marginal distribution of $\mathcal{W}$ conditioned on
$\bm{B}=\bm{B}^{\delta f}=B$, $\bm{p}=p$, and $\bm{p}^{\delta f}=p^{\delta
f}$. Note that under this condition, $C$ and $C^{\delta f}$ are no longer
random variables because they are deterministically determined by $p$ and
$p^{\delta f}$, respectively. Then, we have

$\displaystyle\mathop{\mathbb{E}}_{((\bm{B},\bm{p},\bm{q}),(\bm{B}^{\delta
f},\bm{p}^{\delta f},\bm{q}^{\delta
f}))\sim\mathcal{W}}\left[\|\bm{q}-\bm{q}^{\delta
f}\|_{0}\mid\bm{B}=\bm{B}^{\delta f}=B,\bm{p}=p,\bm{p}=p^{\delta f}\right]$
$\displaystyle\leq\sum_{i=1}^{|U|}\sum_{j=1}^{|V|}\left|\Pr\left[\bm{q}(j)=i\right]-\Pr[\bm{q}^{\delta
f}(j)=i]\right|$
$\displaystyle=\sum_{i=1}^{|U|}\sum_{j=1}^{|V|}\left|\frac{1}{|C_{j}|}\bm{1}_{p(i)=j}-\frac{1}{|C^{\delta
f}_{j}|}\bm{1}_{p^{\delta f}(i)=j}\right|$
$\displaystyle\leq\sum_{i=1}^{|U|}\sum_{j=1}^{|V|}\left|\bm{1}_{p(i)=j}-\bm{1}_{p^{\delta
f}(i)=j}\right|+\sum_{j=1}^{|V|}\left(|C_{j}|\cdot\left|\frac{1}{|C_{j}|}-\frac{1}{|C^{\delta
f}_{j}|}\right|\right)$ $\displaystyle=\|p-p^{\delta
f}\|_{0}+\sum_{j=1}^{|V|}\left(|C_{j}|\cdot\left|\frac{1}{|C_{j}|}-\frac{1}{|C^{\delta
f}_{j}|}\right|\right)$ $\displaystyle\leq\|p-p^{\delta
f}\|_{0}+\sum_{j=1}^{|V|}\left|\frac{|C^{\delta f}_{j}|-|C_{j}|}{|C^{\delta
f}_{j}|}\right|$ $\displaystyle\leq\|p-p^{\delta
f}\|_{0}+\sum_{j=1}^{|V|}\left||C^{\delta f}_{j}|-|C_{j}|\right|$
$\displaystyle=\|p-p^{\delta
f}\|_{0}+\sum_{j=1}^{|V|}\sum_{i=1}^{|U|}\left|\bm{1}_{p(i)=j}-\bm{1}_{p^{\delta
f}(i)=j}\right|$ $\displaystyle=2\cdot\|p-p^{\delta f}\|_{0},$ (9)

where the first inequality is from the fact that $\bm{q}(j)$ (and
$\bm{q}^{\delta f}(j)$) are pairwise independent for $j\in\\{1,\dots,|V|\\}$
and the second inequality is from

$\displaystyle\left|\frac{1}{|C_{j}|}\bm{1}_{p(i)=j}-\frac{1}{|C^{\delta
f}_{j}|}\bm{1}_{p^{\delta
f}(i)=j}\right|\leq\begin{cases}1&(\bm{1}_{p(i)=j}\neq\bm{1}_{p^{\delta
f}(i)=j}),\\\ \left|\frac{1}{|C_{j}|}-\frac{1}{|C^{\delta
f}(j)|}\right|&(\bm{1}_{p(i)=j}=\bm{1}_{p^{\delta f}(i)=j}=1),\\\
0&(\bm{1}_{p(i)=j}=\bm{1}_{p^{\delta f}(i)=j}=0).\end{cases}$

and the fact that there are at most $|C_{j}|$ indices $i$ with
$\bm{1}_{p(i)=j}=\bm{1}_{p^{\delta f}(i)=j}=1$. By integrating (9) over $p$
and $p^{\delta f}$, we obtain

$\displaystyle\mathop{\mathbb{E}}_{((\bm{B},\bm{p},\bm{q}),(\bm{B}^{\delta
f},\bm{p}^{\delta f},\bm{q}^{\delta
f}))\sim\mathcal{W}}\left[\|\bm{q}-\bm{q}^{\delta
f}\|_{0}\mid\bm{B}=\bm{B}^{\delta f}=B\right]$
$\displaystyle\leq\mathop{\mathbb{E}}_{((\bm{B},\bm{p},\bm{q}),(\bm{B}^{\delta
f},\bm{p}^{\delta f},\bm{q}^{\delta
f}))\sim\mathcal{W}}\left[2\cdot\|\bm{p}-\bm{p}^{\delta
f}\|_{0}\mid\bm{B}=\bm{B}^{\delta f}=B\right]\leq 2\cdot\|x-x^{\delta
f}\|_{1},$

where the second inequality is from Lemma 7.17. ∎

Now we can bound the pointwise Lipschitz constant as follows.

###### Proof of Lemma 7.15.

We have

$\displaystyle\mathrm{EM}_{\mathrm{u}}(\textsc{PLipMWBM}(G,w,\epsilon),\textsc{PLipMWBM}(G,w+\delta\mathbf{1}_{f},\epsilon))$
$\displaystyle\leq\mathrm{TV}\left(\bm{B},\bm{B}^{\delta
f}\right)\cdot|U|+\mathop{\mathbb{E}}_{((\bm{B},\bm{p},\bm{q}),(\bm{B}^{\delta
f},\bm{p}^{\delta f},\bm{q}^{\delta
f}))\sim\mathcal{W}}\left[\|\bm{q}-\bm{q}^{\delta
f}\|_{0}\mid\bm{B}=\bm{B}^{\delta f}\right]$
$\displaystyle\leq\mathrm{TV}\left(\bm{B},\bm{B}^{\delta
f}\right)\cdot|U|+\mathop{\mathbb{E}}_{((\bm{B},\bm{p},\bm{q}),(\bm{B}^{\delta
f},\bm{p}^{\delta f},\bm{q}^{\delta
f}))\sim\mathcal{W}}\left[2\cdot\|\bm{x}-\bm{x}^{\delta
f}\|_{1}\mid\bm{B}=\bm{B}^{\delta f}\right]$
$\displaystyle\leq\frac{2\delta}{\mathrm{opt}(G,w)}\cdot|U|+O\left(\delta\sqrt{|U|}\cdot\frac{|U|\log|V|}{\epsilon\cdot\mathrm{opt}(G,w)}\right)=O\left(\frac{\delta\epsilon^{-1}|U|^{\frac{3}{2}}\log|V|}{\mathrm{opt}(G,w)}\right),$

where the second inequality is from Lemma 7.18, and the third inequality is
from Lemma 7.14 and 7.16. ∎

###### Proof of Theorem 7.7.

The approximability result follows by Lemma 7.8. Let
$w,w^{*}\in\mathbb{R}_{\geq 0}^{E}$ be two weight vectors with
$\mathrm{opt}(G,w)>0$ and $\|w-w^{*}\|\leq\frac{\mathrm{opt}(G,w)}{2}$. Then
by Lemma 7.15, we have

$\displaystyle\mathrm{EM}_{\mathrm{u}}(\textsc{PLipMWBM}(G,w^{*},\epsilon),\textsc{PLipMWBM}(G,w^{*}+\delta\mathbf{1}_{f},\epsilon))$
$\displaystyle\leq
O\left(\frac{\delta\epsilon^{-1}|U|^{\frac{3}{2}}\log|V|}{\mathrm{opt}(G,w^{*})}\right)$
$\displaystyle\leq
O\left(\frac{\delta\epsilon^{-1}|U|^{\frac{3}{2}}\log|V|}{\mathrm{opt}(G,w)}\right).$

Thus, the claim follows by Lemma 7.1. ∎

## References

  * [1] Naveed Akhtar and Ajmal Mian.  Threat of adversarial attacks on deep learning in computer vision: A survey.  IEEE Access, 6:14410–14430, 2018.
  * [2] Nicholas Carlini and David Wagner.  Towards evaluating the robustness of neural networks.  In 2017 IEEE Symposium on Security and Privacy (SP), pages 39–57. Ieee, 2017.
  * [3] Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier.  Parseval networks: Improving robustness to adversarial examples.  In International Conference on Machine Learning, pages 854–863. PMLR, 2017.
  * [4] Marco Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  Advances in neural information processing systems, 26, 2013.
  * [5] Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas.  Efficient and accurate estimation of lipschitz constants for deep neural networks.  Advances in Neural Information Processing Systems, 32, 2019.
  * [6] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  In International Conference on Learning Representations (ICLR), 2015\.
  * [7] Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J Cree.  Regularisation of neural networks by enforcing lipschitz continuity.  Machine Learning, 110(2):393–416, 2021.
  * [8] Wassily Hoeffding.  On the distribution of the number of successes in independent trials.  The Annals of Mathematical Statistics, pages 713–721, 1956.
  * [9] Soh Kumabe and Yuichi Yoshida.  Average sensitivity of dynamic programming.  In Proceedings of the 33th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1925–1961, 2022.
  * [10] Soh Kumabe and Yuichi Yoshida.  Average sensitivity of the knapsack problem.  In 30th Annual European Symposium on Algorithms (ESA), volume 244, pages 75:1–75:14, 2022.
  * [11] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In International Conference on Learning Representations (ICLR), 2018\.
  * [12] Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida.  Spectral normalization for generative adversarial networks.  In International Conference on Learning Representations, 2018.
  * [13] Shogo Murai and Yuichi Yoshida.  Sensitivity analysis of centralities on unweighted networks.  In Proceedings of the 2019 World Wide Web Conference (WWW), pages 1332–1342, 2019.
  * [14] Pan Peng and Yuichi Yoshida.  Average sensitivity of spectral clustering.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pages 1132–1140, 2020.
  * [15] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  In International Conference on Learning Representations (ICLR), 2013\.
  * [16] Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama.  Lipschitz-margin training: Scalable certification of perturbation invariance for deep neural networks.  Advances in neural information processing systems, 31, 2018.
  * [17] Nithin Varma and Yuichi Yoshida.  Average sensitivity of graph algorithms.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 684–703. 2021.
  * [18] Aladin Virmaux and Kevin Scaman.  Lipschitz regularity of deep neural networks: analysis and efficient estimation.  Advances in Neural Information Processing Systems, 31, 2018.
  * [19] Tsui-Wei Weng, Huan Zhang, Pin-Yu Chen, Jinfeng Yi, Dong Su, Yupeng Gao, Cho-Jui Hsieh, and Luca Daniel.  Evaluating the robustness of neural networks: An extreme value theory approach.  In International Conference on Learning Representations, 2018.
  * [20] Han Xu, Yao Ma, Hao-Chen Liu, Debayan Deb, Hui Liu, Ji-Liang Tang, and Anil K Jain.  Adversarial attacks and defenses in images, graphs and text: A review.  International Journal of Automation and Computing, 17(2):151–178, 2020.
  * [21] Yuichi Yoshida and Shinji Ito.  Average sensitivity of Euclidean $k$-clustering.  In NeurIPS, 2022.  to appear.
  * [22] Yuichi Yoshida and Takeru Miyato.  Spectral norm regularization for improving the generalizability of deep learning.  arXiv preprint arXiv:1705.10941, 2017.
  * [23] Yuichi Yoshida and Samson Zhou.  Sensitivity analysis of the maximum matching problem.  In Innovations in Theoretical Computer Science (ITCS), pages 58:1–58:20, 2021.
  * [24] Wei Emma Zhang, Quan Z Sheng, Ahoud Alhazmi, and Chenliang Li.  Adversarial attacks on deep-learning models in natural language processing: A survey.  ACM Transactions on Intelligent Systems and Technology, 11(3):1–41, 2020.

##  Appendix A Missing Proofs

###### Proof of Lemma 1.5.

First, note that the inequality in the statement holds even for $\delta>c$
because then

$\displaystyle\mathrm{EM}_{\mathrm{w}}\left((\mathcal{A}(G,w),w),(\mathcal{A}(G,w+\delta\mathbf{1}_{f}),w+\delta\mathbf{1}_{f})\right)$
$\displaystyle\leq\mathrm{EM}_{\mathrm{w}}\left((\mathcal{A}(G,w),w),(\mathcal{A}(G,w+(\delta-c)\mathbf{1}_{f}),w+(\delta-c)\mathbf{1}_{f})\right)$
$\displaystyle\quad+\mathrm{EM}_{\mathrm{w}}\left((\mathcal{A}(G,w+(\delta-c)),w+(\delta-c)),(\mathcal{A}(G,w+\delta\mathbf{1}_{f}),w+\delta\mathbf{1}_{f})\right)$
$\displaystyle\leq(\delta-c)L+cL=\delta L,$

where the last inequality can be proven by induction. Also because
$\mathrm{EM}_{\mathrm{w}}$ is commutative, the inequality

$\mathrm{EM}_{\mathrm{w}}\left((\mathcal{A}(G,w),w),(\mathcal{A}(G,w+\delta\mathbf{1}_{f}),w+\delta\mathbf{1}_{f})\right)\leq|\delta|L$

holds even for $\delta<0$.

Let $e_{1},\ldots,e_{m}$ be an arbitrary ordering of elements in $E$, where
$m=|E|$. For two weight vectors $w,w^{\prime}\in\mathbb{R}_{\geq 0}^{E}$, by
the triangle inequality, we have

$\displaystyle\mathrm{EM}_{\mathrm{w}}\left((\mathcal{A}(G,w),w),(\mathcal{A}(G,w^{\prime}),w^{\prime})\right)\leq\sum_{i=1}^{m}\mathrm{EM}_{\mathrm{w}}\left((\mathcal{A}(G,w_{i-1}),w_{i-1}),(\mathcal{A}(G,w_{i}),w_{i})\right),$

where $w_{i}\in\mathbb{R}_{\geq 0}^{E}$ is the weight vector given by

$\displaystyle w_{i}(e_{j})=\begin{cases}w^{\prime}(e_{j})&(j\leq i)\\\
w(e_{j})&(j>i).\end{cases}$

Since $w_{i}=w_{i-1}+(w^{\prime}(e_{i})-w(e_{i}))\mathbf{1}_{e_{i}}$, we have

$\displaystyle\sup_{\begin{subarray}{c}w,w^{\prime}\in\mathbb{R}_{\geq
0}^{E},\\\ w\neq
w^{\prime}\end{subarray}}\frac{\mathrm{EM}_{\mathrm{w}}\left((\mathcal{A}(G,w),w),(\mathcal{A}(G,w^{\prime}),w^{\prime})\right)}{\|w-w^{\prime}\|_{1}}$
$\displaystyle\leq\sup_{\begin{subarray}{c}w,w^{\prime}\in\mathbb{R}_{\geq
0}^{E},\\\ w\neq
w^{\prime}\end{subarray}}\frac{\sum_{i=1}^{m}\mathrm{EM}_{\mathrm{w}}\left((\mathcal{A}(G,w_{i-1}),w_{i-1}),(\mathcal{A}(G,w_{i}),w_{i})\right)}{\sum_{i=1}^{m}|w^{\prime}(e_{i})-w(e_{i})|}$
$\displaystyle\leq\sup_{\begin{subarray}{c}w,w^{\prime}\in\mathbb{R}_{\geq
0}^{E},\\\ w\neq
w^{\prime}\end{subarray}}\max_{i=1,\ldots,m}\frac{\mathrm{EM}_{\mathrm{w}}\left((\mathcal{A}(G,w_{i-1}),w_{i-1}),(\mathcal{A}(G,w_{i}),w_{i})\right)}{|w^{\prime}(e_{i})-w(e_{i})|}$
$\displaystyle\leq L.\qed$

###### Proof of Lemma 7.1.

Let $e_{1},\ldots,e_{m}$ be an arbitrary ordering of elements in $E$, where
$m=|E|$. For two weight vectors $w,w^{\prime}\in\mathbb{R}_{\geq 0}^{E}$ with
$\|w-w^{\prime}\|_{1}\leq c$, by the triangle inequality, we have

$\displaystyle\mathrm{EM}_{\mathrm{u}}\left(\mathcal{A}(G,w),\mathcal{A}(G,w^{\prime})\right)\leq\sum_{i=1}^{m}\mathrm{EM}_{\mathrm{u}}\left(\mathcal{A}(G,w_{i-1}),\mathcal{A}(G,w_{i})\right),$

where $w_{i}\in\mathbb{R}_{\geq 0}^{E}$ is defined as in the proof of Lemma
1.5. Since $w_{i}=w_{i-1}+(w^{\prime}(e_{i})-w(e_{i}))\mathbf{1}_{e_{i}}$, we
have

$\displaystyle\sup_{\begin{subarray}{c}w,w^{\prime}\in\mathbb{R}_{\geq
0}^{E},\\\ w\neq
w^{\prime}\end{subarray}}\frac{\mathrm{EM}_{\mathrm{u}}\left(\mathcal{A}(G,w),\mathcal{A}(G,w^{\prime})\right)}{\|w-w^{\prime}\|_{1}}$
$\displaystyle\leq\sup_{\begin{subarray}{c}w,w^{\prime}\in\mathbb{R}_{\geq
0}^{E},\\\ w\neq
w^{\prime}\end{subarray}}\frac{\sum_{i=1}^{m}\mathrm{EM}_{\mathrm{u}}\left(\mathcal{A}(G,w_{i-1}),\mathcal{A}(G,w_{i})\right)}{\sum_{i=1}^{m}|w^{\prime}(e_{i})-w(e_{i})|}$
$\displaystyle\leq\sup_{\begin{subarray}{c}w,w^{\prime}\in\mathbb{R}_{\geq
0}^{E},\\\ w\neq
w^{\prime}\end{subarray}}\max_{i=1,\ldots,m}\frac{\mathrm{EM}_{\mathrm{u}}\left(\mathcal{A}(G,w_{i-1}),\mathcal{A}(G,w_{i})\right)}{|w^{\prime}(e_{i})-w(e_{i})|}$
$\displaystyle\leq L,$

where the last inequality is from the fact that
$\|w-w_{i-1}\|_{1}\leq\|w-w^{\prime}\|_{1}\leq c$ for $w(e_{i})\leq
w^{\prime}(e_{i})$ and $\|w-w_{i}\|_{1}\leq\|w-w^{\prime}\|_{1}\leq c$ for
$w(e_{i})>w^{\prime}(e_{i})$. Therefore, $\mathcal{A}$ has pointwise Lipschitz
constant $L$ on $G$ at $w$, considering the neighborhood
$\\{w^{\prime}\colon\|w-w^{\prime}\|\leq c\\}$. ∎


# A mixed-integer-programming-based Gauss–Seidel method for multi-leader-
multi-follower games

Filippo Fabiani1, Barbara Franci2, Martin Schmidt3, and Mathias Staudigl4 1
IMT School for Advanced Studies Lucca, Piazza San Francesco 19, 55100 Lucca,
Italy (filippo.fabiani@imtlucca.it).2 Department of Advanced Computing
Sciences, Maastricht University, NL–6200 MD, Maastricht, The Netherlands
(b.franci@maastrichtuniversity.nl).3 Department of Mathematics at Trier
University, Universitätsring 15, 54296 Trier, Germany (martin.schmidt@uni-
trier.de). 4 University of Mannheim, Department of Mathematics, B6, 68159
Mannheim, Germany (mathias.staudigl@uni-mannheim.de).

###### Abstract

We design a computational approach to find equilibria in a class of Nash games
possessing a hierarchical structure. By using tools from mixed-integer
programming and the characterization of variational equilibria in terms of the
Karush–Kuhn–Tucker conditions, we propose a mixed-integer game formulation for
solving such a challenging instance. Besides providing an equivalent
reformulation, we build upon our previous work and design a proximal
Gauss–Seidel method with global convergence guarantees for the case in which
the game enjoys a potential structure. In addition to proving the convergence
of the resulting scheme, we show its performance on a numerical instance of a
ride-hail market problem.

##  I Introduction

In this work, we are interested in solving a class of hierarchical games
involving a set of $N$ leaders who are strategically attached to $M_{i}$
followers, where $i\in[N]=\\{1,\ldots,N\\}$. The leaders are in turn involved
in a Nash game among the other leading agents. Mathematically, we model each
leader as a rational decision-maker with loss function
$F^{i}(x^{i},\boldsymbol{x}^{-i},\boldsymbol{y}^{i})$, depending on a private
decision $x^{i}$ controlled by leader $i$, a tuple $\boldsymbol{x}^{-i}$
representing the opponent leaders’ decisions, and finally a tuple
$\boldsymbol{y}^{i}$, which constitutes an $M_{i}$-tuple
$\boldsymbol{y}^{i}\coloneqq(y_{1}^{i},\ldots,y^{i}_{M_{i}})$ describing the
lower-level agents’ decisions. We are thus interested in computing Nash
equilibria in games in which the leader $i$ solves

$\min_{x^{i},\boldsymbol{y}^{i}}\quad
F^{i}(x^{i},\boldsymbol{x}^{-i},\boldsymbol{y}^{i})\quad\text{s.t.}\quad
x^{i}\in\mathcal{X}^{i},\ \boldsymbol{y}^{i}\in\mathbf{NE}^{i}(x^{i}),$ (1)

where the followers’ decision strategy $\boldsymbol{y}^{i}$ constitutes an
equilibrium of a generalized Nash equilibrium problem (GNEP), parametric in
the leader’s decision $x^{i}$. Such models have attracted great interest in
control and operations research [1, 2], recently also from a stochastic
perspective [3, 4], and belong to the family of modeling paradigms known as
_multi-leader-multi-follower game_. Under certain assumptions, this class of
problems reduces to mathematical programs with equilibrium constraints (MPECs)
[5] when there is only one leader who controls the equilibrium correspondence
of a set of followers [6, 2, 7, 8, 9]. By adopting the terminology of this
literature, we refer to problem (1) as the optimistic formulation of the
multi-leader-multi-follower game. In this framework, a challenging problem is
the lack of analytically tractable characterizations of the equilibrium
correspondence $\mathbf{NE}^{i}(x^{i})$. For polynomial data, it possesses a
semi-algebraic structure, being defined as a set of polynomial equations and
inequalities [10], which is however not enough to develop tractable numerical
methods for computing an equilibrium solution. In fact, the Nash
correspondence will exhibit nonconvexities, inherited from the complementarity
conditions characterizing first-order optimal points.

The main contributions of this work are the following. First, we develop a
global optimization-based reformulation of the equilibrium conditions for the
proposed multi-leader-multi-follower game. This reformulation is a key
instrument to reduce the hierarchical game to a large-scale, nonlinear, and
mixed-integer optimization formulation. Then, to ensure that the problem is
(numerically) tractable, we recast the leader’s game as a potential game.
While potential games are a relatively small class of games, they are of
fundamental importance in practical optimization and control applications and
thus represent a focal class of games. Building upon such an optimization
reformulation, we propose an iterative method based on a Gauss–Seidel
iteration that has already been analyzed in our previous contribution where we
consider a standard Nash equilibrium problem [11]. Here, we explain how this
iterative method can be extended to solve this challenging class of
hierarchical games, whose effectiveness is illustrated through numerical
simulations considering an example of the competitive ride-hail market
problem, adapted from [12].

##  II Problem setting

To describe our hierarchical game setting, we now introduce the different
levels of strategic interactions separately. To this end, we mostly use the
notation introduced in [13].

###  II-A The leaders’ problem

First, we consider the optimization problem that leader $i\in[N]$ solves, as
formalized next:

$\forall i\in[N]:\left\\{\begin{aligned}
&\underset{x^{i},\boldsymbol{y}^{i}}{\textrm{min}}&&F^{i}(x^{i},\boldsymbol{x}^{-i},\boldsymbol{y}^{i})\\\
&~{}\textrm{s.t.}&&G^{i}(x^{i})\geq
0,~{}\boldsymbol{y}^{i}\in\mathbf{NE}^{i}(x^{i}),\end{aligned}\right.$ (2)

where $x^{i}\in\mathbb{R}^{n^{i}}$ is the vector of the $i$-th leader’s
decisions, while
$\boldsymbol{x}^{-i}=(x_{j})_{j\in[N]\setminus\\{i\\}}\in\mathbb{R}^{n-n^{i}}$
collects the decisions of the $i$-th leader’s opponents and
$n\mathrel{{\mathop{:}}{=}}\sum_{i\in[N]}n^{i}$. The decisions of the
followers of leader $i$ are stacked in
$\boldsymbol{y}^{i}=(y^{i}_{\nu})_{\nu\in[M_{i}]}\in\mathbb{R}^{p^{i}}$, with
$y^{i}_{\nu}\in\mathbb{R}^{p^{i}_{\nu}}$, so that
$p^{i}\mathrel{{\mathop{:}}{=}}\sum_{\nu\in[M_{i}]}p^{i}_{\nu}$.

The cost function of leader $i\in[N]$ is
$F^{i}:\mathbb{R}^{n}\times\mathbb{R}^{p^{i}}\to\mathbb{R}$ while
$G^{i}:\mathbb{R}^{n^{i}}\to\mathbb{R}^{d^{i}}$ defines the private
constraints, where $d^{i}$ is the number of such constraints. With an eye to
(1), we thus define
$\mathcal{X}^{i}\mathrel{{\mathop{:}}{=}}\\{x^{i}\in\mathbb{R}^{n^{i}}\mid
G^{i}(x^{i})\geq 0\\}$. Furthermore, $\mathbf{NE}^{i}(x^{i})$ denotes the set
of generalized Nash equilibria (GNE) of the non-cooperative game among the
$M_{i}$ followers attached to the $i$-th leader, discussed later in §II-B.

Each problem in (2), which satisfies the conditions stated next, defines an
MPEC in which $\boldsymbol{y}^{i}$ is not strictly within the control of the
leader, but corresponds to an optimistic conjecture [14, 15]. We hence assume
the following:

###### Assumption 1

For all $i\in[N]$, it holds that:

  1. (i)

$F^{i}:\mathbb{R}^{n}\times\mathbb{R}^{p^{i}}\to\mathbb{R}$ is jointly
continuous in all its arguments;

  2. (ii)

$G^{i}:\mathbb{R}^{n^{i}}\to\mathbb{R}^{d^{i}}$ is continuous and concave in
each coordinate, i.e.,
$G^{i}(x^{i})=[g^{i}_{1}(x^{i});\ldots;g^{i}_{d^{i}}(x^{i})]$ is a column
vector and each coordinate function $g^{i}_{k}(\cdot)$ is a concave function.
$\square$

Before describing the GNEP involving each leader’s followers, we introduce the
solution notion employed for the considered class of multi-leader-multi-
follower games:

###### Definition 1

A tuple $\\{(\bar{x}^{i,\ast},\bar{\boldsymbol{y}}^{i,\ast})\\}_{i\in[N]}$ is
a leader-follower Nash equilibrium (LF-NE) if, for all $i\in[N]$, it solves
the collection of optimistic MPECs in (2). $\square$

###  II-B The generalized Nash game played by the followers

The optimization problem of each leader is challenging due to the presence of
the equilibrium constraints, aggregating the decisions of all lower-level
agents indexed by $\nu\in[M_{i}]$. The followers attached to leader $i$ are in
turn involved in a strategic competition represented by a generalized Nash
game at the lower level. Specifically, we consider a situation in which the
lower-level problem of leader $i$ hosts $M_{i}$ interdependent minimization
problems of the form

$\displaystyle\underset{y^{i}_{\nu}}{\textrm{min}}$ $\displaystyle
f^{i}_{\nu}(x^{i},y^{i}_{\nu},\boldsymbol{y}^{i}_{-\nu})$ (3a) s.t.
$\displaystyle D^{i}_{\nu}y^{i}_{\nu}\geq
e^{i}_{\nu}-A^{i}_{\nu}x^{i}-\sum_{\mu\in[M_{i}]\setminus\\{\nu\\}}D^{i}_{\nu,\mu}y^{i}_{\mu},$
(3b) $\displaystyle B^{i}x^{i}+\sum_{\mu\in[M_{i}]}E^{i}_{\mu}y^{i}_{\mu}\geq
c^{i},$ (3c)

for $\nu=1,\ldots,M_{i}$. These local minimization problems give rise to a
GNEP with the following features: i) Both the objectives $f^{i}_{\nu}$ and the
constraints depend on the upper-level decision variable $x^{i}$ chosen by the
leader; ii) The control variables of the followers affect the cost criterion
$f^{i}_{\nu}$, as well as the constraints. Therefore the $M_{i}$ followers are
involved in a GNEP, parametric in the leader’s decision variable $x^{i}$. The
restrictions of follower $i$’s decision variable $y^{i}$ feature private
constraints (3b), as well as the shared constraints (3c) that both depend on
the decisions of the other lower-level agents. The cost function of follower
$\nu\in[M_{i}]$ is a real-valued function
$f^{i}_{\nu}:\mathbb{R}^{n^{i}}\times\mathbb{R}^{p^{i}}\to\mathbb{R}$. In
addition, $D^{i}_{\nu,\mu}\in\mathbb{R}^{r^{i}_{\nu}\times p^{i}_{\mu}}$,
$A^{i}_{\nu}\in\mathbb{R}^{r^{i}_{\nu}\times n^{i}},D^{i}_{\nu}\coloneqq
D^{i}_{\nu,\nu}$, and $e^{i}_{\nu}\in\mathbb{R}^{r^{i}_{\nu}}$ define the
private constraints of follower $\nu$, while the matrix
$B^{i}\in\mathbb{R}^{d^{i}\times n^{i}}$ measures the impact of the upper-
level decisions on the lower-level shared constraints. Finally,
$E^{i}_{\nu}\in\mathbb{R}^{d^{i}\times p^{i}_{\nu}}$, and
$c^{i}\in\mathbb{R}^{d^{i}}$ define the coupling constraints of the followers.
Let $\Gamma^{i}(x^{i})$ indicate the lower-level game associated with leader
$i$. We denote the feasible set of the $\nu$-th lower-level agent by
$\Omega^{i}_{\nu}(x^{i},\boldsymbol{y}^{i}_{-\nu})$, which amounts to a
closed, polyhedral set. We define the $\nu$-th agent’s best-response (BR)
correspondence as the solution set to the parametric problem:

$\beta^{i}_{\nu}(x^{i},\boldsymbol{y}^{i}_{-\nu})\coloneqq\underset{y^{i}_{\nu}\in\Omega^{i}_{\nu}(x^{i},\boldsymbol{y}^{i}_{-\nu})}{\textrm{argmin}}~{}f^{i}_{\nu}(x^{i},y^{i}_{\nu},\boldsymbol{y}^{i}_{-\nu}).$

###### Definition 2

A tuple
$\bar{\boldsymbol{y}}^{i}=(\bar{y}^{i}_{\nu})_{\nu\in[M_{i}]}\in\mathbb{R}^{p^{i}}$
is a GNE of the game $\Gamma^{i}(x^{i})$ if
$\bar{y}^{i}_{\nu}\in\beta^{i}_{\nu}(x^{i},\bar{\boldsymbol{y}}^{i}_{-\nu})$
for all $\nu\in[M_{i}]$. The set of GNE for $\Gamma^{i}(x^{i})$ is denoted by
$\mathbf{NE}^{i}(x^{i})$. $\square$

In particular, we are interested in the “well-posed case” in which
$\mathbf{NE}^{i}(x^{i})\neq\emptyset$ for all $x^{i}\in\mathcal{X}^{i}$, a
condition guaranteed beforehand via standard assumptions on the data of (3)
[16].

###### Assumption 2

For all $x^{i}\in\mathcal{X}^{i}$, $\mathbf{NE}^{i}(x^{i})\neq\emptyset$.
$\square$

Moreover, later in the paper we will rely on the Karush–Kuhn–Tucker (KKT)
characterization of the set $\mathbf{NE}^{i}(x^{i})$, and therefore we will
require the following assumption:

###### Assumption 3

For all $\nu\in[M_{i}]$, for any given $x^{i}$ and
$\boldsymbol{y}^{i}_{-\nu}$, $y^{i}_{\nu}\mapsto
f^{i}_{\nu}(x^{i},y^{i}_{\nu},\boldsymbol{y}^{i}_{-\nu})$ is continuously
differentiable and convex, and
$\Omega^{i}_{\nu}(x^{i},\boldsymbol{y}^{i}_{-\nu})$ is nonempty. $\square$

In addition, our numerical scheme will focus on the computation of a specific
solution of the followers’ game, known as the _variational equilibrium_ [17].
Available works on computational game theory usually focus on this solution
concept, as it admits an analytically tractable variational characterization
[16] and, additionally, it can be seen as an appealing selection among the set
of equilibrium points [18] as the dual variables for the shared constraints
coincide.

To introduce such a solution concept, let
$\Omega^{i}(x^{i})=\left\\{\boldsymbol{y}^{i}\in\mathbb{R}^{p_{i}}\mid
y^{i}_{\nu}\in\Omega^{i}_{\nu}(x^{i},\boldsymbol{y}^{i}_{-\nu}),\forall\nu\in[M_{i}]\right\\}$
be the collective feasible set of the followers, and the Nikaido–Isoda
function

$\Psi^{i}(x^{i},\boldsymbol{u}^{i},\boldsymbol{y}^{i})\coloneqq\sum_{\nu\in[M_{i}]}\left[f^{i}_{\nu}(x^{i},u^{i}_{\nu},\boldsymbol{y}^{i}_{-\nu})-f^{i}_{\nu}(x^{i},y^{i}_{\nu},\boldsymbol{y}^{i}_{-\nu})\right].$

###### Definition 3

Given an upper-level strategy $x^{i}\in\mathcal{X}^{i}$, inducing a GNEP
$\Gamma^{i}(x^{i})$, an $M_{i}$-tuple $\bar{\boldsymbol{y}}^{i,\ast}$ is a
variational equilibrium if

$\sup_{\boldsymbol{z}^{i}\in\Omega^{i}(x^{i})}\Psi^{i}(x^{i},\boldsymbol{z}^{i},\bar{\boldsymbol{y}}^{i,\ast})=\Psi^{i}(x^{i},\bar{\boldsymbol{y}}^{i,\ast},\bar{\boldsymbol{y}}^{i,\ast})=0.$
$\square$

###  II-C Special instances

The class of lower-level GNEPs we consider is quite general, as illustrated by
the following special instances.

######  Example 1 (Hierarchical Games)

If $D^{i}_{\nu,\mu}$ and $B^{i}$ as well as all the $E^{i}_{\mu}$’s are all
zero matrices and $c^{i}=0$, then each follower $\nu$ only faces the private
coupling constraints $D^{i}_{\nu}y^{i}_{\nu}\geq
e^{i}_{\nu}-A^{i}_{\nu}x^{i}$. The lower-level problem attached to leader $i$
then becomes a standard Nash equilibrium problem. Accordingly, the restriction
$\boldsymbol{y}^{i}\in\mathbf{NE}^{i}(x^{i})$ could then be reformulated as
the hierarchical game problem with the following data: Define the pseudo-
gradient
$V^{i}(x^{i},\boldsymbol{y}^{i})=(\nabla_{y^{i}_{\nu}}f^{i}_{\nu}(x^{i},y^{i}_{\nu},\boldsymbol{y}^{i}_{-\nu}))_{\nu\in[M_{i}]}$
as well as the sets
$\mathcal{Y}^{i}_{\nu}(x^{i})\coloneqq\\{y^{i}_{\nu}\in\mathbb{R}^{p^{i}_{\nu}}\mid
D^{i}_{\nu}y^{i}_{\nu}\geq e^{i}_{\nu}-A^{i}_{\nu}x^{i}\\}$, and
$\mathcal{Y}^{i}(x^{i})\coloneqq\prod_{\nu\in[M_{i}]}\mathcal{Y}^{i}_{\nu}(x^{i})$.
Then, our leader-follower game can be compactly reformulated as the
mathematical problem with variational inequality constraints:

$\displaystyle\underset{x^{i},\boldsymbol{y}^{i}}{\textrm{min}}$
$\displaystyle F^{i}(x^{i},\boldsymbol{x}^{-i},\boldsymbol{y}^{i})$ s.t.
$\displaystyle x^{i}\in\mathcal{X}^{i},$
$\displaystyle\langle{V^{i}(x^{i},\boldsymbol{y}^{i}),\tilde{\boldsymbol{y}}^{i}-\boldsymbol{y}^{i}\rangle}\geq
0,\;\forall\tilde{\boldsymbol{y}}^{i}\in\mathcal{Y}^{i}(x^{i}).$

The identification of $\mathbf{NE}^{i}(x^{i})$ with the solution of a
variational inequality is a classic concept for Nash games, under Assumption
3; see, e.g., [16]. This class of games received quite some interest recently;
see, e.g., [3, 4]. $\square$

######  Example 2 (Bilevel structure)

If $M_{i}=1$ for all $i$, then each leader defines parameters for a single
follower, who then solves the optimization problem

$\underset{y^{i}}{\textrm{min}}\;f^{i}_{1}(x^{i},y^{i})\quad\text{s.t.}\quad
B^{i}x^{i}+E^{i}_{1}y^{i}\geq c^{i},\ D^{i}_{1}y^{i}\geq e^{i}.$

This is a special case when $A^{i}_{1}=0$. Under Assumption 3, the first-order
optimality conditions for the single follower lead to the variational
inequality

$\langle{\nabla_{y}f^{i}_{1}(x^{i},\bar{y}^{i}),y^{i}-\bar{y}^{i}\rangle}\geq
0\quad\forall y^{i}\in\mathcal{Y}^{i}(x^{i}),$

where $\mathcal{Y}^{i}(x^{i})$ represents the feasible set of the follower’s
optimization problem. The model we aim to solve is then a multi-agent version
of a bilevel optimization problem, reading explicitly (dropping the
superfluous subscripts) as

$\displaystyle\underset{x^{i},y^{i}}{\textrm{min}}$ $\displaystyle
F^{i}(x^{i},\boldsymbol{x}^{-i},y^{i})$ s.t. $\displaystyle
y^{i}\in\textrm{argmin}\\{f^{i}_{1}(x^{i},\tilde{y}^{i})\mid\tilde{y}^{i}\in\mathcal{Y}^{i}(x^{i})\\}.$

Clearly, if $N=1$, this model corresponds to a standard bilevel optimization
problem [19, 20]. $\square$

##  III An equivalent reformulation

To obtain an equivalent reformulation of the single-leader-multi-follower game
in (2) (parametric in the $i$-th leader’s opponents $\boldsymbol{x}^{-i}$), we
use the characterization of a GNE by starting from the KKT conditions
associated with follower $\nu$. In fact, under Assumption 3, any point
$y^{i}_{\nu}\in\beta^{i}_{\nu}(x^{i},\boldsymbol{y}^{i}_{-\nu})$ satisfies the
following set of necessary optimality conditions

$\displaystyle\nabla_{y^{i}_{\nu}}f^{i}_{\nu}(x^{i},y^{i}_{\nu},\boldsymbol{y}^{i}_{-\nu})-(D^{i}_{\nu})^{\top}\lambda^{i}_{\nu}-(E^{i}_{\nu})^{\top}\delta^{i}_{\nu}=0,$
$\displaystyle 0\leq\lambda^{i}_{\nu}\perp
D^{i}_{\nu}y^{i}_{\nu}-e^{i}+D^{i}x^{i}+\sum_{\mu\in[M_{i}]\setminus\\{\nu\\}}D^{i}_{\nu,\mu}y^{i}_{\mu}\geq
0,$ $\displaystyle 0\leq\delta^{i}_{\nu}\perp
B^{i}x^{i}+\sum_{\mu\in[M_{i}]}E^{i}_{\mu}y^{i}_{\mu}-c^{i}\geq 0,$

where the variables
$(\lambda^{i}_{\nu},\delta^{i}_{\nu})\in\mathbb{R}^{r^{i}_{\nu}}\times\mathbb{R}^{p^{i}_{\nu}}$
are the Lagrange multipliers of agent $\nu$. Then, in view of [16, Thm. 4.6],
when the tuple
$(\bar{y}^{i}_{\nu},\bar{\lambda}^{i}_{\nu},\bar{\delta}^{i}_{\nu})$ satisfies
the KKT conditions for every $\nu\in[M_{i}]$, we have that
$\bar{\boldsymbol{y}}^{i}\in\mathbf{NE}^{i}(x^{i})$. Specializing this
characterization to variational equilibria, we only have to replace the agent-
specific Lagrange multipliers $\delta^{i}_{\nu}$ with a single copy
$\delta^{i}$ of these multipliers, which solely affects the last
complementarity condition in the above system.

By replacing the GNEP in the lower-level with the concatenation of all KKT
conditions characterizing the followers’ equilibrium, the single-level
reformulation of the $i$-th leader’s problem reads as follows:

$\displaystyle\underset{x^{i},\boldsymbol{y}^{i},\lambda^{i},\delta^{i}}{\textrm{min}}\quad
F^{i}(x^{i},\boldsymbol{x}^{-i},\boldsymbol{y}^{i})$ (4a)
$\displaystyle~{}~{}~{}~{}\textrm{s.t.}\quad G^{i}(x^{i})\geq 0,$ (4b)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\nabla_{y^{i}_{\nu}}f^{i}_{\nu}(y^{i}_{\nu},x^{i},\boldsymbol{y}^{i}_{-\nu})-(D^{i}_{\nu})^{\top}\lambda^{i}_{\nu}-(E^{i}_{\nu})^{\top}\delta^{i}=0,$
$\displaystyle\hskip 142.26378pt\text{ for all }\nu\in[M_{i}],$ (4c)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}D^{i}_{\nu}y^{i}_{\nu}-e^{i}_{\nu}+A^{i}_{\nu}x^{i}+\sum_{\mu\in[M_{i}]\setminus\\{\nu\\}}D^{i}_{\nu,\mu}y^{i}_{\mu}\geq
0,$ $\displaystyle\hskip 142.26378pt\text{ for all }\nu\in[M_{i}],$ (4d)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}B^{i}x^{i}+\sum_{\mu\in[M_{i}]}E^{i}_{\mu}y^{i}_{\mu}-c^{i}\geq
0,$ (4e) $\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\delta^{i}\geq
0,\lambda^{i}_{\nu}\geq 0,\text{ for all }\nu\in[M_{i}],$ (4f)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\lambda^{i}_{\nu}\perp\left(D^{i}_{\nu}y^{i}_{\nu}-e^{i}+A^{i}_{\nu}x^{i}+\sum_{\mu\in[M_{i}]\setminus\\{\nu\\}}D^{i}_{\nu,\mu}y^{i}_{\mu}\right)$
$\displaystyle\hskip 142.26378pt\text{ for all }\nu\in[M_{i}],$ (4g)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\delta^{i}\perp\left(B^{i}x^{i}-\sum_{\mu\in[M_{i}]}E^{i}_{\mu}y^{i}_{\mu}-c^{i}\right).$
(4h)

As a result, solving the reformulation in (4), parametric in
$\boldsymbol{x}^{-i}$, leads to an optimistic solution of the single-leader-
multi-follower problem, according to Definition 1.

###### Theorem 1

Let $(x^{i,*},\boldsymbol{y}^{i,*})$ be a global optimal solution of the
$i$-th leader’s problem. Then, there exists $\lambda^{i,*}$ and $\delta^{i,*}$
so that $(x^{i,*},\boldsymbol{y}^{i,*},\lambda^{i,*},\delta^{i,*})$ is a
global optimal solution of the single-level reformulation (4). Conversely, if
$(x^{i,*},\boldsymbol{y}^{i,*},\lambda^{i,*},\delta^{i,*})$ solves the single-
level problem (4) globally, then $(x^{i,*},\boldsymbol{y}^{i,*})$ is a global
optimal solution of the single-leader-multi-follower game (2).

###### Proof:

See [8, Thm. 3.3.8]. ∎

###### Remark 1

We discuss here two possible generalizations of the setting considered in this
paper:

  1. 1.

_Extension to nonlinear constraints_ : Our framework can include more generic
convex feasible sets (rather than polyhedral ones) if an appropriate
constraint qualification is satisfied. In view of [21, 22], however, one has
to analyze the respective Lagrange multipliers to establish the relations as
stated in Theorem 1.

  2. 2.

_Multilinear terms for constraints and costs_ : The constraints of the lower-
level problems keep their linear nature even if one allows for multilinear
terms. The associated single-level reformulation (4), however, would inherit
these nonlinearities and the resulting nonconvex terms. Analogous
considerations apply to the lower-level cost functions, where one looses one
degree of the multilinear polynomial by taking the gradient in the KKT
conditions. $\square$

Next, we replace the complementarity constraints in (4d)–(4h) using binary
variables and a standard big-$M$ reformulation. This yields the following
mixed-integer (MI) program:

$\displaystyle\underset{x^{i},\boldsymbol{y}^{i},\lambda^{i},\delta^{i},s^{i},t^{i}}{\textrm{min}}$
$\displaystyle F^{i}(x^{i},\boldsymbol{x}^{-i},\boldsymbol{y}^{i})$ (5a) s.t.
$\displaystyle G^{i}(x^{i})\geq 0,$ (5b)
$\displaystyle\nabla_{y^{i}_{\nu}}f^{i}_{\nu}(y^{i}_{\nu},x^{i},\boldsymbol{y}^{i}_{-\nu})-(D^{i}_{\nu})^{\top}\lambda^{i}_{\nu}-(E^{i}_{\nu})^{\top}\delta^{i}_{\nu}=0,$
$\displaystyle\hskip 85.35826pt\text{ for all }\nu\in[M_{i}],$ (5c)
$\displaystyle
D^{i}_{\nu}y^{i}_{\nu}-e^{i}+A^{i}_{\nu}x^{i}+\sum_{\mu\in[M_{i}]\setminus\\{\nu\\};}D^{i}_{\nu,\mu}y^{i}_{\mu}\geq
0,$ $\displaystyle\hskip 85.35826pt\text{ for all }\nu\in[M_{i}],$ (5d)
$\displaystyle
D^{i}_{\nu}y^{i}_{\nu}-e^{i}+A^{i}_{\nu}x^{i}+\sum_{\mu\in[M_{i}]\setminus\\{\nu\\}}D^{i}_{\nu,\mu}y^{i}_{\mu}$
$\displaystyle\hskip
25.6073pt\leq(\boldsymbol{1}-s^{i}_{\nu})\mathcal{M}^{i}_{\nu}\text{ for all
}\nu\in[M_{i}],$ (5e) $\displaystyle
B^{i}x^{i}+\sum_{\mu\in[M_{i}]}E^{i}_{\mu}y^{i}_{\mu}-c^{i}\geq 0,$ (5f)
$\displaystyle
B^{i}x^{i}+\sum_{\mu\in[M_{i}]}E^{i}_{\mu}y^{i}_{\mu}-c^{i}\leq(\boldsymbol{1}-t^{i}_{\nu})\mathcal{N}^{i}_{\nu},$
(5g) $\displaystyle\lambda^{i}_{\nu},\delta^{i}_{\nu}\geq 0,~{}\nu\in[M_{i}],$
(5h) $\displaystyle\lambda^{i}_{\nu}\leq
s^{i}_{\nu}\mathcal{M}^{i}_{\nu},~{}\delta^{i}_{\nu}\leq
t^{i}_{\nu}\mathcal{N}^{i}_{\nu},~{}\nu\in[M_{i}],$ (5i) $\displaystyle
s^{i}_{\nu}\in\\{0,1\\},~{}\nu\in[M_{i}],$ (5j) $\displaystyle
t^{i}_{\nu}\in\\{0,1\\},~{}\nu\in[M_{i}],$ (5k)

where $\mathcal{M}^{i}_{\nu}$ and $\mathcal{N}^{i}_{\nu}$ are vectors with
sufficiently large entries.

With (5) at hand, we can rewrite (2) as a Nash game with MI variables
$z^{i}=(x^{i},\boldsymbol{y}^{i},\lambda^{i},\delta^{i},s^{i},t^{i})\in\mathbb{R}^{n^{i}}\times\mathbb{R}^{p^{i}}\times\mathbb{R}^{m^{i}}\times\mathbb{R}^{p^{i}}\times\mathbb{R}^{r^{i}}\times\mathbb{R}^{M_{i}d^{i}}\times\\{0,1\\}^{M_{i}}\times\\{0,1\\}^{M_{i}}$,
satisfying (5b)–(5k). We emphasize that the vector $z^{i}$ contains the
leader’s decision, but also all control and dual variables of the attached
followers. Hence, the leader solves the problem of the followers by
identifying a KKT point in this optimistic formulation of the problem. After a
suitable manipulation of the variables and constraints involved, problem (5)
reads as:

$\forall i\in[N]:\left\\{\begin{aligned}
&\underset{z^{i}}{\textrm{min}}&&J^{i}(z^{i},\boldsymbol{z}^{-i})\\\
&~{}\textrm{s.t.}&&z^{i}\in\mathcal{Z}^{i},\end{aligned}\right.$ (6)

where

$\mathcal{Z}^{i}\mathrel{{\mathop{:}}{=}}\left\\{z^{i}=(x^{i},\boldsymbol{y}^{i},\lambda^{i},\delta^{i},s^{i},t^{i})\mid
z^{i}\text{ satisfies }\eqref{eq:single-level-reform:ul-constr-
copy}\text{--}\eqref{eq:single-level-reform:compl-2-binary}\right\\}.$

The proposed reformulation allows us to embed the solution of the multi-
leader-multi-follower problem as a MI-NE between the leaders $i\in[N]$ that
solve the collection of problems in (6). We therefore obtain a Nash game
reformulation of the original multi-leader-multi-follower game, featuring MI
restrictions at the leader level.

Next, we will show that for a relevant class of games, we can ensure existence
of a solution to (6), and develop an efficient numerical scheme that solves
our original multi-leader-multi-follower by relying on the Nash game
reformulation.

##  IV A numerically tractable class of mixed-integer games

Although multi-leader-multi-follower games are a natural model for several
applications in engineering systems, to date existence results for equilibria
are restricted to special classes of games [9]. A commonly made assumption is
that for every upper-level decision $x^{i}$, the set of equilibria
$\mathbf{NE}^{i}(x^{i})$ is a singleton. This is quite restrictive, especially
in the presence of a GNEP at the lower level. We do not impose uniqueness of
the lower-level equilibrium but rather exploit the KKT conditions derived in
the previous section together with a special assumption on the agents’ cost
structure. Following [14], we will consider _separable_ hierarchical games
with _potential structure_ over the leaders’ interactions.

###### Assumption 4

The following conditions hold true:

  1. (i)

For all $i\in[N]$, $F^{i}$ is separable, i.e.,
$F^{i}(x^{i},\boldsymbol{x}^{-i},\boldsymbol{y}^{i})=g^{i}(x^{i},\boldsymbol{x}^{-i})+h^{i}(x^{i},\boldsymbol{y}^{i})$;

  2. (ii)

There exists $W:\mathbb{R}^{n}\to\mathbb{R}$ satisfying
$g^{i}(\tilde{x}^{i},\boldsymbol{x}^{-i})-g^{i}(x^{i},\boldsymbol{x}^{-i})=W(\tilde{x}^{i},\boldsymbol{x}^{-i})-W(x^{i},\boldsymbol{x}^{-i})$
for all $i$. $\square$

Consider then the function
$\pi:\mathbb{R}^{n}\times\mathbb{R}^{p}\to\mathbb{R}$, defined as

$\pi(\boldsymbol{x},\boldsymbol{y})=W(\boldsymbol{x})+\sum_{i\in[N]}h^{i}(x^{i},\boldsymbol{y}^{i}),$

as well as its lifted version to the space $\mathcal{Z}$ as
$P(\boldsymbol{z})=\pi(\boldsymbol{x},\boldsymbol{y})$,
$\boldsymbol{z}\in\mathcal{Z}$. The relation in Assumption 4 (ii) allows us to
verify that $P(\cdot)$ actually amounts to an exact potential for the multi-
leader-multi-follower game $\\{(J^{i},\mathcal{Z}^{i})_{i\in[N]}\\}$:

$\displaystyle P(\tilde{z}^{i},\boldsymbol{z}^{-i}$
$\displaystyle)-P(z^{i},\boldsymbol{z}^{-i})$ $\displaystyle=\ $
$\displaystyle
W(\tilde{x}^{i},\boldsymbol{x}^{-i})-W(x^{i},\boldsymbol{x}^{-i})+h^{i}(\tilde{x}^{i},\tilde{\boldsymbol{y}}^{i})-h^{i}(x^{i},\boldsymbol{y}^{i})$
$\displaystyle=\ $ $\displaystyle
g^{i}(\tilde{x}^{i},\boldsymbol{x}^{-i})-g^{i}(x^{i},\boldsymbol{x}^{-i})+h^{i}(\tilde{x}^{i},\tilde{\boldsymbol{y}}^{i})-h^{i}(x^{i},\boldsymbol{y}^{i})$
$\displaystyle=\ $ $\displaystyle
F^{i}(\tilde{x}^{i},\tilde{\boldsymbol{x}}^{-i},\tilde{\boldsymbol{y}}^{i})-F^{i}(x^{i},\boldsymbol{x}^{-i},\boldsymbol{y}^{i})$
$\displaystyle=\ $ $\displaystyle
J^{i}(\tilde{z}^{i},\boldsymbol{z}^{-i})-J^{i}(z^{i},\boldsymbol{z}^{-i}).$

We can therefore approach the LF-NE computation as the solution to the MI
nonlinear optimization problem:

$\underset{\boldsymbol{z}\in\mathcal{Z}}{\textrm{min}}~{}P(\boldsymbol{z}).$
(7)

###### Assumption 5

There exists $\boldsymbol{z}(0)\in\mathcal{Z}$ for which the level set
$\mathcal{L}_{P}(\boldsymbol{z}(0)):=\\{\boldsymbol{z}\mid
P(\boldsymbol{z})\leq P(\boldsymbol{z}(0))\\}$ is compact. $\square$

In view of Assumptions 2–5 and Theorem 1, the master problem (7) has a global
solution and it induces a LF-NE in the spirit of Definition 1. In addition,
note that Assumption 5 is not overly restrictive. Each block of
$\boldsymbol{z}$ is a tuple of $z^{i}$’s consisting of decision variables
$(x^{i},\boldsymbol{y}^{i})$, Lagrange multipliers $(\lambda^{i},\delta^{i})$
and binary variables $(\delta^{i},s^{i},t^{i})$. Since the Lagrange
multipliers are confined to a compact domain in view of our big-$M$
reformulation, Assumption 5 can hence be guaranteed by assuming that $\pi$ has
compact level sets.

Set $k=0$, choose $\boldsymbol{z}(k)\in\mathcal{Z}$, $\tau(k)>0$ and
$\omega\in(0,1)$

While $\boldsymbol{z}(k)$ is not satisfying a stopping criterion do

For all $i\in[N]$ do

Obtain $\hat{\boldsymbol{z}}^{i}(k)$ and set
$z^{i}(k+1)\in\beta^{i}_{\tau(k)}(\hat{\boldsymbol{z}}^{i}(k))$

Update
$\hat{\boldsymbol{z}}^{i+1}(k)=(z^{i}(k+1),\hat{\boldsymbol{z}}^{-i}(k))$

End forall

Set $\boldsymbol{z}(k+1)=(z^{1}(k+1),\ldots,z^{N}(k+1))$

Update:
$\tau(k+1)\\!=\\!\textrm{max}\left\\{\omega\tau(k),\textrm{min}\\{\tau(k),d_{\rho}(\boldsymbol{z}(k\\!+\\!1),\boldsymbol{z}(k))\\}\right\\}$
Set: $k=k+1$

End while

Algorithm 1 Proximal-like method for MI-NEP with exact potential

To compute an equilibrium through an iterative procedure, we adapt the
proximal-type Gauss–Seidel method defined in [11] and reported in Algorithm 1
for completeness. There, we let $k\geq 0$ denote the iteration index and
$\boldsymbol{z}(k)$ the iterate at the beginning of round $k+1$. For leader
$i\in[N]$, the (local) population state reads as:

$\displaystyle\hat{\boldsymbol{z}}^{i}(k)$
$\displaystyle=(z^{1}(k+1),\ldots,z^{i-1}(k+1),z^{i}(k),z^{i+1}(k),\ldots,z^{N}(k)).$

This corresponds to the collective vector of strategies in the $k$-th
iteration communicated to the agent $i$ when this agent has to perform an
update. Throughout this process, note that
$\hat{\boldsymbol{z}}^{1}(k)=\boldsymbol{z}(k)$ and
$\hat{\boldsymbol{z}}^{N+1}(k)=\boldsymbol{z}(k+1)$. A key element is the
inclusion of an integer-compatible regularization function (ICRF) $\rho^{i}$
(see [11] for details) that gives rise to the augmented cost function

$\tilde{J}^{i}_{\tau}(z^{i},w^{i};\boldsymbol{z}^{-i})\mathrel{{\mathop{:}}{=}}J^{i}(z^{i},\boldsymbol{z}^{-i})+\tau\rho^{i}(z^{i}-w^{i})\quad\forall
i\in[N],$

with $\tau\geq 0$ and the corresponding proximal-like BR mapping:

$\beta^{i}_{\tau}(\boldsymbol{z})\mathrel{{\mathop{:}}{=}}\underset{\zeta^{i}\in\mathcal{Z}^{i}}{\textrm{argmin}}\
\tilde{J}^{i}_{\tau}(\zeta^{i},z^{i};\boldsymbol{z}^{-i})\,.$

Thus, each leader $i\in[N]$ computes the new strategy as a point in the MI
proximal BR mapping,
$z^{i}(k+1)\in\beta^{i}_{\tau(k)}(\hat{\boldsymbol{z}}_{i}(k)).$ Successively,
the next internal state $\hat{\boldsymbol{z}}^{i+1}(k)$ is updated and passed
to the ($i+1$)-th agent.

The proposed algorithm leverages the adaptive update of the regularization
parameter $\tau$, originating a monotonically decreasing sequence
$\\{\tau(k)\\}_{k\geq 0}$, i.e., $\tau(k+1)\leq\tau(k)$ for all $k\geq 0$
[23]. The rate of decrease of the overall scheme, instead, depends on the
”cost-to-move” function
$d_{\rho}(\boldsymbol{z}(k+1),\boldsymbol{z}(k))=\textrm{max}_{i\in[N]}\
\rho^{i}(z^{i}(k+1)-z^{i}(k))\geq 0$, which measures the progress the method
is making in the agents’ proximal steps at the $k$-th iteration, and shall
decrease over time to guarantee convergence towards an MI-NE.

######  Theorem 2 ([11, Th. 1])

Let Assumptions 1–5 hold true. Then, any accumulation point of the sequence
$\\{\boldsymbol{z}(k)\\}_{k\geq 0}$ generated by Algorithm 1 is an MI-NE of
the game in (6), coinciding with an LF-NE of (1). $\square$

###### Remark 2

An accumulation point for $\\{\boldsymbol{z}(k)\\}_{k\geq 0}$ generated by
Algorithm 1 exists in view of Assumption 5: the analysis performed in [11]
shows that the sequence $\boldsymbol{z}(k)$ monotonically decreases the
potential function values, i.e., $P(\boldsymbol{z}(k+1))\leq
P(\boldsymbol{z}(k))$ holds for all $k\in\mathbb{N}$. Hence, the trajectories
$\\{\boldsymbol{z}(k)\\}_{k\in\mathbb{N}}$ belong to the level set
$\mathcal{L}_{P}(\boldsymbol{z}(0))$, which we assume to be a compact set.
Existence of converging subsequences is therefore guaranteed by standard
arguments involving the Bolzano-Weierstrass theorem. $\square$

##  V Case study: Competition among
ride-hailing platforms

Taking inspiration from [12, 24], we now investigate how on-demand competing
ride-hailing platforms (taking the role of the leaders) design their pricing
strategies under a regulated pricing scenario. At the same time, a set of
subscribed drivers (i.e., followers of each platform) decide whether to take a
ride or not, according to the wages they receive and the distance from the
pick-up point. We remark here that, given the reformulation proposed in this
paper, the model described next and the equilibrium it provides are meant to
help the leader in estimating the profit and thereby supporting its pricing
decision process.

###  V-A Model description

####  V-A1 Platforms’ game

Given an area of interest $h\in[H]\subset\mathbb{N}$ (e.g., an airport,
downtown, shopping malls, and so on) we denote with $C^{h}>0$ the mass of
potential riders in that area. Then, each firm $i\in[N]$ aims at maximizing
its profit by setting a price $p^{i,h}\geq 0$ for the on-demand ride-hailing
service to attract as many customers as possible in the $h$-th area. The
prices should satisfy a bound of the form $p^{i,h}\leq\bar{p}^{h}$, usually
imposed by consumer associations. The firms must also set a wage
$w^{i,h}\in[\underline{w},\,\bar{w}^{i,h}]$, with
$\underline{w},\bar{w}^{i,h}>0$ for the registered drivers on the $i$-th ride-
hailing platform. The lower bound $\underline{w}$ is typically regulated by
institutions [25, 26] and therefore can be taken uniform across areas.

Similar to [12], we assume that the fraction of customers who choose the
$i$-th platform’s service in the $h$-th area, i.e., the demand for the $i$-th
firm, is characterized as:

$d^{i,h}=\frac{C^{h}K^{i,h}}{\bar{p}\sum_{j\in[N]}K^{j,h}}\left(\bar{p}-\bar{p}^{h}+\frac{\theta^{i}}{N-1}\sum_{j\in[N]\setminus\\{i\\}}p^{j,h}\right),$
(8)

where $K^{i,h}>0$ denotes the fraction of registered drivers on the $i$-th
ride-hailing platform, based on their willingness to work in the $h$-th area
(properly defined in the next section), $\bar{p}>\textrm{max}_{h\in[H]}\
\bar{p}^{h}$ is a maximum service price, and $\theta^{i}\in[0,1]$ models the
substitutability of the service provided by each firm. The parameter
$\theta^{i}$ being close to $0$ means that the service of the $i$-th platform
is almost independent from the others, while being close to $1$ means that it
is fully substitutable.

The cost function of each platform can then be written as

$F^{i}(x^{i},\boldsymbol{x}^{-i},\boldsymbol{y}^{i})=\sum_{h\in[H]}(w^{i,h}K^{i,h}-p^{i,h}d^{i,h})$
(9)

where $x^{i}=(p^{i},w^{i})$ with $p^{i}=(p^{i,h})_{h\in[H]}$ and
$w^{i}=(w^{i,h})_{h\in[H]}$, and the relation between the followers’ decision
variables $\boldsymbol{y}^{i}$ and $K^{i,h}$ is explained in the next section.
The first part of the cost function amounts to the profit of the $i$-th firm
to provide a service to the customers, while the second one considers the
costs for providing a service to the drivers.

####  V-A2 Drivers’ game

Each platform $i\in[N]$ has $M_{i}$ subscribed drivers, which have the
possibility to choose whether to take a ride or not. In fact, driver $j$
measures the willingness to take a certain ride $y^{i}_{\nu,h}$, where
$h\in[H]$ is the area of interest. It follows that the willingness of all the
drivers to work in area $h$ for platform $i$ is given by

$K^{i,h}=\sum_{\nu\in[M_{i}]}y^{i}_{\nu,h}.$

To select a given area, the drivers take into account a certain preference,
according to the function

$R^{\nu,h}(y^{i}_{\nu,h})=B^{\nu,h}y^{i}_{\nu,h}-A^{\nu,h}(y^{i}_{\nu,h})^{2},$
(10)

where $A^{\nu,h}\in\mathbb{R}$ is the willingness to take a ride based on the
available rides in a given distance $s^{\nu,h}$:

$A^{\nu,h}=\frac{C^{h}}{s^{\nu,h}\beta}.$

The function in (10) expresses the willingness of the drivers to take a ride,
namely a driver is “forced” to provide service if it is close to the pickup
point. The drivers then aim at maximizing, for a given area $h\in[H]$, the
objective function

$U^{\nu,h}(y^{i}_{\nu,h})=w^{i,h}y^{i}_{\nu,h}+R^{\nu,h}(y^{i}_{\nu,h})-Q^{h}\sum_{\nu\in[M_{i}]}y^{i}_{\nu,h}$

where $Q^{h}\sum_{\nu\in[M_{i}]}y^{i}_{\nu,h}$ is a congestion-like term
modeling the fact that other drivers might want to provide service in the same
area $h$, scaled by $Q^{h}>0$.

Moreover, the drivers subscribed to platform $i$ collectively aim at
satisfying a minimum number of rides, e.g., imposed by the platform itself,
for a given area $h\in[H]$:

$\sum_{\nu\in[M_{i}]}y^{i}_{\nu,h}\geq\bar{d}^{i,h}.$ (11)

By defining $y^{i}_{\nu}=(y^{i}_{\nu,h})_{h\in[H]}$, the optimization problem
for driver $\nu\in[M_{i}]$ subscribed to platform $i$ then reads

$\displaystyle\underset{(y^{i}_{\nu,h})_{h\in[H]}}{\textrm{max}}$
$\displaystyle
f^{i}_{\nu}(x^{i},y^{i}_{\nu},\boldsymbol{y}^{i}_{-\nu})=\sum_{h\in[H]}U^{\nu,h}(y^{i}_{\nu,h})$
s.t. $\displaystyle\eqref{eq_constr_drivers}\ \forall h\in[H].$

###  V-B Numerical results

TABLE I: Simulation parameters Parameter | Unit | Description | Value
---|---|---|---
$\bar{p}$ | $ | Maximum service price | $32$
$\bar{p}_{h}$ | $ | Area price cap | $\sim\mathcal{U}(16,30)$
$\underline{w}$ | $ | Wage lower bound | $12$
$\bar{w}^{i,h}$ | $ | Wage upper bound | $\sim\mathcal{U}(20,28)$
$\bar{\theta}$ |  | Substitutability parameter | $0.9$
$C_{h}$ |  | Area costumers’ demand | $\sim\mathcal{U}(50,100)$
$B^{\nu,h}$ |  | Linear coefficient ($R^{\nu,h}$) | $\sim\mathcal{U}(6,15)$
$s^{\nu,h}$ | [m] | Driver-area distance | $\sim\mathcal{U}(50,5000)$
$\beta$ |  | Term in $A^{\nu,h}$ | $\sim\mathcal{U}(0.1,0.001)$
$Q^{h}$ |  | Congestion coefficient | $\sim\mathcal{U}(70,150)$
$\bar{d}^{i,h}$ |  | Minimum number of rides | $20\%C_{h}$
$\mathcal{M}^{i}_{\nu}$ |  | Upper bound (dual variables) | $200$
$\omega$ |  | Scaling factor of Alg. 1 | $0.1$

All simulations are run in MATLAB using Gurobi [27] as a solver on a laptop
with an Apple M2 chip featuring an 8-core CPU and 16 GB RAM. In our tests we
have considered a problem instance with $N=5$ ride-hailing platforms, with
$M_{i}=10$ subscribed drivers, which strive to maximize their profit by
operating in $H=3$ different areas. The remaining numerical values are
reported in Table I. Note that, to make the game an exact potential one, we
set $\theta^{i}=\bar{\theta}$ for all $i\in\\{1,\ldots,5\\}$. The potential
function can be obtained by summing (9) over all platforms, and considering
just one symmetric term at a time [24, §VI-A].

Figure 1: Comparison between the behavior of the sequences generated by
Algorithm 1 (solid blue line), and a naïve algorithm (solid red line),
respectively, averaged over $50$ random numerical instances (shaded areas).

In Fig. 1 we compare the sequences generated by Algorithm 1, and a two-layer
procedure alternating the computation of a Nash equilibrium in the leaders’
game, with fixed followers’ strategies, which is then fed into the
(generalized) Nash game involving the followers. In this naïve algorithm we
have adopted a standard extra-gradient type method [28] for computing both the
equilibria iteratively. Specifically, we have generated $50$ random instances
of the considered game, and tested the behavior of the two procedures. From
Fig. 1 one can appreciate that Algorithm 1 is actually able to return an
equilibrium solution to the multi-leader-multi-follower game, in some cases
with less than $10$ iterations, where each agent takes $0.0135$ s to compute a
BR strategy (worst-case average over the $50$ numerical instances). Such an
equilibrium $\boldsymbol{z}^{\ast}$ has been computed by using $\|\cdot\|_{2}$
as ICRF, and its validity has been verified ex-post by performing an ordered
round of BRs. On the other hand, the naïve algorithm exhibits oscillations
that increase in amplitude with $k$, thereby keeping $\boldsymbol{z}(k)$ far
from an LF-NE.

TABLE II: Numerical results | Firm $1$ | Firm $2$ | Firm $3$ | Firm $4$ | Firm $5$
---|---|---|---|---|---
$F^{i,\ast}$ ($) | $307.5$ | $241.2$ | $245.2$ | $207.4$ | $286.1$
Demand
satisf. (%) | $\begin{bmatrix}27.3\\\ 38.0\\\ 29.4\\\ \end{bmatrix}$ | $\begin{bmatrix}26.5\\\ 38.5\\\ 27.5\\\ \end{bmatrix}$ | $\begin{bmatrix}26.3\\\ 38.5\\\ 29.4\\\ \end{bmatrix}$ | $\begin{bmatrix}28.2\\\ 33.6\\\ 27.5\\\ \end{bmatrix}$ | $\begin{bmatrix}27.4\\\ 34.7\\\ 27.4\\\ \end{bmatrix}$

The first row in Table II, instead, reports the average profit (over the
considered $50$ random instances) obtained by the five companies at the
computed LF-NE, where
$F^{i,\ast}=-F^{i}(\bar{x}^{i,\ast},\bar{\boldsymbol{x}}^{-i,\ast},\bar{\boldsymbol{y}}^{i,\ast})$.
This is made possible since the leaders set competitive wages so that each set
of drivers (i.e., followers) collectively allows to satisfy a certain amount
of costumers’ demand per area of interest, as reported in the second row of
Table II. Specifically, each quantity there averages the value
$100\times\sum_{\nu\in[M_{i}]}y^{i}_{\nu,h}/C_{h}$ over the $50$ numerical
instances, thereby showing that the firms are actually able to meet more than
the $20\%$ of $C_{h}$ in each area, as imposed through (11); see the values
for $\bar{d}^{i,h}$ in Table I.

##  VI Conclusion

We have considered a specific class of hierarchical GNEPs where a number of
leaders play a game while being subject to equilibrium constraints arising
from the decision process of their followers. For this multi-leader-multi-
follower model, we have proposed an equivalent reformulation that allows the
leaders to solve the problem by estimating the behavior of their followers,
and exploiting the relation between the GNEP and the KKT conditions. To
address the mixed-integer nature of the obtained reformulation and to find a
solution, we restrict the analysis to the class of potential games, for which
iterative schemes are available. We have verified the convergence of our
scheme on a numerical instance considering a competitive ride-hail market
problem.

## References

  * [1] H. D. Sherali, “A multiple leader Stackelberg model and analysis,” _Operations Research_ , vol. 32, no. 2, pp. 390–404, 1984.
  * [2] M. Hintermüller, B. S. Mordukhovich, and T. M. Surowiec, “Several approaches for the derivation of stationarity conditions for elliptic MPECs with upper-level control constraints,” _Mathematical Programming_ , vol. 146, no. 1-2, pp. 555–582, 2014.
  * [3] S. Cui and U. V. Shanbhag, “On the computation of equilibria in monotone and potential stochastic hierarchical games,” _Mathematical Programming_ , vol. 198, no. 2, pp. 1227–1285, 2023.
  * [4] S. Cui, U. V. Shanbhag, and M. Staudigl, “A regularized variance-reduced modified extragradient method for stochastic hierarchical games,” _arXiv preprint arXiv:2302.06497_ , 2023.
  * [5] Z.-Q. Luo, J.-S. Pang, and D. Ralph, _Mathematical programs with equilibrium constraints_. Cambridge University Press, 1996.
  * [6] M. Hintermüller and I. Kopacka, “A smooth penalty approach and a nonlinear multigrid algorithm for elliptic MPECs,” _Computational Optimization and Applications_ , vol. 50, pp. 111–145, 2011.
  * [7] J. C. De los Reyes, “Bilevel imaging learning problems as mathematical programs with complementarity constraints: Reformulation and theory,” _SIAM Journal on Imaging Sciences_ , vol. 16, no. 3, pp. 1655–1686, 2023\.
  * [8] D. Aussel and A. Svensson, “A short state of the art on multi-leader-follower games,” _Bilevel optimization: Advances and next challenges_ , pp. 53–76, 2020.
  * [9] J.-S. Pang and M. Fukushima, “Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games,” _Computational Management Science_ , vol. 2, no. 1, pp. 21–56, 2005.
  * [10] L. E. Blume and W. R. Zame, “The algebraic geometry of perfect and sequential equilibrium,” _Econometrica_ , vol. 62, no. 4, pp. 783–794, 1994.
  * [11] F. Fabiani, B. Franci, S. Sagratella, M. Schmidt, and M. Staudigl, “Proximal-like algorithms for equilibrium seeking in mixed-integer Nash equilibrium problems,” in _2022 IEEE 61st Conference on Decision and Control (CDC)_ , 2022, pp. 4137–4142.
  * [12] F. Fabiani and B. Franci, “A stochastic generalized Nash equilibrium model for platforms competition in the ride-hail market,” in _2022 IEEE 61st Conference on Decision and Control (CDC)_. IEEE, 2022, pp. 4455–4460.
  * [13] D. Aussel, C. Egea, and M. Schmidt, “A tutorial on solving single-leader-multi-follower problems using SOS1 reformulations,” Tech. Rep., 2023. [Online]. Available: https://optimization-online.org/?p=23744
  * [14] A. A. Kulkarni and U. V. Shanbhag, “An existence result for hierarchical Stackelberg vs Stackelberg games,” _IEEE Transactions on Automatic Control_ , vol. 60, no. 12, pp. 3379–3384, 2015.
  * [15] F. Fabiani, M. A. Tajeddini, H. Kebriaei, and S. Grammatico, “Local Stackelberg equilibrium seeking in generalized aggregative games,” _IEEE Transactions on Automatic Control_ , vol. 67, no. 2, pp. 965–970, 2021\.
  * [16] F. Facchinei and C. Kanzow, “Generalized Nash equilibrium problems,” _Annals of Operations Research_ , vol. 175, no. 1, pp. 177–211, 2010.
  * [17] J. B. Rosen, “Existence and uniqueness of equilibrium points for concave n-person games,” _Econometrica_ , vol. 33, no. 3, pp. 520–534, 1965.
  * [18] A. A. Kulkarni and U. V. Shanbhag, “On the variational equilibrium as a refinement of the generalized Nash equilibrium,” _Automatica_ , vol. 48, no. 1, pp. 45–55, 2012.
  * [19] S. Dempe, V. Kalashnikov, G. A. Pérez-Valdés, and N. Kalashnykova, _Bilevel Programming Problems_. Springer, 2015.
  * [20] S. Dempe and A. Zemkoho, Eds., _Bilevel Optimization: Advances and Next Challenges_. Springer International Publishing, 2020.
  * [21] D. Aussel and A. Svensson, “Towards tractable constraint qualifications for parametric optimisation problems and applications to generalised Nash games,” _Journal of Optimization Theory and Applications_ , vol. 182, pp. 404–416, 2019.
  * [22] S. Dempe and J. Dutta, “Is bilevel programming a special case of a mathematical program with complementarity constraints?” _Mathematical Programming_ , vol. 131, no. 1-2, pp. 37–48, 2012.
  * [23] F. Facchinei, V. Piccialli, and M. Sciandrone, “Decomposition algorithms for generalized potential games,” _Computational Optimization and Applications_ , vol. 50, no. 2, pp. 237–262, 2011.
  * [24] F. Fabiani, A. Simonetto, and P. J. Goulart, “Personalized incentives as feedback design in generalized Nash equilibrium problems,” _IEEE Transactions on Automatic Control_ , vol. 68, no. 12, pp. 7724–7739, 2023.
  * [25] R. Beer, C. Brakewood, S. Rahman, and J. Viscardi, “Qualitative analysis of ride-hailing regulations in major American cities,” _Transportation Research Record_ , vol. 2650, no. 1, pp. 84–91, 2017.
  * [26] Y. Zhong, T. Yang, B. Cao, and T. Cheng, “On-demand ride-hailing platforms in competition with the taxi industry: Pricing strategies and government supervision,” _International Journal of Production Economics_ , vol. 243, p. 108301, 2022.
  * [27] Gurobi Optimization, LLC, “Gurobi Optimizer Reference Manual,” 2023. [Online]. Available: https://www.gurobi.com
  * [28] M. V. Solodov and P. Tseng, “Modified projection-type methods for monotone variational inequalities,” _SIAM Journal on Control and Optimization_ , vol. 34, no. 5, pp. 1814–1830, 1996.


# A Compact TPC for the sPHENIX Experiment

Henry T. Klest on behalf of the sPHENIX Collaboration  Department of Physics
and Astronomy, Stony Brook University, Stony Brook, New York 11794, USA
<EMAIL_ADDRESS>
###### Abstract

The sPHENIX detector to be installed at RHIC in 2022 is designed to precisely
measure jets, jet correlations, and dilepton pairs in heavy-ion collisions.
With these measurements in mind, sPHENIX will employ a compact TPC covering
20cm $<r<$ 78 cm and $|\eta|<$ 1.1 as the central tracker. Utilizing an
optimized Ne-CF4 gas mixture, zigzag readout pads, a 1.4 T solenoid, and a
modified SAMPA chip for streaming readout, the TPC will provide a position
resolution sufficient for measuring target observables in a high event rate
environment. The design of the TPC will be discussed, as well as test beam
data and potential applicability to the EIC.

##  1 Introduction

sPHENIX [1] is a state-of-the-art detector currently under construction at the
Relativistic Heavy-Ion Collider (RHIC) at Brookhaven National Laboratory.
sPHENIX is designed to make measurements of jet substructure, fragmentation
functions, heavy flavor, and individual $\Upsilon$(nS) states in proton and
heavy ion collisions to advance understanding of the quark-gluon plasma [2].

Employing a MAPS-based silicon vertex detector (MVTX), an intermediate silicon
tracker (INTT), and a compact TPC [3] as the tracking system, along with
precision electromagnetic and hadronic calorimetry [4], sPHENIX will round out
the RHIC physics program with high statistics jet and heavy flavor
measurements [5] [6].

Key to the success of sPHENIX is a combined tracking momentum resolution good
enough to resolve the $\Upsilon$ states from each other in the di-electron
decay channel in both $p+p$ and $Au+Au$ collisions at $\sqrt{s_{NN}}$ $=$
$200$ $GeV/c$. Along with jet substructure measurements, this sets the
requirement for the sPHENIX tracking system to have a momentum resolution of
$\frac{\Delta P}{P}$ $\approx$ $.02\cdot P$ for charged particles with momenta
around 5 $GeV/c$.

In addition to the requirements on detector resolution, the sPHENIX experiment
is required to take large amounts of data at a $Au+Au$ event rate of 15 kHz or
greater to maximize the statistics for rare probes. This rate requirement
demands that the TPC operate in an ungated mode with a fast drift velocity gas
to reduce occupancy.

##  2 sPHENIX TPC Design Considerations

###  2.1 Design Overview

The sPHENIX TPC covers 20 cm $<r<$ 78 cm but is only instrumented for physics
starting at 30 cm. The maximum drift length for an electron is 1.05 m in z.
The readout on each endcap is segmented 36 times. The field cage and gas
volume of the TPC are merged into one structure. The field cage is constructed
of five long, flexible PCBs with very fine stripes designed to step the
voltage down smoothly from the central cathode to the top of the gas electron
multipliers (GEMs) and produce a highly uniform electric field in the
z-direction. The central cathode itself is constructed of rigid ENIG-coated
FR4 segments supported by a central honeycomb structure. The cathode will be
held at 45 kV and will have aluminum stripes evaporated on it for laser
calibration.

Figure 1: sPHENIX detector and subsystems.

Figure 2: Sketch of the sPHENIX TPC.

###  2.2 Size

The primary drivers of the size of the sPHENIX TPC are the requirements that
sufficient room be allotted for calorimetry inside the magnet bore, and that
the TPC sit in the uniform region of the magnetic field.

Although the radial component of the magnetic field in the TPC volume is small
compared to the overall magnitude of the field, this small component causes
centimeter-scale distortions to electron positions that need to be corrected
for. An ionizing laser system that provides straight lines of ionization
throughout the TPC will allow for straightforward calibration of this effect.

Additionally, the electromagnetic calorimeter requires radial extension to
fully contain high $p_{T}$ EM showers. The measurement and identification of
electrons and photons at high $p_{T}$ enables the study of $\Upsilon$ decays
and $\gamma$ \+ jet events, both of which are cornerstones of the sPHENIX
physics program. sPHENIX is also the first midrapidity detector at RHIC to
utilize a full 2$\pi$ hadronic calorimeter in the barrel. One portion of this
hadronic calorimeter, the so-called inner HCal, also sits inside the magnet.
This section improves the hadronic jet resolution of sPHENIX and better
enables the use of particle flow techniques due to the reduced ambiguity in
matching tracks to hadronic calorimeter clusters.

###  2.3 Momentum Resolution

The measurement of momentum in a TPC boils down to the ability to pinpoint the
initial location of primary ionization electrons in the gas. There are many
factors which affect a TPC’s ability to do this, but some of the most notable
are the diffusion in the gas, the intrinsic spatial resolution of the readout,
the magnetic field applied, and the distortion of tracks due to space charge.
The spatial resolution of a TPC can thus be parameterized as in Eq. 1.

$\sigma_{x}^{2}=\frac{D_{T}^{2}L}{N_{eff}}+\sigma_{pad}^{2}+\sigma_{Space~{}Charge}^{2}$
(1)

####  2.3.1 Diffusion

To reduce the first term of Eq. 1, the operating gas must have low diffusion.
Since the sPHENIX physics program does not require particle identification by
dE/dx in the TPC, the gas can be chosen to optimize position resolution.
sPHENIX utilizes the 1.4 T solenoid that was designed for and operated
successfully in the BaBar Experiment at SLAC. In comparison to STAR and ALICE,
the magnetic field of this solenoid is quite strong. This is necessary for
sPHENIX to precisely study high $p_{T}$ probes of the QGP, both due to the
increased bending of tracks and the favorable effect this field has on the TPC
spatial resolution.

A strong, uniform magnetic field is especially suited for a TPC because the
magnetic field decreases the diffusion of the electrons in the gas. The
mechanism behind this is quite simple. As the electrons diffuse, they pick up
velocity components in the directions transverse to the magnetic field. This
causes them to spiral and remain pinned to the direction of the parallel
$\vec{E}$ and $\vec{B}$ fields, effectively negating the transverse kicks
given to the electrons as they traverse the gas.

The diffusion will necessarily worsen the resolution for longer electron drift
lengths. Thus the spatial resolution for electrons ionized near the readout
will be better than those ionized near the central cathode. One of the
advantages of the small size of the sPHENIX TPC is that the maximum drift
length is only 1.05 m, to be compared with 2.45 m in ALICE [7] and 2 m in STAR
[8].

The sPHENIX TPC employs a gas mixture of 50$\%$ neon with 50$\%$ CF4 111At the
time of writing of these proceedings, the gas mixture was Ne:CF4 50:50. Neon
has recently become difficult to acquire, and for that reason the gas mixture
was changed to Argon:CF4 in a 60:40 mixture. The properties are almost
identical to those in Fig. 3, but the ion mobility is worsened. to provide low
diffusion and high drift velocity, as can be seen in Fig. 3. The longitudinal
diffusion and drift velocity are independent of the magnetic field to first
order.

Figure 3: Ne:CF4 50:50 gas properties. The vertical axis is a measure of
diffusion or drift velocity. To minimize transverse diffusion, 400 V/cm is
chosen as the operating point.

The drift velocity of the sPHENIX configuration is $\sim$ 80 $\mathrm{\mu
m/ns}$ compared to $\sim$ 55 $\mathrm{\mu m/ns}$ for the P10 gas of the STAR
TPC and $\sim$ 25 $\mathrm{\mu m/ns}$ for the Ne:CO2:N2 90:10:5 gas mixture of
the ALICE TPC upgrade. The high drift velocity necessitates fast electronics
to have acceptable position resolution in z and low occupancy. Therefore,
sPHENIX is using the 80 ns peaking time option of the SAMPA ASIC designed for
the ALICE upgrade [9]. The sPHENIX TPC will additionally be operated in
streaming readout mode.

####  2.3.2 Pad Resolution

The second term in Eq. 1 comes from the intrinsic pad resolution. It has been
shown elsewhere [10] that pads designed to optimally share charge can have
better intrinsic position resolution than similarly sized rectangular pads.
This allows for macroscopically large pads to have excellent resolution with
relatively small channel counts. For this reason, the sPHENIX TPC has zig-zag
patterned readout pads, shown in Fig. 5, which are designed to have charge
sharing between at least two pads for all incoming charge clouds from the
GEMs.

The position resolution of the sPHENIX TPC prototype was studied extensively
with the 120 GeV/c proton beam at the Fermilab Test Beam Facility. The
prototype is a one-sided, 40 cm drift length TPC with one full readout module
installed. Due to the bunched structure of the beam and the spacing between
spills, space charge contribution to the resolution was negligible. The pad
and diffusion resolution terms could be extrapolated to the case where a
magnetic field was present and the TPC was full length. The end result of this
study showed a position resolution of 90 $\mu$m for electrons deposited just
above the readout and 130 $\mu$m for electrons drifting the full 105 cm TPC
drift length.

Figure 4: sPHENIX readout plane with closeup of zig-zag pads.

Figure 5: sPHENIX Quadruple GEM layout.

####  2.3.3 Space Charge

The ability of the TPC to precisely measure momentum also depends on
minimization of track distortions due to electric and magnetic field non-
uniformities. All TPCs have time-independent track distortions due to
realistic field effects such as field cage granularity, radial $\vec{B}$ field
components, etc. These distortions are typically large and remain throughout
the life of an experiment, however they can typically be easily calibrated
away.

A more difficult to calibrate effect is the time-dependent electric field
produced by the buildup of space charge. This effect is dominated by positive
ions from the gain stage that drift slowly throughout the volume of the TPC
until they reach the TPC field cage or cathode and neutralize. The space
charge density and track distortion near the inner field cage is very large,
which informed the decision to begin physics instrumentation 10 cm beyond the
inner radius of the TPC. In lieu of normal readout, this region has large pads
designed to monitor the amount of incoming charge, providing additional
information about the amount of ions and their locations in the TPC volume at
a given time. The magnitude of the space charge distortions can be drastically
reduced by decreasing the fraction of ions that escape from the GEMs without
neutralizing. To reduce this ion back-flow (IBF) fraction below 1$\%$, the
sPHENIX TPC uses four GEMs in an orientation similar to the ALICE upgrade
[11], as shown in Fig. 6. The operating voltages of the GEMs were determined
via specialized bench experiments that could measure the amount of IBF and
were tested thoroughly in the sPHENIX prototype TPC in test beam.

In addition to the ionizing laser mentioned earlier, a diffuse laser
calibration system shining on aluminum stripes evaporated onto the TPC central
cathode will allow for real-time measurement of space charge-induced
distortions as the experiment runs with beam. Aluminum was chosen because its
work function is lower than that of the gold cathode, allowing photoelectrons
to be liberated from the stripes but not the central cathode itself. These
liberated electrons will traverse the entire drift of the TPC, and accumulate
information about the distribution of space charge. By comparing the known
pattern of the aluminum stripes to the detected pattern at the readout plane,
one can measure the integrated distortions that electrons receive as they
traverse the TPC. Care has been taken to optimize the amount of diffusion and
the power output of the laser such that a uniform illumination can be
achieved.

##  3 Re-use at an Electron-Ion Collider Experiment

Many of the components of sPHENIX, including the aforementioned calorimeters,
can be repurposed for studying $e+p$ and $e+A$ collisions at the future
Electron-Ion Collider (EIC) to be housed at the current RHIC facility. The
event rate for $e+p$ collisions at the EIC will be similar to $Au+Au$
collisions in sPHENIX ($\sim$ 15 kHz), but the track multiplicity will be much
lower. The average track multiplicity at the EIC will be around 15 tracks per
event, compared to 400 tracks per event in $Au+Au$ events at RHIC. This means
that the occupancy of the TPC will be much lower, and perhaps an optimization
could be done to allow the TPC to identify hadron species via dE/dx while also
improving the position resolution. Space charge will be less of an issue, so
the region from 20-30 cm in r can be instrumented for physics.

Figure 6: Example of a possible EIC detector configuration.

Another option is to modify the TPC by removing one of the endcaps and moving
the cathode to the end in the electron-going direction. The impetus for this
modification is that the readout of the TPC requires mechanical support and
cooling, which contribute to the material budget. Since the measurement of the
direction, momentum, and species of the scattered electron is of utmost
importance at the EIC, it is reasonable to attempt to reduce the material in
the electron-going direction. While this will increase the average drift
length and worsen the TPC spatial resolution at large drift lengths due to
diffusion, the reduced material will generally improve the reconstruction and
identification of the scattered electron.

##  4 Summary

The compact sPHENIX TPC will be installed into sPHENIX in July 2022. The
various factors affecting the TPC momentum resolution and rate capability have
been discussed, along with the solutions to be employed. All studies
performed, including test beams and bench experiments, indicate that the TPC
will be able to achieve the resolution required by the sPHENIX physics
program.

## References

## References

  * [1] Adare A et al. (PHENIX) 2014 An Upgrade Proposal from the PHENIX Collaboration (Preprint 1501.06197)
  * [2] Reed R 2017 Journal of Physics: Conference Series 779 012019 URL https://doi.org/10.1088/1742-6596/779/1/012019
  * [3] Klest H 2020 Journal of Physics: Conference Series 1498 012025 URL https://doi.org/10.1088/1742-6596/1498/1/012025
  * [4] Aidala C A, Bailey V, Beckman S, Belmont R, Biggs C, Blackburn J, Boose S, Chiu M, Connors M, Desmond E et al. 2018 IEEE Transactions on Nuclear Science 65 2901–2919 ISSN 1558-1578 URL http://dx.doi.org/10.1109/TNS.2018.2879047
  * [5] Roland G 2019 The sPHENIX experiment at RHIC Proceedings of International Conference on Hard and Electromagnetic Probes of High-Energy Nuclear Collisions — PoS(HardProbes2018) vol 345 p 013
  * [6] Ji Y (sPHENIX) 2021 Nucl. Phys. A 1005 121792
  * [7] Alme J, Andres Y, Appelshäuser H, Bablok S, Bialas N, Bolgen R, Bonnes U, Bramm R, Braun-Munzinger P, Campagnolo R et al. 2010 Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 622 316–367 ISSN 0168-9002 URL http://dx.doi.org/10.1016/j.nima.2010.04.042
  * [8] Anderson M, Berkovitz J, Betts W, Bossingham R, Bieser F, Brown R, Burks M, Calderón de la Barca Sánchez M, Cebra D, Cherney M et al. 2003 Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 499 659–678 ISSN 0168-9002 URL http://dx.doi.org/10.1016/S0168-9002(02)01964-2
  * [9] Adolfsson J et al. 2017 Journal of Instrumentation 12 C04008–C04008 URL https://doi.org/10.1088/1748-0221/12/04/c04008
  * [10] Azmoun B, Garg P, Hemmick T K, Hohlmann M, Kiselev A, Purschke M L, Woody C and Zhang A 2018 IEEE Transactions on Nuclear Science 65 1416–1423 ISSN 1558-1578 URL http://dx.doi.org/10.1109/TNS.2018.2846403
  * [11] Adolfsson J et al. 2021 Journal of Instrumentation 16 P03022 URL https://doi.org/10.1088/1748-0221/16/03/p03022