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 √ T + 4n 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 June 2023 DRAFT 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 June 2023 DRAFT 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 O( T log(T )) worst-case regret. This problem shares certain similarities June 2023 DRAFT 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 zerosum 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.

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 [26],

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].

June 2023 DRAFT

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 N = {1, 2, 3, . . . } to denote the set of positive integers and N 0 = {0, 1, 2, . . . } to denote the set of non-negative integers.

In this section, we formulate the model for the one-slot setting. We extend this model to the online setting in Section IV. Let

the action of player A 1 , where α j = 1 if player 1 chooses resource j and α j = 0 otherwise.

Notice that the actions of the other players will also have the same structure. Notice that, α ∈ J 1 , where,

for q ∈ {1, 2, . . . }.

Now fix 1 ≤ q as a positive integer and imagine q players each choosing vectors (actions) in

For each i ∈ {1, 2, . . . , q}, let α i ∈ J 1 denote the vector (action) chosen by the i-th player.

Consider the following set,

Then we have the following lemma.

Lemma 1: We have that, 1) A q = J q for q ∈ {1, 2, . . . , }, where A q and J q are defined in ( 2) and (1), respectively.

2) Conv(J 1 ) = I, where I is the (n, r)-hypersimplex,

.

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

Claim 1 A q ⊆ J q : This follows directly from the fact that α i ∈ J 1 for all i ∈ {1, 2, . . . , q} and the definition of sets A q and J q .

June 2023 DRAFT Claim 2 J q ⊆ A q : We use induction. The case q = 1 trivially follows from the fact that α 1 ∈ J 1 .

Assume that the statement is true for q ≥ 1. We establish the statement is true for q + 1.

Pick any x ∈ J q+1 . Hence, x i ∈ {0, 1, . . . , q + 1} for each 1 ≤ i ≤ q + 1, and q+1 i=1 x i = r(q + 1). Hence, it should be clear that x has at least r non-zero entries. Define α q+1 ∈ J 1 with exactly r ones in locations i with the highest x i . Hence, x -α q+1 is a non-negative vector. Now, we claim that x -α q+1 ∈ J q . Since x ∈ J q+1 and α q+1 ∈ J 1 , it can be easily seen that n i=1 (x i -α q+1 i ) = rq. Hence, we are only required to prove that the largest element of the vector x -α q+1 is at most q. Assume the contrary and let k be the index of the largest element, so x k -α q+1 k ≥ q + 1. Since, x ∈ J q+1 , we know x k ≤ q + 1. This means α q+1 k = 0, and x k = q + 1. Since α q+1 was constructed by selecting the largest elements of x, and an element with size q + 1 was not selected, we must have for all indices i that α

which is a contradiction. Hence, we have that x -α q+1 ∈ J q as desired. Hence, from the induction hypothesis x -α q+1 ∈ A q . Hence, there exists a set of actions α 1 , α 2 , . . . , α q ∈ J 1 such that, q i=1 α i = x -α q+1 , which implies that q+1 i=1 α i = x. Hence, x ∈ A q+1 as desired. 2) See Appendix B. Now, let α i ∈ J 1 denote the action of player A i for i ∈ {2, 3, . . . , m}. Let us define the vector

We assume that the triplet (α, X, W ) are mutually independent. Nevertheless, our formulation allows the random variables W 1 , W 2 , . . . , W n to be correlated, and the players [2 : m] to cooperate in order to make their decision. Notice that from Lemma 1-1, we have that X ∈ J m-1 .

Given the player A 1 uses possibly randomized action α ∈ J 1 and X is defined according to (5), the expected utility of player A 1 can be written as

June 2023 DRAFT where

for 1 ≤ k ≤ n, and the expectation is taken with respect to the possibly randomized action α k . The equality (a) follows since (α, X, W ) are mutually independent. Hence, notice that the expected utility depends on the action of player A 1 only through p defined in (7). Let us define the function, f : R n × Z n → R as,

Hence, we have that the expected utility of player A 1 is equal to E{f (p, X)}, where p is defined in (7) and X is defined in (5).

Notice that the set of all possible vectors p in ( 7) is Conv(J 1 ), which is equal to I defined in (3) by Lemma 1-2. Given p ∈ I, in Appendix A, we provide an algorithm to sample a set α

In particular, the algorithm finds a distribution over the elements of J 1 defined in (1) for a given p.

The answer in [44] establishes that the found mixture of elements of J 1 contains at most n + 1 elements.

This section focuses on finding the worst-case expected utility of player A 1 for fixed p ∈ I, used by player A 1 . Notice that to obtain the worst-case expected utility of player A 1 , we have to minimize E{f (p, X)} over all possibly randomized actions of players A 2 , . . . , A m . Define the function,

where function f is defined in (8).

Lemma 2: For p ∈ I, the worst-case expected utility of player A 1 is f worst (p).

Consider a possibly randomized set of actions for players A 2 , . . . , A m , and define X according to (5). Recall that the expected utility of player A 1 is E{f (p, X)}. Notice that for any x ∈ J m-1 , we have that f (p, x * ) ≤ f (p, x). Hence, we have that f (p, x * ) ≤ f (p, X). Taking the expectations, June 2023 DRAFT

we have that, f (p, x * ) ≤ E{f (p, X)}. Hence, the expected utility of player A 1 is bounded below by f (p, x * ). Now consider the deterministic policy for players A 2 , . . . , A m that yields X = x * .

Notice that such a policy exists from Lemma 1-1. This policy will yield an expected utility of

) is in fact the worst-case expected utility.

It should be noted that for a given p ∈ I, finding f worst (p) in ( 9) and

is an optimization over a non-convex discrete set x ∈ 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 O(n + mr log(n)) greedy incremental algorithm or an improved O(n log(mr)) algorithm [45]. For completeness, we summarize an O(nmr) algorithm in Algorithm 1. For improved algorithms, refer to [45]. It should be noted that f worst (p) for p ∈ I has an explicit formula in certain special cases. Such cases will be discussed in Section V.

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

For this setting, we assume that none of the players observe W , but all the players know E. Notice that the worst-case expected utility maximization problem can be represented as the max-min problem, (P1): max

June 2023 DRAFT Algorithm 2: Algorithm to solve (P1) Obtain p t+1 by using,

where the function Π I is the projection onto I, function f is defined in (8) (For a given vector y ∈ R, we provide an algorithm to calculate Π I (y) in Appendix F).

where the function f is defined in (8), the sets I and J m-1 are defined in (3) and ( 1) respectively.

Notice that the inner minimization of the above problem amounts to evaluating the function f worst defined in (9), which admits an exact solution for each p ∈ I. Hence, the problem can also be rephrased using the following maximization.

(P2): max p f worst (p)

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

Since the inner minimization of (P1) can be solved using Algorithm 1, 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 2) along with a focused convergence analysis tailored for this problem (Theorem 1) for clarity and completeness.

Theorem 1: The output p, x of Algorithm 2 satisfies,

, where f maximin is the optimal value of (P1), T is the number of iterations of Algorithm 2 and β is the step-size used in (13). Hence, for fixed ε > 0, choosing β = ε, and T ≥ 1/ε 2 , the maximum error is O(ε).

Proof: Part 1 follows since, (p, x) = (p t , x t ) for some t ∈ [1 : T ], and the definition of x t .

For part 2, define

for all i ∈ [1 : T ]. Recall that (p * , x * ) is the optimal solution to (P1). Notice that,

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 (•, x i ). Notice that f maximin = f (p * , x * ). Now we sum the above inequality for i ∈ [1 : T ], which results,

where (a) follows since

and the last inequality follows due f (p * , x * ) ≤ f (p * , x) for any x ∈ J m-1 , and the definition of (p, x) in the last line of Algorithm 2. Hence, we have that,

as desired.

June 2023 DRAFT

This section assumes that the player A 1 does not know the mean vector 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 II.

In particular, let W [t], α[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,

where α k [t] ∈ J 1 is the action of player k ∈ {2, 3, . . . , m} during time-slot t. The history

up to time t can be defined by

We assume that conditioned on the history H[t] of A 1 , the action of player A 1 and the actions of the other players are independent. Let p[t] ∈ I be defined such that,

The expected utility of player A 1 can be written as

where the function f is defined in (8) the function f worst is defined in (9), 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,

where f maximin is the optimal value of (P1).

We assume that

Also, define,

where x ∨ y = min(x, y), and,

We assume that T is large enough such that that log((T (T + 1))/δ) ≥ C. The choice of T will ensure that if n k [t] = 0, we have that,

and

Also, define the functions

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

Lemma 3: Given a sequence {X t } ∞ t=1 of independent 1-sub Gaussian random variables, a positive integer-valued random variable G and δ ∈ (0, 1), we have the following, 1) For all g ∈ N, we have that,

2) If G is independent of {X t } ∞ t=1 , we have,

3) For general random variables G (Possibly dependent on the sequence {X t } ∞ t=1 ), we have,

Proof: Refer to [6].

Let us denote by Wk [t] the reward obtained when the resource k is chosen for the t-th time by

where Wk [t] is set to E k if the resource k is chosen less than t times in

Hence, notice that

Now, applying Lemma 3-3 to the sequence

and

where, we have also used the inequality n k [t] ≤ T . Now, we use the law of total probability on (34) to obtain,

where (a) follows since we have from (26) that

Similar, treatment to (33) yields,

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

and

hold for all t ∈ [1 : T ] and k ∈ [1 : n]. Combining, (35) and (37) with the union bound, we have that

Now we summarize our approach in Algorithm 3, after which Theorem 2 establishes the sublinear worst-case regret bound of the algorithm. For the UCB algorithm, we require two parameters: the learning rate β > 0 and δ ∈ (0, 1). Choose action α[t] for the t-th time-slot by sampling from p[t] using the approach in Appendix A (Algorithm 4) and receive feedback

where Π I (y) denotes the projection of y onto I, function f t is defined in (28), and β is the step size.

yields the worst-case regret bound,

Proof: Notice that since T is fixed large enough such that 1/(2nrCT 2 ) < 1, and δ = 1/(2nrCT 2 ), we have that δ ∈ (0, 1). Moreover, due to the choice of T and δ, we have,

δ , which will ensure ( 26) and (27). We first focus on the good event A. Notice that in this case,

for all k, t ∈ [1 : n] × [1 : T ], where (a) follows since E k < C. Let (p * , x * ) be the optimal solution to (P1). Define

for t ∈ [1 : T ], where f t is defined in (28).

Notice that,

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

First, notice that,

where the first inequality follows due (38), and the second inequality follows from the definition of x * . Also, we have that,

which follows from the definition of x[t] in line 4 of Algorithm 3. Now we sum the (46) for t ∈ [1 : T ], which results (consider event A),

where (a) follows since p [1], p * ∈ I, and

due to ( 44), (b) follows from ( 48) and (49), and (c) follows from (39) and the definition of f t in (28). Hence, we have that,

Now we take the expectation (Conditioned on the event A) of both sides of (51), we have,

Hence,

where (a) follows combining (52), the fact that

and

Using β = 1/(T D 2 ), and δ = 1/(2rnCT 2 ), we have,

as desired.

Notice that since f worst is concave from the definition in (9), we also have that,

June 2023 DRAFT

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 ≤ k ≤ n since otherwise, we can transform the problem into a lower dimensional version. Without loss of generality, we also assume that

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.

Lemma 4: Consider the following constrained optimization problem,

where z i : R n → R for i ∈ {0, 1, 2, . . . , k}, and Y ⊂ R n . Consider the following unconstrained problem for some µ ≥ 0.

Let x * be a solution to the unconstrained problem. Assume x * satisfies for all i ∈ {1, 2, . . . , k},

Then x * is optimal for the constrained problem.

We first focus on finding f worst (p) explicitly for p ∈ I. Then, we use the solution to solve (P2). Recall from the definition (8), f (p, x) = n k=1 p k E k /(1 + x k ), for p ∈ I, and x ∈ J 2 , where J q and I in (1), and (3), respectively.

Proof: Since from the definition of x * , we have that x * ∈ J 2 , we should have n k=1 x * 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 a p a ≥ E k p k for all k ∈ [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 (p, x).

Under case 1: (assignment (60))

Under case 2: (assignment (61))

Comparing the two cases yields the result. Now we can formulate the worst-case expected utility f worst (p) of player A 1 . Lemma 5 allows us to formulate this as,

where Γ 1 , Γ 2 are the largest and the second largest elements of the set

respectively.

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

(P2-(i, j)) : max

where i, j ∈ [1 : n] and i = j. To solve (P2-i), and (P2-(i, j)), 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.

and

where for (P2-1), F ∈ R n is assumed to a positive vector such that

and for (P2-2), F ∈ R n is assumed to a positive vector such that

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

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

1) Solving (P2-1): Consider the problem (P2-1).

(P2-1)

Also, consider the Lagrangian dual of the above problem (P2-1-µ) for µ ∈ R n-1 such that

Let us define u = arg max 1≤i≤n U i , where the sequence

arg max returns the least index in the case of ties. We establish that the solution to (P2-1) is p * , where,

with optimal objective value U u . It can be directly seen that p * defined by (73) satisfies the constraints of the problem (P2-1), specifically, p * ∈ I and p * 1 F 1 ≥ 3p k+1 F k+1 for k ∈ {2, . . . , n}. To prove that p * solves (P2-1), we construct a Lagrange multiplier vector µ ∈ R n-1 with µ i ≥ 0 for all i ∈ {1, . . . , n -1} such that p * solves the problem (P2-1-µ) and establish that (p * , µ) satisfy the conditions of the Lagrange multiplier lemma (Lemma 4), namely:

Define the vector µ ∈ R n-1 as,

Now, we prove the following lemma regarding µ.

Lemma 6: Consider the µ defined in (74). We have that,

2) We have,

Proof: Notice that since u = arg max 1≤i≤n U i , we have that,

We are required to prove,

for all k ∈ {2, 3, . . . , u-1}. It is enough to prove the above for

for k ≥ 2. Notice that from (75), we have that U u ≥ U u-1 . Substituting from (69) and simplifying, we have the result.

2) Substituting from the definition of µ k and simplifying yields the result.

3) If u = n, there is nothing to prove. Otherwise, it is enough to prove the result for k = u+1, since F k ≥ F k+1 for k ≥ 2. From (75), we have that U u ≥ U u+1 . Substituting from (69)

and simplifying, we have the result.

Notice that due to Lemma 6-1, we have that µ i ≥ 0 for all i ∈ {1, . . . , n -1}. Hence, consider the dual problem (P2-1-µ) with µ defined in (74). For this choice of µ k , after eliminating the µ k , which are zero, we have that the objective of the problem (P2-1-µ) is,

Now, due to Lemma 6-2, the above objective simplified to,

Also, notice that from Lemma 6-3, we have that C ≥ F k for all k ∈ {u + 1, . . . , n}. Hence, the optimal solution for (P2-1-µ) is any p ∈ I such that p k = 0 for all k ∈ {u + 1, . . . , n}. Hence, p * given in (73) is a solution to (P2-1-µ). We establish that (p * , µ) also satisfy the conditions of Lemma 4. First, recall that p * satisfies the constraints of the problem (P2-1). Second, from (74) notice that µ k > 0 implies that k ∈ {1, . . . , u -1}. Also, from (73) notice that p * 1 F 1 = 3C/u, and p * k+1 F k+1 = C/u for all k ∈ {1, . . . , u -1}, where C is defined in (78). Hence, we have that

Similar to the solution of (P2-1), consider the Lagrangian dual (P2-2-µ) of the above problem for µ ∈ R n such that µ i ≥ 0 for all i ∈ {1, . . . , n} constructed according to Lemma 4,

We solve the problem by considering two cases. Similar to the solution of (P2-1), for each case we will provide a vector p * ∈ I and the Lagrange multiplier vector µ ∈ R n such that µ i ≥ 0 for all i ∈ {1, . . . , n}, p * is a solution to the problem (P2-2-µ), p * is feasible for the problem (P2-2) specifically,

. . , n} and (p * , µ) satisfy the conditions of the Lagrange multiplier lemma (Lemma 4), namely,

June 2023 DRAFT Let us define u = arg max 2≤i≤n U i , and v = arg max 2≤i≤n V i , where the sequences (U i ; 1 ≤ i ≤ n), and (V i ; 2 ≤ i ≤ n) are defined in (69), and (70), 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

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 p * where,

with optimal objective value V v . It can be easily checked by substitution from (81) that, p * ∈ I,

. . , v}, and p * k F k = 0 for all k ∈ {v + 1, . . . , n}. Hence, p * is feasible for (P2-2). Now, we focus on constructing the Lagrange multiplier vector µ. Define the vector µ ∈ R n as,

Now, we prove the following lemma regarding µ.

Lemma 7: Consider the µ defined in (82). We have that,

Proof: Notice that since u = arg max 2≤i≤n U i , and v = arg max 2≤i≤n V i , we have that

Since from the case description, we have that V v > U u , we should have that,

1) Notice that the result trivially follows for k ∈ {2, . . . , v} since µ k = 0 for such k. Hence, we will focus on k ∈ {2, . . . , v}. We first prove that µ 2 ≥ 0. Notice that from (83), we have that V v > U v . After substituting from (69) and (70) and simplifying, we have the June 2023 DRAFT desired result. To obtain the result for 3 ≤ k ≤ v, we can assume that v ≥ 3. Notice that we are required to prove,

It is enough to prove the above for k = v, since F k ≥ F k+1 for k ≥ 3. From (83) we have that, V v ≥ V v-1 . Substituting from (70) and simplifying gives the result.

2) Substituting from the definition of µ k simplifying will yield the result.

3) If v = n, there is nothing to prove. Otherwise, it is enough to prove the result for k = v+1,

and simplifying gives the result.

Notice that due to Lemma 7-1, we have that µ i ≥ 0 for all i ∈ {1, . . . , n}. Hence, similar to the solution to (P2-1), consider the dual problem (P2-2-µ) with µ defined in (82). After eliminating the µ k , which are zero, we have that the objective of the problem (P2-2-µ) is,

Due to Lemma 7-2, the above objective simplified to,

From Lemma 7-3, we have that C ≥ F k for all k ∈ {v + 1, . . . , n}. Hence, similar to the solution to (P2-1), the optimal solution for (P2-2-µ) is any p ∈ I such that p k = 0 for all k ∈ {v + 1, . . . , n}. Hence, p * given in (81) is a solution to (P2-2-µ). Recall that p * is feasible for (P2-2). Hence, we are only required to establish that (p * , µ) satisfies the conditions of Lemma 4. From (82) notice that µ k > 0 implies that k ∈ {2, . . . , v}. From (81) notice that

for all k ∈ {1, . . . , v}. Hence, µ k > 0 implies the corresponding constraint is met with equality. Hence from Lemma 4, p * is the solution to (P2-2).

Case 2 U u ≥ V v : The solution to (P2-2) in this case is p * where,

with optimal objective value U u . First notice that p * is feasible for (P2-2), since from (87) we have p * ∈ I, p * 1 F 1 = 3p * k F k for all k ∈ {2, . . . , u}, and p * k F k = 0 for all k ∈ {u + 1, . . . , n}. Similar to case 1, we construct the Lagrange multiplier vector µ. Consider the vector µ ∈ R n given by,

We have the following lemma.

Lemma 8: For the µ defined in (88), we have that,

2) We have,

3)

Proof: Notice that since u = arg max 2≤i≤n U i , and v = arg max 2≤i≤n V i , we have that U u ≥ U j for all j ∈ [2 : n], and V v ≥ V j for all j ∈ [2 : n]. Since from the case description, we have that U u ≥ V v , we should have that,

1) Notice that this condition is trivially satisfied for k ∈ {2} ∪{u + 1, . . . , n} since µ k = 0 for such k. Hence, we focus on k ∈ {2} ∪ {u + 1, . . . , n}. First, we prove that µ 1 ≥ 0. Notice that from (90), we have that U u ≥ V u . Substituting from (69) and (70) and simplifying, we have the desired result. To obtain the result for 3 ≤ k ≤ u, notice that we can assume u ≥ 3. Notice that from (90), we have that U u ≥ U u-1 . Substituting from (69) and simplifying, we have the desired result.

2) Substituting from the definition of µ k simplifying will yield the result.

3) If u = n, there is nothing to prove. Otherwise, it is enough to prove the result for k = u+1, since F k ≥ F k+1 for k ≥ 3. From (90) we have that, U u ≥ U u+1 . Substituting from (69) and simplifying gives the result.

The analysis is very similar to case 1. Notice that due to Lemma 8-1, we have that µ i ≥ 0 for all i ∈ {1, . . . , n}. Similar to case 1, consider the dual problem (P2-2-µ) with µ defined in (88).

After eliminating the µ k , which are zero, we have that the objective of the problem (P2-2-µ) is,

Due to Lemma 8-2, the above objective simplified to,

From Lemma 8-3, we have that C ≥ F k for all k ∈ {u + 1, . . . , n}. Hence, similar to case 1, the optimal solution for (P2-2-µ) is any p ∈ I such that p k = 0 for all k ∈ {u + 1, . . . , n}. In particular, p * given in (87) is a solution to (P2-2-µ). Recall that p * is feasible for (P2-2). Now, we establish that (p * , µ) also satisfy the conditions of Lemma 4. From (88) notice that µ k > 0

2 for all k ∈ {3, . . . , v}. Hence, µ k > 0 implies the corresponding constraint is met with equality. Hence from Lemma 4, p * is the solution to (P2-2).

3) 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 (P2-i), and (P2-(i, j)) for i, j ∈ [1 : n] such that i = 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 (P2-1), and (P2-(1, 2)). To prove this, Consider arbitrary (i, j) such that 1 ≤ i, j ≤ n such that i = j. Define, D ∈ R n to be the vector obtained by permuting the entries of E such that

Notice that due to the solution of (P2-2), the optimal value of ( P2-(i, j)) is given by,

Notice that,

where the inequality follows since a k=1 1

But notice that the June 2023 DRAFT left-hand side of (94) 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).

Theorem 3: Define the two sequences

and (70), respectively with F = E. Let u = arg max 1≤i≤n U i , and v = arg max 2≤i≤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 p * , where,

Case 2: If U u ≥ V v , the solution to (P2) is p * , where,

Proof: 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 V-A2, we have that the solution to

)) is (95), with an objective value equal to V v . Also, from the analysis in Section V-A1, we have that the solution to (P2-1) is (96), with an objective value equal to

we have the result.

Case 2: V v ≤ U u : In this case, from the analysis in Section V-A2, we have that the optimal objective value of (P2-(1, 2)) is max{V v , U u ′ }, where u ′ = arg max 2≤i≤n U i . But notice that since u = arg max 1≤i≤n U i , we have that U u ′ ≤ U u . Combining this with the case description, we have that max{V v , U u ′ } ≤ U u . Also, from the analysis in Section V-A1, we have that the solution to (P2-1) is (96), with an objective value equal to U u . Since V v ≤ U u , we have the result.

June 2023 DRAFT

It is interesting to notice the variation of choice probabilities in Fig. 1. 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.

The case r = 1 is solved in [13]. The solution is given by, p * where,

and,

See [13] for the proof.

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

where max (j) returns the j-th largest element in a set. Consider the following n 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 ∈ [1 : n] for each k ∈ [1 : r] and a k < a k+1 for k ∈ [1 : r -1], is given by, (P-a 1 , a 2 , .., a r ): max p, γ n j=1

Notice that the solution of (P2) is the solution of the problem out of the above n r problems with the maximum objective value. Hence, solving (P2) amounts to solving n r linear programs. In the below lemma, we prove that it is, in fact, enough to solve (P-1, 2, .., r) Lemma 9: The optimal objective value of (P-1, 2, .., r) is at least the optimal objective value of (P-a 1 , a 2 , .., a r ), where

Now, we focus on constructing the solution for the problem subjected to two assumptions. The following lemma introduces certain properties regarding triplets.

Lemma 10: Consider the following scenarios. Now, we construct the explicit solution using the functions defined above.

Theorem 4: Assume that we are given the two assumptions A1, and A2 are true. Define the three sets X 1 , X 2 , X 3 , as

and define the vectors p 1,a,c for (a, c) ∈ X 1 , p 2,a,b for (b, c) ∈ X 2 and p 3,b,c for (b, c) ∈ X 3 , where,

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

where c = e(a, b)

June 2023 DRAFT

3) for (b, c) ∈ X 3 ,

where a = g(b, c).

We have that, a) p 1,a,c for all (a, c) ∈ X 1 are all valid vectors belonging to I. where p 1,a,c , p 2,a,b and p 3,b,c are defined in (104), (105), and (106), respectively.

2) We have that, a) for (a, c) ∈ X 1 , (p 1,a,c , γ) is feasible for (P-1,2,..,r), where γ = δ S a+1,b , and b = min{h(a, c), c}.

b) for (a, b) ∈ X 2 , (p 2,a,b , γ) is feasible for (P-1,2,..,r), where γ = E b c) for (b, c) ∈ X 3 , (p 3,b,c , γ) is feasible for (P-1,2,..,r), where γ = E b d) the pair (p 0 , γ), where

and γ = E r+1 is feasible for (P-1,2,..,r).

3) The solution to (P-1, 2, .., r) is the one that produces the maximum objective value out of the elements in the following set

along with the γ values defined in part-2.

Proof: See Appendix E Fig. 2 denotes the optimal probabilities found for n, r = 10, 3, along with E given by,

In Fig. 2, 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 V-A. The intuition behind this is also very similar to the three-player singleton case.

For the simulations, consider the scenarios given below,

2) m = 2, r = 3, n = 4.

3

For all the simulations, we fix E i = 1 for i > 1 and plot different quantities as functions of E 1 . In both Figures 3 and4, 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 June 2023 DRAFT resources as a function of E 1 (Notice that there can be multiple solutions for optimal selection probabilities). Figure 3 shows the first three scenarios, whereas Figure 4 shows the last three scenarios.

Notice that similar to the observations in [13], in Figures 3 and4, 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 E described in Section V-A. 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 3 and4. 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.

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 O( 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. Bottom: One possible solution for the probabilities of choosing different resources when the worst-case approach is used vs.

June 2023 DRAFT APPENDIX A ALGORITHM FOR SAMPLING FROM I Algorithm 4: Algorithm to express p ∈ I as a convex combination of elements in J 1 .

1 Initialize an empty set Y 2 Initialize p 1 = p, t = 1 It can be easily seen that Conv(J 1 ) ⊆ I. To prove that I ⊆ Conv(J 1 ), we start by noticing that I is a compact convex set. We prove that the extreme points of the set I are contained in J 1 , which establishes the claim (See, for example, [47]). Hence, we prove that none of the elements of I \ J 1 is an extreme point of I. For this, take any p ∈ I \ J 1 . Notice that since p ∈ J 1 and p ∈ I, there exists k, j ∈ [1 : n] such that 0 < p j < p k < 1. Now take ε > 0 such that p j -ε > 0 and p k + ε < 1. Define the vector p such that,

Notice that I contains the entire line segment joining p and p. Hence, p is not an extreme point of I as desired.

Let A = (a 1 , a 2 , .., a r ) be a subset of 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 (P-A) has k bad-1 indices. Let (p, γ) be the optimal solution of (P-a 1 , a 2 , .., a r ). We consider two cases.

Case 1: There is no pair (a

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 ≥ E i (Since 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 (p, γ) will be feasible for (P-(A \ {i} ∪ {j})) as well. Moreover, (p, γ) will give the same objective value for (P-(A \ {i} ∪ {j})) as (P-A), and (P-(A \ {i} ∪ {j}))

will have k -1 bad-1 indices.

Case 2: There exists a pair (a

We begin with the following two lemmas.

Lemma 11: There exists t ∈ A, and s ∈ B such that E t p t = E s p s = γ.

Proof: We only prove the existence of t ∈ A such that E t p t = γ. The other part can be solved by repeating the same argument. Assume the contrary. Let γ * = (min{p j E j ; j ∈ A} + γ)/2.

We have that γ * > γ, and p j E j > γ * for all j ∈ 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

and

Hence, there exists δ > 0, small enough such that,

Hence ( p, γ * ), where p is given by,

is feasible for (P-a 1 , a 2 , .., a r ), and also achieves a higher optimal objective value since

This is a contradiction.

Lemma 12: For (P-a 1 , a 2 , .., a r ), there exists an optimal solution with at least one bad-1 element a such that, E a p a = γ, and at least one bad bad-2 element b such that E b p b = γ.

Proof: Notice that for all k ∈ A \ A bad , and j ∈ A bad , we have that

Notice that the entries of p can be rearranged without affecting the objective and feasibility for (P-a 1 , a 2 , .., a r ) such that the following two conditions are satisfied.

C1 For k ∈ A \ A bad , and j ∈ A bad , if we have

C2 For k ∈ B \ B bad , and j ∈ B bad if we have k = E j , then p j ≥ p k . Now we establish that any optimal 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.

June 2023 DRAFT Assume the contrary. Hence, all bad-1 elements j satisfy E j p j > γ. Consider t ∈ A such that E t p t = γ (Such a t always exists from Lemma 11). Notice that t cannot be bad-1. Hence E t ≥ 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 .

Proof: 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 ≥ p j for all bad-1 indices j. Hence, we should have

Consider the i described in the Claim. Since E t p t = γ < E i p i , and E t > E i , we have that,

Hence, it is possible to find δ > 0, small enough such that,

Since E t > E i it is easy to see that, ( p, γ) given by,

is a better solution to (P-a 1 , a 2 , .., a r ). This is a contradiction. 1) Recall that (a, b, c) being a good-triplet is equivalent to,

a) Notice that,

where (a) follows from (121), and the last inequality follows since

where (a) follows from (121) c) Notice that,

where (a) follows from (121) and the last inequality follows since S a+2,b ≥ S a+1,b-1 , which follows since E is non-increasing in it's components.

where (a) follows from (121).

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

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

Since (a, c) ∈ X 1 , we have that h(a, c) > r and c > r, which implies that,

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 ≤ h(a, c), combining with Lemma 10-1-a, we have that,

This means that,

Also, notice that if b < c, then we should have b = h(a, c) and b < n, which implies from the

Hence, if b < c we have that,

where the inequality is strict due to assumption A2. Since (a, c) ∈ X 1 , we have that a + 1 ≤ r < b ≤ c, which implies that (126) is a valid definition. Now we check the conditions for p 1,a,c ∈ I.

The sum constraint can be checked by direct substitution. The constraint, 0 ≤ p 1,a,c

Notice that this holds whenever b < c due to (131). If b = c, the above reduces to r -a > 0, which holds since a < r by the definition of X 1 . Hence, we have,

Now, to establish that p 1,a,c k ≤ 1, we have

where the last inequality follows due to (129).

where c = e(a, b). Now, we prove that p 1,a,b , is a valid vector in I. Since (a, b) ∈ X 2 , we have that,

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

and

This means that,

where the first inequality is strict due to assumption A2. Notice that, a + 1 ≤ r < b < c ≤ n.

Hence, p 2,a,b defined in (134) is a valid definition. Now we check the conditions for p 2,a,b ∈ I

The sum constraint can be checked using direct substitution. Since for k ∈ [a + 1, b] we have,

the constraint, 0 ≤ p 2,a,b k ≤ 1 follows trivially for k = c.

where last inequality follows from (138).

June 2023 DRAFT c) Recall that,

where a = g(b, c). Since (b, c) ∈ X 3 , we have that,

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

and

This means that,

where the first inequality is strict due to assumption A2.

Notice that the definition of p 3,b,c in (141) is a valid since 0 < a < r < b ≤ c ≤ n. Now we check the conditions for p 3,b,c ∈ I. The sum constraint can be checked using direct substitution.

Due to the same argument as case 2, in this case, the constraint,

where the last inequality follows from (145).

2)

we can assume that b < c, in which case we

For k = a, we have that,

where the last inequality follows due to (145).

d) This follows trivially, by substitution, due to the non-increasing property of E.

3) Define the three sets,

Let us denote by z(q) the objective value of (P-1, 2, .., r) for q ∈ I. We solve the problem under four cases. The four cases can be summarized as, C1 Best vector in A comes from A 1 C2 Best vector in A comes from A 2 C3 Best vector in A comes from A 3 C4 Best vector in A is p 0 , where p 0 is defined in (107).

In each of the above cases, we focus on constructing a Lagrange multiplier vector µ ∈ R n that will establish the best vector is optimal from Lagrange Multiplier Lemma (Lemma 4).

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

Lemma 13: We have that,

, where θ is defined in (149).

1) We prove this part in several cases. The cases make sense since c ≥ b ≥ r + 1 from (127), Case 1 c = r+1: Combining b ≤ c and (127), we should have b = r+1. We are required to prove that E r+1 S a+1,r+1 ≥ r-a 2 + 1. Notice that in this case, (129) simplifies to r -a < E r+1 S a+1,r+1 . Hence, we are done if r -a ≥ 2. Hence, the only case to check is a = r -1. In this case, the required statement simplifies to E r ≤ 2E r+1 , which follows from z(p 0 ) ≤ z(p 1,a,c ), where p 0 is defined in (107).

Substituting for z(p 2,a,c-1 ) ≤ z(p 1,a,c ), we get,

Since E c-1 S a+1,c ≥ E c S a+1,c > δ, where the last inequality follows from (129), we are done.

Substituting to z(p 1,a,c-1 ) ≤ z(p 1,a,c ) and simplifying, we get the desired result.

Substituting for z(p 2,a,b ) ≤ z(p 1,a,c ) and simplifying yields,

Combining with (129), we have the desired result.

2) We consider four cases. The cases make sense since a ≤ r -1, b ≤ c from (127).

Case 1 a = r -1: Notice that from (132), in this case we should have c -b ∈ {0, 1}. Also, since z(p 0 ) ≤ z(p 1,a,c ), we have,

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

Hence,

where (a) follows since, E i ≥ E b+1 for i ∈ [r + 1 : b], and (b) follows from (158).

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 (127), we have that (a+1, c) belongs to the domain of h. We prove that in both of the above cases, (a + 1, c) ∈ X 1 and min{h(a + 1, c), c} = b. First, notice that from (128), a < r -1, and Lemma 10-1-c, we have that (a + 1, b, c) is a good-triplet.

• Hence,

Substituting and simplifying z(p 1,a+1,c ) ≤ z(p 1,a,c ) we get,

Notice that E a+1 S a+1,b ≥ E b S a+1,b > δ, where last inequality follows from (129). Since b + 1 ≤ c and a + 1 < r, we have that (b + 1, c) ∈ X 3 . Hence,

Substituting and simplifying z(p 3,b+1,c ) ≤ z(p 1,a,c ) we get,

Combining with (131), we are done.

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

Substituting and simplifying z(p 1,a-1,c ) ≤ z(p 1,a,c ) we get, and 0 < a, we have that (b, c) ∈ X 3 . Hence, Hence,

Substituting and simplifying z(p 1,a,c+1 ) ≤ z(p 1,a,c ) we get the desired result.

Substituting and simplifying z(p 1,a,c+1 ) ≤ z(p 1,a,c ) we get the desired result.

Using z(p 2,a,b+1 ) ≤ z(p 1,a,c ), yields the inequality,

Combining with (131), we have the desired result. Now, we construct a Lagrange multiplier that satisfies the conditions of Lemma 4. Consider µ ∈ R n , given by,

where,

The above µ satisfies µ ≥ 0. If k ∈ [a + 1, r], we have that,

where the last inequality follows due to Lemma 13-2. If k ∈ [r + 1, b], we have that,

where the last inequality follows due to Lemma 13-1.

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

Notice that due to Lemma 13, we have that,

and

Hence, an optimal solution p for the above problem is p = p 1,a,c with arbitrary γ. Let, γ = δ S a+1,b . Notice that from Lemma 4, part-2-a, we have that (p 1,a,c , γ) is feasible for (P-1,2,..,r). Also, notice that from the definition of µ, we have µ k > 0 implies p 1,a,c k E k = γ. Hence, from Lemma 4, we have that (p 1,a,c , γ) solves (P-1,2,..,r), as desired. This is a contradiction.

Combining the claim, and (135), we should have in this case, that

Now we prove the following lemma.

Lemma 14: We have that,

where θ is defined in (177).

Proof:

1) We complete the proof using two cases. Notice that the following two cases make sense due to (178). Hence,

Using z(p 2,a,b ) ≥ z(p 2,a+1,b ), yields the inequality,

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 (178), we have that (b, c -1) belongs to the domain of g. Combining (137) with the case description, we have that g(b, c -1) = a + 1.

Combining the claim, (135), and a + 1 > 0, we have that (b, c -1) ∈ X 3 . Hence,

Using z(p 2,a,b ) ≥ z(p 3,b,c+1 ), yields the inequality,

which establishes the result combined with (138).

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

Using z(p 2,a,b ) ≥ z(p 2,a-1,b ), yields the inequality,

which establishes the result since E a > E b (the inequality is strict by assumption A1).

Case 2 (a -1, b, c) is a bad-triplet: From (178), we have that (b, c) belongs to the domain of g. Combining the case description with (136), we have that g(b, c) = a.Combining (135) and a > 0, we have that (b, c) ∈ X 3 . Hence,

Using z(p 2,a,b ) ≥ z(p 3,b,c ), yields the inequality,

which establishes the result from (138).

Using z(p 2,a,b ) ≥ z(p 2,a,b-1 ), yields the inequality,

yields the result since E b-1 > E b (the inequality is strict due to assumption A1).

Case

we have that (a, c -1) belongs to the domain of h. Combining (137), and the case description,

Using z(p 2,a,b ) ≥ z(p 1,a,c-1 ), yields the inequality,

which establishes the result due to (138).

4) Notice that the above reduces to,

We consider three cases. The cases make sense since (135) tells us b + 1 ≤ c and hence

Using z(p 2,a,b ) ≥ z(p 1,a,c ), yields the inequality,

which establishes the result due to (138).

Using z(p 2,a,b ) ≥ z(p 1,a,b+1 ), yields the inequality, Now, we construct a Lagrange multiplier, similar to case 1. Consider µ ∈ R n , given by,

The above µ satisfies µ ≥ 0. If k ∈ [a + 1, r], we have that,

where the last inequality follows due to Lemma 14-1. If k ∈ [r + 1, b -1], we have that,

If k = b, µ k ≥ 0, is Lemma 14-3.

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

which establishes the desired inequality from (145).

which establishes the result from (145).

3) Notice that the above reduces to,

We consider three cases

which establishes the desired inequality due to (145) Now, we construct a Lagrange multiplier, similar to case 1. Consider µ ∈ R n , given by,

The above µ satisfies µ ≥ 0. If k ∈ [a + 1, r], we have that,

If k ∈ [r + 1, b -1], we have that,

where the last inequality follows due to Lemma 15-4

If k = b, µ k ≥ 0, is Lemma 15-2.

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

Using z(p 0 ) > z(p 1,r-1,r+1 ), yields the desired inequality.

June 2023 DRAFT