This paper considers a multi-player resource-sharing game with a fair reward allocation model. Multiple players choose from a collection of resources. Each resource brings a random reward equally divided among the players who choose it. We consider two settings. The first setting is a one-slot game where the mean rewards of the resources are known to all the players, and the objective of player 1 is to maximize their worst-case expected utility. Certain special cases of this setting have explicit solutions. These cases provide interesting yet non-intuitive insights into the problem. The second setting is an online setting, where the game is played over a finite time horizon, where the mean rewards are unknown to the first player. Instead, the first player receives, as feedback, the rewards of the resources they chose after the action. We develop a novel Upper Confidence Bound (UCB) algorithm that minimizes the worst-case regret of the first player using the feedback received.

Resource-sharing games, congestion games, potential games, fair reward allocation, worst-case expected utility maximization, online games

§ INTRODUCTION

In this paper, we consider the following game with $m \geq 2$ players $A_1,A_2,\dots,A_m$, and $n \geq 2$ resources $1,2,\cdots,n$. The state of the game is described by the random reward vector $\vec{W} = (W_1,W_2,...,W_n)^{\top}$, where  $W_k$ is the reward random variable of resource $k$. Each player selects $r$ resources without knowing the other player's selection (assume that $0 < r <n$). The per-player reward of the resource $k$ is $W_k/S_k$, where $S_k$ is the number of players who selected resource $k$. The sum of all the per-player rewards of resources a player selects is their utility. We consider two settings.

The first setting is a one-slot game where the players have knowledge of the means of the reward random variables but do not observe the realizations before taking action. In this setting, we solve the problem of maximizing the worst-case expected utility of player $A_1$. The general case can be solved using a simple gradient descent algorithm. The more intriguing scenario in this setting is that some of the special cases have non-trivial explicit solutions that provide insight into the problem. The problem of maximizing the worst-case expected utility is motivated by the fact that player $A_1$ does not place any assumptions on the incentives of the opponent, which makes worst-case expected utility an important objective that is different from the equilibrium-based objectives such as Nash-equilibrium [1, 2] and correlated equilibrium [3, 4, 5].

The second setting is an online scenario, where the game is played over a finite time horizon in the presence of feedback. In this setting, we assume that the reward vector of the resources in each time slot is independent and identically distributed. Player $A_1$ takes action without knowledge about the mean rewards of the resources. Instead, player $A_1$ receives the reward of the resources they chose as feedback after each action. The goal of player $A_1$ is to minimize their worst-case regret over time. This setting is inspired by the UCB algorithm of [6] for the problem of zero-sum matrix games with bandit feedback. We provide an algorithm for the above setting that minimizes worst-case regret by learning the mean rewards of the resources. When implemented in a time horizon of $T$ time-slots, the algorithm achieves a worst-case regret of $nD\sqrt{T}+ 4n\sqrt{2rT\log(2nrCT^3(T+1))} + 1$,
where $C$ and $D$ are known constants. The problem of finding an approximate Nash equilibrium of a congestion game with bandit feedback has been considered in [7]. However, implementing the algorithms in [7] requires cooperation among players. The proposed algorithm requires no cooperation among the players since player $A_1$ focuses on maximizing the worst-case regret.

The game model discussed for the above two settings has been studied for the non-stochastic case under the more general framework of resource-sharing games [8], also known as congestion games. In these games, the per-player reward of a resource is a general function of the number of players selecting the resource. Also, an action for a player is a subset of the resources, where the allowed subsets make up the action space of the player. Resource-sharing games have also been extended to various stochastic settings [9, 10]. Problems similar to our work have been studied in the context of adversarial resource-sharing games. The work of [11] considers an adversarial resource-sharing game where each player chooses a single resource from a collection of resources, after which an adversary chooses the resource chosen by the maximum number of players. Also, non-atomic congestion games with malicious players have been considered through the work of [12].

In our model, we have done two simplifications to the resource-sharing game models described above. First, we assume a fair-reward allocation model, where we have assumed the existence of a reward for each resource, which is divided equally between the players selecting it. Second, we have assumed simple action spaces for players by allowing each player to select an arbitrary subset of $r$ resources. Additionally, we assume a non-cooperative model where player $A_1$ does not place any assumptions on the incentives of the opponents. The above simplifications of the general model have several consequences.

First, the simplified model has various real-world applications. The work of [13] discusses different real-world applications of the game in the special case $m=2,r=1$ (and without considering the online setting). These examples are also relevant to the general case of the problem. One example is multiple access control (MAC) in communication systems, where communication channels are accessed by multiple users, and the data rate of a channel is shared amongst the users who select it [14]. Here, a channel can be shared using Time Division Multiple Access (TDMA) or Frequency Division Multiple Access (FDMA), where in TDMA, the channel is time-shared among the users [15, 16], whereas in FDMA, the channel is frequency-shared among the users [17]. In both cases, the total data rate supported by the channel can be considered the utility of the channel. Both game settings of this paper are relevant here: The one-slot setting can be used when the mean data rate is known to the users; The online setting is applicable when the mean data rate is unknown to the users, but they receive feedback on the actual data rate after transmission.

An application in the area of economics, discussed in [13], is a scenario where a firm chooses a market to enter from a pool of market options. Another firm may also choose the same market. This example assumes a simplified model with a total revenue for each market, and the total revenue is divided equally among the firms entering the market. Our treatment of the case $m>2$, $r>1$ is relevant to this application example because, in a real-world scenario, a firm may compete with multiple firms. The online setting treated in this paper is also useful for learning based on repeated market competitions.

Another consequence of our model is that in the one-slot setting, certain special cases have explicit solutions, which provide valuable insights into the problem. The work of [13] discusses the special case $m=2$, $r=1$. The current paper extends the analysis to special cases $m=2$ with general $r$, and $m=3$, $r=1$. The explicit solutions obtained in these cases are non-intuitive; hence, the problem is complex, even for simple cases.

It should be noted that resource-sharing games with special per-player reward definitions have been considered in the literature. One such notable case is when the per-player reward of a resource is non-decreasing in the number of players selecting the resource. These games are called cost-sharing games [18]. The particular case when the total cost of a resource is divided equally among the players choosing it is called fair cost-sharing games. In such a model, a player would prefer to select resources selected by many players. In the fair reward allocation model considered in our work, players have the opposite incentive to select resources selected by a small number of players.

Below, we list the major contributions of this paper

* We consider the problem of worst-case expected utility maximization of resource-sharing games with a fair-reward allocation model. We provide explicit solutions to certain special cases of the problem. These cases, in addition to providing an efficient approach to solving the problem, provide valuable insights into the solution structure of the problem. For instance, for the two-player case, it can be observed that the set of resources can be divided into four groups where each group contains resources with higher mean rewards compared to the next group. Each resource in the first and third group is chosen with probability 1. Each resource in group 2 is chosen with a non-zero probability, whereas the resources in the last group are never chosen. For the general case, we provide an algorithmic solution by solving a concave-non-convex max-min optimization problem, where the non-concave problem is an integer optimization problem that can be solved explicitly.

* We consider an online scenario of the above problem where the game is played over a finite time horizon of $T$ time slots, and player $A_1$ does not know the mean rewards of the resources. Instead, the player $A_1$ takes action using the feedback received after each action on the rewards of the resources they chose. We propose an upper confidence bound algorithm that achieves $\mathcal{O}(\sqrt{T\log(T))}$ worst-case regret. This problem shares certain similarities with the problems of stochastic convex optimization [19], online-convex optimization [20], online-convex optimization with multi-point bandit feedback [21], and adversarial bandit problems [6, 22]. It differs from the first three cases due to the differences in the feedback received. In particular, in the first three cases, the agent first queries the environment with points in the domain of the function to be optimized, after which the environment provides information about the function at the particular points as feedback. In our setting, the agent receives noisy partial information about the function in each iteration. Also, we cannot utilize the algorithms developed for strongly convex/concave objectives (see, for example [19]) since the function we optimize is piece-wise linear and hence is not strongly concave. The problem also differs from classical adversarial bandit problems since our problem requires a different definition of regret. Our problem is more similar to the work of [22] on zero-sum matrix games with bandit feedback. However, the above work considers a two-player scenario where both players receive as feedback the actions and the rewards of themselves and the opponent. Nevertheless, a similar UCB algorithm can be adopted for our case.

§.§ Background on Resource-Sharing Games

The resource-sharing game was first studied in [8]. These games, also known as congestion games, fall under the general category of potential games [23]. In potential games, the effect of any player changing strategies is captured by the change of a global potential function. Various extensions to the classical resource sharing game introduced in [8] have been studied in the literature [24]. Some such extensions are stochastic resource-sharing games [9, 10], weighted resource-sharing games [25], games with player-dependent reward allocation <cit.>, games with resources having preferences over players [27], and singleton games, where each player is only allowed to choose a single resource [28, 29].
Also similar to resource-sharing games are resource allocation games [30, 31]. In these games, a resource has to be fairly divided among a set of claimants claiming a certain portion of the resource.

Resource-sharing games have applications in multiple-accesses [14, 32, 33], network selection [34], network design [35],  spectrum sharing [36], resource sharing in wireless networks [37], load balancing networks [38, 39], radio access selection [40], service chains [41], congestion control [42], and migration of species [43].

§.§ Notation

We use calligraphic letters to denote sets. Vectors and matrices are denoted in boldface characters. For integers $n$ and $m$, we denote by $[n:m]$ the set of integers between $n$ and $m$ inclusive. Also, we use $\mathbb{N} = \{1,2,3,\dots\}$ to denote the set of positive integers and $\mathbb{N}_0 = \{0,1,2,\dots\}$ to denote the set of non-negative integers.

§ FORMULATION

In this section, we formulate the model for the one-slot setting. We extend this model to the online setting in Section <ref>. Let $E_k = \mathbb{E}\{W_k\}$ for all $1\leq k \leq n$. Let us denote by $\alpha \in \{0,1\}^n$ the action of player $A_1$, where $\alpha_j = 1$ if player $1$ chooses resource $j$ and $\alpha_j = 0$ otherwise. Notice that the actions of the other players will also have the same structure. Notice that, $\alpha \in \mathcal{J}_1$, where,

\begin{align}\label{eqn:J_def}
\mathcal{J}_{q} = \left\{\vec{x} \in \{0,1,\dots,q\}^n \Bigg{|} \sum_{j=1}^n x_j = qr \right\},
\end{align}

for $q \in \{1,2,\dots\}$.

Now fix $1 \leq q$ as a positive integer and imagine $q$ players each choosing vectors (actions) in $\mathcal{J}_1$. For each $i \in \{1,2,\dots,q\}$, let $\alpha^i \in \mathcal{J}_1$ denote the vector (action) chosen by the $i$-th player. Consider the following set,

\begin{align}\label{eqn:a_q}
\mathcal{A}_q = \left\{\sum_{i=1}^q\alpha^i :  \alpha^i \in \mathcal{J}_1 \text{ for all } i \in \{1,2,\dots,q\}\right \}.
\end{align}

Then we have the following lemma.

We have that,

* $\mathcal{A}_q = \mathcal{J}_q$ for $q \in \{1,2,\dots,\}$, where $\mathcal{A}_q$ and $\mathcal{J}_q$ are defined in (<ref>) and (<ref>), respectively.

* $\text{Conv}(\mathcal{J}_1) = \mathcal{I}$, where $\mathcal{I}$ is the $(n,r)$-hypersimplex,

\begin{align}\label{eqn:def_i_r}
\mathcal{I} = \left\{\vec{p} \in [0,1]^n\Bigg{|} \sum_{k=1}^np_k = r \right\}.
\end{align}

1) We complete the proof using the following two claims.

Claim 1 $\mathcal{A}_{q} \subseteq \mathcal{J}_q$: This follows directly from the fact that $\alpha^i \in \mathcal{J}_1$ for all $i \in \{1,2,\dots,q\}$ and the definition of sets $\mathcal{A}_q$ and $\mathcal{J}_q$.

Claim 2 $\mathcal{J}_{q} \subseteq \mathcal{A}_q$: We use induction. The case $q = 1$ trivially follows from the fact that $\alpha^1 \in \mathcal{J}_1$. Assume that the statement is true for $q \geq 1$. We establish the statement is true for $q+1$.

Pick any $\vec{x} \in \mathcal{J}_{q+1}$. Hence, $x_i \in \{0,1,\dots,q+1\}$  for each $1 \leq i \leq q+1$, and $\sum_{i=1}^{q+1}x_i = r(q+1)$. Hence, it should be clear that $\vec{x}$ has at least $r$ non-zero entries. Define $\alpha^{q+1} \in \mathcal{J}_1$ with exactly $r$ ones in locations $i$ with the highest $x_i$. Hence, $\vec{x}-\alpha^{q+1}$ is a non-negative vector. Now, we claim that $\vec{x}-\alpha^{q+1}\in \mathcal{J}_q$. Since $\vec{x} \in \mathcal{J}_{q+1}$ and $\alpha^{q+1} \in \mathcal{J}_1$, it can be easily seen that $\sum_{i=1}^n (x_i - \alpha^{q+1}_i) = rq$. Hence, we are only required to prove that the largest element of the vector $\vec{x}-\alpha^{q+1}$ is at most $q$. Assume the contrary and let $k$ be the index of the largest element, so $x_k- \alpha^{q+1}_k\geq q+1$. Since, $\vec{x} \in \mathcal{J}_{q+1}$, we know $x_k\leq q+1$. This means $\alpha^{q+1}_k = 0$, and $x_k = q+1$. Since $\alpha^{q+1}$ was constructed by selecting the largest elements of $\vec{x}$, and an element with size $q+1$ was not selected, we must have for all indices $i$ that $\alpha^{q+1}_i = 1 \implies x_{i} = q+1$. This means that

\begin{align}
\sum_{i=1}^n x_i \geq \sum_{\substack{i \in [1:n]\\ \alpha^{q+1}_i = 1}} x_i +x_k = (r+1)(q+1) > r(q+1),
\end{align}

which is a contradiction. Hence, we have that $\vec{x}-\alpha^{q+1}\in \mathcal{J}_q$ as desired. Hence, from the induction hypothesis $\vec{x}-\alpha^{q+1} \in \mathcal{A}_q$. Hence, there exists a set of actions $\alpha^1,\alpha^2,\dots,\alpha^q \in \mathcal{J}_1$ such that, $\sum_{i=1}^q\alpha^i = \vec{x}-\alpha^{q+1}$, which implies that $\sum_{i=1}^{q+1}\alpha^i = \vec{x}$. Hence, $\vec{x} \in \mathcal{A}_{q+1}$ as desired.

2) See Appendix <ref>.

Now, let $\alpha^i \in \mathcal{J}_1$ denote the action of player $A_i$ for $i \in \{2,3,\dots,m\}$. Let us define the vector $\vec{X} \in \mathbb{R}^n$ as

\begin{align}\label{eqn:def_X}
\vec{X} = \sum_{i=2}^m \alpha^i.
\end{align}

We assume that the triplet $(\alpha, \vec{X}, \vec{W})$ are mutually independent. Nevertheless, our formulation allows the random variables $W_1,W_2,\dots,W_n$ to be correlated, and the players $[2:m]$ to cooperate in order to make their decision. Notice that from Lemma <ref>-1, we have that $\vec{X} \in \mathcal{J}_{m-1}$.

§.§ Expected Utility

Given the player $A_1$ uses possibly randomized action $\alpha \in \mathcal{J}_1$ and $\vec{X}$ is defined according to (<ref>), the expected utility of player $A_1$ can be written as

\begin{align}\label{eqn:exp_util}
\mathbb{E}\left\{\sum_{k=1}^n \frac{W_k\mathbbm{1}_{(\alpha_k = 1)}}{1+X_k} \right\} =_{(a)} \sum_{k=1}^n E_kp_k\mathbb{E}\left\{\frac{1}{1+X_k}\right\}
\end{align}

\begin{align}\label{eqn:def_vec_p}
p_k = \mathbb{E}\{\mathbbm{1}_{(\alpha_k = 1)}\}
\end{align}

for $1 \leq k \leq n$, and the expectation is taken with respect to the possibly randomized action $\alpha_k$. The equality (a) follows since $(\alpha, \vec{X}, \vec{W})$ are mutually independent. Hence, notice that the expected utility depends on the action of player $A_1$ only through $\vec{p}$ defined in (<ref>). Let us define the function, $f: \mathbb{R}^n \times \mathbb{Z}^n \to \mathbb{R}$ as,

\begin{align}\label{def:fun_f}
f(\vec{p},\vec{x}) = \sum_{k=1}^{n}\frac{E_kp_k}{1+x_k}.
\end{align}

Hence, we have that the expected utility of player $A_1$ is equal to $\mathbb{E}\{f(\vec{p},\vec{X})\}$, where $\vec{p}$ is defined in (<ref>) and $\vec{X}$ is defined in (<ref>).

Notice that the set of all possible vectors $\vec{p}$ in (<ref>) is $\text{Conv}(\mathcal{J}_1)$, which is equal to $\mathcal{I}$ defined in (<ref>) by Lemma <ref>-2. Given $\vec{p} \in \mathcal{I}$, in Appendix <ref>, we provide an algorithm to sample a set $\alpha$ of $r$ resources from $\{1,2,\cdots,n\}$,  such that $\mathbb{E}\{\mathbbm{1}_{(\alpha_k=1)}\} = p_k$ is satisfied for all $k \in [1:n]$. In particular, the algorithm finds a distribution over the elements of $\mathcal{J}_1$ defined in (<ref>) for a given $\vec{p}$. The answer in [44] establishes that the found mixture of elements of $\mathcal{J}_1$ contains at most $n+1$ elements.

§.§ Worst-Case Expected Utility

This section focuses on finding the worst-case expected utility of player $A_1$ for fixed $\vec{p} \in \mathcal{I}$, used by player $A_1$. Notice that to obtain the worst-case expected utility of player $A_1$, we have to minimize $\mathbb{E}\{f(\vec{p},\vec{X})\}$ over all possibly randomized actions of players $A_2,\dots,A_m$. Define the function,

\begin{align}\label{eqn:def_f_worst}
f^{\text{worst}}(\vec{p}) = \min_{\vec{x} \in \mathcal{J}_{m-1}}f(\vec{p},\vec{x}),
\end{align}

where function $f$ is defined in (<ref>).

For $\vec{p} \in \mathcal{I}$, the worst-case expected utility of player $A_1$ is $f^{\text{worst}}(\vec{p})$.

Fix $\vec{p} \in \mathcal{I}$. Define $\vec{x}^* = \arg\min_{\vec{x} \in \mathcal{J}_{m-1}}f(\vec{p},\vec{x})$. Hence, $f^{\text{worst}}(\vec{p}) = f(\vec{p},\vec{x}^*)$. Consider a possibly randomized set of actions for players $A_2,\dots,A_m$, and define $\vec{X}$ according to (<ref>). Recall that the expected utility of player $A_1$ is $\mathbb{E}\{f(\vec{p},\vec{X})\}$. Notice that for any $\vec{x} \in \mathcal{J}_{m-1}$, we have that $f(\vec{p},\vec{x}^*) \leq f(\vec{p},\vec{x})$. Hence, we have that $f(\vec{p},\vec{x}^*) \leq f(\vec{p},\vec{X})$. Taking the expectations, we have that, $f(\vec{p},\vec{x}^*) \leq \mathbb{E}\{f(\vec{p},\vec{X})\}$. Hence, the expected utility of player $A_1$ is bounded below by $f(\vec{p},\vec{x}^*)$. Now consider the deterministic policy for players $A_2,\dots,A_m$ that yields $\vec{X} = \vec{x}^*$. Notice that such a policy exists from Lemma <ref>-1. This policy will yield an expected utility of $f(\vec{p},\vec{x}^*)$ for player $A_1$. Hence, $f(\vec{p},\vec{x}^*)$ is in fact the worst-case expected utility.

It should be noted that for a given $\vec{p} \in \mathcal{I}$, finding $f^{\text{worst}}(\vec{p})$ in (<ref>) and $\vec{x}^* = \arg\min_{\vec{x} \in \mathcal{J}_{m-1}}f(\vec{p},\vec{x})$ is an optimization over a non-convex discrete set $\vec{x} \in \mathcal{J}_{m-1}$. However, it has a classical separable structure that is well-studied in the literature and can be solved exactly using either a $\mathcal{O}(n+mr\log(n))$ greedy incremental algorithm or an improved $\mathcal{O}(n\log(mr))$ algorithm [45]. For completeness, we summarize an $\mathcal{O}(nmr)$ algorithm in Algorithm <ref>. For improved algorithms, refer to [45].

Initialize $\vec{x} = [0,0,\dots,0] \in \mathbb{N}^n$

Initialize $f = 0$

each iteration $k \in [1:(m-1)r]$
Increase $x_{i}$ by $1$ where,

\begin{align}
i = \arg\min_{\substack{k \in [1:n]\\x_k<m-1}} \left\{\frac{p_kE_k}{1+x_k}-\frac{p_kE_k}{2+x_k}\right\}
\end{align}

Output $f^{\text{worst}}(\vec{p}) = f(\vec{p},\vec{x})$ and $\vec{x}$.

Algorithm to find $f^{\text{worst}}(\vec{p})$ and $\vec{x}^* = \arg\min_{\vec{x} \in \mathcal{J}_{m-1}}f(\vec{p},\vec{x})$ for $\vec{p} \in \mathcal{I}$

It should be noted that $f^{\text{worst}}(\vec{p})$ for $\vec{p} \in \mathcal{I}$  has an explicit formula in certain special cases. Such cases will be discussed in Section <ref>.

In the following two sections (Section <ref> and Section <ref>), we introduce the two settings, after which we move onto special cases of the one-slot setting in Section <ref>.

§ ONE-SLOT GAME

For this setting, we assume that none of the players observe $\vec{W}$, but all the players know $\vec{E}$. Notice that the worst-case expected utility maximization problem can be represented as the max-min problem,

\begin{align}
\text{(P1): }&\underset{{\vec{p}}}{\text{max }}\underset{\vec{x}}{\text{min }} f(\vec{p},\vec{x})\nonumber\\\vec{p}&\in \mathcal{I}, \vec{x} \in \mathcal{J}_{m-1},
\end{align}

where the function $f$ is defined in (<ref>), the sets $\mathcal{I}$ and $\mathcal{J}_{m-1}$ are defined in (<ref>) and (<ref>) respectively. Notice that the inner minimization of the above problem amounts to evaluating the function $f^{\text{worst}}$ defined in (<ref>), which admits an exact solution for each $\vec{p} \in \mathcal{I}$. Hence, the problem can also be rephrased using the following maximization.

where the function $f^{\text{worst}}$ is defined in (<ref>). First notice, that for fixed $\vec{x} \in \mathcal{J}_{m-1}$, $f(\vec{p},\vec{x})$ is linear in $\vec{p}$. Since $\mathcal{J}_{m-1}$ is a finite set and since the minimum operation is continuous, from the definition of the function $f^{\text{worst}}$ in (<ref>), we have that $f^{\text{worst}}$ is continuous. This, combined with the fact that $\mathcal{I}$ is a compact domain, we have that (P2) admits an optimal solution $\vec{p}^*$. Hence, (P1) admits an optimal solution $(\vec{p}^*,\vec{x}^*)$, where $x^*=\arg\min_{\vec{x} \in \mathcal{J}_{m-1}}f(\vec{p}^*,\vec{x})$. However, it should be noted that $(\vec{p}^*,\vec{x}^*)$ is not in general a saddle point of $f$.

Since the inner minimization of (P1) can be solved using Algorithm <ref>, the min-oracle algorithm can be used to solve the (P1) [46]. Although this algorithm has been studied in the literature, we provide the algorithm (Algorithm <ref>) along with a focused convergence analysis tailored for this problem (Theorem <ref>) for clarity and completeness.

Initialize $\vec{p}^1 = [\frac{r}{n},\frac{r}{n},...,\frac{r}{n}]$

each iteration $t \in [1:T]$
Find $\vec{x}^t =  \min_{\vec{x} \in \mathcal{J}_{m-1}} f(\vec{p}^t,\vec{x})$, using Algorithm <ref>.

Obtain $\vec{p}^{t+1}$ by using,

\begin{align}\label{eqn:grqd_upd}
\vec{p}^{t+1} = \Pi_{\mathcal{I}}\left(\vec{p}^t + \beta\nabla_{\vec{p}} f(\vec{p}^t,\vec{x}^t) \right),
\end{align}

where the function $\Pi_{\mathcal{I}}$ is the projection onto $\mathcal{I}$, function $f$ is defined in (<ref>) (For a given vector $\vec{y} \in \mathbb{R}$, we provide an algorithm to calculate $\Pi_{\mathcal{I}}(\vec{y})$ in Appendix <ref>).

Output $\tilde{\vec{p}},\tilde{\vec{x}} = \arg\max\{f(\vec{p}^t,\vec{x}^t);1 \leq t \leq T\}$.
Algorithm to solve (P1)

The output $\tilde{\vec{p}},\tilde{\vec{x}}$ of Algorithm <ref> satisfies,

* $\tilde{\vec{x}} = \arg\min_{\vec{x} \in \mathcal{J}_{m-1}} f(\tilde{\vec{p}},\vec{x})$,

* $f^{\text{maximin}} - f(\tilde{\vec{p}},\tilde{\vec{x}}) \leq \frac{\lVert \vec{p}^{1} - \vec{p}^* \rVert^2}{2\beta T} + \frac{\beta}{2}\left(\sum_{k=1}^n E_k^2\right)$,

where $f^{\text{maximin}}$ is the optimal value of (P1), $T$ is the number of iterations of Algorithm <ref> and $\beta$ is the step-size used in (<ref>).
Hence, for fixed $\varepsilon>0$, choosing $\beta = \varepsilon$, and $T \geq 1/\varepsilon^2$, the maximum error is $\mathcal{O}(\varepsilon)$.

Part 1 follows since, $(\tilde{\vec{p}},\tilde{\vec{x}}) = (\vec{p}^t, \vec{x}^t)$ for some $t \in [1:T]$, and the definition of $\vec{x}^t$. For part 2, define

\begin{align}
\vec{q}_{i+1} =\vec{p}^{i} + \beta\nabla_{\vec{p}} f(\vec{p}^i,\vec{x}^i),
\end{align}

for all $i \in [1:T]$. Recall that $(\vec{p}^*,\vec{x}^*)$ is the optimal solution to (P1). Notice that,

\begin{align}
\lVert \vec{p}^{i+1} - \vec{p}^*\rVert^2  &\leq_{(a)} \lVert \vec{q}^{i+1} - \vec{p}^*\rVert^2 = \lVert\vec{p}^{i} + \beta\nabla_{\vec{p}} f(\vec{p}^i,\vec{x}^i) - \vec{p}^* \rVert^2 \nonumber\\& \leq \lVert \vec{p}^i - \vec{p}^* \rVert^2 + \beta^2 \lVert \nabla_{\vec{p}}f(\vec{p}^i,\vec{x}^i)\lVert^2 - 2\beta(\vec{p}^*-\vec{p}^i)^{\top}\nabla_{\vec{p}}f(\vec{p}^i,\vec{x}^i) \nonumber\\& =_{(b)}  \lVert \vec{p}^i - \vec{p}^* \rVert^2 + \beta^2 \lVert \nabla_{\vec{p}}f(\vec{p}^i,\vec{x}^i)\lVert^2 - 2\beta(f(\vec{p}^*,\vec{x}^i)-f(\vec{p}^i,\vec{x}^i)),
\end{align}

where (a) follows since projection onto a set reduces the distance to any point in the set, (b) follows from the subgradient equality for the linear function $f(\cdot,\vec{x}^i)$. Notice that $f^{\text{maximin}} = f(\vec{p}^*,\vec{x}^*)$. Now we sum the above inequality for $i \in [1:T]$, which results,

\begin{align}
0 &\leq \lVert \vec{p}^{T+1} - \vec{p}^* \rVert^2 \leq \lVert \vec{p}^{1} - \vec{p}^* \rVert^2 + \sum_{i=1}^T\beta^2\lVert\nabla_{\vec{p}}f(\vec{p}^i,\vec{x}^i)\lVert^2 - 2\beta\sum_{i=1}^Tf(\vec{p}^*,\vec{x}^i)+2\beta\sum_{i=1}^Tf(\vec{p}^i,\vec{x}^i) \nonumber \\& \leq_{(a)} \lVert \vec{p}^{1} - \vec{p}^* \rVert^2 + T\beta^2\left(\sum_{k=1}^nE_k^2\right) - 2\beta\sum_{i=1}^Tf(\vec{p}^*,\vec{x}^i)+2\beta\sum_{i=1}^Tf(\vec{p}^i,\vec{x}^i) \nonumber \\& \leq \lVert \vec{p}^{1} - \vec{p}^* \rVert^2 + T\beta^2\left(\sum_{k=1}^nE_k^2\right) - 2\beta\sum_{i=1}^Tf(\vec{p}^*,\vec{x}^*)+2\beta\sum_{i=1}^Tf(\tilde{\vec{p}},\tilde{\vec{x}}),
\end{align}

where (a) follows since $(\nabla_{\vec{p}}f(\vec{p}^i,\vec{x}^i))_k = E_k/(1+x^i_k) \leq E_k$,
and the last inequality follows due $f(\vec{p}^*,\vec{x}^*) \leq f(\vec{p}^*,\vec{x})$ for any $\vec{x} \in \mathcal{J}_{m-1}$, and the definition of $(\tilde{\vec{p}},\tilde{\vec{x}})$ in the last line of Algorithm <ref>. Hence, we have that,

\begin{align}
f^{\text{maximin}} - f(\tilde{\vec{p}},\tilde{\vec{x}}) \leq  \frac{\lVert \vec{p}^{1} - \vec{p}^* \rVert^2}{2\beta T} + \frac{\beta}{2}\left(\sum_{k=1}^nE_k^2\right),
\end{align}

as desired.

§ ONLINE SETTING

This section assumes that the player $A_1$ does not know the mean vector $\vec{E}$. Instead, the game is played on a horizon of $T$ discrete time slots, where after the decision of player $A_1$ during time-slot $t$, they receive the realizations of the reward random variables of the resources chosen by $A_1$ in time-slot $t$, as feedback. We add a time index to the notation described in Section <ref>. In particular, let $\vec{W}[t],\alpha[t],X_k[t]$  denote the reward random vector, the action of player $A_1$, the number of players (other than player $A_1$) selecting resource $k$, during time-slot $t$. Hence, we have that,

\begin{align}\label{def:vec_xt}
\vec{X}[t] = \sum_{k=2}^{m} \alpha^k[t],
\end{align}

where $\alpha^k[t] \in \mathcal{J}_1$ is the action of player $k \in  \{2,3,\dots,m\}$ during time-slot $t$. The history $\mathcal{H}[t]$ up to time $t$ can be defined by

\begin{align}
\mathcal{H}[t] = \{(\{W_k[\tau]; 1 \leq k \leq n, \alpha_k[\tau]=1\},\alpha[\tau]);1 \leq \tau < t\}
\end{align}

We assume that conditioned on the history $\mathcal{H}[t]$ of $A_1$, the action of player $A_1$ and the actions of the other players are independent. Let $\vec{p}[t] \in \mathcal{I}$ be defined such that,

\begin{align}\label{eqn:pkt}
p_k[t] = \mathbb{E}\{\mathbbm{1}_{(\alpha_k[t] = 1)}|\mathcal{H}[t]\}.
\end{align}

The expected utility of player $A_1$ can be written as

\begin{align}
\mathbb{E}&\left\{\sum_{t=1}^T \sum_{k=1}^n \frac{W_k[t]\mathbbm{1}_{(\alpha_k[t]=1)}}{1+X_k[t]}\right\} =_{(a)} \sum_{t=1}^T \sum_{k=1}^n E_k\mathbb{E}\left\{\frac{\mathbbm{1}_{(\alpha_k[t]=1)}}{1+X_k[t]}\right\} \nonumber\\& = \sum_{t=1}^T \sum_{k=1}^n E_k \mathbb{E}\left\{\mathbb{E}\left\{\frac{\mathbbm{1}_{(\alpha_k[t]=1)}}{1+X_k[t]} \Bigg{|}\mathcal{H}[t]\right\}\right\} =_{(b)}\sum_{t=1}^T \sum_{k=1}^n E_k \mathbb{E}\left\{\mathbb{E}\left\{\frac{p_k[t]}{1+X_k[t]} \Bigg{|} \mathcal{H}[t]\right\}\right\} \nonumber\\&= \sum_{t=1}^T \sum_{k=1}^n E_k \mathbb{E}\left\{\frac{p_k[t]}{1+X_k[t]}\right\} = \sum_{t=1}^T \mathbb{E}\{f(\vec{p}[t],\vec{X}[t])\},
\end{align}

where the function $f$ is defined in (<ref>), (a) follows since $\vec{W}[t]$ is independent of the actions of players during time-slot $t$, and (b) follows from the fact that the action of player $A_1$ is conditionally independent of the actions of other players given the history (recall the definitions of $\vec{X}[t]$, and $\vec{p}[t]$ in (<ref>) and (<ref>), respectively). Now, combining the above with Lemma <ref>, it is clear that the worst-case expected utility of player $A_1$ in this case is $\sum_{t = 1}^T \mathbb{E}\{f^{\text{worst}}(\vec{p}[t])\}$, where the function $f^{\text{worst}}$ is defined in (<ref>), and the expectation is taken with respect to all the feedback and actions of player $A_1$. Hence, we formulate this setting as minimizing the worst-case regret,

\begin{align}\label{eqn:regret}
R[t] = \sum_{t=1}^T\left(f^{\text{maximin}} - \mathbb{E}\{f^{\text{worst}}(\vec{p}[t])\}\right),
\end{align}

where $f^{\text{maximin}}$ is the optimal value of (P1).

We assume that $W_k[t] = E_k + \eta_k[t]$ for all $1\leq k \leq n$, where $\eta_k[t]$ for $(t,k) \in [1:T]\times [1:n]$ are zero-mean, 1-sub-Gaussian random variables. We assume that the collection $\{\vec{W}[t]; 1\leq t \leq T\}$ is independent and identically distributed. Our formulation does not require the components of $\vec{W}[t]$ to be mutually independent for a particular $t \in [1:T]$. Let us also assume that $E_k \in [0,C]$ for each $1 \leq k \leq n$, for some positive constant $C$, where $C$ is known to $A_1$. Fix $\delta \in (0,1)$. We begin with a few definitions. For all $t \in [1:T]$ and $k \in [1:n]$ define $n_k[t]$ as the number of times player $A_1$ chooses resource $k$ before time slot $t$. Formally,

\begin{align}
n_k[t] = \sum_{\tau = 1}^{t-1} \alpha_k[\tau].
\end{align}

Also, define,

\begin{align}
\bar{E}_k[t] = \frac{1}{1\vee n_k[t]}\sum_{\tau=1}^{t-1} \alpha_k[t]W_k[t],
\end{align}

where $x \vee y = \min(x,y)$, and,

\begin{align}
\tilde{E}_k[t] = \bar{E}_k[t]+\sqrt{\frac{2\log\frac{T(T+1)}{\delta}}{n_k[t] \vee 1}}.
\end{align}

We assume that $T$ is large enough such that that $\sqrt{\log((T(T+1))/\delta)} \geq C$. The choice of $T$ will ensure that if $n_k[t] = 0$, we have that,

\begin{align}\label{eqn:e_k_tile_e_up}
E_k < \tilde{E}_k[t],
\end{align}

\begin{align}\label{eqn:e_k_tile_e_lp}
E_k > \tilde{E}_k[t] - 2\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_k[t] \vee 1}}.
\end{align}

Also, define the functions $f_t: \mathbb{R}^n \times \mathbb{N}_0^n\to \mathbb{R}$ for $t \in [1:T]$ as,

\begin{align}\label{eqn:def_f_t}
f_t(\vec{p},\vec{x}) = \sum_{k=1}^{n} \frac{\tilde{E}_k[t]p_k}{1+x_k},
\end{align}

Before moving on to the main result, we introduce the following well-known lemma.

Given a sequence $\{X_t\}_{t=1}^{\infty}$ of independent $1$-sub Gaussian random variables, a positive integer-valued random variable $G$ and $\delta \in (0,1)$, we have the following,

* For all $g \in \mathbb{N}$, we have that,

\begin{align}
P\left\{\frac{1}{g}\sum_{i=1}^gX_i \geq \sqrt{\frac{2\log\frac{1}{\delta}}{g}}\right\} \leq \delta.
\end{align}

* If $G$ is independent of $\{X_t\}_{t=1}^{\infty}$, we have,

\begin{align}
P\left\{\frac{1}{G}\sum_{i=1}^GX_i \geq \sqrt{\frac{2\log\frac{1}{\delta}}{G}}\right\} \leq \delta.
\end{align}

* For general random variables $G$ (Possibly dependent on the sequence $\{X_t\}_{t=1}^{\infty}$), we have,

\begin{align}
P\left\{\frac{1}{G}\sum_{i=1}^GX_i \geq \sqrt{\frac{2\log\frac{G(G+1)}{\delta}}{G}}\right\} \leq \delta,  P\left\{\frac{1}{G}\sum_{i=1}^GX_i \leq -\sqrt{\frac{2\log\frac{G(G+1)}{\delta}}{G}}\right\} \leq \delta.
\end{align}

Refer to [6].

Let us denote by $\tilde{W}_k[t]$ the reward obtained when the resource $k$ is chosen for the $t$-th time by player $A_1$ in $[1:T]$, where $\tilde{W}_k[t]$ is set to $E_k$ if the resource $k$ is chosen less than $t$ times in $[1:T]$. Hence, notice that

\begin{align}
\bar{E}_k[t] = \frac{1}{1 \vee n_k[t]} \sum_{\tau=1}^{n_k[t]} \tilde{W}_k[\tau].
\end{align}

Now, applying Lemma <ref>-3 to the sequence $\{\tilde{W}_k[t]-E_k\}_{t=1}^{T}$ with $G = 1 \vee n_k[t]$ we have,

\begin{align}\label{eqn:app_lemma}
P \left\{ \frac{1}{1 \vee n_k[t]} \sum_{\tau=1}^{n_k[t] \vee 1} \tilde{W}_k[\tau] -E_k \geq \sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_k[t] \vee 1}}\right\} \leq \delta,
\end{align}

\begin{align}\label{eqn:app_lemma_2}
P \left\{ \frac{1}{1 \vee n_k[t]} \sum_{\tau=1}^{n_k[t] \vee 1} \tilde{W}_k[\tau] -E_k \leq -\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_k[t] \vee 1}}\right\} \leq \delta,
\end{align}

where, we have also used the inequality $n_k[t] \leq T$.
Now, we use the law of total probability on (<ref>) to obtain,

\begin{align}\label{eqn:low_bnd}
\delta &\geq P \left\{ \frac{1}{1 \vee n_k[t]} \sum_{\tau=1}^{n_k[t] \vee 1} \tilde{W}_k[\tau] -E_k \leq -\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_k[t] \vee 1}}\right\} \nonumber\\& = P \left\{ \frac{1}{1 \vee n_k[t]} \sum_{\tau=1}^{n_k[t] \vee 1} \tilde{W}_k[\tau] -E_k \leq -\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_k[t] \vee 1}} \Bigg{|} n_k[t]>0 \right\} P(n_k[t]>0)\nonumber\\&\ \ \ \ \ \ + P \left\{ \frac{1}{1 \vee n_k[t]} \sum_{\tau=1}^{n_k[t] \vee 1} \tilde{W}_k[\tau] -E_k \leq -\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_k[t] \vee 1}} \Bigg{|} n_k[t] = 0 \right\} P(n_k[t] = 0) \nonumber \\& = P \left\{E_k \geq \tilde{E}[t] \Bigg{|} n_k[t]>0 \right\} P(n_k[t]>0)\nonumber\\&\ \ \ \ \ \ + P \left\{ \frac{1}{1 \vee n_k[t]} \sum_{\tau=1}^{n_k[t] \vee 1} \tilde{W}_k[\tau] -E_k \leq -\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_k[t] \vee 1}} \Bigg{|} n_k[t] = 0 \right\} P(n_k[t] = 0) \nonumber\\ &\geq P \left\{E_k \geq \tilde{E}[t] \Bigg{|} n_k[t]>0 \right\} P(n_k[t]>0) \nonumber \\& =_{(a)} P \left\{E_k \geq \tilde{E}[t] \Bigg{|} n_k[t]>0 \right\} P(n_k[t]>0)+P \left\{E_k \geq \tilde{E}[t] \Bigg{|} n_k[t]  = 0 \right\} P(n_k[t] = 0) \nonumber\\& = P (E_k \geq \tilde{E}[t])
\end{align}

where (a) follows since we have from (<ref>) that

\begin{align}
P \left\{E_k \geq \tilde{E}[t] \Bigg{|} n_k[t]  = 0 \right\} = 0.
\end{align}

Similar, treatment to (<ref>) yields,

\begin{align}\label{eqn:up_bnd}
P\left\{E_k \leq \tilde{E}_k[t] - 2\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_k[t] \vee 1}} \right\} \leq \delta.
\end{align}

Now consider the good event $A$, which is defined as the event where the inequalities,

\begin{align}\label{eqn:good_ev_1}
E_k < \tilde{E}_k[t],
\end{align}

\begin{align}\label{eqn:good_ev_2}
E_k > \tilde{E}_k[t] - 2\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_k[t] \vee 1}}.
\end{align}

hold for all $t \in [1:T]$ and $k \in [1:n]$. Combining, (<ref>) and (<ref>) with the union bound, we have that

\begin{align}\label{eqn:complment_ineq}
P(A^c) \leq  2Tn\delta.
\end{align}

Now we summarize our approach in Algorithm <ref>, after which Theorem <ref> establishes the sub-linear worst-case regret bound of the algorithm. For the UCB algorithm, we require two parameters: the learning rate $\beta >0$ and $\delta \in (0,1)$.

Initialize $\overline{E}_k[1] = 0$, and $n_k[1] = 0$ for each $1\leq k \leq n$.
Initialize $\vec{p}[1]  = [\frac{r}{n},\frac{r}{n},...,\frac{r}{n}]$.
each time-slot $t \in [1:T]$
Set $\vec{x}[t] = \arg\min_{\vec{x}\in \mathcal{J}_{m-1}} f_t(\vec{p}[t],\vec{x})$
using Algorithm <ref>.
Choose action $\alpha[t]$ for the $t$-th time-slot by sampling from $\vec{p}[t]$ using the approach in Appendix <ref> (Algorithm <ref>) and receive feedback $\{W_k[t]; 1\leq k \leq n, \alpha_k[t] = 1\}$.
Obtain $\vec{p}[t+1]$ by using,

\begin{align}
\vec{p}[t+1] = \Pi_{\mathcal{I}}\left(\vec{p}[t] + \beta\nabla_{\vec{p}} f_t(\vec{p}[t],\vec{x}[t]) \right),
\end{align}

where $\Pi_{\mathcal{I}}(\vec{y})$ denotes the projection of $\vec{y}$ onto $\mathcal{I}$, function $f_t$ is defined in (<ref>), and $\beta$ is the step size.

UCB($\beta,\delta$) Algorithm

Fix $T$ as a positive integer large enough so that $1/(2nrCT^2) < 1$, and $\sqrt{2\log(2nrCT^3(T+1))}\geq C$. Running the UCB($\beta,\delta$) algorithm in Algorithm <ref> with $\delta = 1/(2nrCT^2)$, and $\beta = \sqrt{1/(TD^2)}$, where $D = C + 2\sqrt{2\log{\frac{T(T+1)}{\delta}}}$ yields the worst-case regret bound,

\begin{align}
\delta = 1/(2nrCT^2) < 1, \text{ and }\sqrt{2\log{\frac{T(T+1)}{\delta}}} = \sqrt{2\log(2nrCT^3(T+1))}\geq C,
\end{align}

yields the worst-case regret bound,

\begin{align}
R[t] \leq nD\sqrt{T}+ 4n\sqrt{2rT\log(2nrCT^3(T+1))} + 1.
\end{align}

Notice that since $T$ is fixed large enough such that $1/(2nrCT^2) < 1$, and $\delta = 1/(2nrCT^2)$, we have that $\delta \in (0,1)$. Moreover, due to the choice of $T$ and $\delta$, we have, $C \geq \sqrt{2\log(2nrCT^3(T+1))} = \sqrt{2\log{\frac{T(T+1)}{\delta}}}$, which will ensure (<ref>) and (<ref>).
We first focus on the good event $A$. Notice that in this case,

\begin{align}\label{eqn:grad_bound}
\tilde{E}_k[t] \leq E_k + 2\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_k[t] \vee 1}} \leq_{(a)} C + 2\sqrt{2\log{\frac{T(T+1)}{\delta}}} = D,
\end{align}

for all $k,t \in [1:n]\times[1:T]$, where (a) follows since $E_k < C$. Let $(\vec{p}^*,\vec{x}^*)$ be the optimal solution to (P1). Define

\begin{align}
\vec{q}[t+1] =\vec{p}[t] + \beta\nabla_{\vec{p}} f_t(\vec{p}[t],\vec{x}[t]),
\end{align}

for $t \in [1:T]$, where $f_t$ is defined in (<ref>).

Notice that,

\begin{align}\label{eqn:before_sum}
\lVert \vec{p}[t+1] - \vec{p}^*\rVert^2  &\leq_{(a)} \lVert \vec{q}[t+1] - \vec{p}^*\rVert^2 = \lVert\vec{p}[t] + \beta\nabla_{\vec{p}} f_t(\vec{p}[t],\vec{x}[t]) - \vec{p}^* \rVert^2 \nonumber\\& \leq \lVert \vec{p}[t] - \vec{p}^* \rVert^2 + \beta^2 \lVert \nabla_{\vec{p}}f_t(\vec{p}[t],\vec{x}[t])\lVert^2 - 2\beta(\vec{p}^*-\vec{p}[t])^{\top}\nabla_{\vec{p}}f_t(\vec{p}[t],\vec{x}[t]) \nonumber\\& =_{(b)}  \lVert \vec{p}[t] - \vec{p}^* \rVert^2 + \beta^2 \lVert \nabla_{\vec{p}}f_t(\vec{p}[t],\vec{x}[t])\lVert^2 - 2\beta(f_t(\vec{p}^*,\vec{x}[t])-f_t(\vec{p}[t],\vec{x}[t])),
\end{align}

where (a) follows since projection onto a set reduces the distance to any point in the set, (b) follows from the subgradient equality for the linear function $f_t(\cdot,\vec{x}[t])$. Notice that $f^{\text{maximin}} = f(\vec{p}^*,\vec{x}^*)$. Define

\begin{align}\label{eqn:def_til_x}
\tilde{\vec{x}}[t] = \arg\min_{\vec{x} \in \mathcal{J}_{m-1}} f(\vec{p}[t],\vec{x}).
\end{align}

First, notice that,

\begin{align}\label{eqn:sub_1}
f_t(\vec{p}^*,\vec{x}[t]) \geq f(\vec{p}^*,\vec{x}[t]) \geq f(\vec{p}^*,\vec{x}^*),
\end{align}

where the first inequality follows due (<ref>), and the second inequality follows from the definition of $\vec{x}^*$. Also, we have that,

\begin{align}\label{eqn:sub_2}
f_t(\vec{p}[t],\vec{x}[t]) \leq f_t(\vec{p}[t],\tilde{\vec{x}}[t]),
\end{align}

which follows from the definition of $\vec{x}[t]$ in line 4 of Algorithm <ref>. Now we sum the (<ref>) for $t \in [1:T]$, which results (consider event $A$),

\begin{align}
0 &\leq \lVert \vec{p}[T+1] - \vec{p}^* \rVert^2 \leq \lVert \vec{p}[1] - \vec{p}^* \rVert^2 + \sum_{t=1}^T\beta^2\lVert\nabla_{\vec{p}}f_t(\vec{p}[t],\vec{x}[t])\lVert^2 - 2\beta\sum_{t=1}^Tf_t(\vec{p}^*,\vec{x}[t])\nonumber\\&\ \ \ \ +2\beta\sum_{t=1}^Tf_t(\vec{p}[t],\vec{x}[t])  \leq_{(a)} n + n\beta^2TD^2 - 2\beta\sum_{t=1}^Tf_t(\vec{p}^*,\vec{x}[t])+2\beta\sum_{t=1}^Tf_t(\vec{p}[t],\vec{x}[t]) \nonumber \\&
\leq_{(b)} n + n\beta^2TD^2 - 2\beta\sum_{t=1}^Tf(\vec{p}^*,\vec{x}^*)+2\beta\sum_{t=1}^Tf_t(\vec{p}[t],\tilde{\vec{x}}[t]) \nonumber \\&
\leq_{(c)} n + n\beta^2TD^2 - 2\beta\sum_{t=1}^Tf(\vec{p}^*,\vec{x}^*)+2\beta\sum_{t=1}^T\left\{f(\vec{p}[t],\tilde{\vec{x}}[t]) + \sum_{k=1}^n\left(\frac{2p_k[t]}{1+\tilde{x}_k[t]}\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_k[t] \vee 1}}\right)\right\} \nonumber \\& = n + n\beta^2TD^2 +4\beta\sum_{t=1}^T\sum_{k=1}^n\left\{p_k[t]\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_k[t] \vee 1}}\right\}- 2\beta T f^{\text{maximin}}+2\beta\sum_{t=1}^Tf^{\text{worst}}(\vec{p}[t]) \nonumber
\end{align}

where (a) follows since $\vec{p}[1],\vec{p}^* \in \mathcal{I}$, and

\begin{align}     \lVert\nabla_{\vec{p}}f(\vec{p}[t],\vec{x}[t])\rVert^2 = \sum_{k=1}^n \left|\frac{\tilde{E}_k[t]}{1+x_k[t]}\right|^2 \leq nD^2,
\end{align}

due to (<ref>), (b) follows from (<ref>) and (<ref>), and (c) follows from (<ref>) and the definition of $f_t$ in (<ref>). Hence, we have that,

\begin{align}\label{eqn:before expec}
2\beta T f^{\text{maximin}}-2\beta\sum_{t=1}^Tf^{\text{worst}}(\vec{p}[t]) \leq  n + n\beta^2TD^2 +4\beta\sum_{t=1}^T\sum_{k=1}^n\left\{p_k[t]\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_k[t] \vee 1}}\right\}
\end{align}

Now we take the expectation (Conditioned on the event $A$) of both sides of (<ref>), we have,

\begin{align}\label{eqn:cond_reg_bnd}
&\mathbb{E}\{2\beta T f^{\text{maximin}}-2\beta\sum_{t=1}^Tf^{\text{worst}}(\vec{p}[t])|A\} \nonumber\\&\leq  n + n\beta^2TD^2 +4\beta\sum_{t=1}^T\mathbb{E}\left\{\sum_{k=1}^np_k[t]\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_k[t] \vee 1}}\Bigg{|}A\right\} \nonumber\\& \leq n + n\beta^2TD^2 +\frac{4\beta}{P(A)}\sum_{t=1}^T\mathbb{E}\left\{\sum_{k=1}^np_k[t]\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_k[t] \vee 1}}\right\} \nonumber\\& =  n + n\beta^2TD^2 +\frac{4\beta}{P(A)}\sum_{t=1}^T\mathbb{E}\left\{\mathbb{E}\left\{\sum_{k=1}^np_k[t]\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_k[t] \vee 1}}\Bigg{|}\mathcal{H}[t]\right\}\right\}\nonumber\\& =  n + n\beta^2TD^2 +\frac{4\beta}{P(A)}\sum_{t=1}^T\mathbb{E}\left\{\mathbb{E}\left\{\sum_{k=1}^n\mathbb{E}\{\mathbbm{1}_{(\alpha_k[t] = 1)}|\mathcal{H}[t]\}\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_k[t] \vee 1}}\Bigg{|}\mathcal{H}[t]\right\}\right\}\nonumber\\& =  n + n\beta^2TD^2 +\frac{4\beta}{P(A)}\sum_{t=1}^T\mathbb{E}\left\{\mathbb{E}\left\{\sum_{{j:\alpha_j[t] = 1}}\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_{j}[t] \vee 1}}\Bigg{|}\mathcal{H}[t]\right\}\right\}\nonumber\\& =  n + n\beta^2TD^2 +\frac{4\beta}{P(A)}\sum_{t=1}^T\mathbb{E}\left\{\sum_{j:\alpha_j[t] = 1}\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_{j}[t] \vee 1}}\right\}.
\end{align}

\begin{align}
2\beta R(&T) = \mathbb{E}\left\{2\beta T f^{\text{maximin}}-2\beta\sum_{t=1}^Tf(\vec{p}[t])\Bigg{|}A\right\}P(A) \nonumber\\&\ \ \ \ + \mathbb{E}\left\{2\beta T f^{\text{maximin}}-2\beta\sum_{t=1}^Tf(\vec{p}[t])\Bigg{|}A^c\right\}P(A^c) \nonumber\\& \leq_{(a)} n + n\beta^2TD^2 +4\beta\sum_{t=1}^T\mathbb{E}\left\{\sum_{{j:\alpha_j[t] = 1}}\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_{j}[t] \vee 1}}\right\} + 2\beta rCT\mathbb{P}(A^c) \nonumber\\& \leq_{(b)} n + n\beta^2TD^2 +4\beta\mathbb{E}\left\{\sum_{k=1}^{n}\sum_{\substack{t=1\\{k:\alpha_k[t] = 1} }}^T\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{n_{k}[t] \vee 1}} \right\} + 4\beta rn\delta C T^2  \nonumber\\&=  n + n\beta^2TD^2+4\beta\mathbb{E}\left\{\sum_{k=1}^n\sum_{j=1}^{n_k[t]}\sqrt{\frac{2\log{\frac{T(T+1)}{\delta}}}{j}} \right\} + 4\beta r n\delta C T^2 \nonumber \\& \leq_{(c)}  n + n\beta^2TD^2+8\beta\mathbb{E}\left\{\sum_{k=1}^n\sqrt{2n_k[t]\log{\frac{T(T+1)}{\delta}}} \right\} + 4\beta r n\delta C T^2 \nonumber\\&\leq_{(d)}n + n\beta^2TD^2+8\beta\mathbb{E}\left\{n\sqrt{2\log{\frac{T(T+1)}{\delta}}}\sqrt{\sum_{k=1}^nn_k[t]}\right\} + 4\beta r n\delta C T^2 \nonumber\\&= n + n\beta^2TD^2+8\beta n\sqrt{2rT\log{\frac{T(T+1)}{\delta}}} + 4\beta r n\delta C T^2
\end{align}

where (a) follows combining (<ref>), the fact that

\begin{align}
f^{\text{maximin}} = \sum_{k=1}^n \frac{p^*_kE_k}{1+x^*_k} \leq \sum_{k=1}^n p^*_kC = rC,
\end{align}

and $P(A) \leq 1$, (b) follows due to (<ref>), (c) follows from $\sum_{k=1}^l \sqrt{k}^{-1} \leq 2\sqrt{l}$, and (d) follows since $\sum_{k=1}^n \sqrt{n_k[t]} \leq \sqrt{\sum_{k=1}^n n_k[t]} = \sqrt{n}$. Hence, we have that,

\begin{align}
R(&T)  \leq  \frac{n}{2\beta } + \frac{n\beta}{2} TD^2+4n\sqrt{2rT\log{\frac{T(T+1)}{\delta}}} + 2r n\delta C T^2
\end{align}

Using $\beta = \sqrt{1/(TD^2)}$, and $\delta = 1/(2rnCT^2)$, we have,

\begin{align}
R[t] \leq nD\sqrt{T}+ 4n\sqrt{2rT\log(2nrCT^3(T+1))} + 1
\end{align}

as desired.

Notice that since $f^{\text{worst}}$ is concave from the definition in (<ref>), we also have that,

\begin{align}
f^{\text{maximin}} - \mathbb{E}\left\{f^{\text{worst}}\left(\frac{\sum_{t=1}^T\vec{p}[t]}{T}\right)\right\} \leq \frac{R[t]}{T}.
\end{align}

§ SPECIAL CASES OF THE ONE-SLOT SETTING

This section focuses on solving some special cases of the one-slot setting. These approaches lead to faster solutions and more insight into the problem. In this section, we assume, without loss of generality, that $E_k > 0$ for all $1 \leq k \leq n$ since otherwise, we can transform the problem into a lower dimensional version. Without loss of generality, we also assume that $E_k \geq E_{k+1}$ for $1 \leq k \leq n-1$. First, we derive an explicit solution to the case $m=3, r=1$. Then, we solve the two-player general case. Before constructing the solution, we state the well-known Lagrange multiplier lemma, which will be useful in constructing the solution for both cases.

Consider the following constrained optimization problem,

z_i(x⃗)≥0   for  i ∈{1,2,…,k}

where $z_i:\mathbb{R}^n \to \mathbb{R}$ for $i \in \{0,1,2,\dots,k\}$, and $\mathcal{Y} \subset \mathbb{R}^n$. Consider the following unconstrained problem for some $\vec{\mu} \geq 0$.

Let $\vec{x}^*$ be a solution to the unconstrained problem. Assume $\vec{x}^*$ satisfies for all $i \in \{1,2,\dots,k\}$,

* $z_i(\vec{x}^*) \geq 0$ (That is $\vec{x}^*$ is feasible for the constrained problem)

* $\mu_i > 0$ implies $z_i(\vec{x}^*) = 0$.

Then $\vec{x}^*$ is optimal for the constrained problem.

§.§ $r=1$, $m=3$

We first focus on finding $f^{\text{worst}}(\vec{p})$ explicitly for $\vec{p} \in \mathcal{I}$. Then, we use the solution to solve (P2). Recall from the definition (<ref>), $f(\vec{p},\vec{x}) = \sum_{k=1}^n p_kE_k/(1+x_k)$, for $\vec{p} \in \mathcal{I}$, and $\vec{x} \in \mathcal{J}_2$, where  $\mathcal{J}_{q}$ and $\mathcal{I}$ in (<ref>), and (<ref>), respectively.

Consider fixed $\vec{p} \in \mathcal{I}$. Let $a = \arg\max_{1 \leq i \leq n} E_ip_i$, and $b = \arg\max_{1 \leq i \leq n, i \neq a} E_ip_i$. Then $\vec{x}^* = \arg\min_{\vec{x} \in \mathcal{J}_{2}}$ $f(\vec{p},\vec{x})$ can be given in two cases.

Case 1: $E_a p_a > 3E_bp_b$: We have for $k \in \{1,2,\dots,n\}$,

\begin{align}\label{eqn:first_assign}
x^*_k = \begin{cases}
2 & \text{ if } k = a,\\
0 &  \text{ otherwise. }
\end{cases}
\end{align}

Case 2: $E_a p_a \leq 3E_bp_b$: We have for $k \in \{1,2,\dots,n\}$,

\begin{align}\label{eqn:second_assign}
x^*_k = \begin{cases}
1 & \text{ if } k \in \{a,b\},\\
0 &  \text{ otherwise. }
\end{cases}
\end{align}

Since from the definition of $\vec{x}^*$, we have that $\vec{x}^* \in \mathcal{J}_2$, we should have $\sum_{k=1}^nx^*_k = 2$. Hence, the only way to assign players $A_2$ and $A_3$ to the resources is to assign both players to a single or two different resources. Notice that when assigning both players to a single resource, they should be assigned to resource $a$ since $E_ap_a \geq E_{k}p_{k}$ for all $k \in [1:n]$. For the same reason, when assigning players to two different resources, they should be assigned to resources $a$ and $b$. Hence, it only remains to check which assignment yields the smallest $f(\vec{p},\vec{x})$.

Under case 1: (assignment (<ref>))

\begin{align}
f(\vec{p},\vec{x}) = \frac{p_aE_a}{3} + p_bE_b + \sum_{k \not \in \{a,b\}} p_kE_k = \sum_{k=1}^n p_kE_k - \frac{2p_aE_a}{3}.
\end{align}

Under case 2: (assignment (<ref>))

\begin{align}
f(\vec{p},\vec{x}) = \frac{p_aE_a}{2} + \frac{p_bE_b}{2} + \sum_{k \not \in \{a,b\}} p_kE_k = \sum_{k=1}^n p_kE_k - \frac{p_aE_a}{2}- \frac{p_bE_b}{2}
\end{align}

Comparing the two cases yields the result.

Now we can formulate the worst-case expected utility $f^{\text{worst}}(\vec{p})$ of player $A_1$. Lemma <ref> allows us to formulate this as,

\begin{align}\label{def:f_worst_m3}
f^{\text{worst}}(\vec{p}) = \begin{cases}
\sum_{k =1}^n p_kE_k - \frac{2}{3}\Gamma_1 &\text{ if } \Gamma_1>3\Gamma_2\\
\sum_{k =1}^n p_kE_k - \frac{1}{2}\Gamma_1- \frac{1}{2}\Gamma_2 &\text{ if } \Gamma_1\leq 3\Gamma_2\\
\end{cases}
\end{align}

where $\Gamma_1$, $\Gamma_2$ are the largest and the second largest elements of the set $\{ p_kE_k; 1 \leq k \leq n \}$, respectively.

Hence, notice that the solution of (P2) is the problem with the maximal optimal objective out of the $n^2$ linear programs,

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

∑_k =1^n p_kE_k - p_iE_i/2-p_jE_j/2 (P2-(i,j)):
p⃗ ∈ℐ, p_iE_i ≤3p_jE_j,  p_iE_i ≥p_jE_j
p_jE_j ≥p_kE_k   ∀1 ≤k ≤n , k ≠i,

where $i,j \in [1:n]$ and $i\neq j$. To solve $\text{(P2-}i\text{)}$, and $\text{(P2-}(i,j)\text{)}$, it shall be useful to re-index to associate $i$ with 1, and $(i,j)$ with 1 and 2. Hence, we define the two problems.

f_1(p⃗) =   ∑_k =1^n p_kF_k-2p_1F_1/3(P2-1):
p_1F_1 ≥3p_k+1F_k+1   ∀k ∈{1,…,n-1},

f_2(p⃗) = ∑_k =1^n p_kF_k-p_1F_1/2 -p_2F_2/2 +(P2-2):
p⃗ ∈ℐ, p_1F_1 ≤3p_2F_2,  p_1F_1 ≥p_2F_2
p_2F_2 ≥p_kF_k   ∀3 ≤k ≤n ,

where for (P2-1), $\vec{F} \in \mathbb{R}^n$ is assumed to a positive vector such that $F_k \geq F_{k+1}$ for $k \in [2:n-1]$, and for (P2-2), $\vec{F} \in \mathbb{R}^n$ is assumed to a positive vector such that $F_k \geq F_{k+1}$ for $k \in [3:n-1]$. It should be noted that the $F_k$ values are just the $E_k$ values under more convenient indexing. Solving the above two problems will immediately solve each of the previously defined $n^2$ problems. Define the two sequences $(U_i; 1\leq i \leq n)$, and  $(V_i; 2\leq i \leq n)$ by,

\begin{align}\label{eqn:def_r_i}
U_i = \frac{i}{\frac{3}{F_1} + \sum_{k=2}^{i}\frac{1}{F_k}},
\end{align}

\begin{align}\label{eqn:def_S_i}
V_i = \frac{i-1}{\sum_{k=1}^{i}\frac{1}{F_k}}.
\end{align}

These two sequences will be useful when constructing the solutions to (P2-1) and (P2-2).

§.§.§ Solving (P2-1)

Consider the problem (P2-1).

f_1(p⃗) =   ∑_k =1^n p_kF_k-2p_1F_1/3(P2-1):
p_1F_1 ≥3p_k+1F_k+1   ∀k ∈{1,2,…,n-1},

Also, consider the Lagrangian dual of the above problem $\text{(P2-1-$\vec{\mu}$)}$ for $\vec{\mu} \in \mathbb{R}^{n-1}$  such that $\mu_i \geq 0$ for all $i \in \{1,\dots,n-1\}$ constructed according to Lemma <ref>,

f_1(p⃗) +  ∑_k=1^n-1 μ_k (p_1F_1-3p_k+1  F_k+1)(P2-1-$\vec{\mu}$):
p⃗ ∈ℐ.

Let us define $u = \arg\max_{1 \leq i \leq n} U_i$, where the sequence $(U_i; 1\leq i \leq n)$ is defined in (<ref>) and $\arg\max$ returns the least index in the case of ties. We establish that the solution to (P2-1) is $\vec{p}^*$, where,

\begin{align}\label{eqn:p2-2_sol}
p^*_k = \begin{cases}
\frac{\frac{3}{F_1}}{\frac{3}{F_1}+\sum_{j=2}^{u} \frac{1}{F_j}} &\text{ if }  k = 1\\
\frac{\frac{1}{F_k}}{\frac{3}{F_1}+\sum_{j=2}^{u} \frac{1}{F_j}} &\text{ if } 2\leq k \leq {u}\\
0 & \text{ otherwise,}
\end{cases}
\end{align}

with optimal objective value $U_u$. It can be directly seen that $\vec{p}^*$ defined by (<ref>) satisfies the constraints of the problem (P2-1), specifically, $\vec{p}^* \in \mathcal{I}$ and $p^*_1F_1 \geq 3p_{k+1}F_{k+1}$ for $k \in \{2,\dots,n\}$.
To prove that $\vec{p}^*$ solves (P2-1), we construct a Lagrange multiplier vector $\vec{\mu} \in \mathbb{R}^{n-1}$ with $\mu_i \geq 0$ for all $i\in \{1,\dots,n-1\}$ such that $\vec{p}^*$ solves the problem (P2-1-$\vec{\mu}$) and establish that $(\vec{p}^*,\vec{\mu})$ satisfy the conditions of the Lagrange multiplier lemma (Lemma <ref>), namely:

* $p^*_1F_1 \geq 3p^*_{k+1}F_{k+1}$ for all $k \in \{1,\dots,n-1\}$

* For $k \in \{1,\dots,n-1\}$, $\mu_k > 0 \implies p^*_1F_1 = 3p^*_{k+1}F_{k+1}$.

Define the vector $\vec{\mu} \in \mathbb{R}^{n-1}$ as,

\begin{align}\label{eqn:def_mu_p2-1}
\mu_k = \begin{cases}
\frac{1}{3}\left(1 - \frac{1}{F_{k+1}}\frac{u}{\frac{3}{F_1}+\sum_{k=2}^{u}\frac{1}{F_k}}\right) & \text{ if } 1 \leq k \leq u-1\\
0 & \text{ otherwise. }
\end{cases}
\end{align}

Now, we prove the following lemma regarding $\vec{\mu}$.

Consider the $\vec{\mu}$ defined in (<ref>). We have that,

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

* We have, $F_1\left(\frac{1}{3} + \sum_{i=1}^{u-1}\mu_i\right) = F_k(1-3\mu_{k-1}) = \frac{u}{\frac{3}{F_1}+\sum_{i=2}^{u}\frac{1}{F_i}} \text{ for } 2 \leq k \leq u.$

* $F_k  \leq  \frac{u}{\frac{3}{F_1}+\sum_{k=2}^{u}\frac{1}{F_k}}$ for $u+1 \leq k \leq n$

Notice that since $u = \arg\max_{1 \leq i \leq n} U_i$, we have that,

\begin{align}\label{eqn:u_eq}
U_u \geq U_j \text{ for all $j \in [1:n]$.}
\end{align}

* Notice that $\mu_k = 0$ by definition, when $k>u-1$. Now suppose $k \leq u-1$ (so $u \geq 2$). We are required to prove,

\begin{align}
F_{k+1} \geq \frac{u}{\frac{3}{F_1}+\sum_{k=2}^{u}\frac{1}{F_k}},
\end{align}

for all $k \in \{2,3,\dots,u-1\}$. It is enough to prove the above for $k = u-1$, since $F_k \geq F_{k+1}$ for $k \geq 2$. Notice that from (<ref>), we have that $U_u \geq U_{u-1}$. Substituting from (<ref>) and simplifying, we have the result.

* Substituting from the definition of $\mu_k$ and simplifying yields the result.

* If $u = n$, there is nothing to prove. Otherwise, it is enough to prove the result for $k = u+1$, since $F_k \geq F_{k+1}$ for $k \geq 2$. From (<ref>), we have that $U_u \geq U_{u+1}$. Substituting from (<ref>) and simplifying, we have the result.

Notice that due to Lemma <ref>-1, we have that $\mu_i \geq 0$ for all $i\in \{1,\dots,n-1\}$. Hence, consider the dual problem $\text{(P2-1-$\vec{\mu}$)}$ with $\vec{\mu}$ defined in (<ref>). For this choice of $\mu_k$, after eliminating the $\mu_k$, which are zero, we have that the objective of the problem $\text{(P2-1-$\vec{\mu}$)}$ is,

\begin{align}
p_1F_1\left(\frac{1}{3} + \sum_{i=1}^{u-1}\mu_i\right) + \sum_{k=2}^u p_kF_k(1-3\mu_{k-1}) + \sum_{k=u+1}^np_kF_k,
\end{align}

Now, due to Lemma <ref>-2, the above objective simplified to,

\begin{align}\label{eqn:C_def}
\sum_{i=1}^u p_iC + \sum_{k=u+1}^np_kF_k, \text{ where } C = \frac{u}{\frac{3}{F_1}+\sum_{i=2}^u\frac{1}{F_i}}.
\end{align}

Also, notice that from Lemma <ref>-3, we have that $C \geq F_k$ for all $k \in \{u+1,\dots,n\}$.
Hence, the optimal solution for (P2-1-$\vec{\mu}$) is any $\vec{p} \in \mathcal{I}$ such that $p_k = 0$ for all $k \in \{u+1,\dots,n\}$. Hence, $\vec{p}^*$ given in (<ref>) is a solution to (P2-1-$\vec{\mu}$). We establish that $(\vec{p}^*,\vec{\mu})$ also satisfy the conditions of Lemma <ref>. First, recall that $\vec{p}^*$ satisfies the constraints of the problem (P2-1). Second, from (<ref>) notice that $\mu_k >0$ implies that $k \in \{1,\dots,u-1\}$. Also, from (<ref>) notice that $p_1^*F_1 = 3C/u$, and $p^*_{k+1}F_{k+1} = C/u$ for all $k \in
\{1,\dots,u-1\}$, where $C$ is defined in (<ref>). Hence, we have that $\mu_k>0$ implies $p^*_1F_1 = 3p^*_{k+1}F_{k+1}$. Hence from Lemma <ref>, $\vec{p}^*$ is the solution to (P2-1).

§.§.§ Solving (P2-2)

Consider the problem (P2-2).

f_2(p⃗) = ∑_k =1^n p_kF_k-p_1F_1/2 -p_2F_2/2(P2-2):
p⃗ ∈ℐ, p_1F_1 ≤3p_2F_2,  p_1F_1 ≥p_2F_2
p_2F_2 ≥p_kF_k   ∀3 ≤k ≤n ,

Similar to the solution of (P2-1), consider the Lagrangian dual $\text{(P2-2-$\vec{\mu}$)}$ of the above problem for $\vec{\mu} \in \mathbb{R}^n$ such that $\mu_i \geq 0$ for all $i \in \{1,\dots,n\}$ constructed according to Lemma <ref>,

f_2(p⃗) +  μ_1 (3p_2F_2-p_1F_1)+μ_2(p_1F_1-p_2F_2)+ ∑_k=3^nμ_k(p_2F_2-p_kF_k)(P2-2-$\vec{\mu}$):
p⃗ ∈ℐ.

We solve the problem by considering two cases. Similar to the solution of (P2-1), for each case we will provide a vector $\vec{p}^* \in \mathcal{I}$ and the Lagrange multiplier vector $\vec{\mu} \in \mathbb{R}^n$  such that $\mu_i \geq 0$ for all $i \in \{1,\dots,n\}$, $\vec{p}^*$ is a solution to the problem $\text{(P2-2-$\vec{\mu}$)}$, $\vec{p}^*$ is feasible for the problem (P2-2) specifically,

* $\vec{p}^* \in \mathcal{I}$

* $p^*_1F_1 \leq 3p^*_2F_2$

* $p^*_1F_1 \geq p^*_2F_2$

* $p^*_2F_2 \geq p^*_kF_k$ for all $k \in \{3,\dots,n\}$

and $(\vec{p}^*,\vec{\mu})$ satisfy the conditions of the Lagrange multiplier lemma (Lemma <ref>), namely,

* $\vec{p}^*$ is feasible for (P2-2)

* $\mu_1 > 0 \implies p^*_1F_1 = 3p^*_2F_2$

* $\mu_2 > 0 \implies p^*_1F_1 = p^*_2F_2$

* For $k \geq 3$, $\mu_k >0 \implies p^*_2F_2 = p^*_kF_k$.

Let us define $u = \arg\max_{2 \leq i \leq n} U_i$, and $v = \arg\max_{2 \leq i \leq n} V_i$, where the sequences $(U_i; 1\leq i \leq n)$, and  $(V_i; 2\leq i \leq n)$ are defined in (<ref>), and (<ref>), respectively, and $\arg\max$ returns the least index in the case of ties. In this case, to define $u$, we only consider the indices of the $(U_i; 1\leq i \leq n)$ sequence starting from 2 in contrast to the definition of $u$ in the solution to (P2-1). Now, we introduce the two cases.

Case 1 $V_v>U_u$: The solution to (P2-2) in this case is $\vec{p}^*$ where,

\begin{align}\label{eqn:s_geq_r}
p^*_k = \begin{cases}
\frac{\frac{1}{F_k}}{\sum_{j=1}^v \frac{1}{F_j}} &\text{ if } 1\leq k \leq v\\
0 & \text{ otherwise,}
\end{cases}
\end{align}

with optimal objective value $V_v$. It can be easily checked by substitution from (<ref>) that, $\vec{p}* \in \mathcal{I}$, $p^*_1F_1 = p^*_{k}F_{k}$ for all $k \in \{1,\dots,v\}$, and $p^*_kF_k = 0$ for all $k \in \{v+1,\dots,n\}$. Hence, $\vec{p}^*$ is feasible for (P2-2). Now, we focus on constructing the Lagrange multiplier vector $\vec{\mu}$. Define the vector $\vec{\mu} \in \mathbb{R}^n$ as,

\begin{align}\label{eqn:def_mu}
\mu_k = \begin{cases}
\frac{1}{F_1} \frac{v-1}{\sum_{k=1}^{v}\frac{1}{F_k}} - \frac{1}{2} & \text{ if } k = 2,\\
1 - \frac{1}{F_k}\frac{v-1}{\sum_{k=1}^{v}\frac{1}{F_k}} & \text{ if } 3 \leq k \leq v,\\
0 & \text{ otherwise. }
\end{cases}
\end{align}

Now, we prove the following lemma regarding $\vec{\mu}$.

Consider the $\vec{\mu}$ defined in (<ref>). We have that,

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

* $F_1\left(\frac{1}{2} + \mu_2\right) = F_2\left(\frac{1}{2} - \mu_2 + \sum_{i=3}^v \mu_i\right) = F_k(1-\mu_k) = \frac{v-1}{\sum_{k=1}^{v}\frac{1}{F_k}} \text{ for } 3 \leq k \leq v.$

* $F_k  \leq  \frac{v-1}{\sum_{k=1}^{v}\frac{1}{F_k}}$ for $v+1 \leq k \leq n$

Notice that since $u = \arg\max_{2 \leq i \leq n} U_i$, and $v = \arg\max_{2 \leq i \leq n} V_i$, we have that $U_u \geq U_j$ for all $j \in [2:n]$, and $V_v \geq V_j$ for all $j \in [2:n]$. Since from the case description, we have that $V_v>U_u$, we should have that,

\begin{align}\label{eqn:v_eq}
V_v \geq V_j \text{ for all } j \in [2:n] \text{ and } V_v > U_j \text{ for all } j \in [2:n]
\end{align}

* Notice that the result trivially follows for $k \not\in\{2,\dots,v\}$ since $\mu_k = 0$ for such $k$. Hence, we will focus on $k \in\{2,\dots,v\}$. We first prove that $\mu_2 \geq 0$. Notice that from (<ref>), we have that $V_v > U_v$. After substituting from (<ref>) and (<ref>) and simplifying, we have the desired result.
To obtain the result for $3 \leq k \leq v$, we can assume that $v \geq 3$. Notice that we are required to prove,

\begin{align}
F_k \geq \frac{v-1}{\sum_{k=1}^{v}\frac{1}{F_k}}.
\end{align}

It is enough to prove the above for $k = v$, since $F_k \geq F_{k+1}$ for $k \geq 3$. From (<ref>) we have that, $V_v \geq V_{v-1}$. Substituting from (<ref>) and simplifying gives the result.

* Substituting from the definition of $\mu_k$ simplifying will yield the result.

* If $v = n$, there is nothing to prove. Otherwise, it is enough to prove the result for $k = v+1$, since $F_k \geq F_{k+1}$ for $k \geq 3$. From (<ref>) we have that, $V_v \geq V_{v+1}$. Substituting from (<ref>) and simplifying gives the result.

Notice that due to Lemma <ref>-1, we have that $\mu_i \geq 0$ for all $i\in \{1,\dots,n\}$. Hence, similar to the solution to (P2-1), consider the dual problem $\text{(P2-2-$\vec{\mu}$)}$ with $\vec{\mu}$ defined in (<ref>). After eliminating the $\mu_k$, which are zero, we have that the objective of the problem $\text{(P2-2-$\vec{\mu}$)}$ is,

\begin{align}
p_1F_1\left(\frac{1}{2} + \mu_2\right) +p_2F_2\left(\frac{1}{2} - \mu_2+\sum_{i=3}^v\mu_i\right) + \sum_{k=3}^v p_kF_k(1-\mu_{k}) + \sum_{k=v+1}^np_kF_k,
\end{align}

Due to Lemma <ref>-2, the above objective simplified to,

\begin{align}\label{eqn:C_1_def}
\sum_{i=1}^v p_iC + \sum_{k=v+1}^np_kF_k, \text{ where } C = \frac{v-1}{\sum_{i=1}^v\frac{1}{F_i}}.
\end{align}

From Lemma <ref>-3, we have that $C \geq F_k$ for all $k \in \{v+1,\dots,n\}$.
Hence, similar to the solution to (P2-1), the optimal solution for (P2-2-$\vec{\mu}$) is any $\vec{p} \in \mathcal{I}$ such that $p_k = 0$ for all $k \in \{v+1,\dots,n\}$. Hence, $\vec{p}^*$ given in (<ref>) is a solution to (P2-2-$\vec{\mu}$). Recall that $\vec{p}^*$ is feasible for (P2-2). Hence, we are only required to establish that $(\vec{p}^*,\vec{\mu})$ satisfies the conditions of Lemma <ref>. From (<ref>) notice that $\mu_k >0$ implies that $k \in \{2,\dots,v\}$. From (<ref>) notice that $p_k^*F_k = p_1^*F_1$, for all $k \in
\{1,\dots,v\}$. Hence, $\mu_k>0$ implies the corresponding constraint is met with equality. Hence from Lemma <ref>, $\vec{p}^*$ is the solution to (P2-2).

Case 2  $U_u \geq V_v$: The solution to (P2-2) in this case is $\vec{p}^*$ where,

\begin{align}\label{eqn:r_geq_s}
p^*_k = \begin{cases}
\frac{\frac{3}{F_1}}{\frac{3}{F_1}+\sum_{j=2}^u \frac{1}{F_j}} &\text{ if }  k = 1\\
\frac{\frac{1}{F_k}}{\frac{3}{F_1}+\sum_{j=2}^u \frac{1}{F_j}} &\text{ if } 2\leq k \leq u\\
0 & \text{ otherwise,}
\end{cases}
\end{align}

with optimal objective value $U_u$. First notice that $\vec{p}^*$ is feasible for (P2-2), since from (<ref>) we have $\vec{p}* \in \mathcal{I}$, $p^*_1F_1 = 3p^*_{k}F_{k}$ for all $k \in \{2,\dots,u\}$, and $p^*_kF_k = 0$ for all $k \in \{u+1,\dots,n\}$. Similar to case 1, we construct the Lagrange multiplier vector $\vec{\mu}$. Consider the vector $\vec{\mu} \in \mathbb{R}^n$ given by,

\begin{align}\label{eqn:mu_2}
\mu_k = \begin{cases}
\frac{1}{2}- \frac{1}{F_1} \frac{u}{\frac{3}{F_1}+\sum_{k=2}^{u}\frac{1}{F_k}} & \text{ if } k = 1,\\
1 - \frac{1}{F_k}\frac{u}{\frac{3}{F_1}+\sum_{k=2}^{u}\frac{1}{F_k}} & \text{ if } 3 \leq k \leq u,\\
0 & \text{ otherwise. }
\end{cases}
\end{align}

We have the following lemma.

For the $\vec{\mu}$ defined in (<ref>), we have that,

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

* We have,

\begin{align}
F_1\left(\frac{1}{2} - \mu_1\right) = F_2\left(\frac{1}{2} + 3\mu_1 + \sum_{i=3}^u \mu_i\right) = F_k(1-\mu_k) = \frac{u}{\frac{3}{F_1}+\sum_{k=2}^{v}\frac{1}{F_k}} \text{ for } 3 \leq k \leq u.
\end{align}

* $F_k  \leq  \frac{u}{\frac{3}{F_1}+\sum_{k=2}^{u}\frac{1}{F_k}}$ for $u+1 \leq k \leq n$

Notice that since $u = \arg\max_{2 \leq i \leq n} U_i$, and $v = \arg\max_{2 \leq i \leq n} V_i$, we have that $U_u \geq U_j$ for all $j \in [2:n]$, and $V_v \geq V_j$ for all $j \in [2:n]$. Since from the case description, we have that $U_u \geq V_v$, we should have that,

\begin{align}\label{eqn:v_1_eq}
U_u \geq U_j \text{ for all } j \in [2:n] \text{ and } U_u \geq V_j \text{ for all } j \in [2:n]
\end{align}

* Notice that this condition is trivially satisfied for $k \in \{2\}\cup\{u+1,\dots,n\}$ since $\mu_k = 0$ for such $k$. Hence, we focus on $k \not\in \{2\}\cup\{u+1,\dots,n\}$. First, we prove that $\mu_1 \geq 0$. Notice that from (<ref>), we have that $U_u \geq V_u$. Substituting from (<ref>) and (<ref>) and simplifying, we have the desired result.
To obtain the result for $3 \leq k \leq u$, notice that we can assume $u\geq 3$. Notice that from (<ref>), we have that $U_u \geq U_{u-1}$. Substituting from (<ref>) and simplifying, we have the desired result.

* Substituting from the definition of $\mu_k$ simplifying will yield the result.

* If $u = n$, there is nothing to prove. Otherwise, it is enough to prove the result for $k = u+1$, since $F_k \geq F_{k+1}$ for $k \geq 3$. From (<ref>) we have that, $U_u \geq U_{u+1}$. Substituting from (<ref>) and simplifying gives the result.

The analysis is very similar to case 1. Notice that due to Lemma <ref>-1, we have that $\mu_i \geq 0$ for all $i\in \{1,\dots,n\}$. Similar to case 1, consider the dual problem $\text{(P2-2-$\vec{\mu}$)}$ with $\vec{\mu}$ defined in (<ref>). After eliminating the $\mu_k$, which are zero, we have that the objective of the problem $\text{(P2-2-$\vec{\mu}$)}$ is,

\begin{align}
p_1F_1\left(\frac{1}{2} - \mu_1\right) +p_2F_2\left(\frac{1}{2} +3\mu_1+\sum_{i=3}^u\mu_i\right) + \sum_{k=3}^u p_kF_k(1-\mu_{k}) + \sum_{k=u+1}^np_kF_k,
\end{align}

Due to Lemma <ref>-2, the above objective simplified to,

\begin{align}\label{eqn:C_2_def}
\sum_{i=1}^u p_iC + \sum_{k=u+1}^np_kF_k, \text{ where } C = \frac{u}{\frac{3}{F_1}+\sum_{i=2}^u\frac{1}{F_i}}.
\end{align}

From Lemma <ref>-3, we have that $C \geq F_k$ for all $k \in \{u+1,\dots,n\}$.
Hence, similar to case 1, the optimal solution for (P2-2-$\vec{\mu}$) is any $\vec{p} \in \mathcal{I}$ such that $p_k = 0$ for all $k \in \{u+1,\dots,n\}$. In particular, $\vec{p}^*$ given in (<ref>) is a solution to (P2-2-$\vec{\mu}$). Recall that $\vec{p}^*$ is feasible for (P2-2). Now, we establish that $(\vec{p}^*,\vec{\mu})$ also satisfy the conditions of Lemma <ref>. From (<ref>) notice that $\mu_k >0$ implies that $k \in \{1\}\cup \{3,\dots,v\}$. From (<ref>) notice that $p_1^*F_1 = 3p_2^*F_2$, and $p^*_kF_k = p_2^*F_2$ for all $k \in
\{3,\dots,v\}$. Hence, $\mu_k>0$ implies the corresponding constraint is met with equality. Hence from Lemma <ref>, $\vec{p}^*$ is the solution to (P2-2).

§.§.§ Solving (P2)

Finally, we are ready to combine the solutions of (P2-1) and (P2-2) to solve (P2). Notice that since we solved (P2-1) and (P2-2), we have solved all of the $n^2$ problems $\text{(P2-}i\text{)}$, and $\text{(P2-}(i,j)\text{)}$ for $i,j \in [1:n]$ such that $i \neq j$. Hence, we can solve (P2) by solving all the above problems and finding the one that gives the highest optimal objective. But, it turns out that it is, in fact, enough to solve $\text{(P2-}1\text{)}$, and $\text{(P2-}(1,2)\text{)}$. To prove this, Consider arbitrary $(i,j)$ such that $1 \leq i,j \leq n$ such that $i \neq j$. Define, $\vec{D} \in \mathbb{R}^n$ to be the vector obtained by permuting the entries of $\vec{E}$ such that $D_1 = E_i, D_2 = E_j$, and $D_k \geq D_{k+1}$ for $k \in [3:n-1]$. Notice that due to the solution of (P2-2), the optimal value of (P2-($i,j$)) is given by,

\begin{align}
\gamma^* = \max\left\{ \frac{a-1}{\sum_{k=1}^{a}\frac{1}{D_k}}, \frac{b}{\frac{3}{D_1}+\sum_{k=2}^{b}\frac{1}{D_k}} \Bigg{|} 2 \leq a,b \leq n\right\},
\end{align}

Notice that,

\begin{align}\label{eqn:gamma_st}
\max\left\{ \frac{a-1}{\sum_{k=1}^{a}\frac{1}{E_k}}, \frac{b}{\frac{3}{E_1}+\sum_{k=2}^{b}\frac{1}{E_k}} \Bigg{|} a,b \in [2:n]\right\} \geq \gamma^*,
\end{align}

where the inequality follows since $\sum_{k=1}^{a}\frac{1}{E_k} \leq \sum_{k=1}^{a}\frac{1}{D_k}$, and $\frac{3}{E_1}+\sum_{k=2}^{b}\frac{1}{E_k} \leq \frac{3}{D_1}+\sum_{k=2}^{b}\frac{1}{D_k}$ for all $a,b \in [2:n]$. This follows since, $E_k \geq E_{k+1}$ for all $k \in [1:n-1]$. But notice that the left-hand side of (<ref>) is the optimal value of (P2-($1,2$)). Hence, the optimal value of (P2-($1,2$)) is at least as that of (P2-($i,j$)). Hence, it is enough to solve (P2-($1,2$)). With similar reasoning, we can establish that solving (P2-1) suffices. Considering the solutions (P2-($1,2$)) and (P2-1), we have the result. The theorem below summarizes the solution we constructed for (P2).

Define the two sequences $(U_i; 1\leq i \leq n)$, and $(V_i; 2\leq i \leq n)$ according to (<ref>), and (<ref>), respectively with $\vec{F} = \vec{E}$. Let $u = \arg\max_{1 \leq i \leq n} U_i$, and $v = \arg\max_{2 \leq i \leq n} V_i$, where $\arg\max$ returns the least index in the case of ties. Then, the solution to (P2) can be described in two cases.

Case 1:  If $V_v > U_u$, the solution to (P2) is $\vec{p}^*$, where,

\begin{align}\label{eqn:c1_p2}
p^*_k = \begin{cases}
\frac{\frac{1}{E_k}}{\sum_{j=1}^v \frac{1}{E_j}} &\text{ if } 1\leq k \leq v\\
0 & \text{ otherwise.}
\end{cases}
\end{align}

Case 2:  If $U_u \geq V_v$, the solution to (P2) is $\vec{p}^*$, where,

\begin{align}\label{eqn:c2_p2}
p^*_k = \begin{cases}
\frac{\frac{3}{E_1}}{\frac{3}{E_1}+\sum_{j=2}^u \frac{1}{E_j}} &\text{ if }  k = 1\\
\frac{\frac{1}{E_k}}{\frac{3}{E_1}+\sum_{j=2}^u \frac{1}{E_j}} &\text{ if } 2\leq k \leq u\\
0 & \text{ otherwise.}
\end{cases}
\end{align}

Recall that the solution of (P2) is either the solution of (P2-1) or (P2-($1,2$)), depending on which problem produces the higher optimal objective value. We will consider the following two cases.

Case 1:  $V_v > U_u$: In this case, from the analysis in Section <ref>, we have that the solution to (P2-($1,2$)) is (<ref>), with an objective value equal to $V_v$. Also, from the analysis in Section <ref>, we have that the solution to (P2-1) is (<ref>), with an objective value equal to $U_u$. Since $V_v > U_u$, we have the result.

Case 2:  $V_v \leq U_u$: In this case, from the analysis in Section <ref>, we have that the optimal objective value of (P2-($1,2$)) is $\max\{V_v,U_{u^{'}}\}$, where $u^{'} = \arg\max_{2 \leq i \leq n} U_i$. But notice that since $u = \arg\max_{1 \leq i \leq n} U_i$, we have that $U_{u^{'}} \leq U_u$. Combining this with the case description, we have that $\max\{V_v,U_{u^{'}}\} \leq U_u$. Also, from the analysis in Section <ref>, we have that the solution to (P2-1) is (<ref>), with an objective value equal to $U_u$. Since $V_v \leq U_u$, we have the result.

Fig. <ref> denotes the optimal probabilities found for $n = 10$, along with,

\begin{align}
\vec{E} = [7, 6.7, 5.5, 4.5, 1.26, 1.21, 1.16, 1.11, 1.05, 1.0].
\end{align}

It is interesting to notice the variation of choice probabilities in Fig. <ref>. In particular, it can be seen that while it is optimal to choose a collection of resources with the highest mean rewards with non-zero probability, within the collection, one chooses resources with lower mean rewards with higher probability. This can be explained as follows. First, player $A_1$ will never choose the resources with the lowest mean rewards. Second, in the collection of resources with relatively high mean rewards, player $A_1$ may be tempted to choose resources with lower mean rewards with high probability since, in the worst case, opponents will choose the rewards with the highest mean rewards.

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
xmin= 1, xmax=10,
ymin= 0, ymax=8,
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
only marks,
mark options=scale=1.5
] coordinates

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
xmin= 1, xmax=10,
ymin=-0.1, ymax=1.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.9, transform shape
only marks,
mark options=scale=1.5
] coordinates

Left:  The mean rewards of different resources. Right:  Probabilities of choosing different resources for the considered $\vec{E}$.

§.§ $m=2$, arbitrary $r$

The case $r=1$ is solved in [13]. The solution is given by,
$\vec{p}^*$ where,

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

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

See [13] for the proof.

The general two-player case can be reduced to a linear program. Again $f^{\text{worst}}$ can be found explicitly in this case. It can be easily seen that

\begin{align}
f^{\text{worst}}(\vec{p}) &= \sum_{k =1}^n p_kE_k  -\frac{1}{2}\left(\sum_{j=1}^r\text{max}_{(j)}\{ p_kE_k; 1 \leq k \leq n \}\right),
\end{align}

where $\text{max}_{(j)}$ returns the $j$-th largest element in a set. Consider the following $n \choose r$ linear programs, each indexed by a size $r$ ordered subset  of $[1:n]$ containing distinct elements, where the problem (P-$a_1,a_2,..,a_r$) with $a_k \in [1:n]$ for each $k \in [1:r]$ and $a_k < a_{k+1}$ for $k \in [1:r-1]$, is given by,

p⃗,γ∑_j =1^n p_jE_j  -1/2(∑_j =1^r p_a_jE_a_j)(P-a_1,a_2,..,a_r):
p_a_jE_a_j≥γ  ∀1≤j≤r
γ≥p_tE_t  ∀t ∈[1:n]∖{a_1,a_2,..,a_r}

Notice that the solution of (P2) is the solution of the problem out of the above ${n \choose r}$ problems with the maximum objective value. Hence, solving (P2) amounts to solving $n \choose r$ linear programs. In the below lemma, we prove that it is, in fact, enough to solve $\text{(P-}1,2,..,r\text{)}$

The optimal objective value of $\text{(P-}1,2,..,r\text{)}$ is at least the optimal objective value of $\text{(P-}a_1,a_2,..,a_r\text{)}$, where $a_k \in [1:n]$ for each $k \in [1:r]$ and $a_k < a_{k+1}$ for each $k \in [1:r-1]$.

See Appendix <ref>

For $1 \leq a,b \leq n$, define,

\begin{align}
S_{a,b} = \begin{cases}
\sum_{i=a}^b \frac{1}{E_i} & \text{ if } b \geq a\\
0 & \text{ otherwise }
\end{cases} ,
\end{align}

Now, we focus on constructing the solution for the problem subjected to two assumptions.

A1 $E_1,E_2,\dots,E_n$ are distinct real numbers

A2 for all $a \in [1:r]$, and $b \in [r+1,n]$, $E_bS_{a,b}$ is not an integer.

The solution for this case is defined in terms of three functions $h:[0:r-1]\times[r+1:n] \to \mathbb{R}$, $e:[0:r-1]\times[r+1:n] \to \mathbb{R}$, and $g: [r+1:n]\times [r+1:n] \to \mathbb{R}$. Before introducing the three functions, we begin with a few definitions.

Good triplets and bad triplets: We call a triplet $(a,b,c) \in [0:r-1] \times [r+1:n] \times [r+1:n]$ a good-triplet if $r-a+b-c < E_bS_{a+1,b}$. If the reverse inequality is true, we call $(a,b,c)$ a bad-triplet index.

The following lemma introduces certain properties regarding triplets.

Consider the following scenarios.

* If $(a,b,c)$ is a good-triplet then,

* If $b>r+1$, then $(a,b-1,c)$ is a good-triplet

* If $c<n$, then $(a,b,c+1)$ is a good-triplet

* If $a<r-1$, then $(a+1,b,c)$ is a good-triplet

* If $a>0$, and $c<n$, then $(a-1,b,c+1)$ is a good-triplet

* If $(a,b,c)$ is a bad-triplet then,

* If $b<n$, then $(a,b+1,c)$ is a bad-triplet

* If $c>r+1$, then $(a,b,c-1)$ is a bad-triplet

* If $a>0 $, then $(a-1,b,c)$ is a bad-triplet

* If $a<r-1$, and $c>0$, then $(a+1,b,c-1)$ is a bad-triplet

See Appendix <ref>

Function $h$: From Lemma <ref>-1-a, 2-a, we have that, for fixed $(a,c) \in [0:r-1]\times [r+1,n]$, either $(a,b,c)$ are good-triplets for all $b \in [r+1,n]$, $(a,b,c)$ are bad-triplets for all $b \in [r+1,n]$, or there exists a unique $b \in [r+1,n-1]$ such that $(a,b,c)$ is a good-triplet and $(a,b+1,c)$ is a bad-triplet. Define $h(a,c) = n$ in the first case, $h(a,c) = r$ in the second case, and $h(a,c) = b$ where $b$ is the unique index in the third case.

Function $e$: Similarly, from Lemma <ref>-1-b, 2-b, we have that, for fixed $(a,b) \in [0:r-1]\times [r+1,n]$, either $(a,b,c)$ are good-triplets for all $c \in [r+1,n]$, $(a,b,c)$ are bad-triplets for all $c \in [r+1,n]$, or there exists a unique $c \in [r+2,n]$ such that $(a,b,c)$ is a good-triplet and $(a,b,c-1)$ is a bad-triplet. Define $e(a,b) =  r+1$ in the first case, $e(a,b) = n+1$ in the second case, and $e(a,b) = c$ where $c$ is the unique index in the third case.

Function $g$: Similarly, from Lemma <ref>-1-c, 2-c, we have that, for fixed $(b,c) \in [r+1,n]\times [r+1,n]$, either $(a,b,c)$ are good-triplets for all $a \in [0,r-1]$, $(a,b,c)$ are bad-triplets for all $a \in [0,r-1]$, or there exists a unique $a \in [1,r-1]$ such that $(a,b,c)$ is a good-triplet and $(a-1,b,c)$ is a bad-triplet. Define $g(b,c) =  0$ in the first case, $g(b,c) = r$ in the second case, and $g(b,c) = a$ where $a$ is the unique index in the third case.

Now, we construct the explicit solution using the functions defined above.

Assume that we are given the two assumptions A1, and A2 are true. Define the three sets $\mathcal{X}_1,\mathcal{X}_2,\mathcal{X}_3$, as

\begin{align}
&\mathcal{X}_1 = \{(a,c) \in [0:r-1] \times [r+1:n] | r<h(a,c)\}
\nonumber\\
&\mathcal{X}_2 = \{(a,b) \in [0:r-1] \times [r+1:n] | b< e(a,b) \leq n\}
\nonumber\\
&\mathcal{X}_3 = \{(b,c) \in [r+1:n] \times [r+1:n] | b \leq c,  0< g(b,c) \leq r-1 \},
\end{align}

and define the vectors $\vec{p}^{1,a,c}$ for $(a,c) \in \mathcal{X}_1$, $\vec{p}^{2,a,b}$ for $(b,c) \in \mathcal{X}_2$ and $\vec{p}^{3,b,c}$ for $(b,c) \in \mathcal{X}_3$, where,

* for $(a,c) \in \mathcal{X}_1$

\begin{align}\label{eqn:p1ac}
p^{1,a,c}_k = \begin{cases}
1 & \text{ if } 1\leq k \leq a\\
\frac{r-a+b-c}{E_kS_{a+1,b}}  & \text{ if } a+1\leq k \leq b\\
1 & \text{ if } b+1\leq k \leq c\\
0 & \text{ otherwise},
\end{cases}
\end{align}

where $b = \min\{h(a,c),c\}$,

* for $(a,b) \in  \mathcal{X}_2$,

\begin{align}\label{eqn:p2ab}
p^{2,a,b}_k = \begin{cases}
1 & \text{ if } 1\leq k \leq a\\
\frac{E_b}{E_k}  & \text{ if } a+1\leq k \leq b\\
1 & \text{ if } b+1\leq k \leq c-1\\
(r-a)+b-c - E_bS_{a+1,b-1} & \text{ if } k = c\\
0 & \text{ otherwise},
\end{cases}
\end{align}

where $c = e(a,b)$

* for $(b,c) \in \mathcal{X}_3$,

\begin{align}\label{eqn:p3bc}
p^{3,b,c}_k = \begin{cases}
1 & \text{ if } 1\leq k \leq a-1\\
r-a+b-c - E_bS_{a+1,b-1} & \text{ if } k = a\\
\frac{E_b}{E_k}  & \text{ if } a+1\leq k \leq b\\
1 & \text{ if } b+1\leq k \leq c\\
0 & \text{ otherwise},
\end{cases}
\end{align}

where $a = g(b,c)$.

* We have that,

* $\vec{p}^{1,a,c}$ for all $(a,c) \in \mathcal{X}_1$ are all valid vectors belonging to $\mathcal{I}$.

* $\vec{p}^{2,a,b}$ for all $(a,b) \in \mathcal{X}_2$ are all valid vectors belonging to $\mathcal{I}$.

* $\vec{p}^{3,b,c}$ for all $(b,c) \in \mathcal{X}_3$ are all valid vectors belonging to $\mathcal{I}$.

where $\vec{p}^{1,a,c},\vec{p}^{2,a,b}$ and $\vec{p}^{3,b,c}$ are defined in (<ref>), (<ref>), and (<ref>), respectively.

* We have that,

* for $(a,c) \in \mathcal{X}_1$, $(\vec{p}^{1,a,c},\gamma)$ is feasible for (P-1,2,..,r), where $\gamma = \frac{\delta}{S_{a+1,b}}$, and $b = \text{min}\{h(a,c),c\}$.

* for $(a,b) \in \mathcal{X}_2$, $(\vec{p}^{2,a,b},\gamma)$ is feasible for (P-1,2,..,r), where $\gamma = E_b$

* for $(b,c) \in \mathcal{X}_3$, $(\vec{p}^{3,b,c},\gamma)$ is feasible for (P-1,2,..,r), where $\gamma = E_b$

* the pair $(\vec{p}^0,\gamma)$, where

\begin{align}\label{eqn:def_vecp0}
p^0_k = \begin{cases}
1 & \text{ if } 1\leq k \leq r\\
0 & \text{ otherwise}
\end{cases}
\end{align}

and $\gamma = E_{r+1}$ is feasible for (P-1,2,..,r).

* The solution to $\text{(P-}1,2,..,r\text{)}$ is the one that produces the maximum objective value out of the elements in the following set

\begin{align}
\mathcal{A} = &\{\vec{p}^0\}\cup\{\vec{p}^{1,a,c}: (a,c) \in \mathcal{X}_1\} \cup \{\vec{p}^{2,a,b}: (a,b) \in \mathcal{X}_2 \}\cup \{\vec{p}^{3,b,c}: (b,c) \in \mathcal{X}_3\},
\end{align}

along with the $\gamma$ values defined in part-2.

See Appendix <ref>

Fig. <ref> denotes the optimal probabilities found for $n,r = 10,3$, along with $\vec{E}$ given by,

\begin{align}
E_j = \begin{cases}
7 & \text{ if } j = 1\\
6.7 & \text{ if } j = 2\\
1 + \frac{60-3j}{19} & \text{ otherwise }
\end{cases}
\end{align}

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
xmin= 1, xmax=10,
ymin= 0, ymax=8,
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
only marks,
mark options=scale=1.5
] coordinates

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
xmin= 1, xmax=10,
ymin=-0.1, ymax=1.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.9, transform shape
only marks,
mark options=scale=1.5
] coordinates

Left:  The mean rewards of different resources. Right:  Probabilities of choosing different resources for the considered $\vec{E}$.

In Fig. <ref>, it can be seen that player $A_1$ will always choose a subset of resources with the highest mean rewards, and the probabilities of choosing the remaining resources follow a similar pattern to the $m=3,r=1$ case described in Section <ref>. The intuition behind this is also very similar to the three-player singleton case.

§ SIMULATION RESULTS

For the simulations, consider the scenarios given below,

* $m = 2, r = 1, n = 4$.

* $m = 2, r = 3, n = 4$.

* $m = 3, r = 1, n = 4$.

* $m = 5, r = 1, n = 4$.

* $m = 5, r = 1, n = 6$.

* $m = 5, r = 3, n = 6$.

For all the simulations, we fix $E_i = 1$ for $i>1$ and plot different quantities as functions of $E_1$. In both Figures <ref> and <ref>, the top row depicts the maximum expected worst-case utility as a function of $E_1$ and the bottom row, depicts a solution for the probabilities of choosing different resources as a function of $E_1$ (Notice that there can be multiple solutions for optimal selection probabilities). Figure <ref> shows the first three scenarios, whereas Figure <ref> shows the last three scenarios.

Notice that similar to the observations in [13], in Figures <ref> and <ref>, we have that the probabilities of choosing resource 1 exhibit similar patterns over several ranges. In particular, it can be seen that the probability of choosing resource 1 vs. $E_1$ curve has $m$ discontinuities, and between two adjacent discontinuities, the curve is decreasing. The reason for the decreasing trend of choice probability between discontinuities can be explained using the same idea used to explain the variation of choice probabilities over the resources for a fixed $\vec{E}$ described in Section <ref>. In particular, increasing $E_1$ might mean that other players are more likely to choose resource $1$. On the other hand, the probability of choosing resource 1 should also increase at certain points since for large values of $E_1$ it makes sense to choose resource 1 with high probability irrespective of the decision of other players. For instance, in the case of $E_1>m$ with $r=1$, player $A_1$ chooses resource 1 with probability 1 since even if all the other players select resource 1, it is beneficial for player $A_1$ to select it. This is also evident by the simulation results in Figures <ref> and <ref>. Hence, the discontinuities of the probability of choosing resource 1 vs. $E_1$ curve can be seen as points at which the confidence of player $A_1$ on choosing resource $1$ grows.

[spy using outlines = magnification = 0.5, rectangle,  black, connect spies]
ylabel=Expected Utility,
xmin=0.1, xmax=3.4,
ymin=0.75, ymax=2,
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,name path=lower,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=1] CSV/m2r1.csv;

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Expected Utility,
xmin=0.1, xmax=3.4,
ymin=0.75, ymax=3.2,
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/m2r3.csv;

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Expected Utility,
xmin=0.1, xmax=3.4,
ymin=0.5, 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.9, transform shape
[color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=1] CSV/m3r1.csv;

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Choice probability,
xmin=0.1, xmax=3.4,
ymin=0, ymax=1.7,
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=2] CSV/m2r1.csv;
[color=red,mark=+,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=3] CSV/m2r1.csv;
[color=green,mark=x,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=4] CSV/m2r1.csv;
[color=black,mark=o,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=5] CSV/m2r1.csv;

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Choice probability,
xmin=0.1, xmax=3.4,
ymin=0, ymax=1.7,
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=2] CSV/m2r3.csv;
[color=red,mark=+,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=3] CSV/m2r3.csv;
[color=green,mark=x,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=4] CSV/m2r3.csv;
[color=black,mark=o,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=5] CSV/m2r3.csv;

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Choice probability,
xmin=0.1, xmax=3.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=2] CSV/m3r1.csv;
[color=red,mark=+,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=3] CSV/m3r1.csv;
[color=green,mark=x,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=4] CSV/m3r1.csv;
[color=black,mark=o,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=5] CSV/m3r1.csv;

1st column: Case $m = 2, r = 1, n = 4$. 2nd column: Case $m = 2, r = 3, n = 4$. 3rd column: Case $m = 3, r = 1, n = 4$. Top: The worst case expected utility of player 1 vs. $E_1$ (The maximum possible error of the solution is indicated for scenarios 4 and 5).  Bottom: One possible solution for the probabilities of choosing different resources when the worst-case approach is used vs. $E_1$ (Notice that the probabilities sum to $r$).

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Expected Utility,
xmin=0.1, xmax=5.5,
ymin=0.3, ymax=1.2,
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
[name path=lower,color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=1] CSV/m5r1.csv;
[name path=upper,draw=none,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=2] CSV/m5r1.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=5.5,
ymin=0.3, 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.9, transform shape
[name path=lower,color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=1] CSV/m5r1n6.csv;
[name path=upper,draw=none,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=2] CSV/m5r1n6.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=5.5,
ymin=0.75, ymax=2,
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
[name path=lower,color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=1] CSV/m5r3n6.csv;
[name path=upper,draw=none,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=2] CSV/m5r3n6.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=5.5,
ymin=0, ymax=1.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.9, transform shape
[color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=3] CSV/m5r1.csv;
[color=red,mark=+,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=4] CSV/m5r1.csv;
[color=green,mark=x,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=5] CSV/m5r1.csv;
[color=black,mark=o,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=6] CSV/m5r1.csv;

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Choice probability,
xmin=0.1, xmax=5.5,
ymin=0, ymax=1.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.9, transform shape
[color=blue,mark=*,thick,mark size=1pt] table[col sep=comma,header=false,x index=0,y index=3] CSV/m5r1n6.csv;
[color=red,mark=+,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=4] CSV/m5r1n6.csv;
[color=green,mark=x,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=5] CSV/m5r1n6.csv;
[color=black,mark=o,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=6] CSV/m5r1n6.csv;
[color=purple,mark=o,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=6] CSV/m5r1n6.csv;
[color=orange,mark=o,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=6] CSV/m5r1n6.csv;

[spy using outlines = magnification = 1, rectangle, size=2cm,black, connect spies]
ylabel=Choice probability,
xmin=0.1, xmax=5.5,
ymin=0, ymax=1.8,
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=3] CSV/m5r3n6.csv;
[color=red,mark=+,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=4] CSV/m5r3n6.csv;
[color=green,mark=x,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=5] CSV/m5r3n6.csv;
[color=black,mark=o,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=6] CSV/m5r3n6.csv;
[color=purple,mark=o,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=6] CSV/m5r3n6.csv;
[color=orange,mark=o,thick,mark size=2pt] table[col sep=comma,header=false,x index=0,y index=6] CSV/m5r3n6.csv;

1st column: Case $m = 5, r = 1, n = 4$. 2nd column: Case $m = 5, r = 1, n = 6$. 3rd column: Case $m = 5, r = 3, n = 6$. Top: The worst case expected utility of player 1 vs. $E_1$, along with the maximum possible error of the solution.  Bottom: One possible solution for the probabilities of choosing different resources when the worst-case approach is used vs. $E_1$.

§ CONCLUSIONS

In this paper, we considered the problem of worst-case expected utility maximization for the first player of multi-player resource-sharing games with fair reward allocation under two settings. In the first setting, we provided an algorithmic solution to a one-slot game, where we also provided explicit solutions for two special cases. For the second setting, we considered an online scenario, for which we provided an upper confidence bound algorithm that achieves a worst-case regret of $\mathcal{O}(\sqrt{T\log{(T)}})$. The simulations and the explicit solutions depict interesting variations of the probability of choosing a resource when the mean of the considered resource is changed while holding the mean reward of other resources fixed.

§ ALGORITHM FOR SAMPLING FROM $\MATHCAL{I}$

Initialize an empty set $\mathcal{Y}$

Initialize $\vec{p}^1 = \vec{p}$, $t = 1$

$\vec{p}^t \neq 0$
Let $a_k$ for $1 \leq k \leq n$ be such that $\{a_1,a_2,\dots,a_n\}$ is a permutation of $[1:n]$ such that $p^t_{a_k} \geq p^t_{a_{k+1}}$ for $k \in [1:n-1]$

Set $d_{t} = \min\left(1 - \sum_{k=1}^{t-1} d_k - p^t_{a_{r+1}},p^t_{a_r}\right)$

each $i \in [1:r]$
Set $p^{t+1}_{a_i} = p^t_{a_i} - d_t$

each $i \in [r+1:n]$
Set $p^{t+1}_{a_i} = p^t_{a_i}$

Add $(d_t,\alpha[t])$ to $\mathcal{Y}$ where,

\begin{align}
\alpha_j[t] = \begin{cases}
1 & \text{ if }j \in \{a_1,a_2,\dots,a_r\}\\
0 & \text{ otherwise }
\end{cases}
\end{align}

Set $t \leftarrow t+1$

Output $\mathcal{Y}$ $\big{(}$We have $\vec{p} = \sum_{t=1}^{\lvert\mathcal{Y}\rvert}d_t\alpha[t]$ $\big{)}$.

Algorithm to express $\vec{p} \in \mathcal{I}$ as a convex combination of elements in $\mathcal{J}_1$.

§ PROOF OF LEMMA <REF>-2

It can be easily seen that $\text{Conv}(\mathcal{J}_1) \subseteq \mathcal{I}$. To prove that $\mathcal{I} \subseteq \text{Conv}(\mathcal{J}_1)$, we start by noticing that $\mathcal{I}$ is a compact convex set. We prove that the extreme points of the set $\mathcal{I}$ are contained in $\mathcal{J}_1$, which establishes the claim  (See, for example, [47]). Hence, we prove that none of the elements of $\mathcal{I} \setminus \mathcal{J}_1$ is an extreme point of $\mathcal{I}$. For this, take any $\vec{p} \in \mathcal{I} \setminus \mathcal{J}_1$. Notice that since $\vec{p} \not\in \mathcal{J}_1$ and $\vec{p} \in \mathcal{I}$, there exists $k,j \in [1:n]$ such that $0 < p_j < p_k <1$. Now take $\varepsilon>0$ such that $p_j -\varepsilon >0$ and $p_k + \varepsilon <1$. Define the vector $\vec{\tilde{p}}$ such that,

\begin{align}
\tilde{p}_i = \begin{cases}
p_i & \text{ if } i \not\in \{k,j\}\\
p_j -\varepsilon & \text{ if } i= j\\
p_k +\varepsilon & \text{ if } i= k\\
\end{cases}
\end{align}

Notice that $\mathcal{I}$ contains the entire line segment joining $\vec{p}$ and $\vec{\tilde{p}}$. Hence, $\vec{p}$ is not an extreme point of $\mathcal{I}$ as desired.

§ PROOF OF LEMMA <REF>

Let $\mathcal{A} =(a_1,a_2,..,a_r)$ be a subset of $[1:n]$ containing distinct elements such that $a_k < a_{k+1}$ for each $k \in [1:r-1]$. Consider the problem $\text{(P-}\mathcal{A}\text{)}$. Let us $\mathcal{B} = [1:n]\setminus \mathcal{A}$. Denote $\mathcal{A}_{\text{bad}} = \mathcal{A}\setminus[1:r]$ as the set of bad-1 indices and the set, $\mathcal{B}_{\text{bad}} = \mathcal{B} \cap [1:r]$ as the set of bad-2 indices. Notice that for any given problem, there are an equal number of bad-1 and bad-2 indices. We intend to prove that there is an optimal solution with no bad-1 (or bad-2) indices. For this, we establish that for any problem with $k>0$ bad-1 elements, there exists another problem with $k-1$ bad-1 indices with an objective value at least as the objective value of the problem with $k$ bad-1 indices. Assume $\text{(P-}\mathcal{A}\text{)}$ has $k$ bad-1 indices. Let $(\vec{p},\gamma)$ be the optimal solution of $\text{(P-}a_1,a_2,..,a_r\text{)}$. We consider two cases.

Case 1: There is no pair $(a^{'},b^{'})$ such that $a^{'}$ is a bad-1 index and $b^{'}$ is a bad-2 such that $E_{a^{'}} <E_{b^{'}}$.

Notice that any bad-1 index is greater than any bad-2 index. Hence, for pair $(i,j)$ such that $i$ is a bad-1 index, and $j$ is a bad-2 index, we have that $E_j \geq E_i$ (Since $\vec{E}$ is assumed to be decreasing). Hence, the above condition would mean that $E_j = E_i$ for all $i,j$ such that $i$ is bad-1, and $j$ is bad-2. Hence $(\vec{p},\gamma)$ will be feasible for $\text{(P-}(\mathcal{A}\setminus\{i\} \cup \{j\}\text{))}$ as well. Moreover, $(\vec{p},\gamma)$ will give the same objective value for $\text{(P-}(\mathcal{A}\setminus\{i\} \cup \{j\}\text{))}$ as $\text{(P-}\mathcal{A})$, and $\text{(P-}(\mathcal{A}\setminus\{i\} \cup \{j\}\text{))}$ will have $k-1$ bad-1 indices.

Case 2: There exists a pair $(a^{'},b^{'})$ such that $a^{'}$ is a bad-1 index and $b^{'}$ is a bad-2 such that $E_{a^{'}} <E_{b^{'}}$.

We begin with the following two lemmas.

There exists $t \in \mathcal{A}$, and $s \in \mathcal{B}$ such that $E_tp_t = E_sp_s =  \gamma$.

We only prove the existence of $t \in \mathcal{A}$ such that $E_tp_t = \gamma$. The other part can be solved by repeating the same argument. Assume the contrary. Let $\gamma^* = (\min\{p_jE_j;j \in \mathcal{A}\}+\gamma)/2$. We have that $\gamma^* >\gamma$, and $p_jE_j > \gamma^*$ for all $j \in \mathcal{A}$. Notice that $p_{a^{'}}>0$ and $p_{b^{'}}<1$ (The first inequality follows since $p_{a^{'}}E_{a^{'}} > p_{b^{'}}E_{b^{'}}$, and the second inequality follows since $p_{a^{'}}E_{a^{'}} > p_{b^{'}}E_{b^{'}}$, and  $E_{b^{'}} > E_{a^{'}}$). Hence, there exists $\delta>0$, small enough such that,

\begin{align}
&E_{a^{'}} (p_{a^{'}} -\delta) \geq \gamma^*\\
&E_{b^{'}} (p_{b^{'}} +\delta) \leq \gamma^*\\
&(p_{a^{'}} -\delta) \geq 0\\
&(p_{b^{'}} +\delta) \leq 1.
\end{align}

Hence $(\vec{\tilde{p}},\gamma^*)$, where $\vec{\tilde{p}}$ is given by,

\begin{align}
\tilde{p}_k = \begin{cases}
p_k & \text{ if } k \in [1:n]\setminus\{a^{'},b^{'}\}\\
p_{a^{'}} -\delta & \text{ if } k =a^{'}\\
p_{b^{'}} +\delta & \text{ if } k =b^{'}
\end{cases}
\end{align}

is feasible for $\text{(P-}a_1,a_2,..,a_r\text{)}$, and also achieves a higher optimal objective value since $E_{b^{'}} > E_{a^{'}}$. This is a contradiction.

For $\text{(P-}a_1,a_2,..,a_r\text{)}$, there exists an optimal solution with at least one bad-1 element $a$ such that, $E_a p_a = \gamma$, and at least one bad bad-2 element $b$ such that $E_b p_b = \gamma$.

Notice that for all $k \in \mathcal{A} \setminus\mathcal{A}_{\text{bad}}$, and $j \in \mathcal{A}_{\text{bad}}$, we have that $E_k \geq E_j$.

Notice that the entries of $\vec{p}$ can be rearranged without affecting the objective and feasibility for $\text{(P-}a_1,a_2,..,a_r\text{)}$ such that the following two conditions are satisfied.

C1 For $k \in \mathcal{A} \setminus \mathcal{A}_{\text{bad}}$, and $j \in \mathcal{A}_{\text{bad}}$, if we have $E_k = E_j$, then $p_k \geq p_j$.

C2 For $k \in \mathcal{B} \setminus\mathcal{B}_{\text{bad}}$, and $j \in \mathcal{B}_{\text{bad}}$ if we have $E_k = E_j$, then $p_j \geq p_k$.

Now we establish that any optimal $\vec{p}$ reordered such that both C1 and C2 are met satisfy the conditions of the lemma. We show only the bad-1 case. The bad-2 case can be solved using the same argument.

Assume the contrary. Hence, all bad-1 elements $j$ satisfy $E_j p_j > \gamma$.  Consider $t \in \mathcal{A}$ such that $E_tp_t = \gamma$ (Such a $t$ always exists from Lemma <ref>). Notice that $t$ cannot be bad-1. Hence $E_t \geq E_j$ for all bad-1 indices $j$. In this case, we have the following claim.

Claim: There exists a bad-1 index $i$ such that $E_i < E_t$.

If no such bad-1 index $i$ exists, then we should have $E_t = E_j$ for all bad-1 indices $j$. From C1, this would imply that $p_t \geq p_j$ for all bad-1 indices $j$. Hence, we should have $E_tp_t \geq E_jp_j>\gamma$, which contradicts $E_tp_t = \gamma$.

Consider the $i$ described in the Claim. Since $E_tp_t = \gamma < E_ip_i$, and $E_t > E_i$, we have that, $p_t<p_i \leq 1$. Also we have that $p_i > 0$ since $E_ip_i>\gamma$. Hence, it is possible to find $\delta>0$, small enough such that,

\begin{align}
&E_i (p_i -\delta) \geq \gamma\\
&(p_i -\delta) \geq 0\\
&(p_t +\delta) \leq 1.
\end{align}

Since $E_t > E_i$ it is easy to see that, $(\vec{\tilde{p}},\gamma)$ given by,

\begin{align}
\tilde{p}_k = \begin{cases}
p_k & \text{ if } k \in [1:n]\setminus\{i,t\}\\
p_i -\delta & \text{ if } k =i\\
p_t +\delta & \text{ if } k =t
\end{cases}
\end{align}

is a better solution to $\text{(P-}a_1,a_2,..,a_r\text{)}$. This is a contradiction.

Now, let $a$, $b$ be the indices such that $a$ is bad-1 and $E_ap_a = \gamma$, and $b$ is bad-2 and $E_bp_b = \gamma$, which are guaranteed to exists due to Lemma <ref>. Consider the problem,
$\text{(P-}(\mathcal{A}\setminus\{a\}) \cup\{b\}\text{)}$, which has $k-1$ bad-1 elements. Notice that since $E_ap_a = E_bp_b = \gamma$, we have that $(\vec{p},\gamma)$ is feasible for $\text{(P-}(\mathcal{A}\setminus\{a\}) \cup\{b\}\text{)}$. Also, the objective values of $\text{(P-}(\mathcal{A}\setminus\{a\}) \cup\{b\}\text{)}$ and $\text{(P-}a_1,a_2,..,a_r\text{)}$ evaluated at $(\vec{p},\gamma)$ are equal. Hence, we are done.

§ PROOF OF LEMMA <REF>

Let $\delta = r-a+b-c$.

* Recall that $(a,b,c)$ being a good-triplet is equivalent to,

\begin{align}\label{eqn:pref_1}
\delta < E_bS_{a+1,b}
\end{align}

* Notice that,

\begin{align}
r-a+b-1-c = \delta - 1 <_{(a)} E_bS_{a+1,b}-1 = E_{b}S_{a+1,b-1} \leq E_{b-1}S_{a+1,b-1},
\end{align}

where (a) follows from (<ref>), and the last inequality follows since $E_{b-1} \geq E_b$.

* Notice that,

\begin{align}
r-a+b-(c+1) = \delta - 1 <_{(a)} E_bS_{a+1,b}-1 < E_{b}S_{a+1,b}
\end{align}

where (a) follows from (<ref>)

* Notice that,

\begin{align}
r-(a+1)+b-c = \delta - 1 <_{(a)} E_bS_{a+1,b}-1 = E_{b}S_{a+1,b-1}< E_{b}S_{a+2,b}.
\end{align}

where (a) follows from (<ref>) and the last inequality follows since $S_{a+2,b} \geq S_{a+1,b-1}$, which follows since $\vec{E}$ is non-increasing in it's components.

* Notice that,

\begin{align}
r-(a-1)+b-(c+1) = \delta  <_{(a)} E_bS_{a+1,b} < E_{b}S_{a,b},
\end{align}

where (a) follows from (<ref>).

* All the claims in this part follow from the contra-positives of the corresponding claims in part 1.

§ PROOF OF THEOREM <REF>

a) Recall that, $\mathcal{X}_1 = \{(a,c) \in [0:r-1] \times [r+1:n] | r<h(a,c)\}$, and $\vec{p}^{1,a,c}$ for $(a,c) \in \mathcal{X}_1$ is defined as,

\begin{align}\label{eqn:p1ac_1}
p^{1,a,c}_k = \begin{cases}
1 & \text{ if } 1\leq k \leq a\\
\frac{r-a+b-c}{E_kS_{a+1,b}}  & \text{ if } a+1\leq k \leq b\\
1 & \text{ if } b+1\leq k \leq c\\
0 & \text{ otherwise},
\end{cases}
\end{align}

where $b = \min\{h(a,c),c\}$. We first prove that $\vec{p}^{1,a,c}$, is a valid vector in $\mathcal{I}$.

Since $(a,c) \in \mathcal{X}_1$, we have that $h(a,c) >r$ and $c>r$, which implies that,

\begin{align}\label{eqn:b_geq_r}
0 \leq a < r<b \leq  c \leq n.
\end{align}

Notice that since $h(a,c) >r$, from the definition of $h$, we have that $(a,h(a,c),c)$ is a good-triplet. Since $b \leq h(a,c)$, combining with Lemma <ref>-1-a, we have that,

\begin{align}\label{eqn:good_c1}
(a,b,c)  \text{ is a \textit{good-triplet}}.
\end{align}

This means that,

\begin{align}\label{eqn:10101011}
r-a+b-c < E_bS_{a+1,b}.
\end{align}

Also, notice that if $b < c$, then we should have $b = h(a,c)$ and $b<n$, which implies from the definition of $h$ that $(a,b+1,c)$ is a bad-triplet. Hence,

\begin{align}\label{eqn:bad_c1}
\text{if } b<c, (a,b+1,c) \text{ is a \textit{bad-triplet}}.
\end{align}

Hence, if $b<c$ we have that,

\begin{align}\label{eqn:11101011}
E_{b+1}S_{a+1,b} < r-a+b-c,
\end{align}

where the inequality is strict due to assumption A2. Since $(a,c) \in \mathcal{X}_1$, we have that $a+1 \leq r < b \leq c$, which implies that (<ref>) is a valid definition. Now we check the conditions for $\vec{p}^{1,a,c} \in \mathcal{I}$. The sum constraint can be checked by direct substitution. The constraint, $0 \leq p^{1,a,c}_k \leq 1$ follows trivially for $k \not\in [a+1,b]$. For $k \in [a+1,b]$, the constraint $0 \leq p^{1,a,c}_k$ holds if and only if $r-a+b-c>0$. Notice that this holds whenever $b<c$ due to (<ref>). If $b = c$, the above reduces to $r-a>0$, which holds since $a<r$ by the definition of $\mathcal{X}_1$. Hence, we have,

\begin{align}\label{eqn:del_geq_0}
\delta \geq 0
\end{align}

Now, to establish that $p^{1,a,c}_k \leq 1$, we have

\begin{align}
p^{1,a,c}_k = \frac{\delta}{E_kS_{a+1,b}} \leq \frac{\delta}{E_bS_{a+1,b}} \leq 1,
\end{align}

where the last inequality follows due to (<ref>).

b) Recall that, $\mathcal{X}_2 = \{(a,b) \in [0:r-1] \times [r+1:n] | b< e(a,b) \leq n\}$, and $\vec{p}^{2,a,b}$ for $(a,b) \in \mathcal{X}_2$ is defined as,

\begin{align}\label{eqn:p2ab_1}
p^{2,a,b}_k = \begin{cases}
1 & \text{ if } 1\leq k \leq a\\
\frac{E_b}{E_k}  & \text{ if } a+1\leq k \leq b\\
1 & \text{ if } b+1\leq k \leq c-1\\
(r-a)+b-c - E_bS_{a+1,b-1} & \text{ if } k = c\\
0 & \text{ otherwise},
\end{cases}
\end{align}

where $c = e(a,b)$. Now, we prove that $\vec{p}^{1,a,b}$, is a valid vector in $\mathcal{I}$. Since $(a,b) \in \mathcal{X}_2$, we have that,

\begin{align}\label{eqn:c_ge_b}
n \geq e(a,b) = c >b > r > a \geq 0
\end{align}

Notice that since the definition of function $e$, and the fact that $e(a,b) > b \geq r+1$, we have that,

\begin{align}\label{eqn:good_b1}
(a,b,c)  \text{ is a \textit{good-triplet}},
\end{align}

\begin{align}\label{eqn:bad_b1}
(a,b,c-1) \text{ is a \textit{bad-triplet}}.
\end{align}

This means that,

\begin{align}\label{eqn:100001}
E_bS_{a+1,b}-1 < r-a+b-c < E_bS_{a+1,b},
\end{align}

where the first inequality is strict due to assumption A2. Notice that, $a+1 \leq r < b < c \leq n$. Hence, $\vec{p}^{2,a,b}$ defined in (<ref>) is a valid definition. Now we check the conditions for $\vec{p}^{2,a,b} \in \mathcal{I}$ The sum constraint can be checked using direct substitution. Since for $k \in [a+1,b]$ we have,

\begin{align}
p^{2,a,b}_k = \frac{E_b}{E_k} \leq \frac{E_b}{E_b} = 1,
\end{align}

the constraint, $0 \leq p^{2,a,b}_k \leq 1$ follows trivially for $k \neq c$.

For $k = c$, notice that,

\begin{align}
p^{2,a,b}_c = \delta - E_bS_{a+1,b-1} =  \delta +1 - E_bS_{a+1,b}\in [0,1],
\end{align}

where last inequality follows from (<ref>).

c) Recall that, $\mathcal{X}_3 = \{(b,c) \in [r+1:n] \times [r+1:n] | b \leq c,  0< g(b,c) \leq r-1 \}$, and $\vec{p}^{3,b,c}$ for $(b,c) \in \mathcal{X}_3$ is defined as,

\begin{align}\label{eqn:p3bc_1}
p^{3,b,c}_k = \begin{cases}
1 & \text{ if } 1\leq k \leq a-1\\
r-a+b-c - E_bS_{a+1,b-1} & \text{ if } k = a\\
\frac{E_b}{E_k}  & \text{ if } a+1\leq k \leq b\\
1 & \text{ if } b+1\leq k \leq c\\
0 & \text{ otherwise},
\end{cases}
\end{align}

where $a = g(b,c)$. Since $(b,c) \in \mathcal{X}_3$, we have that,

\begin{align}\label{eqn:a_ge_zer}
0<a <r< b \leq c \leq n.
\end{align}

Notice that since the definition of $g$, and the fact that $g(b,c) > 0$, we have that,

\begin{align}\label{eqn:good_a1}
(a,b,c)  \text{ is a \textit{good-triplet}},
\end{align}

\begin{align}\label{eqn:bad_a1}
(a-1,b,c) \text{ is a \textit{bad-triplet}}.
\end{align}

This means that,

\begin{align}\label{eqn:1000011}
E_bS_{a,b}-1 < r-a+b-c < E_bS_{a+1,b},
\end{align}

where the first inequality is strict due to assumption A2.

Notice that the definition of $\vec{p}^{3,b,c}$ in (<ref>) is a valid since $0< a < r < b \leq c \leq n$. Now we check the conditions for $\vec{p}^{3,b,c} \in \mathcal{I}$. The sum constraint can be checked using direct substitution. Due to the same argument as case 2, in this case, the constraint, $0 \leq p^{3,b,c}_k \leq 1$ follows trivially for $k \neq a$. For $k = a$, notice that,

\begin{align}
p^{3,b,c}_a = \delta - E_bS_{a+1,b-1} =  \delta +1 - E_bS_{a+1,b} \leq 1,
\end{align}

where the last inequality follows from (<ref>).

a)  For $k \in [1:a]$ we have that, $p^{1,a,c}_kE_k = E_k \geq p_{a+1}E_{a+1} = \gamma$. For $k \in [a+1:b]$ we have that, $p^{1,a,c}_kE_k = \gamma$. Finally, for $k \in [b+1:c]$, we can assume that $b < c$, in which case we have that $p^{1,a,c}_kE_k = E_k \leq E_{b+1} \leq \gamma$, where the last inequality follows from (<ref>).

b) For $k \in [1:a]$ we have that, $p^{2,a,b}_kE_k = E_k \geq E_b = \gamma$. For $k \in [a+1:b-1]$ we have that, $p^{2,a,b}_kE_k = E_b =\gamma$. For $k \in [b+1:n]$, we have that $p^{2,a,b}_kE_k  \leq  E_k \leq E_b = \gamma$. For $k = b$, we have that, $p^{2,a,b}_bE_b  \leq  E_b = \gamma$.

c) For $k \in [1:a-1]$ we have that, $p^{3,b,c}_kE_k = E_k \geq E_b = \gamma$. For $k \in [a+1:b]$ we have that, $p^{3,b,c}_kE_k = E_b =\gamma$. For $k \in [b+1:n]$, we have that $p^{3,b,c}_kE_k  \leq  E_k \leq E_b = \gamma$. For $k = a$, we have that,

\begin{align}
p^{3,b,c}_bE_a -E_b &= E_a(r-a+b-c-E_bS_{a+1,b-1})-E_b \nonumber\\&= E_a(r-a+b-c - E_bS_{a,b-1}) \geq 0,
\end{align}

where the last inequality follows due to (<ref>).

d) This follows trivially, by substitution, due to the non-increasing property of $\vec{E}$.

3) Define the three sets,

\begin{align}
&\mathcal{A}_1 = \{\vec{p}^{1,a,c}: (a,c) \in \mathcal{X}_1\},\
\mathcal{A}_2 = \{\vec{p}^{2,a,b}: (a,b) \in  \mathcal{X}_2\},\
\mathcal{A}_3 =  \{\vec{p}^{3,b,c}: (b,c) \in \mathcal{X}_3\},\nonumber\\&
\mathcal{A} =\{\vec{p}^0\} \cup \mathcal{A}_1 \cup \mathcal{A}_2 \cup \mathcal{A}_3
\end{align}

Let us denote by $z(\vec{q})$ the objective value of $\text{(P-}1,2,..,r\text{)}$ for $\vec{q} \in \mathcal{I}$. We solve the problem under four cases. The four cases can be summarized as,

C1 Best vector in $\mathcal{A}$ comes from $\mathcal{A}_1$

C2 Best vector in $\mathcal{A}$ comes from $\mathcal{A}_2$

C3 Best vector in $\mathcal{A}$ comes from $\mathcal{A}_3$

C4 Best vector in $\mathcal{A}$ is $\vec{p}^0$, where $\vec{p}^0$ is defined in (<ref>).

In each of the above cases, we focus on constructing a Lagrange multiplier vector $\vec{\mu} \in \mathbb{R}^n$ that will establish the best vector is optimal from Lagrange Multiplier Lemma (Lemma <ref>).

Case 1: Best vector in $\mathcal{A}$ comes from $\mathcal{A}_1$

Let $\vec{p}^{1,a,c}$ denote the best vector where $(a,c) \in \mathcal{X}_1$ (See the definition in (<ref>)). Define, $b = \min\{h(a,c),c\}$.

\begin{align}\label{eqn:gamma_def}
\theta = \frac{r-a}{2}+b-r
\end{align}

and $\delta = r-a+b-c$. Hence, we have,

\begin{align}\label{eqn:z1ac}
z(\vec{p}^{1,a,c}) = \sum_{i=1}^a \frac{E_i}{2} + \frac{\theta \delta}{S_{a+1,b}} + \sum_{i=b+1}^cE_i.
\end{align}

We introduce the following lemma, which will be useful in handling this case.

We have that,

* $\frac{\theta}{S_{a+1,b}} \leq E_c$

* $\frac{E_{a+1}}{2} \leq  \frac{\theta}{S_{a+1,b}}$

* If $a>0$, we have, $\frac{E_{a}}{2} \geq \frac{\theta}{S_{a+1,b}}$

* If $c<n$, we have, $E_{c+1} \leq \frac{\theta}{S_{a+1,b}}$,

where $\theta$ is defined in (<ref>).

1) We prove this part in several cases. The cases make sense since $c \geq b \geq r+1$ from (<ref>),

Case 1 $c = r+1$: Combining $b\leq c$ and (<ref>), we should have $b = r+1$. We are required to prove that $E_{r+1}S_{a+1,r+1} \geq \frac{r-a}{2}+1$. Notice that in this case, (<ref>) simplifies to $r-a< E_{r+1}S_{a+1,r+1}$. Hence, we are done if $r-a \geq 2$. Hence, the only case to check is $a = r-1$. In this case, the required statement simplifies to  $E_r \leq 2E_{r+1}$, which follows from $z(\vec{p}^0) \leq z(\vec{p}^{1,a,c})$, where $\vec{p}^0$ is defined in (<ref>).

Case 2  $c > r+1$, $b = c$, and $(a,c-1,c-1)$ is a good-triplet: From (<ref>) and $c-1\geq r+1$, we have that $(a,c-1)$ belongs to the domain of function $h$. Since $(a,c-1,c-1)$ is a good-triplet, from the definition of function $h$, we have that $h(a,c-1) \geq c-1$. Since, $c-1 \geq r+1$, we have that $(a,c-1) \in \mathcal{X}_1$, and $\min\{h(a,c-1),c-1\} = c-1$. Hence,

\begin{align}
z(\vec{p}^{1,a,c-1}) = \sum_{i=1}^a \frac{E_i}{2} + \frac{(\theta-1)\delta}{S_{a+1,c-1}}
\end{align}

Simplifying $z(\vec{p}^{1,a,c-1}) \leq z(\vec{p}^{1,a,c})$ we have the result.

Case 3  $c > r+1$, $b = c$, and $(a,c-1,c-1)$ is a bad-triplet: From (<ref>) and $c-1\geq r+1$, we have that $(a,c-1)$ belongs to the domain of function $e$. Combining (<ref>) with Lemma <ref>-1-a, we have that, $(a,c-1,c)$ is a good-triplet. Combining this with the case description, we have that $e(a,c-1) = c$. Since $c-1 < c \leq n$, where the last inequality follows from (<ref>), we have that $(a,c-1) \in \mathcal{X}_2$. Notice that,

\begin{align}
z(\vec{p}^{2,a,c-1}) = \sum_{i=1}^{a}\frac{E_i}{2} + E_{c-1}\left(\theta - 1\right)+E_c(\delta -E_{c-1}S_{a+1,c-1})
\end{align}

Substituting for  $z(\vec{p}^{2,a,c-1}) \leq z(\vec{p}^{1,a,c})$, we get,

\begin{align}
(E_cS_{a+1,c} - \theta)(E_{c-1}S_{a+1,c}-\delta)>0.
\end{align}

Since $E_{c-1}S_{a+1,c} \geq E_cS_{a+1,c} > \delta$, where the last inequality follows from (<ref>), we are done.

Case 4  $c > r+1$, $b < c$, and $(a,b,c-1)$ is a good-triplet: From (<ref>) and $c-1\geq r+1$, we have that $(a,c-1)$ belongs to the domain of function $h$. Since $b<c \leq n$, from (<ref>), we have that $(a,b+1,c)$ is a bad-triplet. Combining with $c>r+1$, from Lemma <ref>-2-b, we have that $(a,b+1,c-1)$ is a bad-triplet. Since $(a,b,c-1)$ is a good-triplet, we have that $h(a,c-1) = b$. Since $c-1 \geq r+1$, we have that $(a,c-1) \in \mathcal{X}_1$. Also, $\min\{h(a,c-1),c-1\} = c-1$, since $b \leq c-1$. Hence,

\begin{align}
z(\vec{p}^{1,a,c-1}) = \sum_{i=1}^a \frac{E_i}{2} + \frac{\theta(\delta+1)}{S_{a+1,b}} + \sum_{i=b+1}^{c-1}
\end{align}

Substituting to $z(\vec{p}^{1,a,c-1}) \leq z(\vec{p}^{1,a,c})$ and simplifying, we get the desired result.

Case 5 $c > r+1$, and $b <c$, $(a,b,c-1)$ is a bad-triplet: From (<ref>), we have that $(a,b)$ belongs to the domain of $e$. Combining $(a,b,c-1)$ is a bad-triplet with (<ref>), we have that $e(a,b) = c$. Since $b<c \leq n$, where the last inequality follows from (<ref>), we have that $(a,b) \in \mathcal{X}_2$. Hence,

\begin{align}
z(\vec{p}^{2,a,b}) = \sum_{i=1}^a \frac{E_i}{2} + E_b\theta + \sum_{i=b+1}^{c-1}E_i+E_c(\delta-E_bS_{a+1,b-1}).
\end{align}

Substituting for $z(\vec{p}^{2,a,b}) \leq z(\vec{p}^{1,a,c})$ and simplifying yields,

\begin{align}
(E_cS_{a+1,b} - \theta)(E_bS_{a+1,b}-\delta) > 0
\end{align}

Combining with (<ref>), we have the desired result.

2) We consider four cases. The cases make sense since $a \leq r-1$, $b \leq c$ from (<ref>).

Case 1  $a = r-1$: Notice that from (<ref>), in this case we should have $c-b \in \{0,1\}$. Also, since $z(\vec{p}^0) \leq z(\vec{p}^{1,a,c})$, we have,

\begin{align}
\frac{E_r}{2} &\leq \frac{\theta \delta}{S_{r,b}} + \sum_{i=b+1}^cE_i  =  \frac{\theta (1+b-c)}{S_{r,b}}  + \sum_{i=b+1}^cE_i \leq \frac{\theta}{S_{r,b}}+ (c-b)\left(E_{b+1} - \frac{\theta}{S_{r,b}}\right)
\end{align}

Now, notice that if $c - b = 0$, we have the desired result. If $c-b = 1$, we have,

\begin{align}\label{eqn:er2_ebp1}
\frac{E_r}{2} \leq E_{b+1}.
\end{align}

\begin{align}
\frac{E_r}{2}S_{r,b} = \frac{1}{2}+ \frac{E_r}{2}\sum_{i=r+1}^b\frac{1}{E_i} \leq_{(a)} \frac{1}{2}+ \frac{E_r}{2}\left(\frac{b-r}{E_{b+1}}\right) \leq_{(b)}\frac{1}{2}+b-r = \theta.
\end{align}

where (a) follows since, $E_i \geq E_{b+1}$ for $i \in [r+1:b]$, and (b) follows from (<ref>).

Case 2 $a < r-1$ and $b=c$:

Case 3  $a<r-1$, $c>b$, $(a+1,b+1,c)$ is a bad-triplet: We handle the above two cases together. In both the above cases, due to $a < r-1$, and (<ref>), we have that $(a+1,c)$ belongs to the domain of $h$. We prove that in both of the above cases, $(a+1,c) \in \mathcal{X}_1$ and $\min\{h(a+1,c),c\} = b$. First, notice that from (<ref>), $a<r-1$, and Lemma <ref>-1-c, we have that $(a+1,b,c)$ is a good-triplet.

* If $b=c$, since $(a+1,b,c)$ is a good-triplet, we have $h(a+1,c) \geq b = c>r$, where last inequality follows from (<ref>). Hence, $(a+1,c) \in \mathcal{X}_1$, and $\min\{h(a+1,c) ,c\} = c = b$.

* If $c>b$ and $(a+1,b+1,c)$ is a bad-triplet, we have that $h(a+1,c) = b > r$, where the last inequality follows from (<ref>). Hence $(a+1,c) \in \mathcal{X}_1$, and $\min\{h(a+1,c),c\} = b$.

\begin{align}
z(\vec{p}^{1,a+1,c}) = \sum_{i=1}^{a+1} \frac{E_i}{2} + \frac{\left(\theta-\frac{1}{2}\right) (\delta-1)}{S_{a+2,b}} + \sum_{i=b+1}^{c}E_i.
\end{align}

Substituting and simplifying $z(\vec{p}^{1,a+1,c}) \leq z(\vec{p}^{1,a,c})$ we get,

\begin{align}
\left(\frac{E_{a+1}}{2}S_{a+1,b} - \theta \right)\left(E_{a+1}S_{a+1,b} - \delta\right) < 0
\end{align}

Notice that $E_{a+1}S_{a+1,b} \geq E_bS_{a+1,b} > \delta$, where last inequality follows from (<ref>).

Case 4:  $a<r-1$, $b<c$, and $(a+1,b+1,c)$ is a good-triplet: Since $c>b$, we have that from (<ref>) that $(a,b+1,c)$ is a bad-triplet. Due to $b+1\leq c$, and (<ref>), we have that $(b+1,c)$ belongs to the domain of $g$. Combining the above with the case description, we have $g(b+1,c) = a+1$. Since $b+1 \leq c$ and $a+1 <r$, we have that $(b+1,c) \in \mathcal{X}_3$. Hence,

\begin{align}
z(\vec{p}^{3,b+1,c}) = \sum_{i=1}^{a} \frac{E_i}{2} + \frac{E_{a+1}}{2}\left(\delta - E_{b+1}S_{a+2,b} \right)+ E_{b+1}\left(\theta +\frac{1}{2}\right) + \sum_{i=b+2}^{c}E_i.
\end{align}

Substituting and simplifying $z(\vec{p}^{3,b+1,c}) \leq z(\vec{p}^{1,a,c})$ we get,

\begin{align}
\left(\frac{E_{a+1}}{2}S_{a+1,b} - \theta \right)\left(E_{b+1}S_{a+1,b} - \delta\right) > 0
\end{align}

Combining with (<ref>), we are done.

3) We consider two cases. The cases make sense since $a-1\geq 0$ from the statement description.

Case 1 $(a-1,b,c)$ is a good-triplet: Notice that since $a>0$ from the statement and (<ref>), we have that $(a-1,c)$ belongs to the domain of $h$. Since, $(a-1,b,c)$ is a good-triplet, we have that $h(a-1,c) \geq b>r$, where the last inequality follows from (<ref>). Hence, $(a-1,c) \in \mathcal{X}_1$.

If $b = c$, we have that $\min\{h(a-1,c),c\} = c = b$. If $c>b$, we have from (<ref>) that $(a,b+1,c)$ is a bad-triplet, which when combined with $a>0$ and Lemma <ref>-2-c, gives $(a-1,b+1,c)$ is a bad-triplet. Combining with the case description, we have that $h(a-1,c) = b$. Hence, $\min\{h(a-1,c),c\} = b$. Hence in either case we have that, $(a-1,c) \in \mathcal{X}_1$ and $\min\{h(a-1,c),c\} = b$. Hence,

\begin{align}
z(\vec{p}^{1,a-1,c}) = \sum_{i=1}^{a-1} \frac{E_i}{2} + \frac{\left(\theta+\frac{1}{2}\right) (\delta+1)}{S_{a,b}} + \sum_{i=b+1}^{c}E_i.
\end{align}

Substituting and simplifying $z(\vec{p}^{1,a-1,c}) \leq z(\vec{p}^{1,a,c})$ we get,

\begin{align}
\left(\frac{E_a}{2}S_{a+1,b} - \theta \right)\left(E_aS_{a+1,b} - \delta\right) \geq 0
\end{align}

Combining (<ref>), and $E_a \geq E_b$, we have $E_aS_{a+1,b} \geq E_bS_{a+1,b} > \delta$ which gives the result.

Case 2 $(a-1,b,c)$ is a bad-triplet: Notice that from (<ref>), we have that $(b,c)$ belongs to the domain of $g$. Combining the case description with (<ref>), we have $g(b,c) = a$. Combining (<ref>), and $0 < a$, we have that $(b,c) \in \mathcal{X}_3$. Hence,

\begin{align}
z(\vec{p}^{3,b,c}) = \sum_{i=1}^{a-1} \frac{E_i}{2} + \frac{E_a}{2}\left(\delta-E_bS_{a+1,b-1}\right) + E_b\theta + \sum_{i=b+1}^{c}E_i
\end{align}

Using $z(\vec{p}^{3,b,c}) \leq z(\vec{p}^{1,a,c})$, yields the inequality,

\begin{align}
\left(\frac{E_a}{2}S_{a+1,b} - \theta \right)\left(E_bS_{a+1,b} - \delta\right) > 0
\end{align}

Using (<ref>), we have the desired result.

4) We consider the following two cases. The cases make sense since $b+1 \leq c+1 \leq n$, where the first inequality follows from (<ref>), and the second follows from the statement description.

Case 1 $(a,b+1,c+1)$ is a bad-triplet: Combining $c<n$ from the statement description with (<ref>), we have that $(a,c+1)$ belongs to the domain of $h$. Notice that from (<ref>), and Lemma <ref>-1-b, we have that $(a,b,c+1)$ is a good-triplet. Hence, we have $h(a,c+1) = b>r$, where the last inequality follows from (<ref>). Hence, $(a,c+1) \in \mathcal{X}_1$, and $\min\{h(a,c+1),c+1\} = b$. Hence,

\begin{align}
z(\vec{p}^{1,a,c+1}) = \sum_{i=1}^{a} \frac{E_i}{2} + \frac{\theta (\delta-1)}{S_{a+1,b}} + \sum_{i=b+1}^{c+1}E_i.
\end{align}

Substituting and simplifying $z(\vec{p}^{1,a,c+1}) \leq z(\vec{p}^{1,a,c})$ we get the desired result.

Case 2 $b = c$,  $(a,b+1,c+1)$ is a good-triplet: Combining $c<n$ from the statement description with (<ref>), we have that $(a,c+1)$ belongs to the domain of $h$. Since, $(a,b+1,c+1)$ is a good-triplet, we should have $h(a,c+1) \geq b+1=c+1>r$, where the last inequality follows from (<ref>). Hence, $(a,c+1) \in \mathcal{X}_1$, and $\min\{h(a,c+1),c+1\} = c+1$. Hence,

\begin{align}
z(\vec{p}^{1,a,c+1}) = \sum_{i=1}^{a} \frac{E_i}{2} + \frac{(\theta+1) \delta}{S_{a+1,c+1}}.
\end{align}

Substituting and simplifying $z(\vec{p}^{1,a,c+1}) \leq z(\vec{p}^{1,a,c})$ we get the desired result.

Case 3 $b< c$, $(a,b+1,c+1)$ is a good-triplet: Since $b<c$, from (<ref>), we have that $(a,b+1,c)$ is a bad-triplet. From (<ref>), we have $b+1 \leq c \leq n$ and $a \geq 0$, which implies that $(a,b+1)$ belongs to the domain of $e$. Combining with $(a,b+1,c+1)$ is a good-triplet, we should have $e(a,b+1) = c+1$. Since $n \geq c+1 > b+1$ where the first inequality follows from (<ref>), we have that $(a,b+1) \in \mathcal{X}_2$. Hence,

\begin{align}
z(\vec{p}^{2,a,b+1}) = \sum_{i=1}^{a} \frac{E_i}{2} + E_{c+1}\left(\delta-E_{b+1}S_{a+1,b}\right) + \theta E_{b+1} + \sum_{i=b+1}^{c}E_i
\end{align}

Using $z(\vec{p}^{2,a,b+1}) \leq z(\vec{p}^{1,a,c})$, yields the inequality,

\begin{align}
\left(E_{c+1}S_{a+1,b} - \theta \right)\left(E_{b+1}S_{a+1,b} - \delta\right) > 0
\end{align}

Combining with (<ref>), we have the desired result.

Now, we construct a Lagrange multiplier that satisfies the conditions of Lemma <ref>. Consider $\vec{\mu} \in \mathbb{R}^n$, given by,

\begin{align}
\mu_k = \begin{cases}
\frac{C}{E_k} - \frac{1}{2} & \text{ if } a+1 \leq k \leq r\\
1-\frac{C}{E_k} & \text{ if } r+1 \leq k \leq b\\
0 & \text{ otherwise }
\end{cases},
\end{align}

\begin{align}
C = \frac{\theta}{S_{a+1,b}}.
\end{align}

The above $\vec{\mu}$ satisfies $\vec{\mu} \geq 0$. If $k \in [a+1,r]$, we have that,

\begin{align}
\mu_k =  \frac{C}{E_k} - \frac{1}{2} \geq \frac{C}{E_a} - \frac{1}{2} \geq 0,
\end{align}

where the last inequality follows due to Lemma <ref>-2.  If $k \in [r+1,b]$, we have that,

\begin{align}
\mu_k = 1- \frac{C}{E_k} \geq 1-\frac{C}{E_c} \geq 0,
\end{align}

where the last inequality follows due to Lemma <ref>-1.

Using the above $\mu$ as a Lagrange multiplier for problem (P-1,2,..,r), we have the problem,

p⃗,γ∑_j =1^a p_jE_j/2 + ∑_j =a+1^b C p_j +∑_j =b+1^n E_j
p⃗∈ℐ, λ∈ℝ

Notice that due to Lemma <ref>, we have that, $E_j/2 \geq C$ for $j \in [1:a]$, $E_j\geq C$, for $j \in [b+1:c]$, and $E_j\leq C$ for $j \in [c+1,n]$. Hence, an optimal solution $\vec{p}$ for the above problem is $\vec{p} = \vec{p}^{1,a,c}$ with arbitrary $\gamma$. Let, $\gamma = \frac{\delta}{S_{a+1,b}}$. Notice that from Lemma <ref>, part-2-a, we have that $(\vec{p}^{1,a,c}, \gamma)$ is feasible for  (P-1,2,..,r). Also, notice that from the definition of $\vec{\mu}$, we have $\mu_k > 0$ implies  $p^{1,a,c}_kE_k = \gamma$. Hence, from Lemma <ref>, we have that $(\vec{p}^{1,a,c}, \gamma)$ solves (P-1,2,..,r), as desired.

Case 2: Best vector in $\mathcal{A}$ comes from $\mathcal{A}_2$

Let $\vec{p}^{2,a,b}$ denote the best vector where $(a,b) \in \mathcal{X}_2$ and let $c = e(a,b)$. Define

\begin{align}\label{eqn:gamma_def_1}
\theta = \frac{r-a}{2}+b-r
\end{align}

and $\delta = r-a+b-c$. We have the following claim.

Claim:  We should have $a < r-1$.

Assume the contrary. Hence, from (<ref>) we have $a = r-1$. Hence, we have $p^{2,a,b}_k = 1$ for all $1 \leq k \leq r-1$. Additionally from (<ref>), notice that $b\geq r+1$. Also from the definition of $\vec{p}^{2,a,b}$, we have $p^{2,a,b}_{b} = 1$, and  $p^{2,a,b}_{r} = E_{r+1}/E_r > 0$, which implies that, $\sum_{k=1}^{n}p^{2,a,b}_k > r$. This is a contradiction.

Combining the claim, and (<ref>), we should have in this case, that

\begin{align}\label{eqn:ap1cm1}
(a+1,b,c-1) \in [0:r-1] \times [r+1:n]\times [r+1:n]
\end{align}

Now we prove the following lemma.

We have that,

* $\frac{E_c}{E_{a+1}} \geq \frac{1}{2}$

* If $a>0$, then $\frac{E_c}{E_a} \leq \frac{1}{2}$

* $E_{c}S_{a+1,b-1} +1\geq \theta$

* $E_b\left(\theta - E_cS_{a+1,b-1}\right) \geq E_c$,

where $\theta$ is defined in (<ref>).

1) We complete the proof using two cases. Notice that the following two cases make sense due to (<ref>).

Case 1 $(a+1,b,c-1)$ is a bad-triplet: From (<ref>), we have $(a+1,b)$ belongs to the domain of $e$. Combining (<ref>) and $a+1 \leq r-1$ with Lemma <ref>-1-c, we have that $(a+1,b,c)$ is a good-triplet. Hence, $e(a+1,b) = c$. Since, $b< c \leq n$ from (<ref>), we have that, $(a+1,b) \in \mathcal{X}_2$. Hence,

\begin{align}
z(\vec{p}^{2,a+1,b}) = \sum_{i=1}^{a+1} \frac{E_i}{2} +E_b \left(\theta-\frac{1}{2}\right)+\sum_{i=b+1}^{c}E_i + E_c\left(\delta-1 - E_bS_{a+2,b}\right).
\end{align}

Using $z(\vec{p}^{2,a,b}) \geq z(\vec{p}^{2,a+1,b})$, yields the inequality,

\begin{align}
(2E_c-E_{a+1})(E_{a+1}-E_b) \geq  0,
\end{align}

which yields the result since $E_{a+1} > E_b$ (the inequality is strict due to assumption A1).

Case 2 $(a+1,b,c-1)$ is a good-triplet: Notice that due to (<ref>), we have that $(b,c-1)$ belongs to the domain of $g$. Combining (<ref>) with the case description, we have that $g(b,c-1)=a+1$. Combining the claim, (<ref>), and $a+1>0$, we have that $(b,c-1) \in \mathcal{X}_3$. Hence,

\begin{align}
z(\vec{p}^{3,b,c-1}) = \sum_{i=1}^{a} \frac{E_i}{2} +E_b\left(\theta-\frac{1}{2}\right)+\sum_{i=b+1}^{c-1}E_i + \frac{E_{a+1}}{2}\left(\delta - E_bS_{a+2,b-1}\right).
\end{align}

Using $z(\vec{p}^{2,a,b}) \geq z(\vec{p}^{3,b,c+1})$, yields the inequality,

\begin{align}
\left(E_c - \frac{E_{a+1}}{2}\right)\left(\delta+1-E_bS_{a+1,b}\right) > 0,
\end{align}

which establishes the result combined with (<ref>).

2) We consider two cases. The two cases make sense since $a>0$ by the statement description.

Case 1 $(a-1,b,c)$ is a good-triplet:  Combining $a>0$ from the statement description and (<ref>), we have that, $(a-1,b)$ belongs to the domain of $e$. Combining $a>0$, (<ref>), and Lemma <ref>-2-c, $(a-1,b,c-1)$ is a bad-triplet. Combining the above with the case description, we have that $e(a-1,b) = c$. Since $b< c \leq n$ from (<ref>), we have that $(a-1,b) \in \mathcal{X}_2$. Hence,

\begin{align}