This paper considers a two-player game where each player chooses a resource from a finite collection of options. Each resource brings a random reward. Both players have statistical information regarding the rewards of each resource. Additionally, there exists an information asymmetry where each player has knowledge of the reward realizations of different subsets of the resources. If both players choose the same resource, the reward is divided equally between them, whereas if they choose different resources, each player gains the full reward of the resource. We first implement the iterative best response algorithm to find an $\epsilon$-approximate Nash equilibrium for this game.  This method of finding a Nash equilibrium may not be desirable when players do not trust each other and place no assumptions on the incentives of the opponent.  To handle this case, we solve the problem of maximizing the worst-case expected utility of the first player.  The solution leads to counter-intuitive insights in certain special cases. To solve the general version of the problem, we develop an efficient algorithmic solution that combines online-convex optimization and the drift-plus penalty technique.

Resource-sharing games, congestion games, potential games, worst-case utility maximization, drift-plus penalty method

§ INTRODUCTION

We consider the following game with two players A and B. There are $n$ resources, each denoted by an integer between $1$ and $n$. Each player selects a resource without knowledge about the other player's selection. The state of the game is described by the random vector $\vec{W} = (W_1,W_2,...,W_n)^{\top}$, where  $W_k$ is the reward random variable of resource $k$. We assume the $W_k$ to be independent random variables for each $1\leq k \leq n$, taking non-negative real values. If both players choose the same resource $k$, each gets a utility of $W_k/2$. If they choose different resources $k,l$, they get utilities of $W_k$ and $W_l$, respectively. It is assumed that the mean and the variance of $W_k$  exist and are finite for each $1\leq k \leq n$. Both players know the distribution of $\vec{W}$. Our formulation allows for an information asymmetry between the players. In particular, $\{1,2,\dots,n\}$ can be partitioned into four sets $\{\mathcal{A},\mathcal{B},\mathcal{C},\mathcal{AB}\}$ where only player A observes the realizations of $W_k$ for $k \in \mathcal{A}$, only player B observes the realizations of $W_k$ for $k \in \mathcal{B}$, no player observes the realizations of $W_k$ for $k \in \mathcal{C}$, and both players
observe the realizations of $W_k$ for $k \in \mathcal{AB}$.

The above game can be viewed as a stochastic version of the class of games defined in [1], which are resource-sharing games, also known as congestion games. In resource-sharing games, players compete for a finite collection of resources. In a single turn of the game, each player is allowed to select a subset of the collection of resources, where the allowed subsets make up the action space of the player. Each resource offers a reward to each player who selected the particular resource, where the reward offered depends on the number of players who selected it. The relationship between the reward offered to a player by a resource and the number of users selecting it is captured by the reward function of the resource. A player's utility is equal to the sum of the rewards offered by the resources in the subset selected by the player. In [1], it is established that the above game has a pure-strategy (deterministic) Nash equilibrium.

Although in the classical setting, these games ignore the stochastic nature of the rewards offered by the resources, the idea of resource-sharing games has been extended to different stochastic versions [2, 3]. Versions of the game with information asymmetry have been considered through the work of [4] in the context of Bayesian games, which considers the information design problem for resource-sharing with uncertainty. Similar Bayesian games have also been considered in [5, 6]. It should be noted that in general resource-sharing games, no conditions are placed on the reward functions of the resources. The special case where the reward functions are non-decreasing in the number of players selecting the resource is defined as cost-sharing games [7]. These games are typically treated as games where a cost is minimized rather than a utility being maximized. In fair cost-sharing games, the cost of a resource is divided equally among the players selecting the resource. We consider a fair reward allocation model, where the reward of a resource is equally shared among the players selecting the resource. It should be noted that in this model, the players have opposite incentives compared to a fair-cost sharing model.

The work on resource-sharing games assumes that the players either cooperate or have the incentive to maximize a private or a social utility. It is interesting to consider a stochastic version of the game with asymmetric information between players who do not necessarily trust each other and who place no assumptions on the incentives of the opponents. In this context, the players have no signaling or external feedback and take actions based only on their personal knowledge of the reward realizations for a subset of the resource options. In this paper, we consider the above problem and limit our attention to the two-player singleton case, where each player can choose only one resource.

In the first part of the paper, we provide an iterative best response algorithm to find an $\epsilon$-approximate Nash equilibrium of the system. In the second part, we solve the problem of maximizing the worst-case expected utility of the first player. We solve the problem in two cases. The first case is when both players do not know the realizations of the reward random variables of any of the resources, in which case an explicit solution can be constructed. This case yields a counter-intuitive solution that provides insight into the problem. One such insight is that, while it is always optimal to choose from a subset of resources with the highest average rewards, within that subset, one chooses the higher-valued rewards with lower probability. For the second case, we solve the general version of the problem by developing an algorithm that leverages the online optimization technique [8, 9] and the drift-plus penalty method [10]. This algorithm generates a mixture of $\mathcal{O}(1/\varepsilon^2)$ pure strategies, which, when used in an equiprobable mixture, provides a utility within $\varepsilon$ of optimality on average.  Below we summarize our major contributions.

* We consider the problem of a two-player singleton stochastic resource-sharing game with asymmetric information. We first provide an iterative best response algorithm to find an $\epsilon$-approximate Nash equilibrium of the system. This equilibrium analysis uses potential game concepts.

* When the players do not trust each other and place no assumptions on the incentives of the opponent, we solve the problem of maximizing the worst-case expected utility of the first player using a novel algorithm that leverages techniques from online optimization and the drift-plus penalty methods. The algorithm developed can be used to solve the general unconstrained problem of finding the randomized decision $\alpha \in \{1,2,\dots,n\}$ which maximizes $\mathbb{E}\{h(\vec{x};\vec{\Theta})\}$, where $\vec{x} \in \mathbb{R}^n$ with $x_k = \mathbb{E}\{\Gamma_k \mathbbm{1}_{\{\alpha = k\}}\}$, $\vec{\Theta} \in \mathbb{R}^m$ and $\vec{\Gamma} \in \mathbb{R}^n$ are non-negative random vectors with finite second moments, and $h$ is a concave function such that $\tilde{h}(\vec{x}) = \mathbb{E}\{h(\vec{x};\vec{\Theta})\}$ is Lipschitz continuous, entry-wise non-decreasing and has bounded subgradients.

* We show our algorithm uses a mixture of only $\mathcal{O}(1/\varepsilon^2)$ pure strategies using a detailed analysis of the sample path of related virtual queues (our preliminary work on this algorithm used a mixture of $\mathcal{O}(1/\varepsilon^3)$ pure strategies). Virtual queues are also used for constrained online convex optimization in [9], but our problem structure is different and requires a different and more involved treatment.

§.§ Background on Resource-Sharing Games

The classical resource-sharing game defined in [1] is a tuple $(\mathcal{M}, \mathcal{N}, \mathcal{T}, \vec{r})$, where $\mathcal{M}$ is a set of $m$ players, $\mathcal{N}$ is a set of $n$ resources, $\mathcal{T} = \mathcal{T}_1 \times \mathcal{T}_2\times...\times \mathcal{T}_m$ where $\mathcal{T}_j$ is the set of possible actions of player $j$ (which is a subset of $2^{\mathcal{N}}$), and $\vec{r} = (r_1,r_2,...,r_n)$, where $r_i : \mathbb{N}_0 \to \mathbb{R}$ is the reward function of resource $i$.  Here we use the notation $\mathbb{N}_0 = \mathbb{N} \cup \{0\}$. Each player has complete knowledge about the tuple $(\mathcal{M}, \mathcal{N}, \mathcal{T}, \vec{r})$, but they do not have knowledge of the actions chosen by other players. For an action profile $\vec{a} = (a_1,a_2,...,a_m) \in \mathcal{T}$, the count function $\#$ is a function from $\mathcal{N} \times \mathcal{T}$  to $\mathbb{N}_0$ where $\#(i,\vec{a}) = \sum_{k=1}^m \mathbbm{1}_{\{i \in a_k\}}$. In other words, $\#(i,\vec{a})$ is the number of players choosing the resource $i$ under the action profile $\vec{a}$. We call the quantity $r_i(\#(i,\vec{a}))$ the per-player reward of resource $i$ under the action profile $\vec{a}$. The utility $u_j$ of player $j$ is a function from $\mathcal{T}$ to $\mathbb{R}$, where $u_j(\vec{a}) = \sum_{i=1}^n \mathbbm{1}_{\{i\in a_k\}} r_i(\#(i,\vec{a}))$. In other words, $u_j(\vec{a})$ is the sum of the per-player rewards of the resources chosen by player $j$ under the action profile $\vec{a}$.  Resource-sharing games fall under the general category of potential games [11]. Potential games are the class of games for which the change of reward of any player as a result of changing their strategy can be captured by the change of a global potential function.

Many game variations of the resource-sharing game have been studied [12]. Weighted resource-sharing games [13], games with player-dependent reward functions <cit.>, and games with resources having preferences over players [15] are some of the extensions. Singleton games, where each player is allowed to choose only one resource, have also been explored explicitly in the literature [16, 17]. Some of the extensions of the classical resource-sharing game possess pure-Nash equilibrium in the singleton case. Two examples would be the games with player-specific reward functions for a resource [14] and the games with priorities where the resources have preferences over the players [15].

Resource-sharing games have been extended to several stochastic versions. For instance, [2] considers the selfish routing problem with risk-averse players in a network with stochastic delays. The work of [3] considers two scenarios where in the first scenario, each player participates in the game with a certain probability, and in the second scenario, the reward functions are stochastic. The problem of information asymmetry in resource-sharing games has been addressed through the work of [18, 4, 5, 6]. The work of [18] considers a network congestion game where the players have different information sets regarding the edges of the network. Also, [4] considers a scenario with a single random state $\theta$, which determines the reward functions. The realization of $\theta$ is known to a game manager who strategically provides recommendations (signaling) to the players to minimize the social cost. An information asymmetry arises among the players in this case due to the actions of the game manager during private signaling, where the game manager provides player-specific recommendations.

Resource-sharing games appear in a variety of applications such as service chain composition [19], congestion control [20], network design [21], load balancing networks [22, 23], resource sharing in wireless networks [24], spectrum sharing [25], radio access selection [26] and migration of species [27]. The Multiple Access (MAC) [28] and network selection [29] are classic applications of resource sharing in wireless communications. In a multiple-access game, two users attempt to transmit using a shared channel, and the transmission during a given time slot is successful only if one player transmits [30, 31]. The network selection game, where players choose a channel from a collection of channels and divide the data rate provided by a channel in case of a collision, can be treated using the proposed resource-sharing game.

Our formulation differs from the literature on resource-sharing games since we consider a scenario that is difficult to be analyzed using the standard equilibrium-based approaches. This is due to the fact that the players do not trust each other and place no assumptions on the incentives of the opponents, and they take action in the absence of a signaling mechanism or external feedback by just using their knowledge of the reward random variables. This motivates our formulation as a one-shot problem tackled using worst-case expected utility maximization.

§.§ Notation

We use calligraphic letters to denote sets. Vectors and matrices are denoted by boldface characters. For integers $n$ and $m$, we denote by $[n:m]$ the set of integers between $n$ and $m$ inclusive.
Given a vector $\vec{w} \in \mathbb{R}^m$, both $w_k$ is used to denote the $k$-th element of $\vec{w}$; $\vec{w}_{k:l}$ for $l\geq k$ represents
the $l-k+1$ dimensional sub-vector $(w_k,w_{k+1},...,.w_l)^{\top}$ of $\vec{w}$; for a subset $\mathcal{S}$ of integers from $1$ to $n$
$\{w_k; k \in\mathcal{S}\}$ represents the sub-vector of $\vec{w}$ with index in $\mathcal{S}$. For $\vec{z} \in \mathbb{R}^m$, we use $\lVert \vec{z}\rVert_2$ to denote the standard Euclidean norm (L2 norm) of $\vec{z}$. For a function $f:\mathbb{R}^m \to \mathbb{R}$, and $\vec{z} \in \mathbb{R}^m$,  we use $f^{'}(\vec{z}) = (f^{'}_{1}(\vec{z}),f^{'}_2(\vec{z}),\cdots,f^{'}_m(\vec{z}))$ to denote a subgradient of $f$ at $\vec{z}$.

§ FORMULATION

Denote $\vec{X} = \{W_k; k\in \mathcal{A}\}$, $\vec{Y} = \{W_k; k\in \mathcal{B}\}$, $\vec{Z} = \{W_k; k\in \mathcal{AB}\}$, and $\vec{V} = \{W_k; k\in \mathcal{C}\}$. Recall that $\vec{X}$ is known only to player A, $\vec{Y}$ is known only to player B, $\vec{Z}$ is known to both players and $\vec{V}$ is known to neither. Let us define $\mathcal{A}^c =[1:n]\setminus \mathcal{A}$, and $\mathcal{B}^c = [1:n]\setminus \mathcal{B}$. Let $|\mathcal{A}| = a$, $|\mathcal{B}| = b$, $|\mathcal{C}| = c$ and $|\mathcal{AB}| = d$. Therefore, $a+b+c+d = n$. Without loss of generality, we assume $\mathcal{A} = [1:a]$, $\mathcal{B} = [a+1:a+b]$, $\mathcal{C} = [a+b+1:a+b+c]$, and $\mathcal{AB} = [a+b+c+1:n]$.

Let $R^{C}(g^A,g^B)$ be the random variable representing the utility of player  $C \in \{A,B\}$, given that player A uses strategy $g^A$, and player B uses strategy $g^B$. General strategies for players A and B can be represented by the Borel-measurable functions,

\begin{align}
&g^A:[0,1) \times \mathbb{R}_{\geq 0}^{a+d} \rightarrow [1:n], \\
&g^B:[0,1) \times \mathbb{R}_{\geq 0}^{b+d} \rightarrow [1:n],
\end{align}

\begin{align}
&\alpha^A = g^A(U^A, \vec{X},\vec{Z}),\\
&\alpha^B = g^B(U^B, \vec{Y},\vec{Z}),
\end{align}

are the resources chosen by players A and B, respectively. Here $U^A$ and $U^B$ are independent randomization variables uniformly distributed in [0,1) and independent of $\vec{W}$. A pure strategy for player A is a function $g^A$ that does not depend on $U^A$, whereas a mixed strategy is a function $g^A$ that depends on $U^A$. Hence, we drop the randomization variable when depicting a pure strategy. Pure strategies and mixed strategies for player B are defined similarly. Let $\mathcal{S}^A$ and $\mathcal{S}^B$ denote the sets of all possible strategies for players A and B, respectively.

It turns out that our analysis is simplified when $\vec{Z}$ is fixed. Fixing $\vec{Z}$ does not affect the symmetry between players A and B since $\vec{Z}$ is observed by both players A and B. Hereafter, we conduct the analysis by considering all quantities conditioned on $\vec{Z}$.

\begin{align} \label{eqn:pq_A_pdef}
&p^A_{k} = \mathbb{E}\{\mathbbm{1}_{\{\alpha^A = k\}}|\vec{Z}\}\text{ for } 1\leq k \leq n,\nonumber\\&q^A_{k} = \mathbb{E}\{W_k\mathbbm{1}_{\{\alpha^A = k\}}|\vec{Z}\} \text{ for } k \in \mathcal{A},
\end{align}

\begin{align} \label{eqn:pq_B_pdef}
&p^B_{k} = \mathbb{E}\{\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\}\text{ for } 1\leq k \leq n,\nonumber\\&q^B_{k} = \mathbb{E}\{W_k\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\} \text{ for } k \in \mathcal{B}.
\end{align}

Note that $p^A_{k}$ and $p^B_k$ are the conditional probabilities of players A and B choosing $k$ given $\vec{Z}$. Define the vectors $\vec{p}^A = \{p^A_k; 1\leq k \leq n\}$, $\vec{q}^A = \{q^A_k; k \in \mathcal{A}\}$, $\vec{p}^B = \{p^B_k; 1\leq k \leq n\}$, and $\vec{q}^B = \{q^B_k;  k \in \mathcal{B}\}$.
For $1\leq k \leq n$, define $E_k = \mathbb{E}\{W_k|\vec{Z}\}$. Hence we have,

\begin{equation}
E_k =
\begin{cases}
W_k & \text{if } k \in \mathcal{AB},\\
\mathbb{E}\{W_k\} & \text{ otherwise},
\end{cases}
\end{equation}

which uses the independence of $W_k$ and $\vec{Z}$ when $k \not\in \mathcal{AB}$.

Note that the utility achieved by player A given the strategies $g^A$ and $g^B$ can be written as

\begin{align}\label{eqn:calc_obj}
R^A(g^A,g^B) = \sum_{k=1}^{n} W_k\left(\mathbbm{1}_{\{\alpha^A = k\}} - \frac{1}{2} \mathbbm{1}_{\{\alpha^A = k\}}\mathbbm{1}_{\{\alpha^B = k\}}\right).
\end{align}

Given the strategies $g^A$ and $g^B$, we provide an expression for the expected utility of player A given $\vec{Z}$, where the expectation is over the random variables $\vec{X},\vec{Y},\vec{V}$, and the possibly random actions $\alpha^A$, and $\alpha^B$. Taking expectations of (<ref>) gives,

\begin{align}\label{eqn:exp^A_r_sim}
\mathbb{E}\{&R^A(g^A,g^B)|\vec{Z}\} = \sum_{k=1}^{n} \mathbb{E}\{W_k \mathbbm{1}_{\{\alpha^A = k\}}|\vec{Z}\} -\frac{1}{2}\sum_{k=1}^{n} \mathbb{E}\{W_k\mathbbm{1}_{\{\alpha^A = k\}}\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\}\nonumber\\&= \sum_{k\in\mathcal{A}} \mathbb{E}\{W_k \mathbbm{1}_{\{\alpha^A = k\}}|\vec{Z}\}+\sum_{k\in\mathcal{A}^c} \mathbb{E}\{W_k|\vec{Z}\}\mathbb{E}\{\mathbbm{1}_{\{\alpha^A = k\}}|\vec{Z}\} -\frac{1}{2}\sum_{k=1}^{n} \mathbb{E}\{W_k\mathbbm{1}_{\{\alpha^A = k\}}\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\} \nonumber\\&= \sum_{k\in \mathcal{A}} q^A_{k}+\sum_{k\in \mathcal{A}^c} E_kp^A_k -\frac{1}{2}\sum_{k=1}^{n} \mathbb{E}\{W_k\mathbbm{1}_{\{\alpha^A = k\}}\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\}.
\end{align}

Note that given $\vec{Z}$, the random variables $\alpha^A$ and $\alpha^B$ are independent. Hence, we can split the last term (<ref>) as follows,

\begin{align}\label{eqn:simplifying_exp_rwd}
\sum_{k=1}^{n} &\mathbb{E}\{W_k\mathbbm{1}_{\{\alpha^A = k\}}\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\} = \sum_{k\in \mathcal{A}} \mathbb{E}\{W_k\mathbbm{1}_{\{\alpha^A = k\}}\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\}+\sum_{k \in \mathcal{B}} \mathbb{E}\{W_k\mathbbm{1}_{\{\alpha^A = k\}}\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\}\nonumber\\&+\sum_{k \in \mathcal{C} \cup \mathcal{AB}} \mathbb{E}\{W_k\mathbbm{1}_{\{\alpha^A = k\}}\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\}= \sum_{k \in \mathcal{A}} \mathbb{E}\{W_k\mathbbm{1}_{\{\alpha^A = k\}}|\vec{Z}\}\mathbb{E}\{\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\}\nonumber\\&+\sum_{k\in \mathcal{B}} \mathbb{E}\{\mathbbm{1}_{\{\alpha^A = k\}}|\vec{Z}\}\mathbb{E}\{W_k\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\}+\sum_{k \in \mathcal{C} \cup \mathcal{AB}} E_k\mathbb{E}\{\mathbbm{1}_{\{\alpha^A = k\}}|\vec{Z}\}\mathbb{E}\{\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\} \nonumber\\&= \sum_{k\in \mathcal{A}} q^A_{k}p^B_k+\sum_{k\in \mathcal{B}} p^A_{k}q^B_{k}+\sum_{k \in \mathcal{C} \cup \mathcal{AB}} E_k p^A_{k}p^B_{k}.
\end{align}

§ COMPUTING THE $\EPSILON$-APPROXIMATE NASH EQUILIBRIUM

This section focuses on finding an  $\epsilon$-approximate Nash-equilibrium of the game. Fix $\epsilon>0$. A strategy pair $(g^A,g^B)$ is defined as an $\epsilon$-approximate Nash equilibrium if neither player can improve its expected reward by more than $\epsilon$ if it changes its strategy (while holding the strategy of the other player fixed).

Combining (<ref>) with (<ref>) we have that,

\begin{align}\label{eqn:As_rwd}
\mathbb{E}\{&R^A(g^A,g^B)|\vec{Z}\} =  \sum_{k\in \mathcal{A}} q^A_{k}+\sum_{k\in \mathcal{A}^c} \hspace{-2mm}  E_kp^A_k - \frac{1}{2}\left(\sum_{k \in \mathcal{A}} q^A_{k}p^B_k+\sum_{k \in \mathcal{B}} p^A_{k}q^B_{k}+\hspace{-2mm} \sum_{k \in \mathcal{C} \cup \mathcal{AB}} \hspace{-3mm} E_k p^A_{k}p^B_{k}\right).
\end{align}

Similarly, for player B, we have,

\begin{align}\label{eqn:Bs_rwd}
\mathbb{E}\{&R^B(g^A,g^B)|\vec{Z}\} =  \sum_{k\in \mathcal{B}} q^B_{k}+\sum_{k\in \mathcal{B}^c} \hspace{-2mm}  E_kp^B_k - \frac{1}{2}\left(\sum_{k \in \mathcal{A}} q^A_{k}p^B_k+\sum_{k \in \mathcal{B}} p^A_{k}q^B_{k}+\hspace{-2mm} \sum_{k \in \mathcal{C} \cup \mathcal{AB}} \hspace{-3mm} E_k p^A_{k}p^B_{k}\right).
\end{align}

First, we focus on finding the best response for players A and B, given the other player's strategy is fixed.

The best response for players A and B  are given by $\alpha^A = \arg\max_{1 \leq k \leq n} A_k$, and $\alpha^B = \arg\max_{1 \leq k \leq n} B_k$, where $A_k$ and $B_k$ are given by,

\begin{align}\label{eqn:A_best_response}
A_k = \begin{cases}
W_k\left(1-\frac{p^B_k}{2}\right) & \text{ if }  k \in \mathcal{A},\\
E_k - \frac{q^B_{k}}{2} & \text{ if } k \in \mathcal{B},\\
E_k\left(1-\frac{p^B_k}{2}\right) & \text{ if } k \in \mathcal{C} \cup \mathcal{AB},
\end{cases}
B_k = \begin{cases}
E_k - \frac{q^A_{k}}{2} & \text{ if } k \in \mathcal{A},\\
W_k\left(1-\frac{p^A_k}{2}\right) & \text{ if } k \in \mathcal{B},\\
E_k\left(1-\frac{p^A_k}{2}\right) & \text{ if } k \in \mathcal{C} \cup \mathcal{AB}.
\end{cases}
\end{align}

We find the best response for A, and the best response for B follows similarly. Notice that we can rearrange (<ref>) as,

\begin{align}
&\mathbb{E}\{R^A(g^A,g^B)|\vec{Z}\} =  \sum_{k\in \mathcal{A}} q^A_{k}\left(1-\frac{p^B_k}{2}\right)+\sum_{k\in \mathcal{B}} p^A_k\left(E_k - \frac{q^B_{k}}{2}\right)  +\hspace{-3mm}\sum_{k \in \mathcal{C} \cup \mathcal{AB}}\hspace{-2mm}p^A_kE_k\left(1-\frac{p^B_k}{2}\right)\nonumber\\&= \sum_{k\in \mathcal{A}}\mathbb{E}\{W_k\mathbbm{1}_{\{\alpha^A = k\}}|\vec{Z}\}\left(1-\frac{p^B_k}{2}\right)+\sum_{k\in \mathcal{B}}\mathbb{E}\{\mathbbm{1}_{\{\alpha^A = k\}}|\vec{Z}\}\left(E_k - \frac{q^B_{k}}{2}\right)\nonumber\\&\ \ \ \ +\sum_{k \in \mathcal{C} \cup \mathcal{AB}}E_k\mathbb{E}\{\mathbbm{1}_{\{\alpha^A = k\}}|\vec{Z}\}\left(1-\frac{p^B_k}{2}\right) \\&= \mathbb{E}\left\{\sum_{k\in \mathcal{A}}W_k\left(1-\frac{p^B_k}{2}\right)\mathbbm{1}_{\{\alpha^A = k\}}+\sum_{k\in \mathcal{B}}\left(E_k - \frac{q^B_{k}}{2}\right)\mathbbm{1}_{\{\alpha^A = k\}}+\hspace{-3mm}\sum_{k \in \mathcal{C} \cup \mathcal{AB}}E_k\left(1-\frac{p^B_k}{2}\right)\mathbbm{1}_{\{\alpha^A = k\}} \Bigg{|}\vec{Z}\right\}.\nonumber
\end{align}

The above expectation is maximized when A chooses according to the given policy.

Next, we find a potential function for the game. A potential function is a function of the strategies of the players such that the change of the utility of a player when he changes his strategy (while the strategies of other players are held fixed) is equal to the change of the potential function [11].

The function $H(g^A,g^B)$ given by,

\begin{align}\label{eqn:potential}
H(g^A,g^B) &= \sum_{k \in \mathcal{A}}(q^A_{k}+E_kp^B_{k}) +\sum_{k \in \mathcal{B}} (q^B_{k}+E_kp^A_k)+\sum_{k \in \mathcal{C} \cup \mathcal{AB}} E_k(p^A_k+p^B_k) \nonumber\\&\ \ \ \ - \frac{1}{2}\left(\sum_{k \in \mathcal{A}} q^A_{k}p^B_k+\sum_{k \in \mathcal{B}} p^A_{k}q^B_{k}+\sum_{k \in \mathcal{C} \cup \mathcal{AB}} E_k p^A_{k}p^B_{k}\right),
\end{align}

is a potential function for the game, where $p^A_k$, $p_k^B$ for $1\leq k \leq n$, $q^A_k$ for $k \in \mathcal{A}$ and $q^B_k$ for $k \in \mathcal{B}$ are defined in (<ref>) and (<ref>). Moreover, we have that for all $g^A,g^B \in \mathcal{S}^A \times \mathcal{S}^B$, $H(g^A,g^B) \leq 2\sum_{k=1}^nE_k$.

The key to the proof is separating (<ref>) (using (<ref>), (<ref>)) as,

\begin{align}
H(g^A,g^B) &= \mathbb{E}\{R^A(g^A,g^B)\} + \sum_{k \in \mathcal{B}^c} E_kp^B_{k}+\sum_{k \in \mathcal{B}} q^B_{k}\label{eqn:pot_f_1}\\& = \mathbb{E}\{R^B(g^A,g^B)\} + \sum_{k \in \mathcal{A}} q_{k}^A+\sum_{k \in \mathcal{A}^c} p^A_{k}E_k\label{eqn:pot_f_2}.
\end{align}

Consider updating the strategy of player A while holding the strategy of player B fixed.
Notice that since $\sum_{k \in \mathcal{B}^c} E_kp^B_{k}+\sum_{k \in \mathcal{B}} q^B_{k}$ is not affected in this process, from (<ref>), we have that the change in the expected utility of player A is equal to the change of the $H$ function. Similar holds when player B updates the strategy while holding player A's strategy fixed. Hence, this is indeed a potential function.

To prove the result on the boundedness of $H(g^A,g^B)$, notice that from the definition of $H(g^A,g^B)$, we have that,

\begin{align}
H(g^A,g^B) &\leq \sum_{k \in \mathcal{A}}(q^A_{k}+E_kp^B_{k}) +\sum_{k \in \mathcal{B}} (q^B_{k}+E_kp^A_k)+\sum_{k \in \mathcal{C} \cup \mathcal{AB}} E_k(p^A_k+p^B_k) \nonumber\\& = \sum_{k \in \mathcal{A}}(\mathbb{E}\{W_k \mathbbm{1}_{\alpha^A = k}|\vec{Z}\}+E_k\mathbb{E}\{ \mathbbm{1}_{\alpha^B = k}|\vec{Z}\}) +\sum_{k \in \mathcal{B}} (\mathbb{E}\{W_k \mathbbm{1}_{\alpha^B = k}|\vec{Z}\}+E_k\mathbb{E}\{ \mathbbm{1}_{\alpha^A = k}|\vec{Z}\})\nonumber\\&\ \ \ \ +\sum_{k \in \mathcal{C} \cup \mathcal{AB}} E_k(\mathbb{E}\{\mathbbm{1}_{\alpha^A = k}|\vec{Z}\}+\mathbb{E}\{\mathbbm{1}_{\alpha^B = k}|\vec{Z}\}) \nonumber\\& \leq 2\sum_{k=1}^nE_k,
\end{align}

where the last inequality follows since $\mathbbm{1}_{\alpha^A = k},\mathbbm{1}_{\alpha^B = k}\leq 1$ and $W_i$ are independent.

Using Theorem <ref> with standard potential game theory (See, for example [32]), we have that the iterative best response algorithm with the best response found in Lemma <ref>, converges to an $\epsilon$-approximate Nash equilibrium in at most $(2\sum_{k=1}^nE_k)/\epsilon$ iterations.

§ WORST-CASE EXPECTED UTILITY

Finding a Nash equilibrium using the above algorithm may not be desirable when the players do not trust each other and place no assumptions on the incentives of the opponent. To mitigate this issue, we consider maximizing the worst-case expected utility of player A. Similar to the case of finding the Nash equilibrium, the analysis is simplified when $\vec{Z}$ is fixed.

Notice that we can simplify (<ref>) to yield,

\begin{align}
\sum_{k=1}^{n} &\mathbb{E}\{W_k\mathbbm{1}_{\{\alpha^A = k\}}\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\} \\&=
\sum_{k\in \mathcal{A}} q^A_{k}\mathbb{E}\{\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\}+\sum_{k\in \mathcal{B}} p^A_k\mathbb{E}\{W_k\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\}+\sum_{k\in \mathcal{C}\cup\mathcal{AB}} E_kp^A_k\mathbb{E}\{\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\} \nonumber\\&= \sum_{k \in \mathcal{A}} \mathbb{E}\{\Omega_kq^A_k\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\} + \sum_{k \in \mathcal{A}^c} \mathbb{E}\{\Omega_kp^A_k\mathbbm{1}_{\{\alpha^B = k\}}|\vec{Z}\},
\end{align}

\begin{equation}\label{eqn:sigma_k}
\Omega_k =
\begin{cases}
1 & \text{if }    k\in \mathcal{A},\\
W_k  & \text{if } k\in \mathcal{B},\\
E_k  & \text{if } k\in \mathcal{C}\cup\mathcal{AB}.
\end{cases}
\end{equation}

Plugging the above in (<ref>), we get that,

\begin{align}\label{eqn:r_A_B}
\mathbb{E}\{R^A(g^A\hspace{-2mm},g^B)|\vec{Z}\}&=\sum_{k\in \mathcal{A}} q^A_{k}+\hspace{-2mm}\sum_{ k\in \mathcal{A}^c}\hspace{-2mm}E_kp^A_{k} -\frac{1}{2} \mathbb{E}\left\{\sum_{k \in \mathcal{A}} \Omega_kq^A_k\mathbbm{1}_{\{\alpha^B = k\}} + \sum_{k \in \mathcal{A}^c} \hspace{-1mm}\Omega_kp^A_k\mathbbm{1}_{\{\alpha^B = k\}}\Bigg{|}\vec{Z} \right\}.
\end{align}

The difficulty in dealing with $\mathbb{E}\{R^A(g^A,g^B)|\vec{Z}\}$ is that it depends on the strategy $g^B$ of player B which is not known to player A. Hence, given a strategy $g^A$ of player A, we first focus on obtaining the worst-case strategy $\widehat{g^A}$ of player B. Then we focus on finding the strategy $g^A$ of player A which maximizes $\mathbb{E}\{R^A(g^A,\widehat{g^A})|\vec{Z}\}$. This way, we can guarantee a minimum expected utility for player A irrespective of player B's strategy.

For given $g^A \in \mathcal{S}^A$, the strategy $g^B \in \mathcal{S}^B$ that minimizes $\mathbb{E}\{R^A(g^A,g^B)|\vec{Z}\}$ chooses $\alpha^B $ $= $ $\arg\max_{1\leq k \leq n} \Lambda_k$, where,

\begin{align}\label{eqn:lambda_k}
\Lambda_k = \begin{cases}
\Omega_k q^A_k & \text{ if } k \in \mathcal{A}, \\
\Omega_k p^A_k & \text{ if } k \in \mathcal{A}^c,
\end{cases}
\end{align}

$\Omega_k$ are defined in (<ref>).

Notice that the only term of $\mathbb{E}\{R^A(g^A,g^B)|\vec{Z}\}$ in (<ref>) that depends on the strategy of player B is the last expectation. This expectation is maximized when player B chooses $k$ for which $\Lambda_k$ is maximized.[Ideally, player B may not have information about $q^A_{j}$ and $p^A_j$. Hence, player B may not be able to utilize this exact strategy. Nevertheless, obtaining a better bound is impossible since we do not have any assumptions or information about player B's strategy. For instance, if player B assumes that player A is using a particular strategy and if player B's assumption turns out to be correct since player B knows the distributions of all $W_j$ for $1\leq j \leq n$, player B's estimates of $q^A_{j}$ and $p^A_j$ are exact.]

Hence we have,

\begin{equation}\label{eqn:init_obj}
\begin{split}
\mathbb{E}\{R^A(g^A,\widehat{g^A})|\vec{Z}\}  =\sum_{k \in \mathcal{A}} q^A_{k}+\sum_{k \in \mathcal{A}^c}E_kp^A_{k} -\frac{1}{2}\sum_{k=1}^{n} \mathbb{E}\{\text{max}\{\Lambda_k; 1\leq k \leq n\}|\vec{Z}\},
\end{split}
\end{equation}

where $\Lambda_k$ are defined in (<ref>).
We formulate a strategy for player A using the following optimization problem

g ∈𝒮^Af(q⃗,p⃗_a+1:n)(P1):
q⃗ ∈ℝ^a
p⃗ ∈ℝ^n
q_k = 𝔼_W⃗,U^A{W_k1_{g(U^A,X⃗,Z⃗) = l}|Z⃗}  $\forall$  1 ≤k ≤a
p_l = 𝔼_W⃗,U^A{1_{g(U^A,X⃗,Z⃗) = l}|Z⃗}  $\forall$  1≤l ≤n,

where $f: \mathbb{R}^n\to \mathbb{R}$ is defined by,

\begin{align}\label{eqn:def_f}
f(\vec{x}) =& \sum_{k \in \mathcal{A}} x_k +\sum_{k \in \mathcal{A}^c}\hspace{-2mm} E_j x_j  -\frac{1}{2}\mathbb{E}\{\text{max}\{\Omega_jx_{j}; 1 \leq j \leq n \}|\vec{Z}\}.
\end{align}

Although not used immediately, we derive certain properties of $f$ in the following theorem, which are useful later.

The function $f$

* is concave.

* is entry-wise non-decreasing.

* satisfies,

\begin{align}
|f(\vec{x}) -f(\vec{y})| \leq \frac{3}{2}\sum_{j \in \mathcal{A}} |x_j-y_j| +\frac{3}{2}\sum_{j \in \mathcal{A}^c} E_j |x_j - y_j|,
\end{align}

for any $\vec{x},\vec{y} \in \mathbb{R}^n$.

See Appendix <ref>.

It is important to notice that the values of $p_k^A$ for $1 \leq k \leq n$ and $q_l^A$ for $l \in \mathcal{A}$ defined in (<ref>) completely determine the optimal value of (P1).  Hence notice that if we have a mechanism to find the set $\mathcal{G}^A \subset \mathbb{R}^{n+a}$ defined by,

\begin{equation}
\mathcal{G}^A = \Set{ (\vec{q},\vec{p})\ | \begin{array}{l}
g \in \mathcal{S}^A, \vec{p} \in \mathbb{R}^n,p_k = \mathbb{E}\{\mathbbm{1}_{\{g(U^A, \vec{X},\vec{Z}) = k\}}|\vec{Z}\} \text{ for } 1\leq k \leq n, \\ \vec{q} \in \mathbb{R}^a,
q_l = \mathbb{E}\{W_l\mathbbm{1}_{\{g(U^A, \vec{X},\vec{Z}) = l\}}|\vec{Z}\} \text{ for } 1\leq l \leq a
\end{array}},
\end{equation}

we can solve the optimization problem,

to find the optimal $(\vec{p^*},\vec{q^*})$, after which we find the optimal strategy $g^*$ for player A that satisfies

\begin{align}
&p^*_{k} =  \mathbb{E}\{\mathbbm{1}_{\{g^*(U^A,\vec{X},\vec{Z}) = k\}}|\vec{Z}\}\text{ for } 1\leq k \leq n,\nonumber\\&q^*_{l} = \mathbb{E}\{W_l\mathbbm{1}_{\{g^*(U^A,\vec{X},\vec{Z})  = l\}}|\vec{Z}\} \text{ for } \text{ for } 1 \leq l \leq a.
\end{align}

It turns out that $\mathcal{G}^A$ is a convex set, as established by the following lemma. Hence combining with Theorem <ref>, we have that (P1.1) is a convex optimization problem.

$\mathcal{G}^A$ is a convex set. Further in the special case $a = 0$, $\mathcal{G}^A$ is the $n$-dimensional probability simplex $\mathcal{I} = \{\vec{p} \in \mathbb{R}^n \ : \sum_{i=1}^n p_i = 1, p_i \geq 0 \forall i\}$.

See Appendix <ref>.

It turns out that finding $\mathcal{G}^A$ for the general scenario is difficult, although the case $a=0$ is handled by Theorem <ref>. In fact, when $a=b=d=0$,  an explicit solution can be obtained to (P1.1), which we describe in section <ref>. In section <ref>, we describe the solution to the general case. In Appendix <ref>, we provide simpler alternative solutions to the special cases $a = 0$ (with no restriction on $b$) and $a=1$ (with the additional assumption that $W_1$ has a continuous CDF).

§.§ Explicit solution for $a = b = d=0$

When neither player knows any of the reward realizations, we have $a=b=d=0$, and the problem reduces to the following.

∑_k =1^n p_kE_k  -1/2max{ p_kE_k; 1 ≤k ≤n }(P2):

\begin{align}\label{eqn:prob_simp}
\mathcal{I} = \{\vec{p} \in \mathbb{R}^n \ : \sum_{i=1}^n p_i = 1, p_i \geq 0 \forall i\}
\end{align}

is the $n$-dimensional probability simplex [The same problem structure arises in the case with symmetric information between the players (Case $a=b=0$ with $d$ arbitrary). Hence we can use the solution obtained in this section for the above case as well].
For this section, we assume without loss of generality that $E_k > 0$ for all $k$. If at least one of the $E_k$'s were zero, we could transform (P2) into a lower dimensional problem with non-zero $E_k$'s. The following lemma constructs an explicit solution for $a = b = 0$.

Assume without loss of generality that $E_k \geq E_{k+1}$ for $1 \leq k \leq n-1$. Also, let,

\begin{align}
r = \arg\max_{1 \leq k \leq n} \frac{k - \frac{1}{2}}{\sum_{j=1}^k \frac{1}{E_j}},
\end{align}

where the lowest index is chosen in the case of ties. The optimal solution for (P2) is given by $\vec{p}^*$ where,

\begin{align}
p^*_k = \begin{cases}
\frac{1}{E_k\left(\sum_{j=1}^{r} \frac{1}{E_j}\right)} & \text{ if } k \leq r,\\
0 & \text{ otherwise. }
\end{cases}
\end{align}

See Appendix <ref>.

It should be noted that this solution is not unique. For instance, consider the case when $n=2$, $E_1 = 2$, and $E_2 = 1$. In this case, the lemma finds the solution $(p_1,p_2) = (1,0)$, but it should be noted that $(p_1,p_2) = (1/3, 2/3)$ is also a solution. It is also interesting that the solution assigns positive probabilities to the $r$ resources with the highest average reward, although within these $r$ resources, higher probabilities are assigned to the resources with lower rewards.

§.§ Solving the general case

In this section, we focus on solving the most general version of (P1) (with no restrictions on the sets $\mathcal{A},\mathcal{B},\mathcal{AB},\mathcal{C}$). In particular, we focus on finding a mixed strategy to optimize the worst-case expected utility for player A. It turns out that our optimal solution chooses from a mixture of pure strategies parameterized by $\vec{Q} \in \mathbb{R}^n$, of the following form

\begin{align}\label{eqn:def_mixture_strats}
g_{\vec{Q}}^A(\vec{X}) = \arg\max_{1\leq j \leq n}\{ \{Q_jW_j;j \in \mathcal{A}\} \cup \{Q_j;j \in \mathcal{A}^c\}\}.
\end{align}

We name this special class of pure strategies as threshold strategies. We develop a novel algorithm to solve this problem. Our algorithm leverages techniques from drift-plus-penalty theory [10] and online convex optimization [8, 9]. It should be noted that our algorithm runs offline and is used to construct an appropriate strategy for player A that approximately solves (P1) conditioned on the observed realization of $\vec{Z}$. We show that we can get arbitrarily close to the optimal value of (P1) by using a finite equiprobable mixture of pure strategies of the above form. It should be noted that the algorithm developed in this section can be used to solve the general unconstrained problem of finding the randomized decision $\alpha \in \{1,2,\dots,n\}$ which maximizes $\mathbb{E}\{h(\vec{x};\vec{\Theta})\}$, where $\vec{x} \in \mathbb{R}^n$ with $x_k = \mathbb{E}\{\Gamma_k \mathbbm{1}_{\{\alpha = k\}}\}$, $\vec{\Theta} \in \mathbb{R}^m$ and $\vec{\Gamma} \in \mathbb{R}^n$ are non-negative random vectors with finite second moments, and $h$ is a concave function such that $\tilde{h}(\vec{x}) = \mathbb{E}\{h(\vec{x};\vec{\Theta})\}$ is Lipschitz continuous, entry-wise non-decreasing and has bounded subgradients.

We first provide an algorithm that generates a mixture of $T$ pure strategies, after which we establish the closeness to the optimality of the mixture. We generate the mixture of $T$ pure strategies $\{g^A_{\vec{Q}(t)}\}_{t=1}^T$ by iteratively updating vector $\vec{Q}$ for $T$ iterations, where $\vec{Q}(t)$, and $g_{\vec{Q}(t)}(\vec{X})$ denote the state of $\vec{Q}$ and the pure strategy generated in the $t$-th iteration, respectively. In addition to $\vec{Q}(t)$, we require another state vector $\vec{\gamma}(t) \in \mathbb{R}^n$, which we also update in each iteration, and a parameter $V$ which decides the convergence properties of the algorithm. We provide the specific details on setting $V$ later in our analysis. We begin with $\vec{Q}(1) = \vec{\gamma}(0) = 0$.
In the $t$-th iteration $(t \geq 1)$, we independently sample $\vec{X}(t)$ and $\vec{\Omega}(t)$ from the distributions of $\vec{X}$ and $\vec{\Omega}$, respectively, where $\vec{\Omega}$ is defined in (<ref>), while keeping $\vec{Z}$ fixed to it's observed value. Then we update $\vec{\gamma}(t)$ and $\vec{Q}(t+1)$ as follows. First, we solve,
\beginmini!|l|
γ⃗(t)-V f^'_t(γ⃗(t-1))^⊤γ⃗(t) + α‖γ⃗(t)- γ⃗(t-1)‖_2^2+∑_j=1^nQ_j(t)γ_j(t)(P3):
\endmini!
to find $\vec{\gamma}(t)$, where

\begin{align}\label{eqn:def:f_t}
f_t(\vec{x}) = \sum_{k \in \mathcal{A}}x_k +  \sum_{k \in \mathcal{A}^c}x_kE_k  -\frac{1}{2}\text{max}\{ x_k\Omega_k(t); 1 \leq k \leq n \},
\end{align}

$\alpha>0$ and $\mathcal{K} = \left(\bigtimes_{j\in \mathcal{A}}[0,E_j]\right) \times [0,1]^{n-a}$. Notice that $f^{'}_t(\vec{x})$ is given by,

\begin{align}\label{eqn:grads_f_t}
f^{'}_{t,j}(\vec{x}) = \begin{cases}
1 - \frac{1}{2}\mathbbm{1}_{\{\arg\max_{1\leq k \leq n}\{ x_k\Omega_k(t)\} = j\}} & \text{ if } j \in \mathcal{A},\\
E_j - \frac{1}{2}\mathbbm{1}_{\{\arg\max_{1\leq k \leq n}\{ x_k\Omega_k(t)\} = j\}}\Omega_j(t) & \text{ if } j \in \mathcal{A}^c,
\end{cases}
\end{align}

where $\arg\max$ returns the lowest index in the case of ties. Notice that $f_t$ is a concave function, which can be established by repeating the same argument used to establish the concavity $f$ in Theorem <ref>. Then we choose the action for the $t$-th iteration $\alpha^A(t) = g_{\vec{Q}(t)}^A(\vec{X}(t))$ (See (<ref>)).
Then to update $\vec{Q}(t+1)$, we use,

\begin{align}\label{eqn:c_vec}
&Q_j(t+1) = \text{max}\left\{Q_j(t) + \gamma_j(t) - X_j(t)\mathbbm{1}_{\{ \alpha^A(t)= j\}},0\right\}, \forall j \in \mathcal{A},\nonumber\\&
Q_j(t+1) = \text{max}\left\{Q_j(t) + \gamma_j(t) - \mathbbm{1}_{\{\alpha^A(t)= j\}},0\right\}, \forall j \in \mathcal{A}^c.
\end{align}

The algorithm is summarized as Algorithm <ref> for clarity.

Initialize $\vec{Q}(1) = \vec{\gamma}(0) = 0$

each iteration $t \in [1:T]$
Sample $\vec{X}(t)$, and $\vec{\Omega}(t)$

Choose $\vec{\gamma}(t)$ by solving (P3)

Choose the action $\alpha^A(t) = g_{\vec{Q}(t)}^A(\vec{X}(t))$

Obtain $\vec{Q}(t+1)$  using (<ref>)

Algorithm to generate the optimal mixture of $T$ pure strategies

After creating the mixture $\{g^A_{\vec{Q}(t)}\}_{t=1}^{T}$ of pure strategies, we choose one of them randomly with probability $1/T$ to take the decision. In the following two sections, we focus on solving (P3) and evaluating the performance of the Algorithm <ref>.

§.§.§ Solving (P3)

Notice that the objective of (P3) can be written as

\begin{align}
&-V f^{'}_t(\vec{\gamma}(t-1))^{\top}\vec{\gamma}(t) + \alpha\lVert \vec{\gamma}(t)- \vec{\gamma}(t-1)\rVert_2^2+\sum_{j=1}^nQ_j(t)\gamma_j(t) \nonumber\\&=
\sum_{j=1}^n \left\{-V f^{'}_{t,j}(\vec{\gamma}(t-1))\gamma_j(t) + \alpha (\gamma_j(t) - \gamma_j(t-1))^2 + Q_j(t)\gamma_j(t)\right\}.
\end{align}

Hence (P3) seeks to minimize a separable convex function over the box constraint $\vec{\gamma}(t) \in \mathcal{K}$. The solution vector $\vec{\gamma}(t)$ is found by separately minimizing each component $\gamma_j(t)$ over $[0,u_j]$, where

\begin{align}\label{eqn:def_us}
u_j = \begin{cases}
E_j & \text{ if } j\in\mathcal{A},\\
1   & \text{ if } j\in\mathcal{A}^c.
\end{cases}
\end{align}

The resulting solution is,

\begin{align}\label{eqn:P4_solution}
\gamma_j(t) = \Pi_{[0,u_j]}\left(\gamma_j(t-1)-\frac{-V  f^{'}_{t,j}(\vec{\gamma}(t-1))  + Q_j(t)}{2\alpha}\right),
\end{align}

where $ \Pi_{[0,u_j]}$ denotes the projection onto $[0,u_j]$. Notice that the above solution is obtained by projecting the global minimizer of the function to be minimized onto $[0,u_j]$.

§.§.§ How good is the mixed strategy generated by Algorithm <ref>

Without loss of generality, we assume that $E_k >0$ for all $1\leq k \leq n$.
The following theorem establishes the closeness of the expected utility generated by Algorithm <ref> to the optimal value  $f^{\text{opt}}$ of (P1).

Assume $\alpha$ is set such that $\alpha \geq V^2$, and we use the mixed strategy $g^A$ generated by Algorithm <ref> to make the decision. Then,

\begin{align}\label{eqn:err_guarantee}
\mathbb{E}\{R^A(g^A,\widehat{g^A})|\vec{Z}\} \geq &f^{\text{opt}} - \frac{D_1}{V} - \frac{VD_2}{16\alpha}-\frac{\alpha D_3}{VT}- \frac{3}{2T}\sum_{k \in \mathcal{A}}\left\{\sqrt{\alpha}+E_k\left(2\sqrt{2\alpha}+1\right)\right\}\nonumber\\&- \frac{3}{2T}\sum_{k \in \mathcal{A}^c}\left\{E_k^2\sqrt{\alpha}+E_k\left(2\sqrt{2\alpha}+1\right)\right\},
\end{align}

\begin{align}\label{eqn:d1d2d3}
&D_1 = n-a+\frac{1}{2}\sum_{j\in\mathcal{A}} (E_j^2 + \mathbb{E}\{W_k^2\}),\nonumber\\
&D_2 = 4a +\mathbb{E}\{\lVert\vec{\Omega}\rVert_2^2|\vec{Z}\}+\sum_{j\in \mathcal{A}^c}4E_j^2,\nonumber\\
&D_3 =  n-a+\sum_{j\in\mathcal{A}} E_j^2,
\end{align}

$\vec{\Omega}$ is defined in (<ref>),
and $f^{\text{opt}}$ is the optimal value of (P1). Hence, by using $V = O(1/\varepsilon)$, $\alpha = O(1/\varepsilon^2) \geq V^2$, and $T = O(1/\varepsilon^2)$, the average error is $\mathcal{O}(\varepsilon)$.

The key to the proof is noticing that $\vec{Q}(t)$ can be treated as $n$  queues. Before proceeding with the proof, we define some quantities. Define the history up to time $t$ by $\mathcal{H}(t) = \{\vec{X}(\tau);1\leq \tau <t\} \cup \{\vec{\Omega}(\tau);1\leq \tau \leq t\}$. Notice that we include $\vec{\Omega}(t)$ in $\mathcal{H}(t)$ since this will allow us to treat $\vec{\gamma}(t)$, and $\vec{Q}(t)$ as deterministic functions of $\mathcal{H}(t)$ and $\vec{Z}$. Let us define the Lyapunov function $L(t) = \frac{1}{2}||\vec{Q}(t)||^2 = \frac{1}{2}\sum_{j=1}^n Q_j(t)^2$, and the drift $\Delta(t) = \mathbb{E}\{L(t+1) - L(t)|\mathcal{H}(t),\vec{Z}\}$. Now notice that,

\begin{align}
\mathbb{E}\{R^A(g^A,\widehat{g^A})|\vec{Z}\} = f\left(\frac{1}{T} \sum_{t=1}^{T} \mathbb{E}\{\vec{x}(t)|\vec{Z}\}\right),
\end{align}

\begin{align}\label{eqn:tilde_x_def}
X_k(t)\mathbbm{1}_{\{g^A_{\vec{Q}(t)}(\vec{X}(t)) = k\}}  & \text{ if }  k \in \mathcal{A},\\
\mathbbm{1}_{\{g^A_{\vec{Q}(t)}(\vec{X}(t)) = k\}}  & \text{ if } k \in \mathcal{A}^c.
\end{cases}
\end{align}

We begin with the following two lemmas, which will be useful in the proof.

The drift is bounded above as,

\begin{align}
\Delta(t) \leq D_1 + \sum_{j=1}^nQ_j(t)\big{(}\gamma_j(t) - \mathbb{E}\{x_j(t)|\mathcal{H}(t),\vec{Z}\}\big{)},
\end{align}

where $D_1$ is defined in (<ref>).

See Appendix <ref>.

The following is a well-known result regarding the minimization of strongly convex functions (See, for example [33]).

Let $\mathcal{G} \subset \mathbb{R}^n$ be a convex set with a non-empty interior $\mathcal{G}^0$. Let $\mathcal{C} \subset \mathcal{G}$ such that $\mathcal{C}$ intersects $\mathcal{G}^0$. Define $\mathcal{C}^0 = C \cap \mathcal{G}^0$. Let $\omega:\mathcal{G} \to \mathbb{R}$ be a function that is continuously differentiable in $\mathcal{G}^0$. The Bregman divergence $D_{\omega}:\mathcal{C} \times \mathcal{C}^0 \to \mathbb{R}$ generated by $\omega$ is denoted by,

\begin{align}
D_{\omega}(\vec{x}\lVert \vec{y}) = \omega(\vec{x}) - \omega(\vec{y})-\nabla \omega(\vec{y})^{\top}(\vec{x}-\vec{y}).
\end{align}

Let $g: \mathcal{G} \to \mathbb{R}$ be a convex function. Fix $\alpha >0$, and $\vec{y} \in \mathcal{C}^0$. Let,

\begin{align}
\vec{x}^* \in \arg\min_{\vec{x}\in \mathcal{C}} g(\vec{x}) + \alpha D_{\omega}(\vec{x}\lVert \vec{y}).
\end{align}

Additionally, assume that $\vec{x}^* \in \mathcal{C}^0$.

\begin{align}
g(\vec{x}^*) + \alpha D_{\omega}(\vec{x}^* \lVert \vec{y}) \leq g(\vec{z}) + \alpha D_{\omega}(\vec{z}\lVert \vec{y}) - \alpha D_{\omega}(\vec{z}\lVert \vec{x}^*),
\end{align}

for all $\vec{z} \in \mathcal{C}$. We have the following special cases.

* Using $\mathcal{G} = \mathbb{R}^n$, we have that $\mathcal{C} = \mathcal{C}^0$. In this case, if $\omega(\vec{x}) = \lVert \vec{x} \rVert_2^2$, we have $D_{\omega}(\vec{x}\lVert \vec{y}) = \lVert \vec{x} - \vec{y}\rVert_2^2$.

* Using $\mathcal{G} = [0,\infty)^n$ and  $\mathcal{C} = \mathcal{I}$, we have $\mathcal{C}^0=\mathcal{I}^0$. In this case, if $\omega(\vec{x}) = \sum_{j=1}^n x_j \ln(x_j)$, we have that, $ D_{\omega}(\vec{x}\lVert \vec{y}) =  D(\vec{x}\lVert \vec{y})$, where $D(\vec{x}\lVert \vec{y})$ is the Kullback-Leibler divergence.

Now we move on to the main proof. Notice that the objective of (P3) can be written as

\begin{align}
g^{'}_t(\vec{\gamma}(t-1))^{\top}\vec{\gamma}(t) + \alpha \lVert \vec{\gamma}(t)-\vec{\gamma}(t-1) \rVert_2^2,
\end{align}

\begin{align}
g_t(\vec{x}) = -V f_t(\vec{x}) + \sum_{j=1}^n Q_j(t)x_j.
\end{align}

Let $g^{A,*}$ be the strategy that is optimal for (P1). Let us define $\vec{x}^*(t) \in \mathbb{R}^n$, where
X_k(t)1_{g^A,*(U^A(t),X⃗(t),Z⃗) = k}      if $k \in \mathcal{A}$,

1_{g^A,*(U^A(t),X⃗(t),Z⃗) = k}      if $k \in \mathcal{A}^c$,

where $U^A(t)$ for $1\leq t \leq T$ is a collection of i.i.d uniform-$[0,1)$ random variables. Notice that $\vec{y}^* =\mathbb{E}\{\vec{x}^*(t)|\vec{Z}\}$ is independent of $t$ and belongs to $\mathcal{K}$. Hence $\vec{y}^*$ is feasible for (P3). Notice that,

\begin{align}\label{eqn:ageq0_1}
&-Vf^{'}_t(\vec{\gamma}(t-1))^{\top}\vec{\gamma}(t) + \sum_{j=1}^n Q_j(t)\gamma_j(t)+\alpha \lVert\vec{\gamma}(t)-\vec{\gamma}(t-1) \rVert_2^2 \nonumber\\&=g^{'}_t(\vec{\gamma}(t-1))^{\top}\vec{\gamma}(t) + \alpha \lVert \vec{\gamma}(t)-\vec{\gamma}(t-1) \rVert_2^2 \nonumber\\&\leq_{(a)}
g^{'}_t(\vec{\gamma}(t-1))^{\top}\vec{y}^* + \alpha \lVert \vec{y}^*-\vec{\gamma}(t-1) \rVert_2^2 - \alpha \lVert \vec{y}^*-\vec{\gamma}(t) \rVert_2^2\nonumber\\&=
-Vf^{'}_t(\vec{\gamma}(t-1))^{\top}\vec{y}^* + \sum_{j=1}^n Q_j(t)y^*_j +\alpha \lVert \vec{y}^*-\vec{\gamma}(t-1) \rVert_2^2  - \alpha \lVert \vec{y}^*-\vec{\gamma}(t) \rVert_2^2,
\end{align}

where (a) follows from Lemma <ref> for the convex function $h$ given by $h(\vec{x}) = g^{'}_t(\vec{\gamma}(t-1))^{\top}\vec{\vec{x}}$ with $\mathcal{G} = \mathbb{R}^n$, and $\mathcal{C} = \mathcal{K}$, since $\vec{\gamma}(t)$ is the solution to (P3) and $\vec{y}^* $ is feasible for (P3).
Also, step 5 in each iteration of Algorithm <ref> of finding the action can be represented as the maximization of

\begin{align}
\sum_{j\in \mathcal{A}}Q_j(t)\mathbb{E}\{X_j(t)\mathbbm{1}_{\{\alpha^A =  j\}}|\mathcal{H}(t),\vec{Z}\} + \sum_{j\in \mathcal{A}^c}Q_j(t)\mathbb{E}\{\mathbbm{1}_{\{\alpha^A = j\}}|\mathcal{H}(t),\vec{Z}\}
\end{align}

over all possible actions $\alpha^A$ at time-slot $t$. Hence comparing the scenario where $g^A_{\vec{Q}(t)}$ is used in the $t$-th iteration with the scenario where $g^{A,*}$ is used with randomization variable $U^A(t)$ in the $t$-th iteration, we have the inequality,

\begin{align}\label{eqn:ageq0_2}
-\sum_{j=1}^nQ_j(t)\mathbb{E}\{x_j(t)|\mathcal{H}(t),\vec{Z}\} &\leq -\sum_{j=1}^nQ_j(t)\mathbb{E}\{x_j^*(t)|\mathcal{H}(t),\vec{Z}\} =  -\sum_{j=1}^nQ_j(t)y^*_j,
\end{align}

where the last equality follows since $\vec{x}^*(t)$ is independent of $\mathcal{H}(t)$. Summing (<ref>) and (<ref>),

\begin{align}
&-Vf^{'}_t(\vec{\gamma}(t-1))^{\top}\vec{\gamma}(t) +\alpha \lVert\vec{\gamma}(t)-\vec{\gamma}(t-1) \rVert_2^2 +\sum_{j=1}^nQ_j(t)\big{(}\gamma_j(t)-\mathbb{E}\{x_j(t)|\mathcal{H}(t),\vec{Z}\}\big{)}\\& \leq
-Vf^{'}_t(\vec{\gamma}(t-1))^{\top}\vec{y}^* + \alpha \lVert \vec{y}^*-\vec{\gamma}(t-1) \rVert_2^2   - \alpha \lVert \vec{y}^*-\vec{\gamma}(t) \rVert_2^2 \nonumber.
\end{align}

Adding $D_1+Vf^{'}_t(\vec{\gamma}(t-1))^{\top}\vec{\gamma}(t-1)$ to both sides and using Lemma <ref> yields,

\begin{align}\label{eqn:ageq0_3}
&\Delta(t) - Vf^{'}_t(\vec{\gamma}(t-1))^{\top}\left\{\vec{\gamma}(t) -\vec{\gamma}(t-1)\right\}+\alpha \lVert\vec{\gamma}(t)-\vec{\gamma}(t-1) \rVert_2^2 \nonumber\\&\leq D_1- Vf^{'}_t(\vec{\gamma}(t-1))^{\top}\big{(}\vec{y}^*-\vec{\gamma}(t-1)\big{)} + \alpha \lVert \vec{y}^*-\vec{\gamma}(t-1) \rVert_2^2  - \alpha \lVert \vec{y}^*-\vec{\gamma}(t) \rVert_2^2 \nonumber\\& \leq D_1- V \{f_t(\vec{y}^*)-f_t(\vec{\gamma}(t-1))\} + \alpha \lVert \vec{y}^*-\vec{\gamma}(t-1) \rVert_2^2  - \alpha \lVert \vec{y}^*-\vec{\gamma}(t) \rVert_2^2,
\end{align}

where the last inequality follows from the sub-gradient inequality for the concave function $f_t$. Now we introduce the following lemma.

We have,

\begin{align}
-Vf^{'}_t(\vec{\gamma}(t-1))^{\top}\left\{\vec{\gamma}(t) -\vec{\gamma}(t-1)\right\}+\alpha \lVert\vec{\gamma}(t)-\vec{\gamma}(t-1) \rVert_2^2 \geq  &- \frac{V^2}{4\alpha}\left(a + \sum_{j\in \mathcal{A}^c}E_j^2\right)\nonumber\\&-\frac{V^2}{16\alpha}\lVert\vec{\Omega}(t)\rVert_2^2,
\end{align}

See Appendix <ref>.

Substituting the bound from Lemma <ref> in (<ref>) we have that,

\begin{align}
&\Delta(t) - \frac{V^2}{4\alpha}\left(a + \sum_{j\in \mathcal{A}^c}E_j^2\right)-\frac{V^2}{16\alpha}\lVert\vec{\Omega}(t)\rVert_2^2\nonumber \\&\leq  D_1- V \{f_t(\vec{y}^*)-f_t(\vec{\gamma}(t-1))\} + \alpha \lVert \vec{y}^*-\vec{\gamma}(t-1) \rVert_2^2 - \alpha \lVert \vec{y}^*-\vec{\gamma}(t) \rVert_2^2,
\end{align}

The above holds for each $t \in \{1,2,\dots,T\}$. Hence we first take the expectation conditioned on $\vec{Z}$ of both sides of the above expression, after which we sum from $1$ to $T$, which results in,

\begin{align}\label{eqn:f:_ineq_3}
&\mathbb{E}\{L(T+1)|\vec{Z}\} -  \mathbb{E}\{L(1)|\vec{Z}\}  -\frac{TV^2}{4\alpha}\left(a + \sum_{j\in \mathcal{A}^c}E_j^2\right)-\frac{TV^2}{16\alpha}\mathbb{E}\{\lVert\vec{\Omega}\rVert_2^2|\vec{Z}\} \nonumber\\&\leq D_1T- V \sum_{t=1}^T\mathbb{E}\{f_t(\vec{y}^*)|\vec{Z}\}+V \sum_{t=1}^T\mathbb{E}\{f_t(\vec{\gamma}(t-1))|\vec{Z}\} + \alpha \mathbb{E}\{\lVert \vec{y}^*-\vec{\gamma}(0) \rVert_2^2|\vec{Z}\} \nonumber\\&\ \ \ \ - \alpha \mathbb{E}\{\lVert\vec{y}^*-\vec{\gamma}(T)\rVert_2^2|\vec{Z}\}.
\end{align}

Notice that,

\begin{align}\label{eqn:f_opt_to_f_t_opt}
\mathbb{E}\{f_t(\vec{y}^*)|\vec{Z}\} = f(\vec{y}^*)=  f^{\text{opt}},
\end{align}

where functions $f$ and $f_t$ are defined in (<ref>), and (<ref>), respectively. Also, we have that,

\begin{align}\label{eqn:f_to_f_t}
\mathbb{E}\{f_t(&\vec{\gamma}(t-1))|\vec{Z}\} = \mathbb{E}\{\mathbb{E}_{\vec{\Omega}(t)}\{f_t(\vec{\gamma}(t-1))|\mathcal{H}(t-1),\vec{Z}\}|\vec{Z}\} =_{(a)}\mathbb{E}\{f(\vec{\gamma}(t-1))|\vec{Z}\},
\end{align}

where (a) follows from the definition of $f_t$ in (<ref>), since $\vec{\gamma}(t-1)$ is a function of $\mathcal{H}(t-1)$ and $\vec{\Omega}(t)$ is independent of $\mathcal{H}(t-1)$.
Substituting (<ref>) and (<ref>) in (<ref>), we have that,

\begin{align}\label{eqn:f:_ineq_0}
&\mathbb{E}\{L(T+1)|\vec{Z}\} -  \mathbb{E}\{L(1)|\vec{Z}\}  -\frac{TV^2}{4\alpha}\left(a + \sum_{j\in \mathcal{A}^c}E_j^2\right)-\frac{TV^2}{16\alpha}\mathbb{E}\{\lVert\vec{\Omega}\rVert_2^2|\vec{Z}\} \nonumber\\&\leq  D_1T- V Tf^{\text{opt}}+V \sum_{t=1}^T\mathbb{E}\{f(\vec{\gamma}(t-1))|\vec{Z}\} +\alpha \mathbb{E}\{\lVert \vec{y}^*-\vec{\gamma}(0) \rVert_2^2|\vec{Z}\} - \alpha \mathbb{E}\{\lVert \vec{y}^*\hspace{-1mm}-\vec{\gamma}(T)\rVert_2^2 |\vec{Z}\}\nonumber\\&\leq_{(a)}D_1T- V Tf^{\text{opt}}+V \sum_{t=1}^T\mathbb{E}\{f(\vec{\gamma}(t-1))|\vec{Z}\} + \alpha\left(n-a + \sum_{k \in \mathcal{A}}E_k^2\right) \nonumber\\&\leq D_1T- V Tf^{\text{opt}}+VTf\left(\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\{\vec{\gamma}(t-1)|\vec{Z}\}\right) + \alpha D_3,
\end{align}

where (a) follows since $\vec{y}^*,\vec{\gamma}(T),\vec{\gamma}(0) \in \mathcal{K}$, and the last inequality follows from Jensen's inequality on the concave function $f$. (See the definition of $D_3$ in (<ref>)). Since $\vec{Q}(1) = 0$ and $\mathbb{E}\{L(T+1)|\vec{Z}\} \geq 0$, after some rearrangements above translates to,

\begin{align}\label{eqn:_perf_eval_main_ineq}
f^{\text{opt}} - \frac{D_1}{V}& - \frac{VD_2}{16\alpha}-\frac{\alpha D_3}{VT}\leq   f\left(\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\{\vec{\gamma}(t)|\vec{Z}\}\right),
\end{align}

where $D_2$ is defined in (<ref>). Now we prove that prove the following lemma.

We have,

\begin{align}
f\left(\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\{\vec{\gamma}(t)|\vec{Z}\}\right) \leq & f\left(\frac{1}{T} \sum_{t=1}^{T} \mathbb{E}\{\vec{x}(t)|\vec{Z}\}\right) + \frac{3}{2T}\sum_{k \in \mathcal{A}}\left\{\sqrt{\alpha}+E_k\left(2\sqrt{2\alpha}+1\right)\right\}\nonumber\\& + \frac{3}{2T}\sum_{k \in \mathcal{A}^c}\left\{E_k^2\sqrt{\alpha}+E_k\left(2\sqrt{2\alpha}+1\right)\right\}.
\end{align}

We first introduce the following two lemmas.

The queues $Q_j(t)$ for $1 \leq j \leq n$ updated according to Algorithm <ref> satisfy,

\begin{align}
\text{max}\left\{\frac{1}{T}\sum_{t=1}^{T-1}\mathbb{E}\{\gamma_j(t)-x_j(t)|\vec{Z}\},\vec{0}\right\} \leq \frac{\mathbb{E}\{Q_j(T) \ |\vec{Z}\}}{T}.
\end{align}

See Appendix <ref>.

The following lemma is vital in constructing the $\mathcal{O}(\sqrt{\alpha})$ bound on the queue sizes, which leads to the $\mathcal{O}(1/\varepsilon^2)$ solution. It should be noted that an easier bound can be obtained on the queue sizes, which leads to a $\mathcal{O}(1/\varepsilon^3)$ solution.

Given that $\alpha \geq V^2$,
$\vec{Q}(t)$ satisfy the bound

\begin{align}
Q_j(t) \leq \begin{cases}
(1+2\sqrt{2}E_j)\sqrt{\alpha}+E_j &\text{ if } j \in \mathcal{A}\\
(E_j+2\sqrt{2})\sqrt{\alpha}+1 &\text{ if } j \in \mathcal{A}^c,
\end{cases}
\end{align}

for each $t \in [1:T]$.

See Appendix <ref>.

Now we move on to the main proof. Notice that,

\begin{align}\label{eqn:f:_ineq_1}
&f\left(\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\{\vec{\gamma}(t)|\vec{Z}\}\right) =  f\left(\frac{\vec{\gamma}(0)}{T}+\frac{1}{T}\sum_{t=1}^{T-1}\mathbb{E}\{\vec{\gamma}(t)|\vec{Z}\}\right) \nonumber\\&
\leq f\left(\frac{1}{T} \sum_{t=1}^T \mathbb{E}\{\vec{x}(t)|\vec{Z}\} + \frac{1}{T}\sum_{t=1}^{T-1}\mathbb{E}\{\vec{\gamma}(t)|\vec{Z}\} - \frac{1}{T} \sum_{t=1}^{T-1} \mathbb{E}\{\vec{x}(t)|\vec{Z}\} - \frac{\mathbb{E}\{\vec{x}(T)|\vec{Z}\}}{T}\right) \nonumber\\& \leq_{(a)} f\left(\frac{1}{T} \sum_{t=1}^T \mathbb{E}\{\vec{x}(t)|\vec{Z}\} + \text{max}\left\{\frac{1}{T}\sum_{t=1}^{T-1}\mathbb{E}\{\vec{\gamma}(t)|\vec{Z}\} - \frac{1}{T} \sum_{t=1}^{T-1} \mathbb{E}\{\vec{x}(t)|\vec{Z}\},\vec{0}\right\}\right) \\&\leq_{(b)} f\left(\frac{1}{T} \sum_{t=1}^T \mathbb{E}\{\vec{x}(t)|\vec{Z}\}\right) + \frac{3}{2}\sum_{k \in \mathcal{A}}\left(\text{max}\left\{\frac{1}{T}\sum_{t=1}^{T-1}\mathbb{E}\{\gamma_k(t)-x_k(t)|\vec{Z}\},\vec{0}\right\}\right)\nonumber\\&\ \ \ \ \ \  + \frac{3}{2}\sum_{k \in \mathcal{A}^c}E_k\left(\text{max}\left\{\frac{1}{T}\sum_{t=1}^{T-1}\mathbb{E}\{\gamma_k(t)-x_k(t)|\vec{Z}\},\vec{0}\right\}\right),\nonumber
\end{align}

where (a) follows from the entry-wise non-decreasing property of $f$ (Theorem <ref>-2) and (b) follows from Theorem <ref>-3. Combining (<ref>), and Lemma <ref> with the bound on $\vec{Q}(T)$ given by Lemma <ref>, we are done with the proof of the lemma.

Combining Lemma <ref> with (<ref>), we are done with the proof of the theorem.

§ SIMULATIONS

For the simulations, we use $W_j$ as exponential random variables and consider three scenarios given below,

* $a = 0, b = 0, c = 3, d = 0$.

* $a = 0, b = 1, c = 2, d = 0$.

* $a = 1, b = 1, c = 1, d = 0$.

Fig. <ref>, Fig. <ref>, and Fig. <ref> show pictorial representations of these cases.

[ultra thick]
(0,-1) rectangle (2,0) node[pos=.5]$1$;
(2,-1) rectangle (4,0) node[pos=.5]$2$;
(4,-1) rectangle (6,0) node[pos=.5]$3$;
[pen colour=black,
decoration = calligraphic brace,
aspect=0.5] (0,0) –  (6,0)

Case $a,b,c,d = 0,0,3,0$

[ultra thick]
(0,-1) rectangle (2,0) node[pos=.5]$1$;
(2,-1) rectangle (4,0) node[pos=.5]$2$;
(4,-1) rectangle (6,0) node[pos=.5]$3$;
[pen colour=black,
decoration = calligraphic brace,
aspect=0.5] (0,0) –  (2,0)
[pen colour=black,
decoration = calligraphic brace,
aspect=0.5] (2,0) –  (6,0)

Case $a,b,c,d = 0,1,2,0$

[ultra thick]
(0,-1) rectangle (2,0) node[pos=.5]$1$;
(2,-1) rectangle (4,0) node[pos=.5]$2$;
(4,-1) rectangle (6,0) node[pos=.5]$3$;
[pen colour=black,
decoration = calligraphic brace,
aspect=0.5] (0,0) –  (2,0)
[pen colour=black,
decoration = calligraphic brace,
aspect=0.5] (2,0) –  (4,0)
[pen colour=black,
decoration = calligraphic brace,
aspect=0.5] (4,0) –  (6,0)

Case $a,b,c,d = 1,1,1,0$

We first consider scenario-1.
For Fig. <ref>-top-left, we fix $E_2 = E_3 = 1$ and plot the expected utilities of players A and B and the potential function $H$ at the $\epsilon$-approximate Nash equilibrium as functions of $E_1$, where $\epsilon = 10^{-3}$ is used. For Fig. <ref>-top-middle, and Fig. <ref>-top-right, we use the same configuration and plot a solution for the probabilities of choosing different resources as a function of $E_1$ at the $\epsilon$-approximate Nash equilibrium for players A and B, respectively. For scenario-2 and scenario-3, Fig. <ref>-middle and Fig. <ref>-bottom have similar descriptions to scenario-1.

We consider the same three scenarios for the simulations on maximizing the worst-case expected utility. In each scenario, for the top figure, we fix $E_2= E_3 = 1$ and plot the maximum expected worst-case utility of player A as a function of $E_1$. For the bottom figure, we use the same configuration and plot a solution for the probabilities of choosing different resources for player A as a function of $E_1$. Notice that the solutions may not be unique as discussed in Section <ref>. Additionally, for Fig. <ref>-top-middle and Fig. <ref>-top-right, we also indicate the possible range of the solution. For scenario-2 and scenario-3, we have obtained the solutions by averaging over $10^{2}$ independent simulations. Also, we have used $T =10^5$, $\alpha = 4 \times 10^{4}$, and $V = 2 \times 10 ^2$.

Comparing Fig. <ref> and Fig. <ref>, it can be seen that the worst-case strategy performs comparably to the strategy at $\epsilon$-approximate Nash equilibrium in many cases. This is surprising in light of the fact that the worst-case strategy can be computed without any cooperation between the players.  For instance, in scenario-1, for $E_1 \geq 2$, the approximate Nash equilibrium strategy coincides with the worst-case strategy of choosing resource 1 with probability 1. However, it should be noted that there are better socially optimal strategies. For instance, when $E_1 = 2$, player A choosing resource 1 with probability 1 and player B choosing resource 2 with probability 1, gives a higher utility for player A without changing the utility of player B.

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Expected Utility,
xmin=0.1, xmax=2.4,
ymin=0.75, ymax=4,
grid style=dashed,
legend pos=north west,
every axis plot/.append style=thin,
label style=font=,
tick label style=font=,
legend style=nodes=scale=0.9, transform shape
[color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=1] CSV/a0b0_Nash.csv;
[color=red,mark=+,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=2] CSV/a0b0_Nash.csv;
[color=green,mark=x,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=3] CSV/a0b0_Nash.csv;
Player A reward, Player B reward, $H(g^A,g^B)$

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Choice probability,
xmin=0.1, xmax=2.4,
ymin=0, ymax=1.5,
grid style=dashed,
legend pos=north west,
every axis plot/.append style=thin,
label style=font=,
tick label style=font=,
legend style=nodes=scale=0.9, transform shape
[color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=4] CSV/a0b0_Nash.csv;
[color=red,mark=+,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=5] CSV/a0b0_Nash.csv;
[color=green,mark=x,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=6] CSV/a0b0_Nash.csv;

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Choice probability,
xmin=0.1, xmax=2.4,
ymin=0, ymax=1.5,
grid style=dashed,
legend pos=north west,
every axis plot/.append style=thin,
label style=font=,
tick label style=font=,
legend style=nodes=scale=0.9, transform shape
[color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=7] CSV/a0b0_Nash.csv;
[color=red,mark=+,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=8] CSV/a0b0_Nash.csv;
[color=green,mark=x,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=9] CSV/a0b0_Nash.csv;

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Expected Utility,
xmin=0.1, xmax=2.4,
ymin=0.7, ymax=4,
grid style=dashed,
legend pos=north west,
every axis plot/.append style=thin,
label style=font=,
tick label style=font=,
legend style=nodes=scale=0.9, transform shape
[color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=1] CSV/a0b1_Nash.csv;
[color=red,mark=+,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=2] CSV/a0b1_Nash.csv;
[color=green,mark=x,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=3] CSV/a0b1_Nash.csv;
Player A reward, Player B reward,$H(g^A,g^B)$

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Choice probability,
xmin=0.1, xmax=2.4,
ymin=0, ymax=1.5,
grid style=dashed,
legend pos=north west,
every axis plot/.append style=thin,
label style=font=,
tick label style=font=,
legend style=nodes=scale=0.9, transform shape
[color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=4] CSV/a0b1_Nash.csv;
[color=red,mark=+,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=5] CSV/a0b1_Nash.csv;
[color=green,mark=x,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=6] CSV/a0b1_Nash.csv;

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Choice probability,
xmin=0.1, xmax=2.4,
ymin=0, ymax=1.5,
grid style=dashed,
legend pos=north west,
every axis plot/.append style=thin,
label style=font=,
tick label style=font=,
legend style=nodes=scale=0.9, transform shape
[color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=7] CSV/a0b1_Nash.csv;
[color=red,mark=+,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=8] CSV/a0b1_Nash.csv;
[color=green,mark=x,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=9] CSV/a0b1_Nash.csv;

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Expected Utility,
xmin=0.1, xmax=2.4,
ymin=0.5, ymax=5,
grid style=dashed,
legend pos=north west,
every axis plot/.append style=thin,
label style=font=,
tick label style=font=,
legend style=nodes=scale=0.9, transform shape
[color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=1] CSV/a1b1_Nash.csv;
[color=red,mark=+,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=2] CSV/a1b1_Nash.csv;
[color=green,mark=x,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=3] CSV/a1b1_Nash.csv;
Player A reward, Player B reward,$H(g^A,g^B)$

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Choice probability,
xmin=0.1, xmax=2.4,
ymin=0, ymax=1.5,
grid style=dashed,
legend pos=north west,
every axis plot/.append style=thin,
label style=font=,
tick label style=font=,
legend style=nodes=scale=0.9, transform shape
[color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=4] CSV/a1b1_Nash.csv;
[color=red,mark=+,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=5] CSV/a1b1_Nash.csv;
[color=green,mark=x,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=6] CSV/a1b1_Nash.csv;

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Choice probability,
xmin=0.1, xmax=2.4,
ymin=0, ymax=1.5,
grid style=dashed,
legend pos=north west,
every axis plot/.append style=thin,
label style=font=,
tick label style=font=,
legend style=nodes=scale=0.9, transform shape
[color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=7] CSV/a1b1_Nash.csv;
[color=red,mark=+,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=8] CSV/a1b1_Nash.csv;
[color=green,mark=x,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=9] CSV/a1b1_Nash.csv;

Top: Case $a = 0$, $b =0$, $c = 3$, $d = 0$. Middle: Case $a = 0$, $b =1$, $c = 2$, $d = 0$. Bottom: Case $a = b = c = 1$, $d = 0$. Left: The expected utility of the players and the function $H$ at the $\epsilon$-approximate Nash equilibrium vs. $E_1$.  Middle: One possible solution for the probabilities of choosing different resources at the $\epsilon$-approximate Nash equilibrium for player A vs. $E_1$. Right: One possible solution for the probabilities of choosing different resources at  the $\epsilon$-approximate Nash equilibrium for player B vs. $E_1$.

In Fig. <ref>, it is interesting to notice the variation in choice probabilities of different resources with $E_1$. Notice that in scenario-1, the choice probability of resource 1 is; non-decreasing for $E_1 \in [0.1,0.8]$; non-increasing for $E_1\in [0.8,1.9]$; and non-decreasing for $E_1 \geq 1.9$. Similar behavior can be observed for scenario-3 as well. This is surprising since the intuition suggests that the probability of choosing a resource should increase with increasing mean of the reward random variable. But notice that in scenario-1 and scenario-3, player B does not observe the reward realization of resource 1. This might force player A, playing for the worst case, to believe that player B increases the probability of choosing resource 1 with increasing $E_1$, as a result of which player A chooses resource 1 with a lower probability. Notice that the probability of choosing resource 1 in scenario-3 does not grow as fast as the other two. This is because player A observes $W_1$ and hence can refrain from choosing it when $W_1$ takes low values.

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Expected Utility,
xmin=0.1, xmax=2.4,
ymin=0.7, ymax=1.3,
grid style=dashed,
legend pos=north west,
every axis plot/.append style=thin,
label style=font=,
tick label style=font=,
legend style=nodes=scale=0.5, transform shape
[color=black,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=1] CSV/a0b0_Worst.csv;

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Expected Utility,
xmin=0.1, xmax=2.4,
ymin=0.7, ymax=1.3,
grid style=dashed,
legend pos=north west,
every axis plot/.append style=thin,
label style=font=,
tick label style=font=,
legend style=nodes=scale=0.7, transform shape
[color=black,name path=lower,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=1] CSV/a0b1_Worst.csv;
[name path=upper,draw=none,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=2] CSV/a0b1_Worst.csv;
[fill=blue!10] fill between[of=upper and lower];

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Expected Utility,
xmin=0.1, xmax=4.8,
ymin=0.5, ymax=3,
grid style=dashed,
legend pos=north west,
every axis plot/.append style=thin,
label style=font=,
tick label style=font=,
legend style=nodes=scale=0.5, transform shape
[color=black,name path=lower,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=1] CSV/a1b1_Worst.csv;
[color=black,name path=upper,draw=none,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=2] CSV/a1b1_Worst.csv;
[fill=blue!10] fill between[of=upper and lower];

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Choice probability,
xmin=0.1, xmax=2.4,
ymin=0, ymax=1,
grid style=dashed,
legend pos=north west,
every axis plot/.append style=thin,
label style=font=,
tick label style=font=,
legend style=nodes=scale=0.7, transform shape
[color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=2] CSV/a0b0_Worst.csv;
[color=red,mark=+,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=3] CSV/a0b0_Worst.csv;
[color=green,mark=x,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=4] CSV/a0b0_Worst.csv;

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Choice probability,
xmin=0.1, xmax=2.4,
ymin=0, ymax=1,
grid style=dashed,
legend pos=north west,
every axis plot/.append style=thin,
label style=font=,
tick label style=font=,
legend style=nodes=scale=0.7, transform shape
[color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=3] CSV/a0b1_Worst.csv;
[color=red,mark=+,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=4] CSV/a0b1_Worst.csv;
[color=green,mark=x,thick,mark size=1pt,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=5] CSV/a0b1_Worst.csv;

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Choice probability,
xmin=0.1, xmax=4.8,
ymin=0, ymax=1,
grid style=dashed,
legend pos=north west,
every axis plot/.append style=thin,
label style=font=,
tick label style=font=,
legend style=nodes=scale=0.7, transform shape
[color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=3] CSV/a1b1_Worst.csv;
[color=red,mark=+,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=4] CSV/a1b1_Worst.csv;
[color=green,mark=x,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=5] CSV/a1b1_Worst.csv;

Left: Case $a = 0$, $b =0$, $c = 3$, $d = 0$. Middle: Case $a = 0$, $b =1$, $c = 2$, $d = 0$. Right: Case $a = b = c = 1$, $d = 0$. Top: The maximum expected worst-case utility of player A vs. $E_1$ and the possible region for the exact maximum expected worst-case utility of player A (shaded in blue). Bottom: One possible solution for the probabilities of choosing different resources for player A vs. $E_1$ (Notice the difference of the range of $E_1$ values for scenario-3).

§ CONCLUSIONS

We have implemented the iterative best response algorithm to find the $\epsilon$-approximate Nash equilibrium of a two-player stochastic resource-sharing game with asymmetric information. To handle situations where the players do not trust each other and place no assumptions on the incentives of the opponent, we solved the problem of maximizing the worst-case expected utility of the first player using a novel algorithm that combines drift-plus penalty theory and online optimization techniques. An explicit solution can be constructed when both players do not observe the realizations of any of the reward random variables. This special case leads to counter-intuitive insights. Extending the work to scenarios with multiple players and improving the algorithm to be implemented in an online scenario are possible future work.

§ PROOF OF THEOREM <REF>

Notice that the term $\mathbb{E}\{\text{max}\{\Omega_jx_j; 1 \leq j \leq n\}|\vec{Z}\}$ of $f$ is convex since the max function is convex and expectation preserves convexity. Hence $f$ is concave.

For the 2, and 3, we use the two inequalities,

\begin{align}\label{eqn:entrywise_inc}
f&(\vec{x}) - f(\vec{y}) \geq\sum_{j \in \mathcal{A}} (x_j\hspace{-1mm}-y_j) +\hspace{-1mm}\sum_{j\in \mathcal{A}^c} E_j (x_j - y_j)-\frac{1}{2}\mathbb{E}\{\text{max}\{\Omega_j(x_{j}-y_j);j\in [1:n]\}|\vec{Z}\},
\end{align}

\begin{align}\label{eqn:Lipschitz}
f&(\vec{x}) - f(\vec{y}) \leq\sum_{j \in \mathcal{A}} (x_j\hspace{-1mm}-y_j) +\hspace{-1mm}\sum_{j\in \mathcal{A}^c} E_j (x_j - y_j)+\frac{1}{2}\mathbb{E}\{\text{max}\{\Omega_j(y_{j}-x_j);j\in [1:n]\}|\vec{Z}\},
\end{align}

both of which follow from the fact that for real numbers $\gamma_1,\gamma_2,\gamma_3,\gamma_4$, $\text{max}\{\gamma_1+\gamma_2,\gamma_3+\gamma_4\} \leq \text{max}\{\gamma_1,\gamma_3\}+\text{max}\{\gamma_2,\gamma_4\}$.

For 2, we consider $\vec{x} \geq \vec{y}$ where the inequality is entry-wise. Notice that,

\begin{align*}
f(\vec{x}) - f(\vec{y}) &\geq \sum_{j\in \mathcal{A}} (x_j-y_j) +\sum_{j\in \mathcal{A}^c} E_j (x_j - y_j)  -\frac{1}{2}\mathbb{E}\Bigg{\{}\sum_{j = 1}^n\Omega_j(x_j-y_j)\Bigg{|}\vec{Z}\Bigg{\}}\nonumber\\&=  \sum_{j \in \mathcal{A}}\frac{1}{2}(x_j-y_j) +\sum_{j \in \mathcal{A}^c} \frac{E_j}{2} (x_j - y_j),
\end{align*}

where the inequality follows from (<ref>) and the fact that for $\gamma_1,\gamma_2 \geq 0$, $\text{max}\{\gamma_1,\gamma_2\} \leq \gamma_1+\gamma_2$.

For 3, note that

\begin{align}
&f(\vec{x}) - f(\vec{y}) \leq_{(a)} \sum_{j \in \mathcal{A}} |x_j-y_j| +\sum_{j \in \mathcal{A}^c} E_j |x_j - y_j| +\frac{1}{2}\mathbb{E}\Bigg{\{}\sum_{j =1}^n \Omega_j|x_j-y_j|\Bigg{|}\vec{Z}\Bigg{\}}\nonumber\\&= \frac{3}{2}\sum_{j \in \mathcal{A}} |x_j-y_j| +\frac{3}{2}\sum_{j \in \mathcal{A}^c} E_j |x_j - y_j|,
\end{align}

where (a) follows from (<ref>) and the fact that for $\gamma_1,\gamma_2 \geq 0$, $\text{max}\{\gamma_1,\gamma_2\} \leq \gamma_1+\gamma_2$.

§ PROOF OF THEOREM <REF>

Define the vector-valued function $P^A: \mathbb{R}^{a+d} \mapsto \mathbb{R}^n$ where,

\begin{align}\label{eqn:def_strt_fun}
&P^A_k(\vec{x},\vec{z}) =\begin{cases}
\text{Pr}\{\alpha^{A} = k|\vec{X} = \vec{x},\vec{Z} = \vec{z}\} & \text{ if } \text{Pr}\{\vec{X} = \vec{x},\vec{Z} = \vec{z}\} >0,\\
0 & \text{ otherwise},
\end{cases}
\end{align}

for $k \in [1:n]$.

Notice that the function $P^A$ completely determines the probabilistic decision of player A. We call $P^A$ the strategy function of player A.

Take any $(\vec{\alpha},\vec{\psi}),(\vec{\eta},\vec{\theta}) \in \mathcal{G}^A$. Then there exists strategies $g^{A,1}$ and $g^{A,2}$ with strategy functions $P^{A,1}$, and $P^{A,2}$ such that,

\begin{align}
&\alpha_{k} = \mathbb{E}\{P^{A,1}_k(\vec{X},\vec{Z})|\vec{Z}\},\  \ \eta_{k} = \mathbb{E}\{P^{A,2}_k(\vec{X},\vec{Z})|\vec{Z}\} \text{ for } 1\leq k \leq n,\nonumber\\
&\psi_{l} = \mathbb{E}\{W_lP^{A,1}_l(\vec{X},\vec{Z})|\vec{Z}\}, \ \ \theta_{l} = \mathbb{E}\{W_lP^{A,2}_l(\vec{X},\vec{Z})|\vec{Z}\}\text{ for } 1\leq  l \leq a.
\end{align}

Consider $\lambda \in [0,1]$, and define $P^{A,*}= \lambda P^{A,1} + (1-\lambda) P^{A,2}$. Hence,

\begin{align}
\lambda (\vec{\alpha},\vec{\psi})+(1-\lambda)(\vec{\eta},\vec{\theta}) =  (\lambda\vec{\alpha}+(1-\lambda)\vec{\eta},\lambda\vec{\psi}+(1-\lambda)\vec{\theta})  = (\vec{\beta}, \vec{\gamma}),
\end{align}

\begin{align}
&\beta_{k} = \mathbb{E}\{P^{A,*}_k(\vec{X},\vec{Z})|\vec{Z}\} \text{ for } 1\leq k \leq n,\nonumber\\
&\gamma_{l} = \mathbb{E}\{W_lP^{A,*}_l(\vec{X},\vec{Z})|\vec{Z}\}\text{ for } 1\leq l \leq a.
\end{align}

Notice that $P^{A,*}$ is the strategy function of the strategy $g^{A,*}$ of using $g^{A,1}$ and $g^{A,2}$ in a mixture with probabilities $\lambda$ and $1 -\lambda$. Hence $(\vec{\beta}, \vec{\gamma}) \in \mathcal{G}^A$, which completes the proof.

§ PROOF OF LEMMA <REF>

We begin with several results which are used in the proof.

If $(\vec{p}^*,\gamma^*)$ solves the problem,

p⃗,γ∑_k =1^n p_kE_k - 1/2γ(P2-1):
p⃗ ∈ℐ
γ ≥p_kE_k   ∀1 ≤k ≤n ,

where $\mathcal{I}$ is the $n$-dimensional probability simplex defined in (<ref>), then $\vec{p}^*$ solves (P2).

\begin{align}\label{eqn:def_f_1}
f_1(\vec{p}, \gamma) = \sum_{k =1}^n p_kE_k - \frac{1}{2}\gamma.
\end{align}

Notice that, $f(\vec{p}) = f_1(\vec{p}, \max\{p_kE_k; 1\leq k \leq n\})$.
Let $(\vec{p}^*,\gamma^*)$ be a solution for (P2-1). Notice that for $(\vec{p}^*, \gamma^*)$ to be feasible for (P2-1), we should have, $\gamma^* \geq \max\{p^*_kE_k; 1\leq k \leq n\}$. But if $\gamma^* > \max\{p^*_kE_k; 1\leq k \leq n\}$, we have that $f_1(\vec{p}, \max\{p^*_kE_k; 1\leq k \leq n\}) > f_1(\vec{p}^*, \gamma^*)$ which contradicts the optimality of $(\vec{p}^*, \gamma^*)$ for (P2-1). Hence,   $\gamma^* = \max\{p^*_kE_k; 1\leq k \leq n\}$. Hence we have, $f(\vec{p}^*) = f_1(\vec{p}^*, \gamma^*)$.

Now consider $\vec{\tilde{p}} \in \mathcal{I}$. Define $\tilde{\gamma} = \max\{\tilde{p}_kE_k; 1\leq k \leq n\}$. Since $(\vec{\tilde{p}}, \tilde{\gamma})$ is also feasible for (P2-1), we should have $f_1(\vec{\tilde{p}}, \tilde{\gamma}) \leq f_1(\vec{p}^*, \gamma^*)$. This implies  $f(\vec{p}^*) \geq f(\vec{\tilde{p}})$. Hence $\vec{p}^*$ is the optimal solution of (P2).

Consider fixed $\vec{\mu} \in \mathbb{R}^n$ such that $\mu_k \geq 0$ for all $1\leq k \leq n$. Now consider the unconstrained problem,

f_2(p⃗,γ) = ∑_k =1^n p_kE_k - 1/2γ+ ∑_k=1^n μ_k (γ-p_k  E_k )(P2-2):
p⃗ ∈ℐ.

Assume $(\vec{p}^*,\gamma^*)$ is a solution (P2-2). Additionally, assume that,

\begin{align}\label{eqn:ineq_lagr}
&E_k p_k^* \leq \gamma^* \text{ for all } 1 \leq k \leq n,\nonumber\\
&E_k p_k^* = \gamma^*  \text{ whenever } \mu_k > 0.
\end{align}

Then $(\vec{p}^*,\gamma^*)$ is a solution for (P2-1).

First, notice that $(\vec{p}^*,\gamma^*)$ satisfies the constraints of (P2-1). To show that it maximizes the objective in (P2-1), consider any $(\vec{p},\gamma)$ that is feasible for (P2-1). Notice that,

\begin{align}
f_1(\vec{p},\gamma) &= f_2(\vec{p}, \gamma) - \sum_{\mu_k >0} \mu_k (\gamma-p_k  E_k ) \nonumber\\&\leq_{(a)} f_2(\vec{p}^*, \gamma^*) - \sum_{\mu_k >0} \mu_k (\gamma-p_k  E_k )  \nonumber\\& = f_1(\vec{p}^*, \gamma^*) + \sum_{\mu_k >0} \mu_k (\gamma^* - p^*_kE_k -\gamma+p_k  E_k )\nonumber\\& =_{(b)} f_1(\vec{p}^*, \gamma^*) - \sum_{\mu_k >0} \mu_k ( \gamma - p_k  E_k )  \leq_{(c)} f_1(\vec{p}^*, \gamma^*),
\end{align}

where $f_1$ is the objective of (P2-1) defined in (<ref>), $f_2$ is the objective of (P2-2), (a) follows from the optimality of $(\vec{p}^*,\gamma^*)$ for (P2-2), (b) follows due to (<ref>), and (c) follows since $\mu_k \geq 0$ and $(\vec{p},\gamma)$ is feasible for (P2-1). Hence we have the result.

\begin{align}
S_k = \sum_{j=1}^k \frac{1}{E_j},
\end{align}

for $1 \leq k \leq n$. We also establish the following lemma, which is useful in our solution.

\begin{align}\label{eqn:def_r}
r = \arg\max_{1 \leq k \leq n} \frac{k - \frac{1}{2}}{S_k},
\end{align}

where $\arg\max$ returns the lowest index in case of ties. Let us also define $\vec{\mu} \in \mathbb{R}^n$ as,

\begin{align}\label{eqn:def_mu}
\mu_k = \begin{cases}
1-\frac{1}{E_k}\frac{r - \frac{1}{2}}{S_r} & \text{ if } 1 \leq k \leq r,\\
0 & \text{ otherwise. }
\end{cases}
\end{align}

Then we have,

* $\mu_k \geq 0$ for all $k$ such that $1 \leq k \leq n$.

* $\sum_{k=1}^n \mu_k = \frac{1}{2}$.

* $E_k(1-\mu_k) = \frac{r-\frac{1}{2}}{S_r}$ for $1 \leq k \leq r$.

* $E_k(1-\mu_k)  \leq \frac{r-\frac{1}{2}}{S_r}$ for $r+1 \leq k \leq n$.

* Notice that by the definition of $\mu_k$, it is enough to prove the result for $1 \leq k \leq r$. Notice that we are required to prove that,

\begin{align}
\frac{1}{E_k}\frac{r - \frac{1}{2}}{S_r} \leq 1,
\end{align}

for all $ 1 \leq k \leq r$. Since $E_k \geq E_{k+1}$ for $1 \leq k \leq n-1$, it suffices to prove that,

\begin{align}
\frac{1}{E_r}\frac{r - \frac{1}{2}}{S_r} \leq 1.
\end{align}

We consider two cases.

Case 1: $r = 1$.
This case reduces to,

\begin{align}
\frac{1}{2E_1} \leq \frac{1}{E_1},
\end{align}

which is trivial.

Case 2: $r > 1$.
Note that from the definition of $r$ in (<ref>), we have,

\begin{align}
\frac{r-\frac{1}{2}}{S_r} \geq \frac{r-\frac{3}{2}}{S_{r-1}}.
\end{align}

After substituting $S_{r-1} = S_r - \frac{1}{E_{r}}$, and rearranging we have the desired result.

* Notice that,

\begin{align}
\sum_{k=1}^n \mu_k = \sum_{k=1}^r \mu_k = \sum_{k=1}^r \left( 1-\frac{1}{E_k}\frac{r - \frac{1}{2}}{S_r} \right) = r - \frac{r - \frac{1}{2}}{S_r} \sum_{k=1}^r \frac{1}{E_k} =  r - \frac{r - \frac{1}{2}}{S_r} S_r = \frac{1}{2}.
\end{align}

* This follows from the definition of $\mu_k$ for $1 \leq k \leq r$.

* There is nothing to prove if $r = n$. Hence we can assume $r<n$. Since $\mu_k = 0$ for $k \geq r+1$, it suffices to prove that, $E_k \leq \frac{r-(1/2)}{S_r}$. Notice that if we can prove the result for $k = r+1$, we are done since $E_k \geq E_{k+1}$ for $1\leq k \leq n$. Note that from the definition of $r$ in (<ref>), we have,

\begin{align}
\frac{r-\frac{1}{2}}{S_r} \geq \frac{r+\frac{1}{2}}{S_{r+1}}.
\end{align}

After substituting $S_{r+1} = S_r + \frac{1}{E_{r+1}}$, and rearranging we have the desired result.

Now we solve the problem using the above lemmas. Consider the problem defined in Lemma <ref> with $\vec{\mu}$ defined in Lemma <ref>. Specifically, consider the problem,

f_2(p⃗,γ) = ∑_k =1^n p_kE_k - 1/2γ+ ∑_k=1^n μ_k (γ-p_k  E_k )(P2-3):
p⃗ ∈ℐ,

where $\vec{\mu}$ and $r$ are defined in (<ref>)-(<ref>). For this choice of $\mu_k$ we have,

\begin{align}
f_2(\vec{p},\gamma) = \sum_{k =1}^n p_kE_k(1-\mu_k) + \gamma \left(\sum_{k=1}^n \mu_k -\frac{1}{2}\right) =  \sum_{k =1}^n p_kE_k(1-\mu_k),
\end{align}

where the last equality follows from Lemma <ref>-2. Now due to Lemma <ref>-3, and Lemma <ref>-4, the optimal solution for (P2-3) is any $(\vec{p}, \gamma)$ such that $\gamma \in \mathbb{R}$, and $\vec{p} \in \mathcal{I}$ such that $p_k = 0$ for $k  >r$. In particular, consider the solution $(\vec{p}^*, \gamma^*)$ given by,

\begin{align}
p^*_k = \begin{cases}
\frac{1}{E_kS_r} & \text{ if } k \leq r,\\
0 & \text{ otherwise, }
\end{cases}
\end{align}

and $\gamma^* = \frac{1}{S_r}$. Notice that for $1 \leq k \leq r$, we have that, $p^*_kE_k = \gamma^*$, and $p^*_kE_k = 0 \leq \gamma$ for $r+1 \leq k \leq n$. Hence from Lemma <ref>, $(\vec{p}^*, \gamma^*)$ is a solution for (P2-1). Hence from Lemma <ref>, $\vec{p}^*$ is a solution for (P2) as desired.

§ PROOF OF LEMMA <REF>

Notice that,

\begin{align}
\Delta&(t)  = \mathbb{E}\{L(t+1)-L(t) | \mathcal{H}(t),\vec{Z}\} =
\frac{1}{2}\mathbb{E}\left\{\sum_{j=1}^nQ_j(t+1)^2-Q_j(t)^2 \Bigg{|} \mathcal{H}(t),\vec{Z}\right\} \nonumber\\&= \frac{1}{2}\sum_{j=1}^n\mathbb{E}\{Q_j(t+1)^2|\mathcal{H}(t),\vec{Z}\}-\frac{1}{2}\sum_{j=1}^nQ_j(t)^2\nonumber\\&= \frac{1}{2}\sum_{j=1}^n\mathbb{E}\{\text{max}\left\{Q_j(t)+\gamma_j(t)-x_j(t),0\right\}^2|\mathcal{H}(t),\vec{Z}\} -\frac{1}{2}\sum_{j=1}^nQ_j(t)^2\nonumber\\&\leq \frac{1}{2}\sum_{j=1}^n\mathbb{E}\{(Q_j(t)+\gamma_j(t)-x_j(t))^2|\mathcal{H}(t),\vec{Z}\} - \frac{1}{2}\sum_{j=1}^nQ_j(t)^2
\nonumber \\&\leq  \sum_{j=1}^nQ_j(t)\big{(}\gamma_j(t)-\mathbb{E}\{x_j(t)|\mathcal{H}(t),\vec{Z}\}\big{)}+\frac{1}{2}\sum_{j=1}^n \gamma_j(t)^2 +\frac{1}{2}\sum_{j=1}^n \mathbb{E}\{x_j(t)^2|\mathcal{H}(t),\vec{Z}\} \nonumber\\&\leq_{(a)} \sum_{j=1}^nQ_j(t)\big{(}\gamma_j(t)-\mathbb{E}\{x_j(t)|\mathcal{H}(t),\vec{Z}\}\big{)}+\frac{1}{2}\sum_{j\in \mathcal{A}} E_j^2 + \frac{n-a}{2}\nonumber\\& \ \ \ +\frac{1}{2}\sum_{j \in \mathcal{A}} \mathbb{E}\{(X_j(t)\mathbbm{1}_{\{\alpha(t)=k\}})^2|\mathcal{H}(t),\vec{Z}\}+\frac{1}{2}\sum_{j \in \mathcal{A}^c}\mathbb{E}\{(\mathbbm{1}_{\{\alpha(t)=k\}})^2|\mathcal{H}(t),\vec{Z}\} \nonumber\\&\leq \sum_{j=1}^nQ_j(t)\big{(}\gamma_j(t)-\mathbb{E}\{x_j(t)|\mathcal{H}(t),\vec{Z}\}\big{)}+\frac{1}{2}\sum_{j \in \mathcal{A}} E_j^2+\frac{n-a}{2}+ \frac{1}{2}\sum_{j \in \mathcal{A}} \mathbb{E}\{X_j(t)^2|\mathcal{H}(t),\vec{Z}\}\nonumber\\& \ \ \ +\frac{1}{2}\sum_{j \in \mathcal{A}^c} \mathbb{E}\{1|\mathcal{H}(t),\vec{Z}\} \nonumber\\&=_{(b)} \sum_{j=1}^nQ_j(t)\big{(}\gamma_j(t)-\mathbb{E}\{x_j(t)|\mathcal{H}(t),\vec{Z}\}\big{)}+\frac{1}{2}\sum_{j \in \mathcal{A}} E_j^2 + \frac{n-a}{2}+\frac{1}{2}\sum_{j \in \mathcal{A}} \mathbb{E}\{W_j^2\}+\frac{n-a}{2} \nonumber\\&=   \sum_{j=1}^nQ_j(t)\big{(}\gamma_j(t)-\mathbb{E}\{x_j(t)|\mathcal{H}(t),\vec{Z}\}\big{)}+D_1,
\end{align}

where the inequality (a) follows since $\vec{\gamma}(t) \in \mathcal{K}$ and  equality (b) follows from the fact that $\vec{X}(t)$ is independent of $\mathcal{H}(t)$ and $\vec{Z}$.

§ PROOF OF LEMMA <REF>

Notice that,

\begin{align}
f^{'}_t(\vec{\gamma}(t-1)) = \vec{v}-\frac{1}{2}\vec{\tilde{\Omega}}(t),
\end{align}

where $\vec{v}$ is defined by,

\begin{align}
v_j = \begin{cases}
1 & \text{ if } j \in \mathcal{A},\\
E_j & \text{ if } j \in \mathcal{A}^c.
\end{cases}
\end{align}

$\vec{\tilde{\Omega}}(t)$ is given by, $\tilde{\Omega}_k(t) = \Omega_k(t)\mathbbm{1}_{\{\arg\max_{1\leq j \leq n}\{ \gamma_j(t-1)\Omega_j(t)\} = k\}}$, and $\arg\max$ return the least index in case of ties. Notice that

\begin{align}
& -Vf^{'}_t(\vec{\gamma}(t-1))^{\top}\left\{\vec{\gamma}(t) -\vec{\gamma}(t-1)\right\}+\alpha \lVert\vec{\gamma}(t)-\vec{\gamma}(t-1) \rVert_2^2 \nonumber\\& \geq_{(a)} -V\lVert f^{'}_t(\vec{\gamma}(t-1)) \rVert_2 \lVert \vec{\gamma}(t) -\vec{\gamma}(t-1)\rVert_2+\alpha \lVert\vec{\gamma}(t)-\vec{\gamma}(t-1) \rVert_2^2 \nonumber\\&= \alpha \left(\lVert\vec{\gamma}(t)-\vec{\gamma}(t-1) \rVert_2 - \frac{V}{2\alpha}\lVert f^{'}_t(\vec{\gamma}(t-1)) \rVert_2 \right)^2- \frac{V^2}{4\alpha}\lVert f^{'}_t(\vec{\gamma}(t-1))\rVert_2^2 \nonumber\\&\geq - \frac{V^2}{4\alpha}\lVert f^{'}_t(\vec{\gamma}(t-1))\rVert_2^2= - \frac{V^2}{4\alpha}\left\lVert\vec{v}-\frac{1}{2}\vec{\tilde{\Omega}}(t)\right\rVert_2^2 \geq_{(b)} - \frac{V^2}{4\alpha}\lVert\vec{v}\rVert_2^2-\frac{V^2}{16\alpha}\lVert\vec{\tilde{\Omega}}(t)\rVert_2^2  \nonumber\\&\geq  - \frac{V^2}{4\alpha}\left(a + \sum_{j\in \mathcal{A}^c}E_j^2\right)-\frac{V^2}{16\alpha}\lVert\vec{\Omega}(t)\rVert_2^2,
\end{align}

where (a) follows from the Cauchy-Schwarz inequality, (b) follows since $v_k\geq 0$, and $\tilde{\Omega}_k(t) \geq 0$ for all $1\leq k \leq n$.

§ PROOF OF LEMMA <REF>

Notice that from the definition of $Q_j(t+1)$ in (<ref>) and the definition of $x_j(t)$ in (<ref>) we have that,

\begin{align}
Q_j(t+1) - Q_j(t) \geq  \gamma_j(t)- x_j(t),
\end{align}

for all $1\leq j \leq n$ and $1 \leq t \leq T-1$. Summing the above from $1$ to $T-1$ we have that,

\begin{align}
Q_j(T) - Q_j(1) \geq  \sum_{t=1}^{T-1} \{\gamma_j(t)- x_j(t)\}.
\end{align}

After using $Q_j(1) = 0$, taking expectations conditioned on $\vec{Z}$, and some algebraic manipulations we have,

\begin{align}
\frac{\mathbb{E}\{Q_j(T)|\vec{Z}\}}{T} \geq  \frac{1}{T}\sum_{t=1}^{T-1} \mathbb{E}\{\gamma_j(t)- x_j(t)|\vec{Z}\}.
\end{align}

We have the desired inequality from the above since $Q_j(T)$ is non-negative.

§ PROOF OF LEMMA <REF>

Define the $\vec{v},\vec{u}$ as follows.

\begin{align}\label{eqn:def_vs_1}
v_k = \begin{cases}
1 & \text{ if } k\in\mathcal{A},\\
E_k & \text{ if } k \in \mathcal{A}^c,
\end{cases} \text{ and } u_k = \begin{cases}
E_k & \text{ if } k\in\mathcal{A},\\
1 & \text{ if } k \in \mathcal{A}^c.
\end{cases}
\end{align}

Hence we are required to prove that $Q_j(t) \leq (v_j+2\sqrt{2}u_j)\sqrt{\alpha}+u_j$ for all $t \in [1:T]$.

We begin with several important results.

We have the following results regarding $Q_j(t)$.

* $Q_j(t+1) \leq Q_j(t) + u_j$ for all $t\geq 1$.

* Assume $Q_j(t) \geq (v_j+\sqrt{2}u_j)\sqrt{\alpha}$ for some $t\geq 1$. Then we have, either $\gamma_j(t) = 0$ or

\begin{align}
\gamma_j(t) \leq \gamma_j(t-1) -\frac{u_j}{\sqrt{2\alpha}}.
\end{align}

* Assume $Q_j(\tau) \geq (v_j+\sqrt{2}u_j)\sqrt{\alpha}$ for all $\tau \in [t: t+t_0]$, where $t\geq 1$ and $t_0 \geq 0$. Additionally assume $\gamma_j(t-1) = 0$. Then $\gamma_j(\tau) = 0$ for all $\tau \in [t-1:t+t_0]$.

* Notice that from the definition of $Q_j(t+1)$ in (<ref>), for $j \in \mathcal{A}$ we have

\begin{align}
Q_j(t+1) &= \max \left\{Q_j(t) + \gamma_j(t) - X_j(t)\mathbbm{1}_{\{ \alpha^A(t)= j\}},0\right\} \leq \max \left\{Q_j(t) + u_j,0\right\} \nonumber\\&= Q_j(t) + u_j,
\end{align}

where the inequality follows from the definition of $u_j$ in (<ref>). The same argument can be repeated for $j \in \mathcal{A}^c$.

* Notice that if $\gamma_j(t) \neq 0$ then we have

\begin{align}
\gamma_j(t) \leq \gamma_j(t-1)-\frac{-V f^{'}_{t,j}(\vec{\gamma}(t-1)) + Q_j(t)}{2\alpha},
\end{align}

which follows since $\gamma_j(t)$ is the projection of $\gamma_j(t-1)-\frac{-V f^{'}_{t,j}(\vec{\gamma}(t-1))  + Q_j(t)}{2\alpha}$ onto $[0,u_j]$ (See (<ref>)).
Hence we have that,

\begin{align}
\gamma_j(t) &\leq \gamma_j(t-1)-\frac{-V f^{'}_{t,j}(\vec{\gamma}(t-1))  + Q_j(t)}{2\alpha} \nonumber\\&\leq_{(a)} \gamma_j(t-1)-\frac{-V v_j  + (v_j+\sqrt{2}u_j)\sqrt{\alpha}}{2\alpha} \leq_{(b)} \gamma_j(t-1)-\frac{u_j}{\sqrt{2\alpha}},
\end{align}

where (a) follows from the subgradients of $f_t$ found in (<ref>) and (b) follows from $\alpha \geq V^2$.

* Notice if we prove $\gamma_j(t) = 0$, we can use the same argument inductively to establish the result. Assume the contrary that $\gamma_j(t) \neq 0$. Then from part-2, we should have,

\begin{align}
\gamma_j(t) \leq \gamma_j(t-1) -\frac{u_j}{\sqrt{2\alpha}} = -\frac{u_j}{\sqrt{2\alpha}},
\end{align}

which is a contradiction since $\gamma_j(t)\geq 0$. Hence we have the result.

Now we use an inductive argument to prove the main result. Notice that the result is true for $t = 1$, since $Q_j(1) = 0 \leq (v_j+2\sqrt{2}u_j)\sqrt{\alpha}+u_j$. Now we prove that $Q_j(t+1) \leq  (v_j+2\sqrt{2}u_j)\sqrt{\alpha}+u_j$ for $t \geq 1$, with the assumption that,
$Q_j(t) \leq  (v_j+2\sqrt{2}u_j)\sqrt{\alpha}+u_j$.

We consider three cases.

Case 1: $Q_j(t) \leq (v_j+2\sqrt{2}u_j)\sqrt{\alpha}$. This case follows from Lemma <ref>-1.

Case 2: $t \leq \sqrt{2\alpha}+1$. Notice that,

\begin{align}
Q_j(t+1) \leq Q_j(1) + u_jt \leq  (\sqrt{2\alpha}+1)u_j \leq (v_j+2\sqrt{2}u_j)\sqrt{\alpha}+u_j,
\end{align}

where first inequality follows from Lemma <ref>-1.

Case 3: $t > \sqrt{2\alpha}+1$ and $Q_j(t) > (v_j+2\sqrt{2}u_j)\sqrt{\alpha}$. For this, we prove that $\gamma_j(t) = 0$, which establishes the claim from the definition of $Q_j(t+1)$ in (<ref>) and the induction hypothesis.

Notice that for all $u \in [1 : t]$ we have,

\begin{align}
Q_j(u) &\geq_{(a)} Q_j(t) -  (t-u)u_j \geq (v_j+2\sqrt{2}u_j)\sqrt{\alpha} -  (t-u)u_j \nonumber\\& = (v_j+\sqrt{2}u_j)\sqrt{\alpha}+ \sqrt{2\alpha}u_j-  (t-u)u_j,
\end{align}

where (a) follows from Lemma <ref>-1.

Hence, for all $u \in \mathbb{Z}$ such that $t-\sqrt{2\alpha}\leq  u \leq t$, we have that,

\begin{align}
Q_j(u) \geq  (v_j+\sqrt{2}u_j)\sqrt{\alpha}.
\end{align}

Now we prove that there exists $u \in \mathbb{Z}$ such that $t-\sqrt{2\alpha} \leq  u \leq t$ and $\gamma_j(u) = 0$, which will establish that $\gamma_j(t) = 0$ from Lemma <ref>-3. For the proof assume the contrary $\gamma_j(u) > 0$ for all $u \in \mathbb{Z}$ such that $t-\sqrt{2\alpha} \leq  u \leq t$ (or $u \in [t-\left\lfloor\sqrt{2\alpha}\right\rfloor :t]$, where $\lfloor x \rfloor$ denotes the largest integer smaller than or equal to $x$). From Lemma <ref>-2 we have that,

\begin{align}
\gamma_j(t) \leq \gamma_j\left(t-\left\lfloor\sqrt{2\alpha}\right\rfloor-1\right) - \frac{\left(\left\lfloor\sqrt{2\alpha}\right\rfloor+1\right)u_j}{\sqrt{2\alpha}} \leq 0,
\end{align}

where the last inequality follows since $\lfloor x \rfloor + 1 \geq x$ and $\gamma_j\left(t-\left\lfloor\sqrt{2\alpha}\right\rfloor-1\right) \leq u_j$. Hence we should have that $\gamma_j(t) = 0$ which contradicts our initial assumption. Hence we are done.

§ SOME SPECIAL CASES IN WHICH SIMPLER ALTERNATIVE SOLUTIONS EXIST

Below we discuss two special cases in which a simpler solution can be obtained for the worst-case expected utility maximization problem. First, we discuss the case $a = 0$ (with no restriction on $b \in \{0,1,\dots,n\}$), after which we discuss the case $a = 1$ where $W_1$ is assumed to have a continuous CDF.

§.§ Mirror descent solution for $a = 0$

Observe that when $a=0$ (with no restriction on $b \in \{0,1,\dots,n\}$), (P1.1) can be written as,

p⃗∑_k =1^n p_kE_k  -1/2𝔼{max{ p_kΩ_k; 1 ≤k ≤n }}(P4):

where $\mathcal{I}$ is the simplex set defined in Theorem <ref>.
Define $\mathcal{I}^0 = \mathcal{I} \cap \mathbb{R}^n_{+}$. We use the online mirror descent algorithm to solve this problem. We first formulate the above problem as an online convex optimization problem, where we obtain the solution by iteratively updating $\vec{p}$ for $T$ iterations. In the $t$-th iteration, we sample $\vec{\Omega}(t)$ from the distribution of $\vec{\Omega}$, where $\vec{\Omega}$ is defined in (<ref>). Let,

\begin{align}
f_t(\vec{p}) = -\sum_{k =1}^n p_kE_k  +\frac{1}{2}\text{max}\{ p_k\Omega_k(t); 1 \leq k \leq n \}.
\end{align}

Let $\vec{p}(t)$ denote the value of $\vec{p}$ after $t$-th iteration. we begin with $\vec{p}(0) = [1/n,1/n,\dots,1/n]$, and we obtain $\vec{p}(t)$ $(1 \leq t \leq T)$ by solving,

p⃗(t)∇f_t(p⃗(t-1))^⊤(p⃗(t) - p⃗(t-1)) + αD(p⃗(t)‖p⃗(t-1)) (P4-1):

where $D(\vec{x} \lVert \vec{y})$ denotes the Kullback-Leibler divergence between $\vec{x}$ and $\vec{y}$ given by,

\begin{align}
D(\vec{x}||\vec{y}) = \sum_{k=1}^n x_k \ln\left(\frac{x_k}{y_k}\right),
\end{align}

for $\vec{x} \in \mathcal{I}$ and $\vec{y} \in \mathcal{I}^0$, $\nabla f_t(\vec{x}) \in \mathbb{R}^n$ is the subgradient of $f_t$ at $\vec{x}$ which is given by,

\begin{align}\label{eqn:sub_grd_pk_1}
(\nabla f_t(\vec{x}))_j = -E_j + \frac{1}{2}\mathbbm{1}_{(\arg\max_{1\leq k \leq n}\{ x_k\Omega_k(t)\} = j)} \Omega_j(t),
\end{align}

for each $1\leq j \leq n$, and $\alpha$ is the constant step size. It is assumed that $\arg\max$ returns the lowest index in the case of ties. It should be noted that $\vec{p}(t)$ can be found explicitly [34]. The solution is given by,

\begin{align}\label{eqn:pkt}
p_k(t) = \frac{p_k(t-1)\exp\left(-\frac{(\nabla f_t(\vec{p}(t-1)))_k}{\alpha}\right)}{\sum_{j=1}^n p_j(t-1)\exp\left(-\frac{(\nabla f_t(\vec{p}(t-1)))_j}{\alpha}\right)},
\end{align}

for each $k$ such that $1 \leq k \leq n$. Note that $\vec{p}(t) \in \mathcal{I}^0$. This is useful when establishing the performance bound of the algorithm.

We summarize the above algorithm under Algorithm <ref> for brevity.

Initialize $\vec{p}(0) = [1/n,1/n,\dots,1/n]$

each iteration $1\leq t \leq T$
Sample $\vec{\Omega}(t)$ from the distribution of $\vec{\Omega}$

Calculate the subgradient $\nabla f_t(\vec{p}(t-1))$ according to (<ref>)

Obtain $\vec{p}(t)$ according to (<ref>)

Calculate $\vec{p}^* =\frac{1}{T}\sum_{t=1}^{T}\vec{p}(t-1)$
Mirror descent algorithm to solve the case $a = 0$

We have the following lemma regarding the performance of the above algorithm.

Let $\vec{p} = \frac{1}{T} \sum_{t=1}^T \vec{p}(t-1)$. Then we have that,

\begin{align}
\mathbb{E}\{f(\vec{p})|\vec{Z}\} -f^{*} \geq  -\frac{2\lVert \vec{E}\rVert_{\infty}^2+\frac{1}{2}\mathbb{E}\left\{\left \lVert\vec{\Omega} \right\rVert^2_{\infty}|\vec{Z}\right\}}{2\alpha } - \frac{\alpha}{T}\ln(n),
\end{align}

where $f^{*}$ denotes the optimal value of (P4). Hence for $\alpha = \mathcal{O}(1/ \varepsilon)$, and $T = \mathcal{O}(1/\varepsilon^2)$, the error is $\mathcal{O}(\varepsilon)$.

We begin with a few lemmas, which are useful in the proof.

We have that,

\begin{align}
\nabla f_t(\vec{p}(t-1))^{\top}(\vec{p}(t) - \vec{p}(t-1)) + \alpha D(\vec{p}(t) \lVert \vec{p}(t-1)) \geq  -\frac{1}{2\alpha}\lVert\nabla f_t(\vec{p}(t-1))\rVert_{\infty}^2.
\end{align}

Notice that,

\begin{align}
&\nabla f_t(\vec{p}(t-1))^{\top}(\vec{p}(t) - \vec{p}(t-1)) + \alpha D(\vec{p}(t) \lVert \vec{p}(t-1)) \nonumber\\&\geq_{(a)} -\lVert\nabla f_t(\vec{p}(t-1))\rVert_{\infty}\lVert\vec{p}(t) - \vec{p}(t-1))\rVert_1 + \alpha D(\vec{p}(t) \lVert \vec{p}(t-1))\nonumber\\&\geq_{(b)} -\lVert\nabla f_t(\vec{p}(t-1))\rVert_{\infty}\lVert\vec{p}(t) - \vec{p}(t-1))\rVert_1 + \frac{1}{2}\alpha \lVert\vec{p}(t) -\vec{p}(t-1)\rVert_1^2 \nonumber\\& =\frac{\alpha}{2}\left(\lVert\vec{p}(t) -\vec{p}(t-1)\rVert_1-\frac{\lVert\nabla f_t(\vec{p}(t-1))\rVert_{\infty}}{\alpha}\right)^2 - \frac{\lVert\nabla f_t(\vec{p}(t-1))\rVert_{\infty}^2}{2\alpha} \nonumber \\& \geq  -\frac{1}{2\alpha}\lVert\nabla f_t(\vec{p}(t-1))\rVert_{\infty}^2,
\end{align}

where (a) follows from the Cauchy-Schwarz inequality, and (b) follows from Pinsker's inequality.

We have,

\begin{align}
\mathbb{E}\{ \lVert \nabla f_t(\vec{p}(t-1)) \rVert^2_{\infty}|\vec{Z}\} \leq 2\lVert \vec{E}\rVert_{\infty}^2+\frac{1}{2}\mathbb{E}\left\{\left \lVert\vec{\Omega} \right\rVert^2_{\infty}|\vec{Z}\right\}.
\end{align}

(Notice that the upper bound is finite since $W_k$ for each  $k \in \mathcal{B}\}$ has finite variance).

Notice that,

\begin{align}
\nabla  f_t(\vec{p}(t-1)) = -\vec{E}+\frac{1}{2}\vec{\tilde{\Omega}}(t),
\end{align}

where $\vec{\tilde{\Omega}}(t)$ is given by, $\tilde{\Omega}_k(t) = \Omega_k(t)\mathbbm{1}_{(\arg\max_{1\leq j \leq n}\{ x_j\Omega_j(t) \} = k)}$.
Notice that,

\begin{align}
\mathbb{E}\{ \lVert &\nabla f_t(\vec{p}(t-1)) \rVert^2_{\infty}|\vec{Z}\}\leq \mathbb{E}\left\{\left \lVert -\vec{E}+\frac{1}{2}\vec{\tilde{\Omega}}(t) \right\rVert^2_{\infty}\Bigg{|}\vec{Z}\right\}\nonumber\\&\leq_{(a)}
2\lVert \vec{E}\rVert_{\infty}^2+\frac{1}{2}\mathbb{E}\left\{\left \lVert\vec{\tilde{\Omega}}(t) \right\rVert^2_{\infty}\Bigg{|}\vec{Z}\right\}
\leq  2\lVert \vec{E}\rVert_{\infty}^2+\frac{1}{2}\mathbb{E}\left\{\left \lVert\vec{\Omega}(t) \right\rVert^2_{\infty}\Bigg{|}\vec{Z}\right\}\nonumber\\& =  2\lVert \vec{E}\rVert_{\infty}^2+\frac{1}{2}\mathbb{E}\left\{\left \lVert\vec{\Omega} \right\rVert^2_{\infty}|\vec{Z}\right\},
\end{align}

where (a) follows from $\lVert \vec{x}+\vec{y}\rVert_{\infty}^2 \leq 2\lVert\vec{x}\rVert_{\infty}^2 + 2\lVert\vec{y}\rVert_{\infty}^2$.

Now, let $\vec{p}^{*}$ be the optimal solution of (P4). Notice that,

\begin{align}
-\frac{1}{2\alpha}\lVert\nabla f_t(\vec{p}(t-1))\rVert_{\infty}^2 &\leq_{(a)} \nabla f_t(\vec{p}(t-1))^{\top}(\vec{p}(t) - \vec{p}(t-1)) + \alpha D(\vec{p}(t) \lVert \vec{p}(t-1)) \nonumber\\&\leq_{(b)} \nabla f_t(\vec{p}(t-1))^{\top}(\vec{p}^* - \vec{p}(t-1)) + \alpha D(\vec{p}^{*} \lVert \vec{p}(t-1)) - \alpha D(\vec{p}^{*} \lVert \vec{p}(t))\nonumber\\& \leq_{(c)}  f_t(p^*) - f_t(\vec{p}(t-1)) + \alpha D(\vec{p}^{*} \lVert \vec{p}(t-1)) - \alpha D(\vec{p}^{*} \lVert \vec{p}(t)),
\end{align}

where (a) follows from Lemma <ref>, (b) follows from Lemma <ref> with $\mathcal{G} = [0,\infty)^n$, $\mathcal{C} = \mathcal{I}$, and $\omega(\vec{x}) = \sum_{j=1}^n x_j \ln(x_j)$ (Notice that from (<ref>), $\vec{p}(t) \in \mathcal{I}^0$ which is required for the lemma), and (c) follows from sub-gradient inequality for the convex function $f_t$. Summing the above inequality for $t$ from $1$ to $T$, and dividing by $T$, we have,

\begin{align}
-\sum_{t=1}^{T}& \frac{\lVert  \nabla f_t(\vec{p}(t-1)) \rVert^2_{\infty}}{2\alpha T} \leq \frac{\sum_{t=1}^T f_t(p^*)}{T} - \frac{\sum_{t=1}^T f_t(\vec{p}(t-1))}{T} + \frac{\alpha D(\vec{p}^{*} \lVert \vec{p}(0))}{T} - \frac{\alpha D(\vec{p}^{*} \lVert \vec{p}(T))}{T} \nonumber\\& \leq  \frac{\sum_{t=1}^T f_t(p^*)}{T} - \frac{\sum_{t=1}^T f_t(\vec{p}(t-1))}{T} + \frac{\alpha}{T}\left( \sum_{k=1}^n p_k^* \ln(\frac{p_k(T)}{p_k(0)})\right)\nonumber\\& \leq_{(a)} \frac{\sum_{t=1}^T f_t(p^*)}{T} - \frac{\sum_{t=1}^T f_t(\vec{p}(t-1))}{T} + \frac{\alpha}{T} \max\left(\ln(\frac{1}{p_k(0)}); 1 \leq k \leq n\right) \nonumber\\& \leq_{(b)} \frac{\sum_{t=1}^T f_t(p^*)}{T} - \frac{\sum_{t=1}^T f_t(\vec{p}(t-1))}{T} + \frac{\alpha}{T} \ln(n),
\end{align}

where (a) follows from the facts that natural logarithm is an increasing function in $(0,\infty)$, and $p_k(T) \leq 1$ for all $k$, and (b) follows from $p_k(0) = 1/n$.
After taking expectations of both sides and some rearrangements, we have

\begin{align}\label{eqn:final_before}
&-\sum_{t=1}^{T} \frac{\mathbb{E}\{ \lVert \nabla f_t(\vec{p}(t-1)) \rVert^2_{\infty} |\vec{Z}\}}{2\alpha T}- \frac{\alpha}{T} \ln(n) \nonumber\\&\leq \mathbb{E}\left\{\frac{\sum_{t=1}^T f_t(p^*)}{T}\Bigg{|}\vec{Z}\right\} - \mathbb{E}\left\{\frac{\sum_{t=1}^T f_t(\vec{p}(t-1))}{T}\Bigg{|}\vec{Z}\right\}.
\end{align}

Substituting the results from Lemma <ref> in (<ref>), we have that,

\begin{align}\label{eqn:final}
-\frac{C}{2\alpha } - \frac{\alpha}{T}\ln(n) \leq \mathbb{E}\left\{\frac{\sum_{t=1}^T f_t(p^*)}{T}\Bigg{|}\vec{Z}\right\} - \mathbb{E}\left\{\frac{\sum_{t=1}^T f_t(\vec{p}(t-1))}{T}\Bigg{|}\vec{Z}\right\} ,
\end{align}

\begin{align}
C =2\lVert \vec{E}\rVert_{\infty}^2+\frac{1}{2}\mathbb{E}\left\{\left \lVert\vec{\Omega} \right\rVert^2_{\infty}|\vec{Z}\right\}.
\end{align}

But notice that,

\begin{align}
\mathbb{E}\left\{\frac{\sum_{t=1}^T f_t(p^*)}{T}\right\} = -\frac{1}{T} \sum_{t=1}^T\mathbb{E}\{f_t(p^*)|\vec{Z}\} = \frac{1}{T} \sum_{t=1}^Tf(p^*) = -f^*.
\end{align}

Also,  we have that,

\begin{align}
\mathbb{E}&\left\{\frac{\sum_{t=1}^T f_t(\vec{p}(t-1))}{T}\Bigg{|}\vec{Z}\right\} =  \frac{\sum_{t=1}^T \mathbb{E}\left\{f_t(\vec{p}(t-1))|\vec{Z}\right\}}{T} \nonumber\\&=  \frac{\sum_{t=1}^T \mathbb{E}\{\mathbb{E}_{\vec{\Omega}(t)}\left\{f_t(\vec{p}(t-1))|\vec{\Omega}(\tau) \text{ for } t\neq \tau \right\}|\vec{Z}\}}{T} \nonumber\\&=_{(a)} \frac{\sum_{t=1}^T \mathbb{E}\{-f(\vec{p}(t-1))| \vec{Z}\}}{T} \nonumber\\&=  -\mathbb{E}\left\{\frac{\sum_{t=1}^T f(\vec{p}(t-1))|\vec{Z}}{T}\right\}   \geq -\mathbb{E}\left\{f\left(\frac{\sum_{t=1}^T \vec{p}(t-1)}{T}\right)\Bigg{|}\vec{Z}\right\},
\end{align}

where (a) follows since $\vec{\Omega}(t)$ is independent of $\vec{\Omega}(\tau) \text{ for } \tau \neq t$ and $\vec{p}(t-1)$ is a function of $\vec{\Omega}(\tau) \text{ for } \tau <t$ and hence is independent of $\vec{\Omega}(t)$.
The last inequality follows from Jensen's inequality since $f$ is a concave function. Substituting, in
(<ref>), we have the desired result.

§.§  Case $a = 1$

When $a=1$, the set $\mathcal{G}^A$ is more complex than the simplex $\mathcal{I}$. The next two lemmas compute for each $\vec{p} \in \mathcal{I}$, the largest $q \in \mathbb{R}$, such that $(q,\vec{p}) \in \mathcal{G}^A$. For simplicity of exposition, this subsection assumes $W_1$ has a continuous CDF $F_{W_1}:\mathbb{R} \to [0,1]$.

If $(q,\vec{p}) \in \mathcal{G}^A$, then we have,

\begin{align}
q \leq\mathbb{E}\{W_1 | F_{W_1}(W_1)\geq 1-p_1\}p_1.
\end{align}

See Appendix <ref>

Consider any $\vec{p} \in \mathcal{I}$. Let $q = \mathbb{E}\{W_1 | F_{W_1}(W_1)\geq 1-p_1\}p_1$. Then $(q,\vec{p}) \in \mathcal{G}^A$. In particular, there exists $g^A \in \mathcal{S}^A$ such that,

\begin{align}
&p_{k} =  \mathbb{E}\{\mathbbm{1}_{g^A(U^A, W_1,\vec{Z}) = k}|\vec{Z}\}\text{ for } 1\leq k \leq n,\nonumber\\&q = \mathbb{E}\{W_k\mathbbm{1}_{g^A(U^A, W_1,\vec{Z}) = 1}|\vec{Z}\}.
\end{align}

See Appendix <ref>

Given that $W_1$ has a continuous CDF, for a fixed $\vec{p}$, it is optimal to choose the strategy given by Lemma <ref> due to Theorem <ref>-2. Hence we can simply focus on solving the problem,

f(𝔼{W_1 | F_W_1(W_1)≥1-p_1}p_1,p⃗_2:n)(P5):

It can be shown that $\mathbb{E}\{W_1 | F_{W_1}(W_1)\geq 1-p_1\}p_1$ is concave and non-increasing in $p_1$. Hence (P5) is also a convex optimization problem since $f$ is entry-wise, non-decreasing, and concave. Hence, when $\mathbb{E}\{W_1 | F_{W_1}(W_1)\geq 1-p_1\}p_1$ has a bounded subgradient at $p_1 = 0$, its subgradients are bounded for all $p_1 \in [0,1]$, and (P5) can be solved using the mirror-descent algorithm described for $a=0$. When subgradients at $p_1 = 0$ are not bounded, extra care should be taken, such as by restricting the search to a subregion of $\mathcal{I}$.

§ PROOF OF LEMMA <REF>

Let $\tau_1 \in \mathbb{R}$, be such that, $F_{W_1}(W_1) = 1-p_1$. Since the CDF of $W_1$ is assumed to be continuous, the intermediate value theorem guarantees the existence of such a $\tau_1$. Let $f_{1}: \mathbb{R} \to \mathbb{R}$ be defined such that,
0      if $x \leq \tau_1$,

1      otherwise.

Hence, we have that $p_1\mathbb{E}\{W_1 | F_{W_1}(W_1)\geq 1-p_1\} $$=$$ \mathbb{E}\{W_1f_{1}(W_1)\}$ $=$ $\mathbb{E}\{W_1f_{1}(W_1)|\vec{Z}\}$, where the last equality follows from the fact that $\vec{Z}$ and $W_1$ are independent.

Recall the definition of strategy function in (<ref>).
Let $P^A$ be the strategy function of the strategy relating to $(q,\vec{p})$ (See (<ref>)). Hence,

\begin{align*}
q &- p_1\mathbb{E}\{W_1 | F_{W_1}(W_1)\geq 1-p_1\} = \mathbb{E}\{W_1(P^{A}(W_1,\vec{Z})-f_{1}(W_1))|\vec{Z}\}\\&=_{(a)} \text{Pr}\{W_1 \leq \tau_1\}\mathbb{E}\{W_1(P^{A}(W_1,\vec{Z})-f_{1}(W_1))|\vec{Z},W_1\leq \tau_1\} \\&+ \text{Pr}\{W_1 > \tau_1\}\mathbb{E}\{W_1(P^{A}(W_1,\vec{Z})-f_{1}(W_1))|\vec{Z},W_1> \tau_1\} \\&=
\text{Pr}\{W_1 \leq \tau_1\}\mathbb{E}\{W_1P^{A}(W_1,\vec{Z})|\vec{Z},W_1\leq \tau_1\} \\&+ \text{Pr}\{W_1 > \tau_1\}\mathbb{E}\{W_1(P^{A}(W_1,\vec{Z})-1)|\vec{Z},W_1> \tau_1\} \\&\leq \text{Pr}\{W_1 \leq \tau_1\}\mathbb{E}\{\tau_1P^{A}(W_1,\vec{Z})|\vec{Z},W_1\leq \tau_1\} \\&+ \text{Pr}\{W_1 > \tau_1\}\mathbb{E}\{\tau_1(P^{A}(W_1,\vec{Z})-1)|\vec{Z},W_1> \tau_1\} \\&= \text{Pr}\{W_1 \leq \tau_1\}\mathbb{E}\{\tau_1P^{A}(W_1,\vec{Z})|\vec{Z},W_1\leq \tau_1\} \\&+ \text{Pr}\{W_1 > \tau_1\}\mathbb{E}\{\tau_1P^{A}(W_1,\vec{Z})|\vec{Z},W_1> \tau_1\}  - \text{Pr}\{W_1 >  \tau_1\}\mathbb{E}\{\tau_1|\vec{Z},W_1\leq \tau_1\}\\& =_{(b)} \mathbb{E}\{\tau_1P^{A}(W_1,\vec{Z})|\vec{Z}\} - \text{Pr}\{W_1 >  \tau_1\}\mathbb{E}\{\tau_1|\vec{Z},W_1\leq \tau_1\}  = \tau_1p_1 - p_1\tau_1 = 0,
\end{align*}

where (a) and (b) follow from the total probability law.
Hence, $q \leq p_1\mathbb{E}\{W_1 | F_{W_1}(W_1)\geq1- p_1\}$.

§ PROOF OF LEMMA <REF>

Similar to Appendix <ref>, define $\tau_1 \in \mathbb{R}$, be such that, $F_{W_1}(W_1) = 1-p_1$.
Now  consider the strategy for A of choosing 1 whenever $\tau_1 \leq W_1$ and $\{2,\dots,n\}$ with probabilities $\{p_{2},\dots,p_{n}\}$ otherwise.  Note that Pr$\{\alpha^A=1$$|\vec{Z}\}$$=$$\text{Pr}\{\tau_1 \leq W_1 \} = p_{1}$. Moreover, notice that

\begin{align}
\mathbb{E}\{W_1\mathbbm{1}_{\alpha^A = 1}|\vec{Z}\} = p_{1}\mathbb{E}\{W_1| \alpha^A = 1,\vec{Z}\}=p_{1}\mathbb{E}\{W_1 |  F_{W_1}(W_1) \geq 1-p_1\} = q,
\end{align}

which follows since $\vec{Z}$ and $W_1$ are independent. Hence, $(q, \vec{p}) \in \mathcal{G}^A$, as desired.

[1]
R. W. Rosenthal, “A class of games possessing pure-strategy Nash
equilibria,” International Journal of Game Theory, vol. 2, pp.
65–67, 1973.

[2]
E. Nikolova and N. E. Stier-Moses, “Stochastic selfish routing,” in
Algorithmic Game Theory, G. Persiano, Ed.1em plus 0.5em minus
0.4emBerlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp.

[3]
H. Angelidakis, D. Fotakis, and T. Lianeas, “Stochastic congestion games with
risk-averse players,” in Lecture Notes in Computer Science, 10 2013.

[4]
C. Zhou, T. H. Nguyen, and H. Xu, “Algorithmic information design in
multi-player games: Possibilities and limits in singleton congestion,” in
Proceedings of the 23rd ACM Conference on Economics and Computation,
ser. EC '22.1em plus 0.5em minus 0.4emNew York, NY, USA:
Association for Computing Machinery, 2022, p. 869. [Online]. Available:

[5]
M. Castiglioni, A. Celli, A. Marchesi, and N. Gatti, “Signaling in
Bayesian network congestion games: The subtle power of
symmetry,” in AAAI Conference on Artificial Intelligence, 2020.

[6]
M. Wu, J. Liu, and S. Amin, “Informational aspects in a class of
Bayesian congestion games,” in 2017 American Control
Conference (ACC), 2017, pp. 3650–3657.

[7]
V. Syrgkanis, “The complexity of equilibria in cost sharing games,” in
Internet and Network Economics: 6th International Workshop, WINE 2010,
Stanford, CA, USA, December 13-17, 2010. Proceedings 6.1em plus 0.5em
minus 0.4emSpringer, 2010, pp. 366–377.

[8]
M. Zinkevich, “Online convex programming and generalized infinitesimal
gradient ascent,” in Proceedings of the Twentieth International
Conference on International Conference on Machine Learning, ser.
ICML'03.1em plus 0.5em minus 0.4emAAAI Press, 2003, p.

[9]
H. Yu, M. Neely, and X. Wei, “Online convex optimization with stochastic
constraints,” in Advances in Neural Information Processing Systems,
I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan,
and R. Garnett, Eds., vol. 30.1em plus 0.5em minus 0.4emCurran
Associates, Inc., 2017.

[10]
M. J. Neely, Stochastic Network Optimization with Application to
Communication and Queueing Systems.1em plus 0.5em minus 0.4emMorgan & Claypool, 2010.

[11]
D. Monderer and L. S. Shapley, “Potential games,” Games and Economic
Behavior, vol. 14, no. 1, pp. 124–143, 1996. [Online]. Available:

[12]
S. Chien and A. Sinclair, “Convergence to approximate Nash
equilibria in congestion games,” Games and Economic Behavior,
vol. 71, no. 2, pp. 315–327, 2011. [Online]. Available:

[13]
K. Bhawalkar, M. Gairing, and T. Roughgarden, “Weighted congestion games:
Price of anarchy, universal worst-case examples, and tightness,” in
Lecture Notes in Computer Science, 09 2010, pp. 17–28.

[14]
I. Milchtaich, “Congestion games with player-specific payoff functions,”
Games and Economic Behavior, vol. 13, no. 1, pp. 111–124, 1996.
[Online]. Available:

[15]
H. Ackermann, P. W. Goldberg, V. S. Mirrokni, H. Röglin, and
B. Vöcking, “A Unified Approach to Congestion Games and Two-Sided
Markets,” Internet Mathematics, vol. 5, no. 4, pp. 439 – 458, 2008.
[Online]. Available: <https://doi.org/>

[16]
D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas, and P. Spirakis,
“The structure and complexity of Nash equilibria for a selfish
routing game,” Theoretical Computer Science, vol. 410, no. 36, pp.
3305–3326, 2009, graphs, Games and Computation: Dedicated to Professor
Burkhard Monien on the Occasion of his 65th Birthday. [Online]. Available:

[17]
M. Gairing, T. Lücking, M. Mavronicolas, and B. Monien, “Computing
Nash equilibria for scheduling on restricted parallel links,” in
Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of
Computing, ser. STOC '04.1em plus 0.5em minus 0.4emNew York,
NY, USA: Association for Computing Machinery, 2004, p. 613–622. [Online].
Available: <https://doi.org/10.1145/1007352.1007446>

[18]
D. Acemoglu, A. Makhdoumi, A. Malekian, and A. Ozdaglar, “Informational
braess’ paradox: The effect of information on traffic congestion,”
Operations Research, vol. 66, no. 4, pp. 893–917, 2018. [Online].
Available: <https://doi.org/10.1287/opre.2017.1712>

[19]
S. Le, Y. Wu, and M. Toyoda, “A congestion game framework for service chain
composition in NFV with function benefit,” Inf. Sci.,
vol. 514, no. C, p. 512–522, apr 2020. [Online]. Available:

[20]
L. Zhang, K. Gong, and M. Xu, “Congestion control in charging stations
allocation with Q-learning,” Sustainability, vol. 11,
no. 14, 2019. [Online]. Available:

[21]
E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and
T. Roughgarden, “The price of stability for network design with fair cost
allocation,” in 45th Annual IEEE Symposium on Foundations of Computer
Science, 2004, pp. 295–304.

[22]
I. Caragiannis, M. Flammini, C. Kaklamanis, P. Kanellopoulos, and
L. Moscardelli, “Tight bounds for selfish and greedy load balancing,”
Algorithmica, vol. 58, pp. 311–322, 01 2006.

[23]
F. Zhang and M. M. Wang, “Stochastic congestion game for load balancing in
mobile-edge computing,” IEEE Internet of Things Journal, vol. 8,
no. 2, pp. 778–790, 2021.

[24]
M. Liu, S. H. A. Ahmad, and Y. Wu, “Congestion games with resource reuse and
applications in spectrum sharing,” in 2009 International Conference on
Game Theory for Networks, 2009, pp. 171–179.

[25]
M. Liu and Y. Wu, “Spectum sharing as congestion games,” in 2008 46th
Annual Allerton Conference on Communication, Control, and Computing.1em plus 0.5em minus 0.4emIEEE, 2008, pp. 1146–1153.

[26]
M. Ibrahim, K. Khawam, and S. Tohme, “Congestion games for distributed radio
access selection in broadband networks,” in 2010 IEEE Global
Telecommunications Conference GLOBECOM 2010, 2010, pp. 1–5.

[27]
T. Quint and M. Shubik, “A model of migration,” 1994.

[28]
K. Akkarajitsakul, E. Hossain, D. Niyato, and D. I. Kim, “Game theoretic
approaches for multiple access in wireless networks: A survey,” IEEE
Communications Surveys & Tutorials, vol. 13, no. 3, pp. 372–395, 2011.

[29]
I. Malanchini, M. Cesana, and N. Gatti, “Network selection and resource
allocation games for wireless access networks,” IEEE Transactions on
Mobile Computing, vol. 12, no. 12, pp. 2427–2440, 2013.

[30]
J.-B. Seo and H. Jin, “Two-user noma uplink random access games,” IEEE
Communications Letters, vol. 22, no. 11, pp. 2246–2249, 2018.

[31]
——, “Revisiting two-user s-aloha games,” IEEE Communications
Letters, vol. 22, no. 6, pp. 1172–1175, 2018.

[32]
N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, Algorithmic Game
Theory.1em plus 0.5em minus 0.4emCambridge University Press,

[33]
X. Wei, H. Yu, and M. J. Neely, “Online primal-dual mirror descent under
stochastic constraints,” Proc. ACM Meas. Anal. Comput. Syst., vol. 4,
no. 2, jun 2020. [Online]. Available: <https://doi.org/10.1145/3392157>

[34]
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro, “Robust stochastic
approximation approach to stochastic programming,” Society for
Industrial and Applied Mathematics, vol. 19, pp. 1574–1609, 01 2009.