Proof. The proof is split into several steps.

6.1.0.1 Step 1: Instance Construction

To prove the result, we consider the case where \(n=2\). Then, we consider two different instances where the unknown strategy profiles \((x^0, y^0)\) and \((x^1, y^1)\) are defined as follows: \[\begin{align} & x^0=(0,1), y^0=(1,0) \\ & x^1=(\pi, 1-\pi), y^1=(1,0) \end{align}\] where \(\pi\) is any number in \((0,1)\).

6.1.0.2 Step 2: Haussdorff Distance

Next, we analyze the distances \(H(\mathcal{G}(x^0, y^0), \mathcal{G}(x^1, y^1))\) and \(H(\mathcal{Z}(x^0, y^0), \mathcal{Z}(x^1, y^1))\). In particular, we will provide lower bounds on these quantities.

We start from \(H(\mathcal{G}(x^0, y^0), \mathcal{G}(x^1, y^1))\). First of all, we note that: \[\begin{align} \label{eq:lb-alpha0-gsg-eq1} H(\mathcal{G}(x^0, y^0), \mathcal{G}(x^1, y^1)) \ge \max_{A \in \mathcal{G}^x(x^0, y^0)} \min_{A' \in \mathcal{G}^x(x^1, y^1)} \| A- A' \|_{\infty}. \end{align}\tag{11}\] Next, we analyze this lower bound in our simplified case. For any matrix \(A=\begin{bmatrix}a_{11}&a_{12}\\ a_{21}&a_{22}\end{bmatrix} \in [-1,1]^{2\times2}\), using the definition of \(\mathcal{G}^x(x,y)\), we have that: \[\begin{align} & \text{(i) } A \in \mathcal{G}^x(x^0, y^0) \iff a_{21} \le a_{11} \text{ and } a_{21} \le a_{21} \iff a_{21} \le a_{11}; \\ & \text{(ii) }A \in \mathcal{G}^x(x^1, y^1) \iff \pi a_{11} + (1-\pi)a_{21} \le \min\{a_{11}, a_{21} \} \iff a_{21} \le a_{11} \text{ and } a_{11} \le a_{21} \iff a_{21} = a_{11} . \end{align}\]

We now use this result to further lower bound the r.h.s. of 11 . In particular, we have that: \[\begin{align} \max_{A \in \mathcal{G}^x(x^0, y^0)} \min_{A' \in \mathcal{G}^x(x^1, y^1)} \| A- A' \|_{\infty}& =\max_{a_{11}, a_{21} \in [-1,1]^2: a_{11} \ge a_{21}} \min_{t \in [-1,1]} \max \{ |a_{11} - t|, |a_{21}-t| \} \\ & \ge \min_{t \in [-1,1]} \max \{ |1-t|, |1+t| \} \\ & = 1, \end{align}\] where the first equality is justified by points (i) and (ii) above, together with the fact that for any \(A \in \mathcal{G}(x^0,y^0)\) we can pick \(A' \in \mathcal{G}(x^1, y^1)\) such that \(a_{22} = a'_{22}\) and \(a_{12} = a'_{12}\), and the inequality follows by setting \(a_{11} = 1\) and \(a_{21} = -1\).

Similarly we can analyze \(H(\mathcal{Z}(x^0,y^0), \mathcal{Z}(x^1, y^1))\). In this case, we have: \[\begin{align} & \text{(i) } A \in \mathcal{Z}(x^0, y^0) \iff a_{22} \le a_{21} \le a_{11}; \\ & \text{(ii) } A \in \mathcal{Z}(x^1, y^1) \iff \pi a_{21} + (1-\pi)a_{22} \le \pi a_{11} + (1-\pi)a_{21} \le \min\{a_{11}, a_{21} \}. \end{align}\] Hence, we have that: \[\begin{align} H(\mathcal{Z}(x^0, y^0), \mathcal{Z}(x^1, y^1)) & \ge \max_{A \in \mathcal{Z}(x^0, y^0)} \min_{A' \in \mathcal{Z}(x^1, y^1)} \| A- A' \|_{\infty} \\ & \ge \min_{A' \in \mathcal{Z}(x^1, y^1)} \max \{ |1-a'_{11}|, |-1-a'_{21}| \} (x^0,y^0): a_{11}=1, a_{21}=-1 }\\ & \ge \min_{t \in [-1,1]} \max \{ |1-t|, |1+t| \} (x^1, y^1) \implies a'_{11} = a'_{22}}\\ & = 1. \end{align}\]

Therefore, the following holds: \[\begin{align} & H(\mathcal{G}(x^0, y^0), \mathcal{G}(x^1, y^1)) \ge 1 \tag{12} \\ & H(\mathcal{Z}(x^0, y^0), \mathcal{Z}(x^1, y^1)) \ge 1. \tag{13} \end{align}\]

6.1.0.3 Step 3: Change of measure

We first set some notation. For any \(x,y \in \Delta_n\), we have that \(\mathbb{P}_{x, y} = \prod_{t=1}^{\tau_\delta} p_{x}(X_t) p_y(Y_t)\), where \(p_q(\cdot)\) denotes the density function of \(q \in \Delta_n\). Then, since [eq:lb-alpha0-gsg-eq2,eq:lb-alpha0-gsg-eq2-new] hold (and since \(\epsilon < 1\)), we can apply 17. Thus for any \((\epsilon,\delta)\)-correct algorithm, for both GSGs and ZSGs we obtain \[\begin{align} \delta \ge \frac{1}{4} \exp\left( -\text{KL}(\mathbb{P}_{x^0, y^0}, \mathbb{P}_{x^1, y^1}) \right). \end{align}\] We proceed by analyzing the r.h.s. of this equation. In the case we are considering we have set \(n=2\). Hence, \(x,y\) are Bernoulli distributions, and we obtain that: \[\begin{align} \text{KL}\left(\mathbb{P}_{x^0, y^0}, \mathbb{P}_{x^1, y^1}\right) & = \mathbb{E}_{x^0, y^0}\left[ \sum_{t=1}^{\tau_\delta} \text{KL}(p_{x^0}(X_t), p_{x^1}(X_t)) \right]\\ & = \mathbb{E}_{x^0, y^0}\left[ \tau_\delta \right] \text{KL}(p_{x^0}, p_{x^1}) \\ & = \mathbb{E}_{x^0, y^0}\left[ \tau_\delta \right] \log\left( \frac{1}{1-\pi} \right).\end{align}\] Then, we obtained that: \[\begin{align} \delta \ge \frac{1}{4} \exp\left( -\mathbb{E}_{x^0, y^0}\left[ \tau_\delta \right] \log\left( \frac{1}{1-\pi} \right) \right), \end{align}\] which yields: \[\begin{align} \mathbb{E}_{x^0, y^0}\left[ \tau_\delta \right] \ge \frac{\log\left( \frac{1}{4\delta} \right)}{\log\left( \frac{1}{1-\pi} \right)}, \end{align}\] thus concluding the proof. ◻

Proof of 3. It is sufficient to consider the instances presented in [thm:alpha0-pimin,thm:alpha0-eps,thm:alpha0-n]. The results then follows from applying \(\max\{ a, b, c\} \ge \frac{1}{3} (a+b+c)\). ◻

Proof. The results follow from applying 2 with \(\pi = \pi_{\min}\). ◻

Proof. The proof is split into three steps

6.2.0.2 Step 1: Instance Construction

We consider the setting with \(n=2\). Then, we consider two different instances where the unknown strategy profiles \((x^0, y^0)\) and \((x^1, y^1)\) are defined as follows: \[\begin{align} &x^0=\left(\frac{1}{2}, \frac{1}{2}\right),~y^0=\left(\frac{1}{2}, \frac{1}{2}\right) \\ &x^1=\left(\frac{1}{2}+\gamma, \frac{1}{2}-\gamma\right),~y^1= \left(\frac{1}{2}, \frac{1}{2}\right), \end{align}\] where \(\gamma \in (0,1/2)\) is a real number that will specified later in the proof.

6.2.0.3 Step 2: Haussdorff Distance

Next, we analyze the distances \(H(\mathcal{G}(x^0, y^0), \mathcal{G}(x^1, y^1))\) and \(H(\mathcal{Z}(x^0, y^0), \mathcal{Z}(x^1, y^1))\). In particular, we will provide lower bounds on these quantities.

We start from \(H(\mathcal{G}(x^0, y^0), \mathcal{G}(x^1, y^1))\). We have that: \[\begin{align} H(\mathcal{G}(x^0, y^0), \mathcal{G}(x^1, y^1)) & \ge \max_{B \in \mathcal{G}^y(x^0,y^0)} \min_{B ' \in \mathcal{G}^y(x^1, y^1)} \| B - B'\|_{\infty} \\ & \ge \min_{B ' \in \mathcal{G}^y(x^1, y^1)} \max \{ |1-b'_{11}|, |b'_{12}|, |b'_{21}|, |1-b'_{22} | \}, \end{align}\] where, in the second step, we have set \(B=\begin{bmatrix}1&0\\ 0&1\end{bmatrix} \in \mathcal{G}^y(x^0, y^0)\) and \(B'=\begin{bmatrix}b'_{11}&b'_{12}\\ b'_{21}&b'_{22}\end{bmatrix}\).¹² Now, using the values of \((x^1, y^1)\), we can rewrite the last optimization problem as follows: \[\begin{align} & \min_{B'}\max \{ |1-b'_{11}|, |b'_{12}|, |b'_{21}|, |1-b'_{22} | \} \\ & \text{s.t.\quad} b'_{ij} \in [-1, 1] \quad \forall i,j \in [n] \\ & \phantom{\text{s.t.}\quad} \tfrac12\Bigl((\tfrac12+\gamma)(b'_{11}+b'_{12}) +(\tfrac12-\gamma)(b'_{21}+b'_{22})\Bigr) \le b'_{11}(\tfrac12+\gamma)+b'_{21}(\tfrac12-\gamma),\\ & \phantom{\text{s.t.}\quad}\tfrac12\Bigl((\tfrac12+\gamma)(b'_{11}+b'_{12}) +(\tfrac12-\gamma)(b'_{21}+b'_{22})\Bigr) \le b'_{12}(\tfrac12+\gamma)+b'_{22}(\tfrac12-\gamma). \end{align}\] Introducing an additional variable \(t \mathrel{\vcenter{:}}= \|B-B' \|_{\infty} \ge 0\) and simplifying the constraints, we can rewrite this optimization problem as follows: \[\label{eq:lb-alpha0-gsg-eq1-eps} \begin{alignedat}{2} & \min_{B' \in [-1,1]^{2\times 2},t \ge 0} t \\ & \text{s.t.\quad} |1-b'_{11}|\le t,~~~|b'_{12}| \le t,~~~ |b'_{21}| \le t,~~~ |1-b'_{22}|\le t \\ & \phantom{\text{s.t.}\quad}(b'_{11}-b'_{12})(\tfrac12+\gamma)+(b'_{21}-b'_{22})(\tfrac12-\gamma)=0. \end{alignedat}\tag{14}\] Let \(t(B')\) be the optimal value of Problem 14 for any feasible matrix \(B'\). In the following, we will prove that \(t(B') \ge \gamma\) for any feasible matrix \(B'\). To this end, let us introduce the following vector \(g^\top = [(\tfrac12+\gamma), (-\tfrac12-\gamma), (\tfrac12-\gamma), (-\tfrac12+\gamma) ]\). Then, the last linear constraints in 14 can be rewritten as \(g^\top z(B')=0\), where \(z(B')\) denotes the flattened version of matrix \(B'\), i.e., \(z(B')=(b'_{11}, b'_{12}, b'_{21}, b'_{22})\). Next, let \(z_0 = (1,0,0,1)\). Note that \(g^\top z_0 = 2 \gamma\). Thus, for any feasible \(B'\), \(g^\top (z(B') - z_0) = -2\gamma\). Therefore, \[\begin{align} 2\gamma & = |g^\top (z(B') - z_0)| \\ & \le \| g \|_{1} \| z(B') - z_0 \|_{\infty} lder's inequality}\\ & =\| g \|_1 t(B')} \\ & = 2t(B') \end{align}\] Thus, we obtained that, for any feasible matrix \(B'\), \(t(B') \ge \gamma\). Choosing \(\gamma = 2\epsilon\),¹³ we obtained that \[\begin{align} \label{eq:lb-alpha0-gsg-eq2-eps} H(\mathcal{G}(x^0, y^0), \mathcal{G}(x^1, y^1)) \ge 2\epsilon . \end{align}\tag{15}\]

Next, we analyze \(H(\mathcal{Z}(x^0, y^0), \mathcal{Z}(x^1, y^1))\). We have that: \[\begin{align} H(\mathcal{Z}(x^0, y^0), \mathcal{Z}(x^1, y^1)) &\ge \max_{A \in \mathcal{Z}(x^0,y^0)} \min_{A' \in \mathcal{Z}(x^1,y^1)} \|A-A'\|_\infty \\ &\ge \min_{A' \in \mathcal{Z}(x^1,y^1)} \max\bigl\{|1-a'_{11}|,\;|a'_{12}|,\;|a'_{21}|,\;|1-a'_{22}|\bigr\}, \end{align}\] where, in the second step, we have set \[A=\begin{bmatrix}1&0\\0&1\end{bmatrix}\in \mathcal{Z}(x^0,y^0). \footnote{Indeed, (x^0)^\top A y^0 = \frac{1}{2}, e_j^\top A y^0 = \frac{1}{2} and (x^0)^\top A e_j = \frac{1}{2} for all j \in [n]. Hence, all the constraints of \mathcal{Z}(x^0, y^0) are satisfied.}\] Now, using the values of \((x^1,y^1)\), we can rewrite the last optimization problem as follows: \[\begin{align} & \min_{A'}\max \{ |1-a'_{11}|,\;|a'_{12}|,\;|a'_{21}|,\;|1-a'_{22}| \} \\ & \text{s.t.\quad} a'_{ij} \in [-1, 1] \quad \forall i,j \in \{1,2\} \\ & \phantom{\text{s.t.}\quad}(\tfrac12+\gamma)a'_{11}+(\tfrac12-\gamma)a'_{21} \le \tfrac12\Bigl((\tfrac12+\gamma)(a'_{11}+a'_{12})+(\tfrac12-\gamma)(a'_{21}+a'_{22})\Bigr) \\ & \phantom{\text{s.t.}\quad}(\tfrac12+\gamma)a'_{12}+(\tfrac12-\gamma)a'_{22} \le \tfrac12\Bigl((\tfrac12+\gamma)(a'_{11}+a'_{12})+(\tfrac12-\gamma)(a'_{21}+a'_{22})\Bigr) \\ & \phantom{\text{s.t.}\quad}\tfrac12\Bigl((\tfrac12+\gamma)(a'_{11}+a'_{12})+(\tfrac12-\gamma)(a'_{21}+a'_{22})\Bigr) \le \tfrac12(a'_{11}+a'_{12}) \\ & \phantom{\text{s.t.}\quad}\tfrac12\Bigl((\tfrac12+\gamma)(a'_{11}+a'_{12})+(\tfrac12-\gamma)(a'_{21}+a'_{22})\Bigr) \le \tfrac12(a'_{21}+a'_{22}). \end{align}\]

Introducing the additional variable \(t\mathrel{\vcenter{:}}= \|A-A'\|_\infty\ge 0\) and simplifying the constraints, we can rewrite the above minimization as the following optimization problem: \[\label{eq:lb-alpha0-zsg-eq1-eps} \begin{alignedat}{2} & \min_{A'\in[-1,1]^{2\times 2},~t\ge 0}\quad t\\ & \text{s.t.}\quad |1-a'_{11}|\le t,\quad |a'_{12}|\le t,\quad |a'_{21}|\le t,\quad |1-a'_{22}|\le t,\\ & \phantom{\text{s.t.}\quad} (\tfrac12+\gamma)(a'_{11}-a'_{12})+(\tfrac12-\gamma)(a'_{21}-a'_{22})=0,\\ & \phantom{\text{s.t.}\quad}\tfrac12\Bigl((\tfrac12+\gamma)(a'_{11}+a'_{12})+(\tfrac12-\gamma)(a'_{21}+a'_{22})\Bigr) \le \tfrac12(a'_{11}+a'_{12}) \\ & \phantom{\text{s.t.}\quad}\tfrac12\Bigl((\tfrac12+\gamma)(a'_{11}+a'_{12})+(\tfrac12-\gamma)(a'_{21}+a'_{22})\Bigr) \le \tfrac12(a'_{21}+a'_{22}). \end{alignedat}\tag{16}\]

Now, as we did for General-Sum Games, let \(t(A')\) be the optimal value of Problem 16 for any feasible matrix \(A'\). In the following, we will prove that \(t(A') \ge \gamma\) for any feasible matrix \(A'\). To this end, let us introduce the following vector \(g^\top = [(\tfrac12+\gamma), (-\tfrac12-\gamma), (\tfrac12-\gamma), (-\tfrac12+\gamma) ]\). Then, the second constraint in 16 can be rewritten as \(g^\top z(A')=0\), where \(z(A')\) denotes the flattened version of matrix \(A'\), i.e., \(z(A')=(a'_{11}, a'_{12}, a'_{21}, a'_{22})\). Next, let \(z_0 = (1,0,0,1)\). Note that \(g^\top z_0 = 2 \gamma\). Thus, for any feasible \(A'\), \(g^\top (z(A') - z_0) = -2\gamma\). Therefore, \[\begin{align} 2\gamma & = |g^\top (z(A') - z_0)| \\ & \le \| g \|_{1} \| z(A') - z_0 \|_{\infty} lder's inequality}\\ & =\| g \|_1 t(A')} \\ & = 2t(A'). \end{align}\] Thus, we obtained that, for any feasible matrix \(A'\), \(t(A') \ge \gamma\). Choosing \(\gamma = 2\epsilon\),¹⁴ we obtained that \[\begin{align} \label{eq:lb-alpha0-zsg-eq2-eps} H(\mathcal{Z}(x^0, y^0), \mathcal{Z}(x^1, y^1)) \ge 2\epsilon. \end{align}\tag{17}\]

6.2.0.4 Step 3: Change of measure

For any \(x,y \in \Delta_n\), let \(\mathbb{P}_{x, y} = \prod_{t=1}^{\tau_\delta} p_{x}(X_t) p_y(Y_t)\), where \(p_q(\cdot)\) denotes the density function of \(q \in \Delta_n\). Then, since [eq:lb-alpha0-gsg-eq2-eps,eq:lb-alpha0-zsg-eq2-eps] holds, we can apply 17. Thus, both for GSGs and ZSGs, we have that: \[\begin{align} \delta \ge \frac{1}{4} \exp\left( -\text{KL}(\mathbb{P}_{x^0, y^0}, \mathbb{P}_{x^1, y^1}) \right). \end{align}\] We proceed by analyzing the r.h.s. of this equation. In the case we are considering we have set \(n=2\). Hence, \(x,y\) are Bernoulli distributions, and we obtain that: \[\begin{align} \text{KL}\left(\mathbb{P}_{x^0, y^0}, \mathbb{P}_{x^1, y^1}\right) & = \mathbb{E}_{x^0, y^0}\left[ \sum_{t=1}^{\tau_\delta} \text{KL}(p_{x^0}(X_t), p_{x^1}(X_t) \right]\\ & = \mathbb{E}_{x^0, y^0}\left[ \tau_\delta \right] \text{KL}(p_{x^0}, p_{x^1}) \\ & = \frac{1}{2}\mathbb{E}_{x^0, y^0}\left[ \tau_\delta \right]\log\!\left(\frac{1}{1-16\epsilon^2}\right) \\ & \le \mathbb{E}_{x^0, y^0}\left[ \tau_\delta \right] \frac{8 \epsilon^2}{1-16\epsilon^2} {1-x} for x \le 1} \\ & \le 16 \mathbb{E}_{x^0, y^0}\left[ \tau_\delta \right] \epsilon^2 {32}} \implies (1-16\epsilon^2) \ge \tfrac12} \end{align}\] Hence, we obtained that: \[\begin{align} \delta \ge \frac{1}{4} \exp\left( -16\mathbb{E}_{x^0, y^0}\left[ \tau_\delta \right] \epsilon^2 \right) \end{align}\] Rearranging the terms yields: \[\begin{align} \mathbb{E}_{x^0, y^0}\left[ \tau_\delta \right] \ge \frac{\log\left( \frac{1}{4\delta} \right)}{16 \epsilon^2}, \end{align}\] which concludes the proof. ◻

Proof. As before, the proof is split into three main steps.

6.2.0.5 Step 1: Instance Construction

In the following, taking inspiration from the work of [43], we construct a set of different \(n\)-dimensional instances. We assume that \(n \ge 16\) and that \(n \mod 16 = 0\). These instances are parameterized with an \(n\)-dimensional vector \(v \in \{-1,1 \}^n\) such that \(\sum_{k=1}^n v_k = 0\) and are constructed as follows. We denote by \(\mathcal{V}\) the set of vectors that satisfies these two requirements. Now, let \(\gamma \in (0, \tfrac12)\); we define \((x^v, y^v)\) as follows: \[\begin{align} x^v = (1, 0, \dots 0) \text{ and } y^v = \left( \frac{1+\gamma v_1}{n}, \frac{1+ \gamma v_2}{n}, \dots, \frac{1+\gamma v_n}{n} \right). \end{align}\]

Observe that \(n \ge 2, \gamma \in (0, \tfrac12), \text{and~} v \in \{-1,1 \}^n\). Therefore, by construction, we have that \(y^v\in \Delta_n\).

In the rest of the proof, we restrict our attention to vectors \(v\) belonging to a subset \(\bar{\mathcal{V}}\) of \(\mathcal{V}\). In particular, consider a pair \(v,w \in \bar{\mathcal{V}}\) and let \[\begin{align} D^+_{v,w} = \{ k \in [n]: v_k = 1 \text{ and } w_k = -1\} \quad \quad D^-_{v,w} = \{k \in [n]: v_k=-1 \text{ and }w_k = 1 \}, \end{align}\] where we will drop the explicit dependence on \(v,w\) when clear from context. Then, we require that for any pair \(v,w\in\bar{\mathcal{V}}\) it holds \[\begin{align} |D^+_{v,w}| = |D^-_{v,w}| \ge \frac{n}{64}.\label{eq:lb-alpha0-n-dep-eq1} \end{align}\tag{18}\] It is easy to see that \(|D^+_{v,w}| = |D^-_{v,w}|\) is granted for any pair \(v,w \in \mathcal{V}\). The requirement that, e.g.,\(|D^+_{v,w}| \ge \tfrac{n}{64}\), is instead equivalent to impose that \(\sum_{k=1}^n |v_k - w_k| \ge \tfrac{n}{16}\). Thanks to 22, we know that: \[\begin{align} \label{eq:pack-arg} \exists \bar{\mathcal{V}} \subseteq \mathcal{V} \,\text{ s.t. }\, \forall v,w \in \bar{\mathcal{V}}, \quad \sum_{k=1}^n |v_k - w_k| \ge \frac{n}{16} \text{~and~} |\bar{\mathcal{V}}| > 2^{\frac{n}{5}}. \end{align}\tag{19}\] In the following step, we will consider two generic profiles \((x^v,y^v)\) and \((x^w,y^w)\) such that \(v,w \in \bar{\mathcal{V}}\).

6.2.0.6 Step 2: Haussdorff Distance

We analyze the distances \(H(\mathcal{G}(x^v, y^v), \mathcal{G}(x^w, y^w))\) and \(H(\mathcal{Z}(x^v, y^v), \mathcal{Z}(x^w, y^w))\). In particular, we will provide lower bounds on these quantities.

We start from \(H(\mathcal{G}(x^v, y^v), \mathcal{G}(x^w, y^w))\). We have that: \[\begin{align} H(\mathcal{G}(x^v, y^v), \mathcal{G}(x^w, y^w)) & \ge \max_{A \in \mathcal{G}^x(x^v,y^v)} \min_{A' \in \mathcal{G}^x(x^w, y^w)} \| A - A'\|_{\infty} \\ & \ge \min_{A' \in \mathcal{G}^x(x^w, y^w)} \|A- A' \|_{\infty} , \end{align}\] where we define the matrix \(A \in \mathcal{G}(x^v, y^v)\) as \[\label{eq:lb-alpha0-n-dep-eq2} A_{ij}:= \begin{cases} 0, & i=1, j \in [n]\\[2pt] \tfrac13, & i>1,j\in D^+,\\[2pt] -\tfrac13 \kappa , & i> 1,j\in D^-,\\[2pt] 0, & i>1,j\in[n]\setminus(D^+\cup D^-), \end{cases} \qquad\text{where}\qquad \kappa \mathrel{\vcenter{:}}= \frac{\sum_{j\in D^+} y^v_j}{\sum_{j\in D^-} y^v_j}.\tag{20}\] Before continuing, we prove that \(A\) constructed as in 20 satisfies \(A \in \mathcal{G}(x^v, y^v)\). To this end, we first verify that \(A \in [-1,1]^{n \times n}\). It suffices to check that \(\kappa \le 3\). With some simple manipulations, we have that: \[\begin{align} \kappa = \frac{\sum_{j\in D^+} y^v_j}{\sum_{j\in D^-} y^v_j} = \frac{\frac{|D^+|(1+\gamma)}{n}}{\frac{|D^-|(1-\gamma)}{n}} = \frac{1+\gamma}{1-\gamma} \le 3, \end{align}\] where the second equality is due to [{eq:lb-alpha0-n-dep-eq1}] and the last step is due to \(\gamma \in (0, \tfrac12)\). Next, we verify that \(A\) satisfies the Nash constraints. Since \(x^v = e_1\), those constraints are equivalent to \((e_1 - e_i)^\top A y^v \le 0\) for all \(i \in [n]\). Using the definition of \(A\) and \(y^v\) we have that: \[\begin{align} (e_1 - e_i)^\top A y^v & = \sum_{j=1}^n y_j^v (A_{1j}-A_{ij}) \\ & = -\sum_{j=1}^n y_j^v A_{ij}= 0 for all j \in [n]} \\ & = - \frac{1}{3} \left( \sum_{j \in D^+} y_j^v - \kappa\sum_{j \in D^-} y_j^v \right)\\ & = 0. \end{align}\] Hence, all constraints are tight and \(A \in \mathcal{G}^x(x^v, y^v)\).

We can now continue by lower bounding \(\min_{A' \in \mathcal{G}^x(x^w, y^w)} \|A- A' \|_{\infty}\). In the following, we will prove that: \[\begin{align} \label{eq:lb-alpha0-n-dep-eq3} \min_{A' \in \mathcal{G}^x(x^w, y^w)} \|A- A' \|_{\infty} \ge \frac{2|D^+|\gamma}{3n(1-\gamma)}. \end{align}\tag{21}\]

To this end, consider any matrix \(A' \in \mathcal{G}^x(x^w, y^w)\). Let \(\Delta(A') = A'-A\) so that \(A' = \Delta(A')+A\). Since \(x^w = e_1\), then \(A'\) satisfies \((e_1 - e_i)^\top A' y^w \le 0\) for all \(i \in [n]\). Moreover, for all \(A' \in \mathcal{G}^x(x^w, y^w)\) it holds that: \[\begin{align} (e_1 - e_i)^\top A' y^w & = (e_1 - e_i)^\top (\Delta(A')+A) y^w \\ & = (e_1 - e_i)^\top \Delta(A') y^w + (e_1 - e_i)^\top A y^w \\ & = (e_1 - e_i)^\top \Delta(A') y^w - \sum_{j=1}^n y^w_jA_{ij}= 0 for all j \in [n]} \\ & = (e_1 - e_i)^\top \Delta(A') y^w - \frac{1}{3} \left( \frac{|D^+|(1-\gamma)}{n} - \kappa \frac{|D^-|(1+\gamma)}{n} \right)\\ & = (e_1 - e_i)^\top \Delta(A') y^w - \frac{1}{3} \left( \frac{|D^+|(1-\gamma)}{n} - \frac{|D^+|(1+\gamma)^2}{n(1-\gamma)} \right)\\ & = (e_1 - e_i)^\top \Delta(A') y^w + \frac{4|D^+|\gamma}{3n(1-\gamma)} \\ & \le 0 ^x(x^w, y^w)} \end{align}\] Then, it follows that any feasible \(A' \in \mathcal{G}^x(x^w, y^w)\) satisfies \((e_i - e_1)^\top \Delta(A') y^w \ge \frac{4|D^+|\gamma}{3n(1-\gamma)}\). This yields the following: \[\begin{align} \frac{4|D^+|\gamma}{3n(1-\gamma)} & \le (e_i - e_1)^\top \Delta(A') y^w \\ & \le \sum_{j=1}^n y^w_j \left( |\Delta(A')_{ij}| + |\Delta(A')_{1j}| \right) \\ & \le 2 \sum_{j=1}^n y^w_j \| \Delta(A') \|_{\infty} \\ & = 2 \|A- A' \|_{\infty}, \end{align}\] which proves 21 .

Combining this result with 18 gives \(H(\mathcal{G}(x^v, y^v), \mathcal{G}(x^w, y^w)) \ge \frac{\gamma}{96}\). Picking \(\gamma = 192 \epsilon\),¹⁵ we obtained \[\begin{align} \label{eq:lb-alpha0-n-dep-eq4} H(\mathcal{G}(x^v, y^v), \mathcal{G}(x^w, y^w)) \ge 2 \epsilon. \end{align}\tag{22}\]

Next we analyze \(H\!\left(\mathcal{Z}(x^v,y^v),\mathcal{Z}(x^w,y^w)\right)\). We have that: \[\begin{align} H\!\left(\mathcal{Z}(x^v,y^v),\mathcal{Z}(x^w,y^w)\right) & \ge \max_{A \in \mathcal{Z}(x^v,y^v)} \min_{A' \in \mathcal{Z}(x^w, y^w)} \| A - A'\|_{\infty} \\ & \ge \min_{A' \in \mathcal{Z}(x^w, y^w)} \|A- A' \|_{\infty}, \end{align}\] where the matrix \(A \in \mathcal{Z}(x^v, y^v)\) is defined as in 20 . We already proved above that \(A \in [-1,1]^{n \times n}\). It remains to prove that it satisfies the Nash constraints for zero-sum games, i.e., that \(A\) satisfies: \[\begin{align} e_1^\top A e_j\le e_1^\top A y^v \le e_i^\top A y^v \quad \forall i,j \in [n]. \end{align}\] We already proved above that \(e_1^\top A y^v \le e_i^\top A y^v\) holds for all \(i \in [n]\). We only need to check that \(e_1^\top A e_j\le e_1^\top A y^v\) holds for all \(j \in [n]\). Since \(A_{1j} = 0\) for all \(j \in [n]\), we have that: \[\begin{align} e_1^\top A e_j = A_{1j} = 0 = \sum_{j \in [n]} y^v_j A_{1j} = e_1^\top A y^v, \end{align}\] thus showing that \(A \in \mathcal{Z}(x^v, y^v)\).

We now continue by lower bounding \(\min_{A' \in \mathcal{Z}(x^w, y^w)} \|A- A' \|_{\infty}\). We can follow the same reasoning that we used for General-Sum Games to prove that: \[\begin{align} \label{eq:lb-alpha0-n-dep-eq6} H(\mathcal{Z}(x^v, y^v), \mathcal{Z}(x^w, y^w)) \ge 2 \epsilon. \end{align}\tag{23}\]

6.2.0.7 Step 3: Change of measure

For any \(x,y \in \Delta_n\), let \(\mathbb{P}_{x, y} = \prod_{t=1}^{\tau_\delta} p_{x}(X_t) p_y(Y_t)\), where \(p_q(\cdot)\) denotes the density function of \(q \in \Delta_n\). Then, since [eq:lb-alpha0-n-dep-eq4,eq:lb-alpha0-n-dep-eq6] holds, we can apply 18 using the set of instances \(\{(x^v, y^v)\}_{v \in \bar{\mathcal{V}}}\) and \((x^0, y^0) = \!(e_1, (\tfrac{1}{n}, \dots \tfrac{1}{n})\!)\) as base instance. Thus, for both GSGs and ZSGs we have that for any \((\epsilon, \delta)\)-correct algorithm it holds \[\begin{align} \delta \ge 1-\frac{1}{\log (|\bar{\mathcal{V}}|)} \left( \frac{1}{|\bar{\mathcal{V}}|}\sum_{v \in \bar{\mathcal{V}}} \mathrm{KL}(\mathbb{P}_{x^v, y^v}, \mathbb{P}_{x^0, y^0}) + \log2 \right). \end{align}\] We proceed by analyzing the kl-divergence term in the r.h.s. of this equation. Specifically, we have that: \[\begin{align} \mathrm{KL}(\mathbb{P}_{x^v, y^v}, \mathbb{P}_{x^0, y^0}) & = \mathbb{E}_{(x^v,y^v)}\left[ \sum_{t=1}^{\tau_\delta} \text{KL}(p_{y^v}(Y_t),p_{y^0}(Y_t))\right] \\ & = \mathbb{E}_{(x^v,y^v)}\left[ \tau_\delta \right] \text{KL}(p_{y^v},p_{y^0})\\ & \le 2 (192^2)\epsilon^2 \mathbb{E}_{(x^v,y^v)}\left[ \tau_\delta \right] }. \end{align}\] Plugging this result in the previous equation and rearranging the terms, we obtain: \[\begin{align} \frac{1}{|\bar{\mathcal{V}}|} \sum_{v \in \bar{\mathcal{V}}} \mathbb{E}_{(x^v,y^v)}\left[ \tau_\delta \right] \ge \frac{(1-\delta) \log(|\bar{\mathcal{V}}|) + \log 2}{2(192)^2 \epsilon^2}. \end{align}\] Since \(\mathbb{E}_{(x^v,y^v)}\left[ \tau_\delta \right] \le \max_{w \in \bar{\mathcal{V}}} \mathbb{E}_{(x^w,y^w)}\left[ \tau_\delta \right]\) for all \(v \in \bar{\mathcal{V}}\), the last equation implies that there exists \(\bar{w} \in \bar{\mathcal{V}}\) such that: \[\begin{align} \mathbb{E}_{(x^{\bar{w}},y^{\bar{w}})}\left[ \tau_\delta \right] \ge \frac{(1-\delta) \log(|\bar{\mathcal{V}}|) + \log 2}{2(192)^2 \epsilon^2} \end{align}\] Finally, we have \[\begin{align} \mathbb{E}_{(x^{\bar{w}},y^{\bar{w}})}\left[ \tau_\delta \right] & \ge \frac{(1-\delta) \log(|\bar{\mathcal{V}}|) + \log 2}{2(192)^2 \epsilon^2} \\ & \ge \frac{\log(2) ((1-\delta)\frac{n}{5} + 1) }{2(192)^2 \epsilon^2} } \\ & \ge \frac{\log(2)n}{40(192)^2\epsilon^2} , \end{align}\] which concludes the proof. ◻

Proof of 4. It is sufficient to consider the case where the agent observes the instances presented in [thm:lb-any-alpha-log,thm:lb-any-alpha-n] with probability \((\tfrac12, \tfrac12)\). The result is then straightforward. ◻

Proof. The proof is divided into three steps.

6.3.0.1 Step 1: Instance Construction

To prove the result, we consider the case in which \(n=2\), and we have two different instances where the unknown strategy profiles \((x^0, y^0)\) and \((x^1, y^1)\) are defined as follows: \[\begin{align} &x^0=\left(\tfrac{\alpha}{2}, 1- \tfrac{\alpha}{2} \right),~y^0=\left(1, 0\right) \\ &x^1=\left( \tfrac{\alpha}{2} + \tfrac{\beta}{2}, 1-\tfrac{\alpha}{2}-\tfrac{\beta}{2} \right),~y^1= \left(1, 0\right), \end{align}\] where \(\beta \in (0, \tfrac14)\) is a parameter that will be tuned later on. Since \(\alpha \in (0, \tfrac14)\) and \(\beta \in (0, \tfrac14)\), \(x^0\) and \(x^1\) both belong to the simplex.

6.3.0.2 Step 2: Haussdorff Distance

Next, we lower bound \(H(\mathcal{G}_\alpha(x^0, y^0), \mathcal{G}_\alpha(x^1, y^1))\) and \(H(\mathcal{Z}_\alpha(x^0, y^0), \mathcal{Z}_\alpha(x^1, y^1))\).

We start from \(H(\mathcal{G}_\alpha(x^0, y^0), \mathcal{G}_\alpha(x^1, y^1))\). We have that: \[\begin{align} H(\mathcal{G}_\alpha(x^0, y^0), \mathcal{G}_\alpha(x^1, y^1)) & \ge \max_{A \in \mathcal{G}_\alpha^x(x^0, y^0)} \min_{A' \in \mathcal{G}_\alpha^x(x^1, y^1)} \| A - A'\|_{\infty} \\ & \ge \min_{A' \in \mathcal{G}_\alpha(x^1, y^1)} \max \{ |1-a'_{11}|, |1+a'_{12}|, |1+a'_{21}|, |1+a'_{22}| \}, \end{align}\] where, in the second step, we have set \(A=\begin{bmatrix}1&-1\\ -1&-1\end{bmatrix} \in \mathcal{G}_\alpha^x(x^0, y^0)\). ¹⁶

Now, using the values of \(x^1\) and \(y^1\), we are interested in solving the following problem: \[\begin{alignedat}{2} \min_{A' \in [-1,1]^{2 \times 2}}\max &\,\,\{ |1-a'_{11}|, |1+a'_{12}|, |1+a'_{21}|, |1+a'_{22}| \} \\ \text{s.t.~} & (\tfrac\alpha2+\tfrac\beta2) a'_{11}+(1-\tfrac\alpha2 - \tfrac \beta 2) a'_{21} \le a'_{11}+\alpha\\ & (\tfrac\alpha2+\tfrac\beta2) a'_{11}+(1-\tfrac\alpha2 - \tfrac \beta 2) a'_{21} \le a'_{21}+\alpha. \end{alignedat}\] Simplifying the constraints we can rewrite this optimization problem as follows: \[\label{eq:lb-anyalpha-eq1} \begin{alignedat}{2} \min_{A' \in [-1,1]^{2 \times 2}} & \max \,\, \{ |1-a'_{11}|, |1+a'_{21}| \} \;\\ \text{s.t.~} \,\,\quad & a'_{21}-a'_{11} \le \tfrac{2\alpha}{2-\alpha-\beta} \\ & a'_{11} - a'_{21} \le \tfrac{2\alpha}{\alpha + \beta}. \end{alignedat}\tag{24}\] Now, we note that: \[\begin{align} \max \{ |1-a'_{11}|, |1+a'_{21}| \} & \ge \frac{1}{2} \left( |1-a'_{11}|+ |1+a'_{21}|\right)\ge \tfrac12 (a+b)} \\ & \ge \frac{1}{2} |2 - (a'_{11}-a'_{21}) |. \end{align}\] Let \(\Delta = a'_{11} - a'_{21}\) and observe that \(\Delta \in [-2, 2]\). We can then lower bound the value of Problem 24 with the value of the following optimization problem: \[\label{eq:lb-anyalpha-eq2} \begin{alignedat}{2} \min_{\Delta \in [-2,2]} & \frac{1}{2} |2-\Delta| \;\\ \text{s.t.~} & -\frac{2\alpha}{2-\alpha-\beta}\le \Delta \le \frac{2\alpha}{\alpha+\beta}. \end{alignedat}\tag{25}\] This can be easily solved in closed form, yielding \(\Delta^\star = 2\frac{\alpha}{\alpha+\beta}\). Consequently, we have obtained the following lower bound on the Hausdorff distance: \(H(\mathcal{G}_\alpha(x^0, y^0), \mathcal{G}_\alpha(x^1, y^1)) \ge \frac{\beta}{\alpha+\beta}\).

Set \(\beta = \tfrac83\epsilon \alpha\). We have obtained that:¹⁷ \[\begin{align} \label{eq:lb-anyalpha-eq3} H(\mathcal{G}_\alpha(x^0, y^0), \mathcal{G}_\alpha(x^1, y^1)) \ge 2\epsilon. \end{align}\tag{26}\]

We continue by lower bounding \(H(\mathcal{Z}_\alpha(x^0, y^0), \mathcal{Z}_\alpha(x^1, y^1))\). We have that: \[\begin{align} H(\mathcal{Z}_\alpha(x^0, y^0), \mathcal{Z}_\alpha(x^1, y^1)) & \ge \max_{A \in \mathcal{Z}_\alpha(x^0, y^0)} \min_{A' \in \mathcal{Z}_\alpha(x^1, y^1)} \|A - A' \|_\infty \\ & \ge \min_{A' \in \mathcal{Z}_\alpha(x^1, y^1)} \max \{ |1-a'_{11}|, |1+a'_{12}|, |1+a'_{21}|, |1+a'_{22}| \}, \end{align}\] where, in the second step, we have set \(A=\begin{bmatrix}1&-1\\ -1&-1\end{bmatrix} \in \mathcal{Z}_\alpha(x^0, y^0)\). Indeed, we already proved above that \(A\) satisfies \(-1+\alpha = (x^0)^\top A y^0 \le e_i^\top A y^0 + \alpha\) for all \(i \in \{1,2\}\). It is also easy to see that \((x^0)^\top A e_1 = -1+\alpha\) and \((x^0)^\top Ae_2 = -1\) for all \(j \in \{ 1,2\}\). Hence, we obtained \(A \in \mathcal{Z}_\alpha(x^0, y^0)\). Then, one can proceed as above to obtain:¹⁸ \[\begin{align} \label{eq:lb-anyalpha-eq4} H(\mathcal{Z}_\alpha(x^0, y^0), \mathcal{Z}_\alpha(x^1, y^1)) \ge 2\epsilon. \end{align}\tag{27}\]

6.3.0.3 Step 3: Change of measure

For any \(x,y \in \Delta_n\), let \(\mathbb{P}_{x, y} = \prod_{t=1}^{\tau_\delta} p_{x}(X_t) p_y(Y_t)\), where \(p_q(\cdot)\) denotes the density function of \(q \in \Delta_n\). Then, since [eq:lb-anyalpha-eq3,eq:lb-anyalpha-eq4] hold, we can apply 17. For both GSGs and ZSGs we have \[\begin{align} \delta \ge \frac{1}{4} \exp\left( -\text{KL}(\mathbb{P}_{x^0, y^0}, \mathbb{P}_{x^1, y^1}) \right). \end{align}\]

We proceed by analyzing the r.h.s. of this equation. In the case we are considering we have set \(n=2\). Hence, \(x,y\) are Bernoulli distributions, and we obtain that: \[\begin{align} \text{KL}\left(\mathbb{P}_{x^0, y^0}, \mathbb{P}_{x^1, y^1}\right) & = \mathbb{E}_{x^0, y^0}\left[ \sum_{t=1}^{\tau_\delta} \text{KL}(p_{x^0}(X_t), p_{x^1}(X_t) )\right]\\ & = \mathbb{E}_{x^0, y^0}\left[ \tau_\delta \right] \text{KL}(p_{x^0}, p_{x^1}) \\ & \le 2\mathbb{E}_{x^0, y^0}\left[ \tau_\delta \right] \frac{\text{TV}(p_{x^0}, p_{x^1})^2}{\alpha}\\ & \le 2\mathbb{E}_{x^0, y^0}\left[ \tau_\delta \right] \frac{(\tfrac83 \epsilon \alpha)^2}{\alpha}\\ & \le 18 \mathbb{E}_{x^0, y^0}\left[ \tau_\delta \right] {\alpha \epsilon^2}. \end{align}\] Hence, we obtained that: \[\begin{align} \delta \ge \frac{1}{4} \exp\left( -18\mathbb{E}_{x^0, y^0}\left[ \tau_\delta \right] \alpha \epsilon^2 \right). \end{align}\] Rearranging the terms yields: \[\begin{align} \mathbb{E}_{x^0, y^0}\left[ \tau_\delta \right] \ge \frac{\log\left( \frac{1}{4\delta} \right)}{18 \alpha \epsilon^2}. \end{align}\] which concludes the proof. ◻

Proof. The proof is split into three main steps.

6.3.0.4 Step 1: Instance Construction

Similar to 9, we construct a large set of different \(n\)-dimensional instances. We assume that \(n\ge 22\) and that \(n -1 \mod 16 = 0\). These instances are parameterized with an \(n-1\)-dimensional vector \(v \in \{-1,1 \}^{n-1}\) such that \(\sum_{k=1}^{n-1} v_k = 0\) and are constructed as follows. We denote by \(\mathcal{V}\) the set of vectors that satisfies these two requirements. Now, let \(\gamma \in (0, \alpha)\); we define \((x^v, y^v)\) as follows: \[\begin{align} y^v = (1, 0, \dots 0) \text{ and } x^v = \left( \frac{\alpha+\gamma v_1}{n-1}, \frac{\alpha+ \gamma v_2}{n-1}, \dots, \frac{\alpha+\gamma v_{n-1}}{n-1}, 1-\alpha\right). \end{align}\]

Observe that \(n -1 \ge 16, \gamma \in (0, \alpha), \alpha \in (0,\tfrac12)~ \text{and~} v \in \{-1,1 \}^{n-1} \implies x^v \in [0,1]\). Furthermore \(\sum_{k=1}^{n-1} v_k = 0 \implies \sum_{j=1}^n x^v_k=1\). Therefore, we have that \(x^v\in \Delta_n\).

In the rest of the proof, we restrict our attention to vectors belonging to a subset \(\bar{\mathcal{V}}\) of \(\mathcal{V}\). Precisely, consider any pair \(v,w \in \bar{\mathcal{V}}\) and let \[\begin{align} D^+_{v,w} = \{ k \in [n-1]: v_k = 1 \text{ and } w_k = -1\} \quad \quad D^-_{v,w} = \{k \in [n-1]: v_k=-1 \text{ and }w_k = 1 \}, \end{align}\] where we will drop the explicit dependence on \(v,w\) when clear from context. Then, we require that for any \(v,w\in\bar{ \mathcal{V}}\) it holds \[\begin{align} |D^+_{v,w}| = |D^-_{v,w}| \ge \frac{n-1}{16}.\label{eq:lb-any-alpha-n-eq1} \end{align}\tag{28}\] It is easy to see that \(|D^+_{v,w}| = |D^-_{v,w}|\) is satisfied for any pair \(v,w \in \mathcal{V}\). The requirement that, e.g.,\(|D^+| \ge \tfrac{n-1}{16}\), is instead equivalent to imposing that \(\sum_{k=1}^{n-1} |v_k - w_k| \ge \tfrac{n-1}{16}\). Thanks to 22, we know that: \[\begin{align} \label{eq:lb-any-alpha-n-eq2} \exists \bar{\mathcal{V}} \subseteq \mathcal{V}: \forall v,w \in \bar{\mathcal{V}}, \quad \sum_{k=1}^{n-1} |v_k - w_k| \ge \frac{n-1}{16} \text{~and~} |\bar{\mathcal{V}}| > 2^{\frac{n-1}{5}}. \end{align}\tag{29}\] In the following step, we will consider two generic profiles \((x^v,y^v)\) and \((x^w,y^w)\) such that \(v,w \in \bar{\mathcal{V}}\).

6.3.0.5 Step 2: Hausdorff Distance

We analyze the distances \(H(\mathcal{G}_\alpha(x^v, y^v), \mathcal{G}_\alpha(x^w, y^w))\) and \(H(\mathcal{Z}_\alpha(x^v, y^v), \mathcal{Z}_\alpha(x^w, y^w))\). In particular, we will provide lower bounds on these quantities.

We start from \(H(\mathcal{G}_\alpha(x^v, y^v), \mathcal{G}_\alpha(x^w, y^w))\). We have that: \[\begin{align} H(\mathcal{G}_\alpha(x^v, y^v), \mathcal{G}_\alpha(x^w, y^w)) & \ge \max_{A \in \mathcal{G}_\alpha^x(x^v,y^v)} \min_{A' \in \mathcal{G}_\alpha^x(x^w, y^w)} \| A - A'\|_{\infty} \\ & \ge \min_{A' \in \mathcal{G}_\alpha^x(x^w, y^w)} \|A- A' \|_{\infty} , \end{align}\] where the matrix \(A \in \mathcal{G}^x_\alpha(x^v, y^v)\) that we used in the second inequality is constructed as follows:

\[\label{eq:lb-any-alpha-n-eq3} A_{ij}:= \begin{cases} -1 & i \in [n], j > 1, \\[2pt] - \kappa & i \in D^+,j=1,\\[2pt] 1 & i \in D^- ,j=1,\\[2pt] 0 & i \in [n-1] \setminus (D^+ \cup D^-),j=1, \\ -1 & i=n, j =1. \end{cases} \qquad\text{where}\qquad \kappa \mathrel{\vcenter{:}}= \frac{\sum_{j\in D^-} x^v_j}{\sum_{i\in D^+} x^v_i}.\tag{30}\] Before continuing, we prove that \(A\) constructed as in 30 satisfies \(A \in \mathcal{G}^x_\alpha(x^v, y^v)\). To this end, we first verify that \(A \in [-1,1]^{n \times n}\). It suffices to check \(|\kappa| \le 1\). With some simple manipulations, we have that: \[\begin{align} |\kappa| = \frac{\sum_{j\in D^-} x^v_j}{\sum_{i\in D^+} x^v_i} = \frac{\frac{|D^-|(\alpha-\gamma)}{n-1}}{\frac{|D^+|(\alpha+\gamma)}{n-1}} = \frac{\alpha-\gamma}{\alpha+\gamma} \le 1, \end{align}\] where the second equality is due to 28 and the definition of \(x^v\). Next, we verify that \(A\) satisfy the \(\alpha\)-Nash constraints. To this end, we need to verify that \((x^v)^\top A y \le -1 +\alpha\). We note that: \[\begin{align} (x^v)^\top A y & = \sum_{i \in D^+} x^v_i A_{i1} + \sum_{i \in D^-} x_i^v A_{i1} + x_n A_{n1} \\ & = -\kappa \sum_{i \in D^+} x^v_i + \sum_{i \in D^-} x_i^v+(\alpha - 1)\\ & = -1+\alpha . \end{align}\] Hence, all constraints are satisfied and \(A \in \mathcal{G}_\alpha^x(x^v, y^v)\).

We can now continue by lower bounding \(\min_{A' \in \mathcal{G}_\alpha^x(x^w, y^w)} \|A- A' \|_{\infty}\). Specifically, let us introduce the auxiliary variable \(t = \| A - A' \|_{\infty}\). Then, using the definition of \(y^w\), we can rewrite this optimization problem as follows: \[\label{eq:lb-any-alpha-n-eq4} \begin{alignedat}{2} \min_{A' \in [-1,1]^{n\times n},t \ge 0} & t \\ \text{s.t.\quad} & |A'_{ij}-A'_{ij}| \le t,~\forall i,j \in [n]^2\\ & \sum_{i \in [n]} x^w_i A'_{i1} \le \min_{i \in [n]} A'_{i1} + \alpha. \end{alignedat}\tag{31}\] Consider any feasible matrix \(A'\). Then, it must hold that: \[\begin{align} A'_{1n} + \alpha & \ge (x^w)^\top A' y }\\ & = \sum_{i \ne n}x^w_i A'_{i1} + (1-\alpha) A'_{n1} \\ & = \sum_{i \ne n} x^w_i A_{i1} + \sum_{i \ne n} (x_i^w (A'_{i1} - A_{i1})) + (1-\alpha) A'_{n1} \\ & \ge \sum_{i \ne n} x^w_i A_{i1} - t \alpha + (1-\alpha) A'_{n1}- A_{ij}| \le t and \sum_{i \ne n}x^w_i = \alpha}\\ & = \sum_{i \ne n} (x^w_i - x^v_i) A_{i1} - t \alpha + (1-\alpha) A'_{n1} x_i^v A_{i1} = 0} \\ & = \frac{2\kappa |D^+| \gamma}{n-1} + \frac{2|D^-| \gamma}{n-1} - t \alpha + (1-\alpha) A'_{n1}\\ & = \frac{4|D^+|\gamma}{n-1} \left( \frac{\alpha}{\alpha+\gamma} \right) - t \alpha + (1-\alpha) A'_{n1}\\ & \ge \frac{\gamma \alpha}{16(\alpha + \gamma)} - t \alpha + (1-\alpha) A'_{n1} }. \end{align}\] Hence, rearranging the terms, and manipulating the equations, we obtain that any feasible \(A'\) satisfies: \[\begin{align} \frac{\gamma \alpha}{16(\alpha + \gamma)} & \le \alpha (1+ A'_{n1}) + t \alpha \\ & \le 2 t \alpha- A'_{n1}| = |1+A'_{n1}| \le t} \end{align}\]

Therefore, we arrived at \(H(\mathcal{G}_\alpha(x^v, y^v), \mathcal{G}_\alpha(x^w, y^w)) \ge \frac{\gamma}{32(\alpha + \gamma)}\). Picking \(\gamma = 128 \alpha \epsilon\), we obtained that:¹⁹ \[\begin{align} \label{eq:lb-any-alpha-n-eq5} H(\mathcal{G}_\alpha(x^v, y^v), \mathcal{G}_\alpha(x^w, y^w)) \ge 2 \epsilon. \end{align}\tag{32}\]

Next we analyze \(H\!\left(\mathcal{Z}_\alpha(x^v,y^v),\mathcal{Z}_\alpha(x^w,y^w)\right)\). We have that: \[\begin{align} H\!\left(\mathcal{Z}_\alpha(x^v,y^v),\mathcal{Z}_\alpha(x^w,y^w)\right) & \ge \max_{A \in \mathcal{Z}_\alpha(x^v,y^v)} \min_{A' \in \mathcal{Z}_\alpha(x^w, y^w)} \| A - A'\|_{\infty} \\ & \ge \min_{A' \in \mathcal{Z}_\alpha(x^w, y^w)} \|A- A' \|_{\infty}, \end{align}\] where the matrix \(A \in \mathcal{Z}_\alpha(x^v, y^v)\) is defined as in 30 . We already proved above that \(A \in [-1,1]^{n \times n}\). It remains to prove that it satisfies the \(\alpha\)-Nash constraints for zero-sum games, i.e., that \(A\) satisfies: \[\begin{align} (x^v)^\top A e_j - \alpha \le (x^v)^\top A y \le e_i^\top A y + \alpha, \quad \forall i,j \in [n]^2. \end{align}\] Above, we have shown that \(-1+\alpha=(x^v)^\top A y \le e_i^\top A y + \alpha, \quad \forall i,j \in [n]^2\). Now, it is sufficient to note that \((x^v)^\top A e_1 = (x^v)^\top A y\) and \((x^v)^\top A e_j = -1\) for all \(j > 1\). Hence, \(A \in \mathcal{Z}_\alpha(x^v, y^v)\).

Then, one can proceed as above to obtain: \[\begin{align} \label{eq:lb-anyalpha-n-eq6} H(\mathcal{Z}_\alpha(x^v, y^v), \mathcal{Z}_\alpha(x^w, y^w)) \ge 2\epsilon. \end{align}\tag{33}\]

6.3.0.6 Step 3: Change of measure

For any \(x,y \in \Delta_n\), let \(\mathbb{P}_{x, y} = \prod_{t=1}^{\tau_\delta} p_{x}(X_t) p_y(Y_t)\), where \(p_q(\cdot)\) denotes the density function of \(q \in \Delta_n\). Then, since [eq:lb-anyalpha-n-eq6,eq:lb-anyalpha-n-eq6] holds, we can apply 18 using the set of instances \(\{(x^v, y^v)\}_{v \in \bar{\mathcal{V}}}\) and \((x^0, y^0) = \!((\tfrac{\alpha}{n-1}, \dots \tfrac{\alpha}{n-1}, 1-\alpha), e_1\!)\) as base instance. Thus, both for GSGs and ZSGs, we have that, for any \((\epsilon, \delta)\)-correct algorithm, it holds that: \[\begin{align} \delta \ge 1-\frac{1}{\log (|\bar{\mathcal{V}}|)} \left( \frac{1}{|\bar{\mathcal{V}}|}\sum_{v \in \bar{\mathcal{V}}} \mathrm{KL}(\mathbb{P}_{x^v, y^v}, \mathbb{P}_{x^0, y^0}) + \log2 \right). \end{align}\] We proceed by analyzing the kl-divergence term in the r.h.s. of this equation. Specifically, we have that: \[\begin{align} \mathrm{KL}(\mathbb{P}_{x^v, y^v}, \mathbb{P}_{x^0, y^0}) & = \mathbb{E}_{(x^v,y^v)}\left[ \sum_{t=1}^{\tau_\delta} \text{KL}(p_{x^v}(X_t),p_{x^0}(X_t))\right] \\ & = \mathbb{E}_{(x^v,y^v)}\left[ \tau_\delta \right] \text{KL}(p_{x^v},p_{x^0})\\ & \le 2 (128^2) \alpha \epsilon^2 \mathbb{E}_{(x^v,y^v)}\left[ \tau_\delta \right] }. \end{align}\] Plugging this result in the previous equation and rearranging the terms, we obtain: \[\begin{align} \frac{1}{|\bar{\mathcal{V}}|} \sum_{v \in \bar{\mathcal{V}}} \mathbb{E}_{(x^v,y^v)}\left[ \tau_\delta \right] \ge \frac{(1-\delta) \log(|\bar{\mathcal{V}}|) + \log 2}{2(128)^2 \alpha \epsilon^2}. \end{align}\] Since \(\mathbb{E}_{(x^v,y^v)}\left[ \tau_\delta \right] \le \max_{w \in \bar{\mathcal{V}}} \mathbb{E}_{(x^w,y^w)}\left[ \tau_\delta \right]\) for all \(v \in \bar{\mathcal{V}}\), the last equation implies that there exists \(\bar{w} \in \bar{\mathcal{V}}\) such that: \[\begin{align} \mathbb{E}_{(x^{\bar{w}},y^{\bar{w}})}\left[ \tau_\delta \right] \ge \frac{(1-\delta) \log(|\bar{\mathcal{V}}|) + \log 2}{ 2 (128^2) \alpha \epsilon^2} \end{align}\] With some final algebraic steps, we can now conclude the proof: \[\begin{align} \mathbb{E}_{(x^{\bar{w}},y^{\bar{w}})}\left[ \tau_\delta \right] & \ge \frac{(1-\delta) \log(|\bar{\mathcal{V}}|) + \log 2}{2(128)^2 \epsilon^2} \\ & \ge \frac{\log(2) ((1-\delta)\frac{(n-1)}{5} + 1) }{2(128)^2 \alpha\epsilon^2} } \\ & \ge \frac{\log(2)n}{20(128)^2\alpha\epsilon^2} , \end{align}\] This concludes the proof. ◻

Proof. We first prove 34 by construction. For brevity, let \(S_x:=\mathrm{supp}(x) \subseteq [n]\) and define the set of maximizers of \(\sum_{j \in [n]} \hat{y}_j A_{ij}\) over the different rows of the support of \(x\) as \(S^\star_x\), namely \(S^{\star}_x \mathrel{\vcenter{:}}= \operatornamewithlimits{argmax}_{k\in S_x} \sum_{j \in [n]} \hat{y}_j A_{kj}\). Note that, since \(A_{ij} \in [-1,1]\) and \(\hat{y} \in \Delta_n\), we have that \(\Delta_i^x \in [0,2]\). Furthermore, for all \(i \in S_x\) \[\begin{align} \Delta_i^x & = \max_{k \in S_x} \sum_{j \in [n]} \hat{y}_j A_{kj} - \sum_{j \in [n]} \hat{y}_j A_{ij} \\ & = \sum_{j \in [n]} \hat{y}_j (A_{kj} - A_{ij})\\ & = \sum_{j \in [n]} y_j (A_{kj} - A_{ij}) + \sum_{j \in [n]} (\hat{y}_j - y_j) (A_{kj}-A_{ij}) \\ & = \sum_{j \in [n]} (\hat{y}_j - y_j) (A_{kj}-A_{ij})and i, k \in S_x} \\ & \le 2 \| y - \hat{y} \|_1\\ & \mathrel{\vcenter{:}}= \Delta, \end{align}\] where in the last step we have introduced \(\Delta \mathrel{\vcenter{:}}= 2 \|y - \hat{y} \|_1\).

Now, we are ready to define a matrix \(\hat{A}\) that we will use to prove 34 . Specifically, \(\hat{A}\) is defined as follows: \[\hat{A}_{ij} := \begin{cases} \dfrac{A_{ij}}{1+\Delta}, & \text{if } i \in S^{\star}_x,\\ \dfrac{A_{ij} + \Delta_i^x}{1+\Delta}, & \text{if } i \in S_x \setminus S^{\star}_x,\\ \dfrac{A_{ij} + \Delta}{1+\Delta}, & \text{if } i \notin S_x. \end{cases}\] First of all, note that since \(A \in [-1,1]^{n \times n}\) and \(\Delta_i^x \le \Delta\), we have that \(\hat{A} \in [-1,1]^{n \times n}\).

At this point, we continue by showing that \(\hat{A} \in \mathcal{G}^x(\hat{x},\hat{y})\). To this end, since \(\alpha=0\) and \(\mathrm{supp}(x) = \mathrm{supp}(\hat{x}) = S_x\), due to 19 we only need to show that \[\tag{36} \begin{align} e_i^{\top}\hat{A} \hat{y} &= e_j^{\top}\hat{A} \hat{y} \quad \forall\, i,j\in S_x, \tag{37}\\ e_i^{\top}\hat{A} \hat{y} &\le e_j^{\top}\hat{A} \hat{y} \quad \forall\, i\in S_x,\;j\notin S_x. \tag{38} \end{align}\]

7.1.0.2 Condition 37

To prove that Condition 37 holds, we first show that for any \(i_1, i_2 \in S^*_x\), we have \(e_{i_1}^{\top}\hat{A} \hat{y} = e_{i_2}^{\top}\hat{A} \hat{y}\). Specifically, let \(i_1,i_2 \in S^\star_x\). Then, \[\begin{align} e_{i_1}^\top \hat{A} \hat{y} & = \frac{1}{1+\Delta} \sum_{j \in [n]} A_{i_1 j} \hat{y}_j \\ & = \frac{1}{1+\Delta} \sum_{j \in [n]} A_{i_2 j} \hat{y}_j _{i \in S_x} \sum_{j \in [n]} \hat{y}_j A_{i j} and i_1, i_2 \in S^\star_x} \\ & = e_{i_2}^\top \hat{A} \hat{y}. \end{align}\] To conclude the proof of Condition 37 , we need to consider \(i_1\in S^{\star}_x\), and \(i_2\in S_x \setminus S^{\star}_x\) and prove that \(e_{i_1}^\top \hat{A} \hat{y} = e_{i_2}^\top \hat{A} \hat{y}\). Using the definition of \(\hat{A}\), we have that: \[\begin{align} e_{i_1}^\top \hat{A} \hat{y} = e_{i_2}^\top \hat{A} \hat{y} \iff \sum_{j \in [n]} \hat{y}_j A_{i_1 j} = \sum_{j \in [n]} \hat{y}_j A_{i_2 j} + \Delta_{i_2}^x. \end{align}\] However, by definition of \(\Delta_{i_2}^x\), we have that, \[\begin{align} \Delta_{i_2}^x = \max_{k \in S} \sum_{j \in [n]} \hat{y}_j A_{k j} - \sum_{k \in [n]} \hat{y}_j A_{i_2 k} = \sum_{j \in [n]} \hat{y}_j A_{i_1 j} - \sum_{k \in [n]} \hat{y}_j A_{i_2 k}, \end{align}\] hence, \(\sum_{j \in [n]} \hat{y}_j A_{i_1 j} = \sum_{j \in [n]} \hat{y}_j A_{i_2 j} + \Delta_{i_2}\) holds, and \(e_{i_1}^\top \hat{A} \hat{y} = e_{i_2}^\top \hat{A} \hat{y}\) holds as well. Finally, we note that the above argument also covers the case where \(i_1, i_2 \in S_x \setminus S_x^\star\). Indeed, for any \(i \in S_x \setminus S_x^\star\), we have \[e_i^\top \hat{A} \hat{y} = e_{i^\star}^\top \hat{A} \hat{y}\] for any \(i^\star \in S_x^\star\). Therefore, for any \(i_1, i_2 \in S_x \setminus S_x^\star\), \[e_{i_1}^\top \hat{A} \hat{y} = e_{i^\star}^\top \hat{A} \hat{y} = e_{i_2}^\top \hat{A} \hat{y},\] which shows that Condition 37 holds for all pairs \(i_1,i_2 \in S_x\).

7.1.0.3 Condition 38 .

To prove that Condition 38 holds, since we already proven Condition 37 , it is sufficient to show that, for \(i_1 \in S^\star_x\) and \(i_2 \notin S_x\), we have that \(e_{i_1}^\top \hat{A} \hat{y} \le e_{i_2}^\top \hat{A} \hat{y}\). Consider the following inequalities: \[\begin{align} e_{i_1}^\top \hat{A} \hat{y} & = \frac{1}{1+\Delta} \left( \sum_{j \in [n]} \hat{y}_j A_{i_1 j}\right) \\ & = \frac{1}{1+\Delta} \left( \sum_{j \in [n]} y_j A_{i_1 j} + \sum_{j \in [n]} (\hat{y}_j - y_j) A_{i_1 j} \right) \\ & \le \frac{1}{1+\Delta} \left( \sum_{j \in [n]} y_j A_{i_2 j} + \sum_{j \in [n]} (\hat{y}_j - y_j) A_{i_1 j} \right) ^x(x,y) and \Cref{lemma:nash-support}} \\ & = \frac{1}{1+\Delta} \left( \sum_{j \in [n]} \hat{y}_j A_{i_2 j} + \sum_{j \in [n]} (\hat{y}_j - y_j) (A_{i_1 j} - A_{i_2 j})\right) \\ & \le \frac{1}{1+\Delta} \left( \sum_{j \in [n]} \hat{y}_j A_{i_2 j} + 2\| y - \hat{y}\|_1 )\right) \\ & = e_{i_2}^\top \hat{A} \hat{y}. \end{align}\] Hence, we proved that \(\hat{A} \in\mathcal{G}^x(\hat{x},\hat{y})\).

Finally, to conclude the proof of 34 , it remains to bound \(\|A - \hat{A}\|_\infty\). Fix any pair of \(i,j \in [n]\). Then, if \(i \in S^\star_x\), we have that: \[|A_{ij}-\hat{A}_{ij}| = \left|A_{ij}-\frac{A_{ij}}{1+\Delta}\right| = |A_{ij}|\,\frac{\Delta}{1+\Delta} \le \frac{\Delta}{1+\Delta} \le 2 \Delta.\] If, instead, \(i\in S_x\setminus S^{\star}_x\): \[|A_{ij}-\hat{A}_{ij}| = \left|A_{ij}-\frac{A_{ij}+\Delta_i^x}{1+\Delta}\right| = \frac{|\,\Delta A_{ij}-\Delta_i^x\,|}{1+\Delta} \le \frac{|A_{ij}|\Delta + \Delta_i^x}{1+\Delta} \le \frac{2\Delta}{1+\Delta} \le 2\Delta,\] Finally, if \(i\notin S_x\), we have that: \[|A_{ij}-\hat{A}_{ij}| = \left|A_{ij}-\frac{A_{ij}+\Delta}{1+\Delta}\right| = \frac{\Delta|1-A_{ij}|}{1+\Delta} \le \frac{2\Delta}{1+\Delta} \le 2\Delta.\] Hence, \(\|A-\hat{A}\|_\infty \le 2\Delta\), thus concluding the proof of 34 .

We continue by proving 35 . In particular, the proof of 35 follows from arguments that are symmetrical to the ones that we presented above. More precisely, consider \(B \in \mathcal{G}^y(x,y)\). Let \(S_y \mathrel{\vcenter{:}}= \mathrm{supp}(y)\) and for all \(j \in [n]\) and define: \[\Delta_j^y = \max_{k \in S_y} \sum_{i \in [n]} \hat{x}_i B_{ik} - \sum_{i \in [n]} \hat{x}_i B_{ij}.\] Furthermore, let \(S^{\star}_y = \operatornamewithlimits{argmax}_{j \in [n]} \sum_{i \in [n]} \hat{x}_i B_{ij}\). Then, we define \(\hat{B}\) as follows: \[\hat{B}_{ij} := \begin{cases} \dfrac{B_{ij}}{1+\Delta}, & \text{if } j \in S^{\star}_y,\\ \dfrac{B_{ij} + \Delta_i^x}{1+\Delta}, & \text{if } j \in S_y \setminus S^{\star}_y,\\ \dfrac{B_{ij} + \Delta}{1+\Delta}, & \text{if } j \notin S_y. \end{cases}\] where \(\Delta = 2 \|x - \hat{x} \|_1\). The proof of the results than follows from arguments that are analogous to the ones that we presented for 34 . ◻

Proof. The proof is a direct application of 1. Precisely: \[\begin{align} H(\mathcal{G}(x,y), \mathcal{G}(\hat{x}, \hat{y})) & = \max \Bigg \{ \max_{(A,B) \in \mathcal{G}(x,y)} \min_{(\hat{A}, \hat{B}) \in \mathcal{G}(\hat{x}, \hat{y})} \max\{ \|A - \hat{A} \|_{\infty}, \|B - \hat{B}\|_\infty , \\& \max_{(\hat{A}, \hat{B}) \in \mathcal{G}(\hat{x}, \hat{y})} \min_{(A, B) \in \mathcal{G}(x, y)} \max\{ \|A - \hat{A} \|_{\infty}, \|B - \hat{B}\|_\infty \Bigg\} \\ & \le 4\max \left\{ \|x-\hat{x} \|_1, \|y - \hat{y} \|_1 \right\} } \\ & \le 4 (\|x-\hat{x} \|_1 + \|y-\hat{y} \|_1). \end{align}\] which concludes the proof. Here, we simply remark that, in order to apply 1 in the first inequality, it is important to recall that \(\mathcal{G}(x,y) = \mathcal{G}^x(x,y) \times \mathcal{G}^{y}(x,y)\). ◻

Proof. We first define the following good event \(\mathcal{E}\) and shows that it holds with probability at least \(1-\delta\). We define \(\mathcal{E} = \mathcal{E}_1 \cap \mathcal{E}_2\), where \[\begin{align} & \mathcal{E}_1 = \left\{ \| x - \hat{x} \|_1 \le \sqrt{\frac{2 \log\left(\frac{4}{\delta}\right)+2n\log(6m)}{m}} \right\} \cap \left\{ \|y - \hat{y} \|_1 \le \sqrt{\frac{2 \log\left(\frac{4}{\delta}\right)+2n\log(6m)}{m}} \right\} \\ & \mathcal{E}_2 = \{ \mathrm{supp}(x) = \mathrm{supp}(\hat{x}) \} \cap \{ \mathrm{supp}(y) = \mathrm{supp}(\hat{y}) \}. \end{align}\] Then, we have that \(\mathbb{P}(\mathcal{E}) = 1 - \mathbb{P}(\mathcal{E}^\complement) \ge 1 - (\mathbb{P}(\mathcal{E}_1^\complement) + \mathbb{P}(\mathcal{E}^{\complement}_2))\). Hence, we simply upper bound \(\mathbb{P}(\mathcal{E}_1^\complement)\) and \(\mathbb{P}(\mathcal{E}^\complement_2)\). \[\begin{align} \mathbb{P}( \mathcal{E}_1^\complement) & \le \mathbb{P}\left( \| x - \hat{x} \|_1 > \sqrt{\frac{2 \log\left(\frac{4}{\delta}\right)+2n\log(6m)}{m}} \right) + \mathbb{P}\left( \|y - \hat{y} \|_1 > \sqrt{\frac{2 \log\left(\frac{4}{\delta}\right)+2n\log(6m)}{m}} \right) \\ & \le \frac{\delta}{2} }. \end{align}\] Furthermore, \[\begin{align} \mathbb{P}(\mathcal{E}_2^\complement) & \le \mathbb{P}(\mathrm{supp}(x) \ne \mathrm{supp}(\hat{x})) + \mathbb{P}(\mathrm{supp}(y) \ne \mathrm{supp}(\hat{y})) \\ & \le \frac{\delta}{2}and \Cref{lemma:support}}. \end{align}\] Thus, we obtained that \(\mathbb{P}(\mathcal{E}) \ge 1-\delta\).

Therefore, due to the definition of \(\mathcal{E}\) and by using 2, we have that, with probability at least \(1-\delta\): \[\begin{align} H(\mathcal{G}(x,y), \mathcal{G}(\hat{x}, \hat{y})) & \le 4 (\| x - \hat{x}\|_1 + \|y - \hat{y} \|_1) \\ & \le 8 \sqrt{\frac{2 \log\left(\frac{4}{\delta}\right)+2n\log(6m)}{m}}, \end{align}\] which concludes the proof. ◻

Proof. First, we give a precise expression of the number of samples \(m\) needed by 2.

\[\begin{align} \label{eq:thm-41-alpha0} m & = \max \left\{ \frac{\log\left( \frac{4n}{\delta} \right)}{\log\left( \frac{1}{1-\pi_{\min}} \right)}, 2 \left( 2 + \frac{4\log(4/\delta)}{(\epsilon/\sqrt{128})^2} + \frac{4n}{(\epsilon/\sqrt{128})^2} \log\left( \frac{12n}{(\epsilon/\sqrt{128})^2} \right)\right)\right\} \\ & \in \widetilde{\mathcal{O}}\left( \frac{\log\left( \frac{1}{\delta} \right)}{\log\left( \frac{1}{1-\pi_{\min}} \right)}+ \frac{\log\left( \frac{1}{\delta} \right)+n}{\epsilon^2} \right). \end{align}\tag{40}\] Now, since \(m \ge \frac{\log\left( \frac{4n}{\delta} \right)}{\log\left( \frac{1}{1-\pi_{\min}} \right)}\), by 3, we have that, with probability at least \(1-\delta\): \[\begin{align} H(\mathcal{G}(x,y), \mathcal{G}(\hat{x}, \hat{y}) & \le 8 \sqrt{\frac{2 \log\left(\frac{4}{\delta}\right)+2n\log(6m)}{m}} \end{align}\]

Thus, we need to show that, for \(m\) chosen as in 40 , \(8 \sqrt{\frac{2 \log\left(\frac{4}{\delta}\right)+2n\log(6m)}{m}} \le \epsilon\). That holds if and only if \[\begin{align} \frac{ \log\left(\frac{4}{\delta}\right)+n\log(6m)}{m} \le \left( \frac{\epsilon}{\sqrt{128}} \right)^2. \end{align}\]

This, however, is granted by the definition of \(m\). To this end, it is sufficient to apply 20 with \(c_1 = 4, c_2=6, K=(\epsilon/\sqrt{128})\).

Hence, after \(m\) samples, 2 is \((\epsilon, \delta)\)-correct for \(\alpha=0\) and General-Sum Games. ◻

Proof. Given the definition of \(\hat{A}\), we already know from 1 that all the following statements are true: \[\begin{align} & \text{(i)}~\|A - \hat{A} \|_{\infty} \le 4 \|y - \hat{y} \|_1 \\ & \text{(ii)}~e_i^\top \hat{A} \hat{y} = e_j^\top \hat{A} \hat{y} \quad \quad \quad \quad~ \forall i,j \in \mathrm{supp}(x) \\ & \text{(iii)}~e_i^\top \hat{A} \hat{y} \le e_j^\top \hat{A} \hat{y} \quad \quad \quad \quad \forall i \in \mathrm{supp}(x), \forall j \notin \mathrm{supp}(x). \end{align}\] Hence, from 19 it only remains to verify that \(\hat{A}\) satisfies: \[\begin{align} & x^\top \hat{A} e_j = x^\top \hat{A} \hat{y}~\quad \forall j \in \mathrm{supp}(\hat{y}) \tag{41} \\ & x^\top \hat{A}e_j \le x^\top \hat{A} \hat{y} ~\quad\forall j \notin \mathrm{supp}(\hat{y}) \tag{42}. \end{align}\] Before proving [eq:zsg-alpha0-cnd1,eq:zsg-alpha0-cnd2] we make some preliminary considerations. First, we recall from 19 that, since \(A \in \mathcal{Z}(x, y)\), it holds that: \[\begin{align} & x^{\top}Ay = x^{\top}Ae_j =e_i^TAy, \quad \forall\, i \in \mathrm{supp}(x),j\in \mathrm{supp}(y),\label{eq:mat-constr-zero-sum-alpha0-helper}\\ & x^\top A e_j \le x^{\top}Ay \le e_i^\top A y, \quad \forall\, i\notin \mathrm{supp}(x),\;\forall\, j\notin \mathrm{supp}(y). \end{align}\tag{43}\] Now, let \(\Delta = 2 \|y-\hat{y} \|_1\) and let \(j \in [n]\). Then, we have that: \[\begin{align} x^\top \hat{A} e_j & = \sum_{i \in [n]} x_i \hat{A}_{ij} \\ & = \frac{1}{1+\Delta} \left( x^\top A e_j + \sum_{i: x_i > 0}x_i \Delta_i \right) }. \end{align}\] Now, let us focus in detail on the term \(\sum_{i: x_i > 0} x_i \Delta_i\). We have that: \[\begin{align} \sum_{i: x_i > 0} x_i \Delta_i & = \sum_{i: x_i > 0} x_i \sum_{j \in [n]} \hat{y}_j (A_{kj} - A_{ij}) _{\star \in \mathrm{supp}(x)} \sum_{j \in [n]} \hat{y}_j A_{\star,j}} \\ & = \sum_{j \in [n]} \hat{y}_j \left( A_{kj}-\sum_{i: x_i>0} x_iA_{ij} \right) \\ & = \sum_{j \in [n]} \hat{y}_j \left( A_{kj}-x^\top A e_j \right) \\ & = \sum_{j \in [n]} \hat{y}_j A_{kj}- \sum_{j: y_j > 0} \hat{y}_j (x^\top Ae_j) (y)=\mathrm{supp}(\hat{y})} \\ & = \sum_{j \in [n]} \hat{y}_j A_{kj}- x^\top A y } \end{align}\] Hence, we obtained that, for all \(j \in [n]\): \[\begin{align} \label{eq:mat-constr-zero-sum-alpha0-helper2} x^\top \hat{A} e_j = \frac{1}{1+\Delta} \left( x^\top A e_j - x^\top Ay + \max_{k \in \mathrm{supp}(x)} e_k^\top A \hat{y} \right) \end{align}\tag{44}\]

We are now ready to conclude the proof. Consider \(j_1, j_2 \in [n]\) such that \(y_{j_1} > 0\) and \(y_{j_2} = 0\). Then, combining [eq:mat-constr-zero-sum-alpha0-helper,eq:mat-constr-zero-sum-alpha0-helper2], we have that: \[\begin{align} & x^\top \hat{A} e_{j_1} = \frac{\max_{k \in \mathrm{supp}(x)} e_k^\top A\hat{y}}{1+\Delta} \\ & x^\top \hat{A} e_{j_2} \le \frac{\max_{k \in \mathrm{supp}(x)} e_k^\top A\hat{y}}{1+\Delta}, \end{align}\] thus proving Conditions 41 and 42 . Hence, \(\hat{A} \in \mathcal{Z}(x, \hat{y})\). ◻

Proof. First, as in 1, one can trivially verify that, since \(A \in [-1,1]^{n \times n}\), \(\hat{A} \in [-1,1]^{n \times n}\) as well. Furthermore, by following analogous arguments, it is also easy to see that \(\| A - \hat{A} \|_{\infty} \le 4 \|x - \hat{x} \|_1\)

By applying 19 it thus remains to verify that: \[\begin{align} & \hat{x}^\top \hat{A} e_i = \hat{x}^\top \hat{A} e_j,\quad \forall i,j \in \mathrm{supp}(y) \tag{45}\\ & \hat{x}^\top \hat{A} e_i \ge \hat{x}^\top \hat{A} e_j, \quad \forall i \in \mathrm{supp}(y), j \notin \mathrm{supp}(y)\tag{46} \\ & e_i^\top \hat{A} y = e_i^\top \hat{A} e_j, \quad \forall i,j \in \mathrm{supp}(x) \tag{47} \\ & e_i^\top \hat{A} y \le e_j^\top \hat{A} y, \quad \forall i \in \mathrm{supp}(x), j \notin \mathrm{supp}(x) \tag{48}. \end{align}\]

Before continuing, we introduce some additional notation for the sake of brevity. Let \(\Delta = 2 \|x - \hat{x} \|_1\) and define \(S=\mathrm{supp}(y)\) and \(S^{\star}_y = \operatornamewithlimits{argmax}_{k \in \mathrm{supp}(y)} \sum_{i \in [n]} \hat{x}_i A_{ik}\).

7.2.0.2 Conditions 45 and 46

Given the expression of \(\hat{A}\), 45 is a direct consequence of 1. We now prove 46 . Since 45 holds, we only need to consider \(j_1 \in \mathrm{supp}(y)\) and \(j_2 \notin \mathrm{supp}(y)\) and show that \(\hat{x}^\top \hat{A} e_{j_1} \ge \hat{x}^\top \hat{A} e_{j_2}\). Specifically, we consider \(j_1 \in S^\star_y\). Then, it holds that:

\[\begin{align} \hat{x}^\top \hat{A} e_{j_1} & = \frac{1}{1+\Delta} \sum_{i \in [n]} \hat{x}_i A_{i j_1} \\ & = \frac{1}{1+\Delta} \left( x^\top A e_{j_1} + \sum_{i \in [n]} (\hat{x}_i - x_i) A_{i j_1}\right) \\ & \ge \frac{1}{1+\Delta} \left( x^\top A e_{j_2} + \sum_{i \in [n]} (\hat{x}_i - x_i) A_{i j_1}\right) (x,y), \Cref{lemma:nash-support} and j_1 \in \mathrm{supp}(y)} \\ & = \frac{1}{1+\Delta} \left( \sum_{i \in [n]} \hat{x}_i A_{ij_2} + \sum_{i \in [n]} (\hat{x}_i - x_i) (A_{i j_1} - A_{i j_2}) \right) \\ & \ge \frac{1}{1+\Delta} \left( \sum_{i \in [n]} \hat{x}_i A_{i j_2} - 2\|x-\hat{x} \|_1 \right) \\ & = \hat{x}^\top \hat{A} e_{j_2}, \end{align}\] which concludes the proof.

7.2.0.3 Conditions 47 and 48

Here, we proceed in a way that is analogous to 4. Specifically, consider any \(i \in [n]\). Then, it holds that: \[\begin{align} e_i^\top \hat{A} y & = \sum_{j \in [n]} y_j \hat{A}_{ij} \\ & = \frac{1}{1+\Delta} \left( e_i^\top A y + \sum_{j: y_j > 0} y_j \Delta_j \right)}. \end{align}\] Let us focus on \(\sum_{j: y_j > 0} y_j \Delta_j\). We have that: \[\begin{align} \sum_{j: y_j > 0} y_j \Delta_j & = \sum_{j: y_j > 0} y_j \sum_{i \in [n]} \hat{x}_i (A_{ik}- A_{ij}) _{\star \in \mathrm{supp}(y)} \sum_{i \in [n]} \hat{x}_i A_{i\star}} \\ & = \sum_{i \in [n]} \hat{x}_i \left( A_{ik} - \sum_{j: y_j > 0} y_j A_{ij} \right) \\ & = \sum_{i \in [n]} \hat{x}_i (A_{ik} - e_i^\top A y) \\ & = \sum_{i \in [n]} \hat{x}_i A_{ik} - \sum_{i: x_i > 0} \hat{x}_i (e_i^\top A y)) (x) = \mathrm{supp}(\hat{x})} \\ & = \sum_{i \in [n]} \hat{x}_i A_{ik} - x^\top A y (x,y)} \end{align}\] Therefore, we obtained that, for all \(i \in [n]\): \[\begin{align} e_i^\top \hat{A} y = \frac{1}{1+\Delta} \left( e_i^\top A y - x^\top A y + \max_{k \in \mathrm{supp}(y)} \hat{x}^\top A e_k \right). \end{align}\] Now, let \(i_1\in \mathrm{supp}(\hat{x})\) and \(i_2 \notin \mathrm{supp}(\hat{x})\). We have that: \[\begin{align} & e_{i_1}^\top \hat{A} y = \frac{1}{1+\Delta} \max_{k \in \mathrm{supp}(y)} \hat{x}^\top A e_k \\ & e_{i_2}^\top \hat{A} y \ge \frac{1}{1+\Delta} \max_{k \in \mathrm{supp}(y)} \hat{x}^\top A e_k \end{align}\] which proves 47 and 48 , thus showing that \(\hat{A} \in \mathcal{Z}( \hat{x}, y)\). ◻

Proof. Use 49 . Then, the proof follows from the same arguments of 12. ◻

Proof. We first prove 50 .

Specifically, for \((A,B) \in \mathcal{G}_\alpha(x,y)\) we define \((\hat{A}, \hat{B})\) as \((\hat{A}, \hat{B})=(\lambda_A A, \lambda_B B)\), where \(\lambda_A, \lambda_B \in \mathbb{R}\) are defined as follows \[\begin{align} \lambda_A = \min \left\{1, \frac{\alpha}{\max_{i \in [n]} \hat{x}^\top A y - e_i^\top Ay} \right\}, \quad \lambda_B = \min \left\{ 1, \frac{\alpha}{\max_{j \in [n]} \hat{x} By - \hat{x}Be_j}\right\}. \end{align}\] From now on, w.l.o.g., we asume that \(\lambda_A, \lambda_B > 0\). Otherwise, we could simply pick \(\hat{A} = A\) and \(\hat{B} = B\) and all the Nash constraints are verified.

Next, we verify that \((A,B) \in \mathcal{G}_\alpha(\hat{x},y)\). First, under the assumption that \(\lambda_A, \lambda_B > 0\), it follows that \(\lambda_A, \lambda_B \in (0,1]\), and hence \(\hat{A}, \hat{B} \in [-1,1]^{n \times n}\). Secondly, for any \(i \in [n]\): \[\begin{align} \hat{x}^\top \hat{A} y - e_i^\top \hat{A} y & = \lambda_A \left( \hat{x}^\top A y - e_i^\top A y \right) \\ & = \min \left\{1, \frac{\alpha}{\max_{i \in [n]} \hat{x}^\top A y - e_i^\top Ay} \right\} \left( \hat{x}^\top A y - e_i^\top A y \right) \\ & \le \alpha, \end{align}\] where, (i) if \(\lambda_A < 1\), the last step is trivial, and (ii) if \(\lambda_A = 1\), then, \(\alpha > \max_{i \in [n]} \hat{x}^\top A y - e_i^\top A y\). Thus, we have proved that \(\hat{A} \in \mathcal{G}^x_\alpha(\hat{x},y)\). The proof for showing that \(\hat{B} \in \mathcal{G}^y_\alpha(\hat{x},y)\) is equivalent.

Next, we proceed by analyzing \(\|A - \hat{A} \|_{\infty}\). We consider the case where \(\lambda_A < 1\), otherwise \(A = \hat{A}\) and 50 is trivial. We have that: \[\begin{align} \| A - \hat{A} \|_{\infty} & \le (1-\lambda_A) \| A \|_{\infty} \\ & \le 2 (1-\lambda_A) \\ & \le 2 \frac{\max_{i \in [n]}\hat{x}^\top A y - e_i^\top A y - \alpha}{\alpha} \\ & = 2 \frac{(\hat{x}-x)^\top A y + x^\top A y - \min_{i \in [n]}e_i^\top A y - \alpha}{\alpha} \\ & \le 2 \frac{(\hat{x}-x)^\top A y}{\alpha} _\alpha^x(x,y)}, \end{align}\] which proves the first part of 50 . One can follow the same steps to prove the second part of 50 .

The proof of 51 follows from analogous argument. It is indeed sufficient to define \((\hat{A}, \hat{B}) = (\tilde{\lambda}_A A, \tilde{\lambda}_B B)\) where: \[\begin{align} \tilde{\lambda}_A = \min \left\{1, \frac{\alpha}{\max_{i \in [n]} x^\top A \hat{y}- e_i^\top A \hat{y}} \right\}, \quad \tilde{\lambda}_B = \min \left\{1, \frac{\alpha}{\max_{j \in [n]} x^\top B \hat{y} - x^\top B e_j} \right\}. \end{align}\] The proof is thus concluded. ◻

Proof. First, we observe that, due to symmetry, once 52 and 53 hold, 54 and 55 hold as well.

We now start by proving 52 . We assume w.l.o.g. that the supremum is positive. Furthermore, for any \(A \in \mathcal{G}_\alpha(x,y)\), denote by \(\star \in [n]\) any index that attains the argmin in \(\min_{i \in [n]} (Ay)_i\). Then, we have that: \[\begin{align} \sup_{A \in \mathcal{G}_\alpha^x(x,y)} \left( (\hat{x}-x)^\top A y \right)_+ & =\sup_{A \in \mathcal{G}_\alpha^x(x,y)} \sum_{i \in [n]} (\hat{x}_i - x_i) [(Ay)_i - (Ay)_\star] , x \in \Delta_n} & \\ & \le \left( \sup_{A \in \mathcal{G}_\alpha^x(x,y)} \sum_{i: x_i >0} (\hat{x}_i - x_i) [(Ay)_i - (Ay)_\star] \right) + 2 \sum_{i: x_i = 0} \hat{x}_i \:. \end{align}\] Let us focus on the remaining optimization problem over \(A\). We are interested in solving:²⁰ \[\label{eq:key-int-step-eq5} \begin{alignedat}{2} & \max_{A \in [-1,1]^{n \times n}} \sum_{i: x_i > 0} (\hat{x}_i - x_i) [(Ay)_i - (Ay)_\star] \\ & \text{s.t.~} \sum_{i: x_i > 0} x_i [(Ay)_i - (Ay)_\star] \le \alpha. \end{alignedat}\tag{56}\] Let us introduce the following auxiliary variable \(c_i = x_i[(Ay)_i-(Ay)_\star] \in[0, 2x_i]\) . Then, 56 is upper bounded by: \[\label{eq:key-int-step-eq7} \begin{alignedat}{2} & \max_{(c_1, \dots, c_n)} \sum_{i: x_i > 0} c_i \frac{(\hat{x}_i - x_i)}{x_i} \\ & \text{s.t.~} \sum_{i: x_i > 0} c_i \le \alpha \text{ and } c_i \in [0, 2x_i]. \end{alignedat}\tag{57}\] This is a fractional knapsack problem. It is well-known that such problems can be solved by a greedy algorithm that sorts the indexes \(i\)’s according to their value (i.e.,\(\frac{\hat{x}_i -x_i}{x_i}\)) and allocates the maximum value of \(c_i\) according to this order until all the budget (i.e.,\(\sum_{i: x_i > 0} c_i \le \alpha\)) expires. More formally, any optimal solution \(c^\star\) of 57 has the following shape. Let \(S \subseteq \{ i \in [n]: x_i > 0 \}\) be any subset such that \[\min_{i \in S}\frac{\hat{x}_i - x_i}{x_i} \ge \max_{i \in S^\complement}\frac{\hat{x}_i - x_i}{x_i},\] where \(S^\complement = \{i \in [n]: x_i > 0 \} \setminus S\). Then \(c^\star_i = 2x_i\) for all \(i \in S\). Furthermore, there exists at most one \(j \in S^\complement\) such that \(c^\star_j \in [0, 2x_j]\). For all the remaining elements, we have that \(c^\star_i = 0\). Hence, the optimal value of 57 can be written (and upper bounded) as follows: \[\begin{align} 2 \sum_{i \in S} (\hat{x}_i - x_i) + \frac{\hat{x}_j - x_j}{x_j} c^\star_j & \le 4 \sum_{i \in S} ( \hat{x}_i - x_i ) \\ & \le 4 \sup_{S \in \mathcal{S}_\alpha(x)} \sum_{i \in S} (\hat{x}_i - x_i) _\alpha(x)}. \end{align}\] where the first inequality step follows from the fact that, for \(j \in S^\complement\) it holds that \(c_j \frac{\hat{x}_j - x_j}{x_j} \le c_i \frac{\hat{x}_i - x_i}{x_i}\) for any \(i \in S\). This concludes the proof of 52 .

Next, we continue by proving 53 . Again, we assume w.l.o.g. that the sup is greater or equal than \(0\). Then, we have that: \[\begin{align} \sup_{B \in \mathcal{G}_\alpha^y(x,y)} \left( \max_{j \in [n]} (\hat{x} - x)^\top B (y - e_j) \right)_+ & = \max_{B \in \mathcal{G}_\alpha^y(x,y)} \max_{\star \in [n]} \sum_{i \in [n]} (\hat{x}_i - x_i) \left[\sum_{j \in [n]} y_j B_{ij} - B_{i\star}\right] \\ & \le \max_{B \in \mathcal{G}_\alpha^y(x,y)} \max_{\star \in [n]} \sum_{i: x_i > 0} (\hat{x}_i - x_i) \left[\sum_{j \in [n]} y_j B_{ij} - B_{i\star}\right] + 2\sum_{i: x_i = 0} \hat{x}_i \\ & = \max_{\star \in [n]} \max_{\substack{B \in \mathcal{G}_\alpha(x,y) \\ \star \in \operatornamewithlimits{argmax}(\hat{x} -x)^\top B (y-e_\star)}} \sum_{i: x_i > 0} (\hat{x}_i - x_i) \left[\sum_{j \in [n]} y_j B_{ij} - B_{i\star}\right] + 2\sum_{i: x_i = 0} \hat{x}_i \\ & \le \max_{\star \in [n]} \max_{\substack{B \in \mathcal{G}_\alpha(x,y)}} \sum_{i: x_i > 0} (\hat{x}_i - x_i) \left[\sum_{j \in [n]} y_j B_{ij} - B_{i\star}\right] + 2\sum_{i: x_i = 0} \hat{x}_i\:. \end{align}\] Hence, fix any \(\star \in [n]\) in the outer maximization problem, and restrict our attention to the maximization problem over \(B\), that is \[\label{eq:key-int-step-eq9} \begin{alignedat}{2} & \max_{B \in [-1,1]^{n \times n}} \sum_{i: x_i > 0} (\hat{x}_i - x_i) \left[ \sum_{j \in [n]} y_j B_{ij} - B_{i\star} \right]\\ & \text{s.t.~} \sum_{i: x_i > 0} x_i \left[ \sum_{j \in [n]} y_j B_{ij} - B_{ik}\right] \le \alpha \quad \forall k \in [n]. \end{alignedat}\tag{58}\] Since the \(\alpha\)-Nash constraint holds for all \(k \in [n]\), it holds also for \(\star\). Hence, we can upper bound 58 with the following problem: \[\label{eq:key-int-step-eq10} \begin{alignedat}{2} & \max_{B \in [-1,1]^{n \times n}} \sum_{i: x_i > 0} (\hat{x}_i - x_i) \left[ \sum_{j \in [n]} y_j B_{ij} - B_{i\star} \right]\\ & \text{s.t.~} \sum_{i: x_i > 0} x_i \left[ \sum_{j \in [n]} y_j B_{ij} - B_{i\star}\right] \le \alpha \end{alignedat}\tag{59}\] Introducing the variable \(c_i = x_i \left[ \sum_{j \in [n]} y_j B_{ij} - B_{i\star}\right]\) and rewriting the objective function as \(\sum_{i: x_i > 0} c_i \frac{\hat{x}_i - x_i}{x_i}\), we obtain again a fractional knapsack problem that can be solved in closed form, as we presented above. Following the same steps as above, the proof is concluded. ◻

Proof. From 1, we have that: \[\begin{align} H(\mathcal{G}_\alpha(x, y), \mathcal{G}_\alpha(\hat{x}, \hat{y}) & \le H(\mathcal{G}_\alpha(x, y), \mathcal{G}_\alpha(\hat{x}, y) + H(\mathcal{G}_\alpha(\hat{x}, y), \mathcal{G}_\alpha(\hat{x}, \hat{y}) \end{align}\] Let us focus on the fist term. From 6, we have that: \[\begin{align} H(\mathcal{G}_\alpha(x, y), \mathcal{G}_\alpha(\hat{x}, y) \le 2 \sup_{A \in \mathcal{G}^x_\alpha(x,y)}\left( \frac{(\hat{x}-x)^\top A y}{\alpha} \right)_+ & + 2 \sup_{A \in \mathcal{G}^x_\alpha(\hat{x},y)}\left( \frac{(x-\hat{x})^\top A y}{\alpha} \right)_+ +\\ &+ \sup_{A \in \mathcal{G}^y_\alpha(x, y)}2\left( \frac{\max_{j \in [n]}(\hat{x}-x)^\top B(y-e_j)}{\alpha} \right)_+ + \\ & + \sup_{A \in \mathcal{G}^y_\alpha(\hat{x}, y)}2\left( \frac{\max_{j \in [n]}(x-\hat{x})^\top B(y-e_j)}{\alpha} \right)_+ \end{align}\] This, in turn, can be upper bounded using 7. We thus obtain: \[\begin{align} H(\mathcal{G}_\alpha(x, y), \mathcal{G}_\alpha(\hat{x}, y) \le \frac{16}{\alpha} \left( \sup_{S \in \mathcal{S}_\alpha(x)} \sum_{i \in S} (\hat{x}_i - x_i) + \sup_{S \in \mathcal{S}_\alpha(\hat{x})} \sum_{i \in S} ( x_i - \hat{x}_i) + \sum_{i: \hat{x}_i= 0} x_i\right), \end{align}\] where we used the fact that \(\sum_{x_i = 0} \hat{x}_i = 0\). Similarly, for \(H(\mathcal{G}_\alpha(\hat{x}, y), \mathcal{G}_\alpha(\hat{x}, \hat{y})\), we obtain: \[\begin{align} H(\mathcal{G}_\alpha(\hat{x}, y), \mathcal{G}_\alpha(\hat{x}, \hat{y}) \le \frac{16}{\alpha} \left( \sup_{S \in \mathcal{S}_\alpha(y)} \sum_{j \in S} (\hat{y}_j - y_j) + \sup_{S \in \mathcal{S}_\alpha(\hat{y})} \sum_{j \in S} ( y_j - \hat{y}_j) + \sum_{j: \hat{y}_j= 0} y_j\right), \end{align}\] thus concluding the proof. ◻

Proof. We first fix any \(m \ge 1\) and we consider the following good event \[\mathcal{E} = \mathcal{E}_{\mathrm{miss}} \cap \mathcal{E}_{\mathrm{set}} \cap \mathcal{E}_{\text{err},x} \cap \mathcal{E}_{\text{err},y}\] where these events are defined as: \[\begin{align} & \mathcal{E}_{\text{miss}} = \left\{ \sum_{i: \hat{x}_i=0} x_i - \mathbb{E}\left[ \sum_{i: \hat{x}_i = 0} x_i \right] \le \frac{3\sqrt{n} \log\left(\frac{6}{\delta} \right)}{m} \right\} \bigcap \left\{ \sum_{j: \hat{y}_j=0} y_j - \mathbb{E}\left[ \sum_{j: \hat{y}_j = 0} y_j \right] \le \frac{3\sqrt{n} \log\left(\frac{6}{\delta} \right)}{m} \right\} \\ & \mathcal{E}_{\text{set},x} = \bigcap_{S \subseteq[n]} \left\{ \Bigg|\sum_{i \in S} (\hat{x}_i - x_i) \Bigg| \le \sqrt{\frac{2 \sum_{i \in S} \hat{x}_i\left(n+\log(\frac{24}{\delta}) \right)}{m}} + \frac{4 (n + \log(\frac{24}{\delta}))}{m-1} \right\} \\ & \mathcal{E}_{\text{set},y} = \bigcap_{S \subseteq[n]} \left\{ \Bigg|\sum_{j \in S} (\hat{y}_j - y_j) \Bigg| \le \sqrt{\frac{2 \sum_{j \in S} \hat{y}_j\left(n+\log(\frac{24}{\delta}) \right)}{m}} + \frac{4 (n + \log(\frac{24}{\delta}))}{m-1} \right\} \\ & \mathcal{E}_{\text{err},x} = \bigcap_{S \in \mathcal{S}_{2\alpha}(x)} \left\{ \Bigg|\sum_{i \in S} (\hat{x}_i - x_i) \Bigg| \le \sqrt{\frac{4\alpha \left( n+\log\left( \frac{6}{\delta} \right) \right) }{m}} + \frac{4(n+\log\left( \frac{6}{\delta} \right))}{m} \right\}\\ & \mathcal{E}_{\text{err},y} = \bigcap_{S \in \mathcal{S}_{2\alpha}(y)} \left\{ \Bigg|\sum_{j \in S} (\hat{y}_j - y_j) \Bigg| \le \sqrt{\frac{4\alpha \left( n+\log\left( \frac{6}{\delta} \right) \right) }{m}} + \frac{4(n+\log\left( \frac{6}{\delta} \right))}{m} \right\} \end{align}\]

We now continue by showing that \(\mathbb{P}(\mathcal{E}) \ge 1-\delta\). In particular, using a union bound, we obtain that \(\mathbb{P}(\mathcal{E}) = 1- \mathbb{P}(\mathcal{E}^\complement) \ge 1 - \left(\mathbb{P}\left(\mathcal{E}_{\text{miss}}^\complement\right) + \mathbb{P}\left(\mathcal{E}_{\text{set},x}^\complement\right) + \mathbb{P}\left(\mathcal{E}_{\text{set},y}^\complement\right) + \mathbb{P}\left(\mathcal{E}_{\text{err},x}^\complement\right) + \mathbb{P}\left(\mathcal{E}_{\text{err},y}^\complement\right) \right)\). Hence, we continue by upper bounding the complement of each event that compose \(\mathcal{E}\). We start from \(\mathbb{P}(\mathcal{E}^\complement_{\text{miss}})\). We have that: \[\begin{align} \mathbb{P}(\mathcal{E}^\complement_{\text{miss}}) \le \mathbb{P}\left( \sum_{i: \hat{x}_i=0} x_i - \mathbb{E}\left[ \sum_{i: \hat{x}_i = 0} x_i \right] \ge \frac{\sqrt{n} \log\left(\frac{6}{\delta} \right)}{m} \right) + \mathbb{P}\left( \sum_{i: \hat{y}_i=0} y_i - \mathbb{E}\left[ \sum_{i: \hat{y}_i = 0} y_i \right] \ge \frac{\sqrt{n} \log\left(\frac{6}{\delta} \right)}{m} \right) \le \frac{\delta}{3}. \end{align}\]

where the last inequality is a direct application of concentration results for the missing mass, i.e.,13.

Next, we analyze \(\mathbb{P}(\mathcal{E}_{\text{set},x}^\complement)\) and \(\mathbb{P}(\mathcal{E}_{\text{set},y}^\complement)\). Using 16, we have that: \[\begin{align} \mathbb{P}(\mathcal{E}_{\text{set},x}^\complement) = \mathbb{P}\left(\exists S \subseteq [n]: \Bigg|\sum_{i \in S} (\hat{x}_i - x_i) \Bigg| > \sqrt{\frac{2 \sum_{i \in S} \hat{x}_i\left(n+\log(\frac{24}{\delta}) \right)}{m}} + \frac{4 (n + \log(\frac{24}{\delta}))}{m-1} \right) \le \frac{\delta}{6}. \end{align}\]

Finally, it remains to analyze \(\mathbb{P}(\mathcal{E}_{\text{err},x}^\complement)\) and \(\mathbb{P}(\mathcal{E}_{\text{err},y}^\complement)\). We present our argument for \(\mathbb{P}(\mathcal{E}_{\text{err},x}^\complement)\) and the computations for \(\mathbb{P}(\mathcal{E}_{\text{err},y}^\complement)\) follows from analogous arguments. Specifically, using 16, we have that: \[\begin{align} \mathbb{P}(\mathcal{E}_{\text{err},x}^\complement) = \mathbb{P}\left( \exists S \in \mathcal{S}(2\alpha): \Bigg| \sum_{i \in S}(\hat{x}_i - x_i) \Bigg| \ge \sqrt{\frac{4\alpha \left( n+\log\left( \frac{6}{\delta} \right) \right) }{m}} + \frac{4(n+\log\left( \frac{6}{\delta} \right))}{m} \right) \le \frac{\delta}{6}. \end{align}\] Hence, we obtained that \(\mathbb{P}(\mathcal{E}) \ge 1-\delta\).

At this point, we proceed by upper bounding the Hausdorff distance under the good event \(\mathcal{E}\). We start by applying 8 and we analyze \(f_\alpha(x, \hat{x})\).²¹ We recall that: \[\begin{align} f_\alpha(x, \hat{x}) & = \frac{16}{\alpha} \left( \sup_{S \in \mathcal{S}_\alpha(x)} \sum_{i \in S} (\hat{x}_i - x_i) + \sup_{S \in \mathcal{S}_\alpha(\hat{x})} \sum_{i \in S} ( x_i - \hat{x}_i) + \sum_{i: \hat{x}_i= 0} x_i\right) \end{align}\] At this point, let us focus on \(\mathcal{S}_\alpha(\hat{x})\). With probability at least \(1-\delta\) it holds that: \[\begin{align} \mathcal{S}_\alpha(\hat{x}) & = \{S \subseteq [n]: \hat{x}_i > 0~\forall i \in S \text{ and } \sum_{i \in S} \hat{x}_i \le \tfrac\alpha2 \} \\ & \subseteq \{S \subseteq [n]: x_i > 0~\forall i \in S \text{ and } \sum_{i \in S} \hat{x}_i \le \tfrac\alpha2 \} _i > 0\implies x_i > 0} \\ & = \left\{S \subseteq [n]: x_i > 0~\forall i \in S \text{ and } \sum_{i \in S} \hat{x}_i \le \tfrac{\alpha}{2} \text{ and }\sum_{i \in S} x_i \le \tfrac\alpha2 + \Big|\sum_{i \in S} x_i - \hat{x}_i\Big| \right\} \\ & \subseteq \left\{S \subseteq [n]: x_i > 0~\forall i \in S \text{ and } \sum_{i \in S} \hat{x}_i \le \tfrac{\alpha}{2} \text{ and }\sum_{i \in S} x_i \le \tfrac\alpha2 + \sqrt{\frac{2 \sum_{i \in S} \hat{x}_i (n+\log(\frac{24}{\delta}))}{m}} + \frac{4 (n+\log(\frac{24}{\delta}))}{m-1} \right\} \\ & = \left\{S \subseteq [n]: x_i > 0~\forall i \in S \text{ and } \sum_{i \in S} \hat{x}_i \le \tfrac{\alpha}{2} \text{ and }\sum_{i \in S} x_i \le \tfrac\alpha2 + \sqrt{\frac{\alpha (n+\log(\frac{24}{\delta}))}{m}} + \frac{4 (n+\log(\frac{24}{\delta}))}{m-1} \right\} \\ & \subseteq \left\{S \subseteq [n]: x_i > 0~\forall i \in S \text{ and } \sum_{i \in S} x_i \le \tfrac\alpha2 + \sqrt{\frac{\alpha (n+\log(\frac{24}{\delta}))}{m}} + \frac{4 (n+\log(\frac{24}{\delta}))}{m-1} \right\} \\ & \subseteq \{S \subseteq [n]: x_i > 0~\forall i \in S \text{ and } \sum_{i \in S} x_i \le \alpha \} }\\ & = S_{2\alpha}(x). \end{align}\] where (i) the equality steps in the middle of these arguments follows from the fact that, with high probability, \(\sum_{i \in S} \hat{x}_i \le \frac{\alpha}{2}\) implies the additional conditions that are mentioned in the formula, and (ii) the last \(\subseteq\) step follows rom the fact that, if \(m\) satisfies 60 , then: \[\begin{align} \sqrt{\frac{\alpha (n+\log(\frac{24}{\delta})}{m}} + \frac{4 \log(\frac{24}{\delta})}{m-1} \le \frac{\alpha}{2}. \end{align}\]

Plugging this result within \(f_\alpha(x, \hat{x})\), we have that, with probability at least \(1-\delta\), \[\begin{align} f_\alpha(x, \hat{x}) & \le \frac{32}{\alpha} \left( \sup_{S \in \mathcal{S}_{2\alpha}(x)} \Bigg| \sum_{i \in S} \hat{x}_i - x_i \Bigg| + \sum_{i: \hat{x}_i= 0} x_i\right) \\ & \le \frac{32}{\alpha} \left(\sqrt{\frac{4\alpha \left( n+\log\left( \frac{6}{\delta} \right) \right) }{m}} + \frac{4(n+\log\left( \frac{6}{\delta} \right))}{m} + \sum_{i: \hat{x}_i= 0} x_i \right) } \\ & \le \frac{32}{\alpha} \left(\sqrt{\frac{4\alpha \left( n+\log\left( \frac{6}{\delta} \right) \right) }{m}} + \frac{4(n+\log\left( \frac{6}{\delta} \right))}{m} +\frac{3\sqrt{n} \log\left(\frac{6}{\delta} \right)}{m} + \mathbb{E}\left[ \sum_{i: \hat{x}_i= 0} x_i \right]\right).} \end{align}\] It thus remains to control \(\mathbb{E}[\sum_{i: \hat{x}_i=0} x_i]\). It holds that: \[\begin{align} \mathbb{E}\left[\sum_{i: \hat{x}_i=0} x_i\right] = \sum_{i \in [n]} x_i \mathbb{P}[\hat{x}_i = 0] = \sum_{i \in [n]} x_i (1-x_i)^m \le n \max_{p \in [0,1]}p(1-p)^m \le \frac{n}{m} . \end{align}\] Following similar steps, we arrived at the following high-probability bound: \[\begin{align} H(G_\alpha(x,y), \mathcal{G}_\alpha(\hat{x}, \hat{y}) & \le f_\alpha(x, \hat{x}) + f_\alpha(y, \hat{y}) \\ & \le \frac{64}{\alpha} \left(\sqrt{\frac{4\alpha \left( n+\log\left( \frac{6}{\delta} \right) \right) }{m}} + \frac{5(n+\log\left( \frac{6}{\delta} \right))}{m} +\frac{3\sqrt{n} \log\left(\frac{6}{\delta} \right)}{m}\right), \end{align}\] which concludes the proof. ◻

Proof. Let \(m_1, m_2, m_3, m_4\) be defined as follows: \[\begin{align} & m_1= 1+ \frac{4 \left(n+\log\left( \frac{24}{\delta} \right)\right)}{\alpha} \\ & m_2 = \frac{16 (192)^2 (n+\log(6/\delta))}{\alpha \epsilon^2} \\ & m_3 = \frac{960 (n+\log(6/\delta))}{\alpha \epsilon} \\ & m_4 = \frac{576 \sqrt{n} \log(6/\delta)}{\epsilon \alpha}. \end{align}\] Finally, let \(m = \lceil \max \{m_1, m_2, m_3, m_4 \}\rceil\). Since \(m \ge m_1\), we can apply 9, and using the definition of \(m\), one can verify that, with probability at least \(1-\delta\), ²² \[\begin{align} H(\mathcal{G}_\alpha(x,y), \mathcal{G}_\alpha(\hat{x}, \hat{y}) ) \le \epsilon. \end{align}\] thus concluding the proof. ◻

Proof. We first prove 61 .

Let \(A \in \mathcal{Z}_\alpha(x,y)\). We define \(\hat{A} = \lambda A\) where \(\lambda \in \mathbb{R}\) is given by: \[\begin{align} \lambda = \min\left\{ 1, \frac{\alpha}{\max \{ \max_{i \in [n]} \hat{x}^\top Ay - e_i^\top A y , \max_{j \in [n]} \hat{x}^\top A e_j - \hat{x}^\top A y\}} \right\}. \end{align}\] In the following, we assume w.l.o.g., that \(\lambda \ge 0\). If \(\lambda < 0\), one could pick \(\hat{A} = A\) and all the equilibrium constraints would be satisfied.

Now, we verify that \(A \in \mathcal{Z}_\alpha(\hat{x} , y)\). First, since \(\lambda \in (0, 1]\), we have that \(\hat{A} \in [-1,1]^{n \times n}\). Secondly, for all \(i \in [n]\) it holds that: \[\begin{align} \hat{x}^\top \hat{A} y - e_i^\top \hat{A} y & = \lambda ( \hat{x}^\top A y - e_i^\top A y) \\ & = \min\left\{ 1, \frac{\alpha}{\max \{ \max_{i \in [n]} \hat{x}^\top Ay - e_i^\top A y , \max_{j \in [n]} \hat{x}^\top A e_j - \hat{x}^\top A y\}} \right\} ( \hat{x}^\top A y - e_i^\top A y) \\ & \le \alpha, \end{align}\] where, (i) if \(\lambda = 1\), we have that \(\max_{i \in [n]} \hat{x}^\top A y - e_i^\top A y \le \alpha\), and (ii) if \(\lambda < 1\), the last step is trivial. Following similar arguments, one can prove that \(\hat{x}^\top \hat{A} e_j - \hat{x}^\top \hat{A} y \le \alpha\) for all \(j \in [n]\). Hence, \(\hat{A} \in \mathcal{Z}_\alpha(\hat{x}, y)\).

Next, we proceed by analyzing \(\| A - \hat{A}\|_{\infty}\). We consider the case where \(\lambda < 1\), otherwise \(A = \hat{A}\) and 61 is direct. We have that: \[\begin{align} \| A - \hat{A} \|_{\infty} & \le (1-\lambda) \| A \|_{\infty} \\ & \le 2(1-\lambda) \\ & \le 2 \frac{\max \{ \max_{i \in [n]} \hat{x}^\top Ay - e_i^\top A y , \max_{j \in [n]} \hat{x}^\top A e_j - \hat{x}^\top A y\} - \alpha}{\alpha} \\ & \le 2 \max \left\{ \frac{\max_{i \in [n] }\hat{x}^\top A y - e_i^\top A y - \alpha}{\alpha}, \frac{\max_{j \in [n] } \hat{x}^\top A e_j - \hat{x}^\top A y- \alpha}{\alpha} \right\} \\ & \le 2 \max \left\{ \frac{(\hat{x} - x)^\top A y}{\alpha}, \frac{\max_{j \in [n] } (\hat{x} - x)^\top A (e_j-y) }{\alpha} \right\} _\alpha(x,y)}, \end{align}\] thus concluding the proof of 61 .

The proof of 62 follows from analogous arguments. One has simply to define \(\hat{A} = \tilde{\lambda} A\) where \(\tilde{\lambda}\) is given by: \[\begin{align} \tilde{\lambda} = \min\left\{ 1, \frac{\alpha}{\max \{ \max_{i \in [n]} x^\top A \hat{y} - e_i^\top A \hat{y}, \max_{j \in [n]} x^\top A e_j - x^\top A \hat{y} \}} \right\}. \end{align}\] ◻

Proof. We start by proving 63 . Specifically, we have that: \[\begin{align} \sup_{A \in \mathcal{Z}_\alpha(x,y)} (\hat{x} - x)^\top A y & \le \sup_{A \in \mathcal{G}^x_\alpha(x,y)} (\hat{x} - x)^\top A y \\ & \le 4 \sup_{S \in \mathcal{S}_\alpha(x)} \sum_{i \in S} (\hat{x}_i - x_i) + 2 \sum_{i: x_i= 0} \hat{x}_i }, \end{align}\] where in the first inequality we have simply dropped the constraints \(x^\top A e_j - x^\top A y \le \alpha\) for all \(j \in [n]\). We can follow the same argument (i.e., simply drop the constraints) also for proving 65 .

Next, we continue with 64 . We have that: \[\begin{align} \sup_{A \in \mathcal{Z}_\alpha(x,y)}\max_{j \in [n] } (\hat{x} - x)^\top A (e_j-y) \le \sup_{B \in \mathcal{G}_\alpha^y(x,y)} \max_{j \in [n] } (\hat{x} - x)^\top B (y-e_j) \\ \sup_{S \in \mathcal{S}_\alpha(x)} \sum_{i \in S} (\hat{x}_i - x_i) + 2 \sum_{i: x_i= 0} \hat{x}_i }, \end{align}\] where, in the first step, we have dropped the constraints \(x^\top A y - e_i^\top A y \le \alpha\) and we applied a change of variable \(B = -A\). We can use the same argument (i.e., dropping constraints and change of variable) also for proving 66 . ◻

Proof. Combining 10 and 11, we can upper bound the Hausdorff distance \(H(\mathcal{Z}_\alpha(x,y), \mathcal{Z}_\alpha(\hat{x}, \hat{y}))\) with the same quantities that we obtained in General Sum Games (i.e., those appearing in 8). Hence, we can proceed as in the proof of General-Sum Games, and we obtain the same result. ◻

Proof. With probabilistic arguments, we have that: \[\begin{align} \mathbb{P}\left( \exists i \in \mathcal{I}(\beta): N_i(m) = 0 \right) & \le \sum_{i \in \mathcal{I}(\beta)} \mathbb{P}(N_i(m) = 0)\\ & \le \sum_{i: x_i \ge \beta} (1-x_i)^m \\ & \le D (1-\beta)^m \\ & \le \delta {\delta} \right)}{\log\left( \frac{1}{1-\beta} \right)}}, \end{align}\] where, in the second inequality, we have used the fact that, for any \(i\), \(N_i(m) = 0\) if and only if, for all the samples \(m\), the outcome \(i\) is never observed.

The corollary is a direct application of this claim by setting \(\beta = p_{\min}\). ◻

Proof. By Pinsker’s inequality we have: \[\|\hat{p}_m-p\|_1 \leq \sqrt{2\mathrm{KL}(\hat{p}_m,p)}\] where \(\mathrm{KL}(p_1,p_2)\) denotes the Kullback–Leibler divergence between distributions \(p_1\) and \(p_2\).

Now, applying Proposition 1 in [44], we obtain \[\mathbb{P}\left[\forall m \in \mathbb{N}^*,\: m\mathrm{KL}(\hat{p}_m,p) \leq \log\left(\frac{1}{\delta}\right) + (D-1)\log \left(e\left(1+\frac{m}{D-1}\right) \right) \right] \geq 1-\delta.\] Thus, we obtained that: \[\mathbb{P}\left[\|\hat{p}_m-p\|_1 \leq \sqrt{\frac{2}{m} \left( \log\left(\frac{1}{\delta}\right) + (D-1)\log \left(e\left(1+\frac{m}{D-1}\right) \right)\right) } \right] \geq 1-\delta.\] At this point, we observe that: \[\sqrt{\frac{2}{m} \left( \log\left(\frac{1}{\delta}\right) + (n-1)\log \left(e\left(1+\frac{m}{D-1}\right) \right)\right) } \leq \sqrt{\frac{2\log(1/\delta) + 2D \log(6m)}{m}}\] Thus concluding the proof. ◻

Proof. We have that: \[\begin{align} \mathrm{KL}(\mathbb{P}, \mathbb{Q}) & = \sum_{i \in [n-1]: v_i = 1} \frac{\beta + \gamma\beta }{n-1} \log\left(1+\gamma \right) + \sum_{i \in [n-1]: v_i = -1} \frac{\beta - \gamma\beta }{n-1} \log\left(1-\gamma \right) \\ & = \frac{1}{2} \beta (1+\gamma) \log(1+\gamma) + \frac{1}{2} \beta (1-\gamma) \log(1-\gamma) \\ & = \frac{\beta}{2} \left( \log(1-\gamma^2) + \gamma \log(1+\gamma) - \gamma \log(1-\gamma) \right) \\ & \le \frac{\beta}{2} \left( \gamma \log(1+\gamma) - \gamma \log(1-\gamma) \right)\\ & \le \frac{\beta}{2} \left( \gamma^2 + \gamma\left(\frac{1}{1-\gamma} - 1\right) \right) {1-x} -1 for x \in (0,1)} \\ & \le 2\beta \gamma^2. \end{align}\] This concludes the proof. ◻

Proof. We start by proving 67 . Fix a set \(S \in \mathcal{S}(\beta)\), then \(\sum_{i \in S} \hat{p}_i\) is the empirical mean of a Bernoulli r.v. with mean \(\mu = \sum_{i \in S} p_i\). Hence, for \(\delta' \in (0,1)\), a standard application of Bernstein’s inequality [45] yields \[\begin{align} \mathbb{P}\left( \Bigg| \sum_{i \in S} ( p_i - \hat{p}_i) \Bigg| > \sqrt{\frac{4\beta \log\left( \frac{1}{\delta'} \right) }{m}} + \frac{4\log\left( \frac{1}{\delta'} \right)}{m}\right) \le \delta', \end{align}\] where we have used that \(\mathbb{V}\mathrm{ar}(\sum_{i \in S} p_i) \le \sum_{i \in S} p_i \le \beta\).

Now, for any value of \(\beta\), the cardinality of \(\mathcal{S}(\beta)\) is bounded by \(2^D\). Hence, for any \(\delta' \in (0,1)\) we have that: \[\begin{align} \mathbb{P}\left( \exists S \in \mathcal{S}(\beta): \Bigg| \sum_{i \in S} ( p_i - \hat{p}_i) \Bigg| > \sqrt{\frac{4\beta \log\left( \frac{1}{\delta'} \right) }{m}} + \frac{4\log\left( \frac{1}{\delta'} \right)}{m}\right) \le 2^D \delta'. \end{align}\] Picking \(\delta' = \frac{\delta}{2^D}\) concludes the proof.

68 follows from similar arguments, but we replaced Bernstein’s inequality with its empirical version [46]. In particular, the empirical Bernstein’s inequality, replace the variance in the Bernstein inequality with the sample variance. In the following, we show how the sample variance of a Bernoulli r.v. with mean \(q\) can be upper bouded with \(2 \hat{q}\). Let Denote by \(Z_1, \dots, Z_m \sim q\) the \(m\) independent samples from \(q\). Then: \[\begin{align} \hat{\mathbb{V}\mathrm{ar}}(\hat{q}) & = \frac{1}{m(m-1)} \sum_{i < j} (Z_i - Z_j)^2 \\ & = \frac{1}{m-1} \sum_{i=1}^m (Z_i - p)^2 \\ & = \frac{m}{m-1} \hat{q} (1-\hat{q}) \\ & \le 2 \hat{q} \end{align}\] From this follows the result of 68 . ◻

Proof. This is a well-known result (e.g. [38]). For completeness, we prove 71 . The proof of 72 follows analogous arguments. We first show that (i) \(\Rightarrow\) (ii). Assume \(x^\top A y \le e_i^{\top}Ay\) for all \(i \in [n]\). Rewrite \(x^\top A y\) as follows: \[x^\top A y = \sum_{k \in [n]} x_k \sum_{j \in [n]} y_j A_{ij} = \sum_{k\in \mathrm{supp}(x)} x_k \sum_{j \in [n]} y_j A_{ij}, = \sum_{k\in \mathrm{supp}(x)} x_k \left( e_k^\top A y \right)\] since \(x_k=0\) for \(k\notin \mathrm{supp}(x)\). Note that \(\sum_{k \in S}x_i =1\). Then, since \(x_k>0\) for \(k\in \mathrm{supp}(x)\) and each \(e_k^{\top}Ay \ge x^\top A y\) (by assumption), it must follows that \(e_k^\top A y = x^\top A y\) for all \(k \in \mathrm{supp}(x)\). Hence, we have proved the first condition of (ii) and it remains to prove that for all \(j \notin \mathrm{supp}(x)\) and all \(i \in \mathrm{supp}(x)\), we have that \(e_i^\top A y \le e_j^\top A y\).

Fix any \(j \notin \mathrm{supp}(x)\). By assumption (i), we have \(x^\top A y \le e_j^\top A y\). Combining this with the equality \(e_i^\top A y = x^\top A y\) for all \(i \in \mathrm{supp}(x)\), we obtain \[e_i^\top A y \le e_j^\top A y \qquad \forall\, i \in \mathrm{supp}(x),\;\forall\, j \notin \mathrm{supp}(x),\] which concludes the proof of \((i) \Rightarrow (ii)\).

We conclude the proof by showing that (ii) \(\Rightarrow\) (i). Assume (ii) holds. Let \(c\) denote the common value \(e_i^{\top}Ay\) for \(i\in \mathrm{supp}(x)\). Then: \[x^{\top}Ay = \sum_{i\in \mathrm{supp}(x)} x_i\, \left( e_i^{\top}Ay\right) = \sum_{i\in S} x_i\, c = c.\] Hence, \(x^\top A y \le e_i^\top A y\) for all \(i \in \mathrm{supp}(x)\).

For any \(j \notin \mathrm{supp}(x)\), (ii) gives \(e_j^{\top}Ay \ge c=x^\top A y\), which concludes the proof. ◻

Proof. First, it is easy to see that: \[\begin{align} \bar{T} & \le \max \left\{ \inf \left\{t \in \mathbb{N}: \frac{\log(c_1/\delta)}{t} \le \frac{K^2}{2} \right\}, \inf \left\{t \in \mathbb{N}: \frac{n\log(c_2t)}{t} \le \frac{K^2}{2} \right\} \right\} \\ & \le 2 \left( \inf \left\{t \in \mathbb{N}: \frac{\log(c_1/\delta)}{t} \le \frac{K^2}{2} \right\} + \inf \left\{t \in \mathbb{N}: \frac{n\log(c_2t)}{t} \le \frac{K^2}{2} \right\} \right) \\ & \le 2 \left( 1 + \frac{4\log(c_1/\delta)}{K^2} + \inf \left\{t \in \mathbb{N}: \frac{n\log(c_2t)}{t} \le \frac{K^2}{2} \right\} \right) \\ & \mathrel{\vcenter{:}}= 2 \left( 1 + \frac{4\log(c_1/\delta)}{K^2} + \tilde{T} \right). \end{align}\]

It remains to analyze the term: \[\tilde{T} =\inf \left\{t \in \mathbb{N}: \frac{n\log(c_2t)}{t} \le \frac{K^2}{2} \right\} = \left\{ t \in \mathbb{N}: t \ge \frac{2n \log(c_2t)}{K^2} \right\}.\] By definition, for \(\tilde{T}-1\), we have that: \[\begin{align} \label{eq:tech-lemma} \tilde{T} - 1 < \frac{2n \log(c_2(\tilde{T}-1))}{K^2}. \end{align}\tag{73}\] Since \(\log(x) \le \sqrt{x}\), we have that: \[\begin{align} \sqrt{\tilde{T} - 1} < \frac{2n\sqrt{c_2}}{K^2}, \end{align}\] which leads to: \[\begin{align} \tilde{T} - 1 < \left( \frac{2n\sqrt{c_2}}{K^2} \right)^2. \end{align}\] Plugging this result within 73 , we obtain: \[\begin{align} \tilde{T} < \frac{4n}{K^2} \log\left( \frac{2nc_2}{K^2} \right) + 1, \end{align}\] which leads to the desired result. ◻

Proof. For any \(y \in \mathcal{Y}\), let \(c(y) \in \operatornamewithlimits{argmin}_{c \in F(\hat{x}_1, x_2)} d(y,c)\). Note that, by Heine-Cantor, this minimum is attained since \(d(y, \cdot)\) is a continuous function and \(F\) is compact-valued. Then, recall that: \[\begin{align} \label{eq:decomposition-lemma-eq-1} H_d(F(x_1,x_2), F(\hat{x}_1, \hat{x}_2) & = \max \left\{ \sup_{y \in F(x_1,x_2)} \inf_{\hat{y} \in F(\hat{x}_1, \hat{x}_2)} d(y, \hat{y}), \sup_{\hat{y} \in F(\hat{x}_1,\hat{x}_2)} \inf_{ y \in F( x_1, x_2)} d(y, \hat{y}) \right\} \end{align}\tag{74}\] Now, focus on the first term. We have that: \[\begin{align} \sup_{y \in F(x_1,x_2)} \inf_{\hat{y} \in F(\hat{x}_1, \hat{x}_2)} d(y, \hat{y}) & \le \sup_{y \in F(x_1,x_2)} \inf_{\hat{y} \in F(\hat{x}_1, \hat{x}_2)} \left( d(y, c(y)) + d(c(y), \hat{y}) \right)\\ & = \sup_{y \in F(x_1,x_2)} \left( d(y, c(y)) + \inf_{\hat{y} \in F(\hat{x}_1, \hat{x}_2)} d(c(y), \hat{y}) \right) \\ & \le \sup_{y \in F(x_1,x_2)} d(y, c(y)) + \sup_{y \in F(x_1,x_2)} \inf_{\hat{y} \in F(\hat{x}_1, \hat{x}_2)} d(c(y), \hat{y}) \\ & \le H_d(F(x_1, x_2), F(\hat{x}_1, x_2)) + \sup_{y \in F(x_1,x_2)} \inf_{\hat{y} \in F(\hat{x}_1, \hat{x}_2)} d(c(y), \hat{y})\\ & \le H_d(F(x_1, x_2), F(\hat{x}_1, x_2)) + H_d(F(\hat{x}_1, x_2), F(\hat{x}_1, \hat{x}_2)) _1, x_2)} \end{align}\] Similarly, by using the triangular inequality with \(c(\hat{y})\), one has that: \[\begin{align} \sup_{\hat{y} \in F(\hat{x}_1,\hat{x}_2)} \inf_{ y \in F( x_1, x_2)} d(y, \hat{y}) \le H_d(F(x_1, x_2), F(\hat{x}_1, x_2)) + H_d(F(\hat{x}_1, x_2), F(\hat{x}_1, \hat{x}_2)). \end{align}\] Plugging these results within 74 , concludes the proof. ◻

Proof. This is a direct application of 21. ◻