Honor Among Bandits: No-Regret Learning for Online Fair Division
Authors: Ariel D. Procaccia
Benjamin Schiffer
Shirley Zhang
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Fair Division
Multi-Armed Bandits
Primary area: algorithmic_game_theory

Abstract: We consider the problem of online fair division of indivisible goods to players when there are a finite number of types of goods and player values are drawn from distributions with unknown means. Our goal is to maximize social welfare subject to allocating the goods fairly in expectation. When a player's value for an item is unknown at the time of allocation, we show that this problem reduces to a variant of (stochastic) multi-armed bandits, where there exists an arm for each player's value for each type of good. At each time step, we choose a distribution over arms which determines how the next item is allocated. We consider two sets of fairness constraints for this problem: envy-freeness in expectation and proportionality in expectation. Our main result is the design of an explore-then-commit algorithm that achieves $\tilde{O}(T^{2/3})$ regret while maintaining either fairness constraint. This result relies on unique properties fundamental to fair-division constraints that allow faster rates of learning, despite the restricted action space.

Honor Among Bandits: No-Regret Learning for Online Fair Division
Ariel D. Procaccia"
Benjamin Schiffer
Shirley Zhang
Abstract
We consider the problem of online fair division of indivisible goods to players when there finite number of types of goods and player values are drawn from distributions with unknown means. Our goal is to maximize social welfare subject allocating the goods fairly in expectation. When player's value for an item is unknown at the time of allocation, we show that this problem reduces to variant of (stochastic) multi-armed bandits, where there exists an arm for each player's value for each type of good. At each time step, we choose distribution over arms which determines how the next item is allocated. We consider two sets of fairness constraints for this problem: envy savy-freeness in expectation and proportionality in algorithm
expectation. Our main result the design an explore-then-comie that achieves (TT2/3) regret while maintaining either fairness constraint. This result relies on unique properties fundamental to fair-division constraints that allow faster rates of learning, despite the restricted action space. We also prove a lower bound of (2T2333 regret for our setting, showing that our results are tight.
Introduction
Fair allocation of indivisible goods is a fundamental problem with a wide range of applications; implemented algorithms for this task have heen widely used in practice [14]. We consider the online fair division setting, which introduces additional complexities as items arrive one by one and each item must be immediately and irrevocably allocated at its time of arrival. Crucially, this allocation must be done without knowledge of future items [5]. One motivating example for this setting is food bank that receives donations for a region and then allocates these donations among many different food pantries and soup kitchens in that region. Donations are often perishable, and therefore must be immediately allocated. Furthermore, donations can be unpredictable, and hence knowledge of future items is limited.
Two standard notions of fairness envy-freeness and proportionality Envy-freeness implies that every player is at least as happy with their own allocation as with any other player's allocation. Intuitively, envy-freeness guarantees that no player will want to trade their allocation for that of another player. Proportionality is slightly weaker notion, which requires only that each of the n players receive at least 1/n fraction of their total value for all items. Finding solution which is envy-free or proportional is often interesting in and of itself, as can be seen from many previous results fair division [7, 30, 12, 3]. In cases where there may exist multiple envy-free or proportional allocations, however, natural goal is then to find the best solution among such allocations [13]. J. In our work, evaluate the quality of fair solution by its (utilitarian) social welfare, which is defined as the sum over all players of each player's value for their own allocation.
We take probabilistic approach analyzing online fair division. In particular, we assume that there are a finite number of item types, and each player's value for each type of item is drawn from
Paulson School of Engineering and Applied Sciences, Harvard University
E-mail: ariel-
pro @seas wawear.hararr.....
Department of Statisties, Harvard University E-mail: bschifferl @ haraaddadddd.
Paulson School of Engineering and Applied Sciences, Harvard University E-mail: szhang2 @ harvardd.du..
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

random distribution. In practice, these distributions would not be known in advance and must be learned as items are allocated. For example, consider again the food bank. When new food pantry opens, the values of that food pantry for different types of products are unknown. After items have been allocated to the food pantry, however, the food bank can easily collect information on the demand for various item types at the food pantry. Therefore, we primarily consider the setting where the player distributions are unknown in advance, and a player's true value for an item is observed and only if that player receives the item. This problem can be viewed as variant of the multi-armed bandits problem, as the goal is to learn unknown distributions (player values) while maintaining high reward (social welfare), subject to fairness constraints; with finite number of types of items, pulling an arm represents allocating a specific item type to a specific player.
As is standard in the multi-armed bandits literature, we use the notion of regret to measure the difference between our algorithm's performance and that of the optimal policy that knows the value distributions and is subject to the same fairesss constraints. Our overarching challenge is this: design online allocation algorithms that achieve low regret while maintaining fairness in the form of envy-freeness or proportionality
1.1 Our Results
Our main result that there exists a simple optimization- achieves Ö(T2/3) regret and maintains envy-freeness in expectation (Algorithm 1 and Theorem 1). A variant of the same algorithm achieves ((T2/3) regret while maintaining proportionality in expectation. The key step of the algorithm is a linear program- based optimization that guarantees that the constraints are satisfied without significantly decreasing social welfare.
peplore-then-comeee algorithm that
The main difficulty in this learning problem is that the envy-freeness and proportionality constraints depend on the unknown value distributions and may be tight constraints without any slack. We therefore develop novel machinery that relies fundamental properties of these faimess notions. One observation is that our faimess constraints are always satisfied when players are treated equally. Another crucial property is that when players have unequal values, these fairness notions can be satisfied with slack (Property 2). The latter property is especially challenging to show for envy- freeness, and the combinatorial algorithm that achieves it (Lemma 1) should be of independent interest to researchers in fair division.
1.2 Related Work
Online Fair Division. Work in online fair division generally deals with dividing goods when there is uncertainty about the future. Early work in the area focused on axiomatic questions [31, 1].
Our paper is most closely related to work by Benadè et al. [5]. Like us, they consider a setting where indivisible items arrive online and must be allocated immediately and irrevocably to players. They study several models for how the values of items are determined, ranging from a model where values are drawn i.i.d. from a distribution common to all players and items to, at the other extreme, an adversarial model with worst-case values. There are two fundamental differences between their work and ours. First, Benadè et al. [5] do not optimize social welfare; rather, they seek to either just minimize envy, do so while (approximately) satisfying the axiomatic notion of Pareto efficiency. Second, and more crucially, they assume that the values of all players for an item are known at the time of its arrival, whereas in model the values are unknown. It is precisely this modeling choice that induces a learning problem and underlies the connection between our setting and multi-armed bandits, which is absent in prior work in online fair division.
Like us, Yamada et al. [35] also study online fair division through the lens of bandit learning. Their setting is similar to ours in that they consider a finite number of item types where player values for item types are initially unknown. However, [35] do not guarantee fairness through constraints instead, they incorporate fairness through their objective function of Nash social welfare. [35] also make an additional assumption that player values are normalized, which we do not require for our results.
Fairness in Multi-armed Bandits. The other main body of literature related to our paper is multi- armed bandits with constraints. One notion of fairness in multi-armed bandits the idea that similar individuals and/or groups should be treated similarly [9. 18, 23]. The fairness constraint of Joseph et al. [17] is that a worse arm not pulled with higher probability than a better arm. Their definition of fairness is actually incompatible with maintaining envy- freeness (or proportionality), because
2

---

maintaining envy-freeness may require allocating an item to player with lower value to prevent envy. Another common fairness constraint in multi-armed bandits that every arm receives a minimum fraction of pulls [10, 11, 20, 28]. This notion of fairness is also not compatible with envy- sevy-frenness because the optimal envy-free allocation may never give player a specific item type. There also exist many other fairness notions in contextual bandits that are farther from our setting [15, 29, 32, 34]. Wei et al. [33] analyze a form of anvy-freeness in contextual bandits, but their envy-freeness notion depends only on the treatment probabilities instead of the values.
Our paper is also closely related to work on multi-armed bandits subject to general linear constraints. Multiple works in linear bandits study "safety" with respect to a linear constraint that depends on the unknown true mean values [2, 8, 26]. Amani et al. [2] focus on single constraint and specifically show that if there is positive slack in the optimal solution, then ((T1/2) regret is possible. If there is zero slack, however, their al algorithm only achieves O(T2/3) regret. This differs from our work because envy-freeness and proportionality involve multiple constraints that can have zero slack. Note that our setting is similar but not equivalent to linear bandits, as single arm is pulled in each step in our setting. There also exist many results for cumulative constraints in bandits [21, 22]. These are less closely related to model there is a branch of multi-armes bandits that studies constraints in expectation at each step as in our paper. However, these works are also in the linear bandits setting and again require safety gap that fairness constraints such as envy-freeness may not guarantee [27].
consider constraints that must hold at every time step. Finally,
Practical Motivation. Mertzanidis et al. [25] apply online fair division algorithms through a partnership with program in Indiana that redistributes rejected truckloads of food. The program, known as Food Drop, allocates 10,000+ pounds of rejected food per month to food banks. In this application, the available food arrives in an online and unpredictable way, and the trucks must be allocated immediately. More generally, the specific food donations depend on what items grocery stores restaurants have remaining at the end of the day. Therefore, donations are unpredictable, which we model through randomness.
In practice, utilities for food donations such as in the Food Drop program may not be additive. However, if the deliveries are sufficiently infrequent, then additive player utilities are likely to be a good approximation. For example, in the food allocation data of [19]. there were a total of 1760 donations from 169 donors over the course of five months and 277 organizations that received donations. Therefore, the organizations receive donations every 3-4 weeks on average, suggesting that donations can be largely regarded as independent.
2
Model
In this section we introduce our basic setting and terminology.
2.1 Online Allocation With Unknown Values
Suppose we have set of players N = [r]] and set of object types M = [mm]. Given a set of T indivisible items, an allocation A = (AI,... (A.)))..))) is a partition of the T items among the n players, where player i receives the items in A;. In our model, we assume that every item j has a type k(j) E [m]] and that there exists a (possibly unknown) matrix μ²' such that each player i's value for an item of type k [m]] is independently drawn from Sub-Gaussian distribution with mean Mik Player values are assumed to be independent across both players and items. We will often refer to ug as the vector of mean values for player i. For specific item j. we denote player i's value for item j as Vi(j), and similarly, player i's value for their allocation A; as Va(A,) = EjeA, V.(i). The (utilitarian) social welfare of an allocation A is (w()) Di=1 Vi(A.).
We consider algorithms in the following online setting. At each time step E [T'] an item je of type ky arrives, where K₂- D. for some known distribution D> supported on [m]]. We will assume that D = Uni(((])) or in other words that every item has an equal probability of being type 1..... m. We make this choice purely for ease of exposition, in order to simplify notation; our results and techniques extend seamlessly to arbitrary distributions D that do not depend on T, as we explain in Appendix C. The algorithm observes the item type k., and must then immediately allocate the item j, to player i, at which time the algorithm observes that player's 's value V,, (jz). Note that the algorithm does not observe any other player's 's value for item jr- The high-level goal is to allocate these items in manner that maximizes the social welfare of the final allocation of all T items.
3

---

We denote X E R as a valid fractional allocation if Σ, Xik 1 for every k E [m]] One valid fractional allocation we will often refer the uniform at random allocation (UAR), where every entry is 3.- At every time-step I, before observing kiz the allocation algorithm AT.G takes as input the history HI, = [(ky, ig. V4, (ix)) t' < {) and returns fractional allocation X, = ALG where (xt) represents the probability of allocating the item player if the item is of type k. If the next item is of type ke then the algorithm allocates the item randomly among the n players according to the distribution induced by the v column of Xt, i.e. (X, )a, Therefore, the tth item is allocated to player i with probability (Xt)sk.- We denote the final realized allocation that ALG returns as A(AG)). and the corresponding partial allocation up to time as A A (ALG). This online process is summarized in pseudo-code in Appendix A.
We will also assume (explicitly in our theorem statements) that for all i, k, there exist known constants a, b, > 0 such that a S M4 I b. This assumption is necessary because if we allow the means of values to be arbitrary close to zero, then can be impossible to achieve regret of o(T). This is formalized in Theorem 11 in Appendix C.2.
2.2 Fairness Notions
We will primarily use two metries of fairness to evaluate an online allocation algorithm ALG: envy- freeness in expectation and proportionality in expectation. Both are defined below. For two vectors y E R", we use (z, 3) x y to represent the dot product of the two vectors.
Definition 1. Let X, = ALG(H,) be the fractional allocation used by algorithm ALG at time I given history Hz. Then ALG satisfies envy-freeness in expectation (EFE) if for all and all Hr, (Xi)s 14 2 maxre[m] (Xt)r -4, for all i.
Definition 2. Let X, = (L,(HH) be the fractional allocation used by algorithm ALG at time t given history H,. Then ALG satisfies proportionality in expectation (PE) if for all t and all histories Hr. (Xt). 14 2 #. Ere(n) (Xt)z : 14 for all i.
Intuitively, envy-freeness in expectation is equivalent to maintaining that at every time step t and before observing the item type ki, no player prefers the fractional allocation of any other player in X₁. Similarly, proportionality in expectation is equivalent to maintaining that at every time step and before observing the item type kr, the expected value of every player for their fractional allocation is at least 1/n times that player's 's value if they received the item with probability 1.
In Appendix B, we justify some of the implicit choices behind these definitions. Specifically, we discuss why we consider anvy-freeness in expectation rather than its realization, and also why we require envy-freeness in expectation to hold at every individual time step. Analogous results for proportionality can be found in Appendix B.1. For the former question, Theorem 3 shows that in our setting, no algorithm can with high probability output an allocation A(ALG) with realized envy less than VT. Note that Benadè et al. [5] show that in the adversarial setting, no algorithm can guarantee of (T) realized envy. Conversely, they also show that when values are generated randomly and observed before allocation, there exists algorithm that can guarantee o(1) realized envy with high probability. Theorem shows that when values are still generated randomly but are anknown at the time of allocation (as in our setting), no algorithm can guarantee of o(vT) realized envy with high probability. We complement Theorem 3 with Theorem 4, which shows that any algorithm ALG that satisfics envy-freeness in expectation will output a final allocation A A(ALG) with realized envy of at most VT log with high probability. Therefore, envy-free in expectation algorithms are within a lTg factor of being "optimal" in terms of final realized envy.
We also show that requiring envy-freeness in expectation at every time step does not lead to any social welfare loss compared requiring envy-freeness in expectation only at the end of T rounds. More specifically, Theorem 5 (again in Appendix B) implies that requiring that no player is envious in expectation of any other player at the end of all T' rounds equivalent maintaining envy-freeness in expectation at all times t E [T] when maximizing social welfare. A key step of our proof of Theorem 5 is showing that for every time- or distoet-dependent algorithm ALG which achieves envy-freeness in expectation at the end of T rounds, there exists another algorithm ALG' that is time- and histery-independent, envy-free in expectation at every time step, and achieves the same social welfare. Therefore, maximizing social welfare only over algorithms which are envy-free in expectation at every time step is sufficient even if envy-freeness in expectation at the end of T rounds is all that is desired.

---

We can formulate our faimess notions as linear constraints, in the spirit of prior work in fair di- vision [4]. Formally, define (A, B) F as the Frobenius inner product of matrices and B. For B E IR E RR and a fractional allocation X, we represent the linear constraint (B, X) 2 cs the tuple [B, (B,c). fractional allocation X satisfies a set of I. linear constraints ((Be if for all & E [L. (Be. X)F 2 cz. Because the constraints represent "fairness in expectation" relative to the mean values, we will explicitly let the constraint matrix Br(x²) be a function of the mean value matrix μ², Therefore, we will consider sets of constraints of the form {BBe(u"), ),))) Because these constraints are functions of μr, we will also refer to families of constraints (L)
The following two remarks show how envy-freennss in expectation and proportionality in expectation can be represented within this framework.
Remark 1. For every & [n²],, construct 3 follows. Define i [ and i' (E mod n) + For every & [K], let (B (f*) = U.x. and (BFf -Has For all i" & (", let (Bff
O. Then the envy-freeness in expectation constraints for mean μ¹ as defined in Definition correspond to efe()²) ) == ((BBte (4*), 0)]e
Remark 2. For every e E [r²]. construct (²((")) as follows. For every h E [m], (B₁" (p )ex ni j& for every & Then the proportionality in expectation constraints for mean μ² as defined in Definition correspond pe(p") = {[B," (1)).
(-=1) ulx and (x"))) = 1
2.3 Regret and Problem Formulation
An algorithm ALG satisfies constraints ((e)()").ee))) if for all & E (7), the fractional allocation X, used by ALG at time t satisfies the constraints {(Be(n*) cc))) When μ² is known, the expected social welfare can be directly optimized over all algorithms ALG that satisfy constraints {(Be(H"), k/))/ This problem is equivalent to solving LP (1) with μ = n² and using the solution y as the fractional allocation for all time steps.
y := arg max (X, 1)
s.t. (Be()),)) 2 4 A4
X x Vk:
(I)
When f² is unknown, define the regret of algorithm ALG follows. Note that the baseline algorithm in this definition of regret is the optimal allocation algorithm under the constraints when 1x" is known.
Definition 3. Let Y"' be the solution to LP (1) for μ 1²" Let X, = (HG(H:: be the fractional allocation used by algorithm ALG at time given history Н, Then the T T-step regret of ALG for (X,,)²))
constraints ((Ba()²), 22) 7 (Y"" ,1²)r
We are now ready to present the formal problem statement. Because the constraints depend on the unknown values that are being learned, we only require constraint satisfaction with high probability.
Problem Suppose we are given n, m, T, a, such that Given a family of fairness constraints { [[(Be(p), H)), representing either envy-freeness in expectation or proportionality in expectation, the goal is to construct an algorithm ALG such that with probability 1 1-1 1/T, X: = ALG(HH)) satisfies the constraints (Brlx²) ),ct)) for all t E [T] and the regret of AT. for constraints (Be(ee) ), (t is o(T).
S phe S for all i [m]] k [m].
Note that the (T) regret in Problem 1 will be ( for our results. We use the standard O() and Ō() notation with respect to the number of time steps T, and therefore the constants represented by this notation may depend on other problem parameters such as n and m.
Fairness Machinery
Our goal in this section is to establish novel, fundamental properties of envy-freeness and propor- tionality in expectation, which will serve as a crucial part of the machinery underlying our regret bounds.
In the context of fairness, natural assumption is that a group individuals are treated equally, then that group is considered to be treated fairly. In that spirit, our first key property is as follows.
5

---

Property 1. For any & E [L], suppose that fractional allocation X E R= satisfies X,, X1,. Vi,. E {i: Be()), + 0). Then (Br(u), F 2 ct.
Informally, a set of constraints satisfies Property 1 if for any constraint in the set, the constraint always satisfied when all players involved in the constraint have the same fractional allocation. An important consequence of Property 1 is that the uniform at random allocation satisfies every constraint. This implies that even with no information about the players' mean values, the uniform at random allocation will always be fair.
Note that envy-freeness in expectation satisfies Property because any two players with equal allocations are never envious of each other. Proportionality in expectation also satisfies Property because if every player has the same allocation, then every player is receiving exactly their proportional allocation.
Observation 1. The envy-freeness in expectation and proportionality in expectation constraints satisfy Property 1.
Our second key property is more technical and novel. Intuitively, the property requires the existence of a fractional allocation X" that is only slightly worse than the optimal constrained allocation YP, but unlike the latter allocation, in X' the constraints either hold with slack or all players involved in the constraint are treated equally. Interestingly, this property does not hold for arbitrary sets of linear constraints, but relies on structure inherent to the envy-freeness in expectation and proportionality in expectation constraints. The bulk of the theoretical work of this paper is proving that the envy-freeness in expectation and proportionality in expectation constraints satisfy this property.
Property 2. Let Y be the solution to LP (1). Then there exists constants (relative to T) 7ro and Cp2 O such that for any 7 < To and any μs, there exists a fractional allocation X' such that (X', P)F 2 (YP, ((, - Cp27, and such that for each & E [L]. either
1. (Be(r), X')F 2 cg 77 or
2. Vin,22 E {i: Be(p), * 03. X =X
Lemma 1. The family of envy-freeness in expectation constraints satisfies Property 2.
Proof sketch. We will informally argue that we can transform Y" into a fractional allocation X' which satisfies Property 2 through Algorithm 3. Algorithm 3 iterates over ennyy-wihhsslackoo graphs, which track whether a player prefers their allocation by at least a over another player's allocation. More specifically, given parameters μl, X, and a, the corresponding graph has vertices N and edge set E' such that a directed edge from i to i' exists if and only if X, - p4 a. The weight of each such edge is X 11:----a -4i At high level, Algorithm 3 constructs sivy-with-slack-a graphs with progressively smaller a, with a 2 r for all iterations. The algorithm operates on sets of nodes called equivalence classes, where every pair of nodes in an equivalence class has the same allocation. Algorithm 3 makes progress in every iteration by either 1) merging two equivalence classes, or 2) removing an edge from the graph.
wittswith-slack'
An overview of the algorithm is as follows. In each iteration, Algorithm 3 generally performs one of three operations and decreases a. First, if there exists an equivalence class S with at least one incoming edge but no outgoing edges, then operation remove iinpooe-iincomngedgeee transfers allocation probability from nodes in S to all other nodes. This will remove all incoming edges to S. If such an equivalence class does not exist, then Algorithm 3 finds a special type of directed cycle in the wlack'slack' graph. The directed cycle is chosen so that the outgoing edge of each node in the cycle is among i's outgoing edges with minimal weight. Therefore, each node i in the cycle is pointing to an E N for whom i has the least slack. If there exists some node i* E N which has an edge to some but not all of the nodes in the cycle, then operation cycle-shift gives each node in the cycle half of its current allocation and half of the next node's allocation. This will remove an outgoing edge from i*. If such node does not exist, then Algorithm 3 either decreases to remove an edge or creates a new equivalence class by merging all equivalence classes that the nodes in the cycle belong to via operation average-clique.
However, such a merge may lead to envy, which is removed by Algorithm 4. Each call to Algorithm 4 removes envy from at least one edge. Algorithm 4 does so by first carefully redistributing allocation among the nodes until there exists a cycle where each node has non-negative envy (which is equivalent to cycle with non-positive slack). Each node in the cycle is then given the allocation of the next

---

node in the cycle. We prove that each call to Algorithm 4 decreases the number of edges with envy, while not increasing the number of edges in the 'envy-with-slace graph. Furthermore, Algorithm does not significantly decrease the social welfare of the allocation.
The three operations and Algorithm 4 each take as input an allocation X and returns new allocation X' which is close in social welfare to X. Furthermore, each iteration begins with an envy-free allocation, and the size of the edge set of the "envy-with-slack graphs never increases throughout the algorithm. The maximum size of an equivalence class is "envy-with-slack" graph every n iterations. There are at most n² edges, and the algorithm therefore terminates in at most n iterations with an allocation which satisfies Property 2. For the numerous details, see Appendix F.
an edge must be removed from the
Lemma 2. The family of proportionality in expectation constraints satisfies Property 2.
Proof sketch. Define the slack S; of a player i for an allocation as the amount by which that player's value for their allocation is greater than their proportional value. In other words, the slack is the amount of welfare player can lose and still satisfy the proportionality constraint. We construct the fractional allocation X" in one of two different ways depending on the amount of total slack for the allocation Y across all n players.
the amount of total slack across all n players is less than bay then we take X' UAR. Note that the total slack is equivalent to the change in social welfare between YP and UAR. Therefore, because the total slack was less than buz, the difference in social welfare between Y" and UAR is at most bny which is O(7). Furthermore, by definition the UAR allocation satisfies option of Property a
for all constraints &.
If the amount of total slack is greater than bny, then we construct X' from Y" by transferring allocation away from players with slack greater than the required y and redistributing this allocation so that every player has slack of at least 7. Specifically, each player i loses a of their allocation for item k where
Y
S
my
Ask
=== ik
2 =1==1
S
The allocation X' is then constructed
n2 Σ
X :
YH ik
ck
Ark-
(2)
n
Intuitively, this can be viewed as each player putting a part of their allocation (proportional to S; 7)) into a communal "pot." The pot, consisting of Σi= Avk for item k, is then divided evenly among all n players to form X'. By construction, no player loses more than S; social welfare when the pot is created, and every player receives at least y additional social welfare when the pot is redistributed. Therefore, in the resulting allocation X', every player prefers their allocation to their proportional value by at least 7, i.e. each player has slack of at least y for X'. Furthermore, the total difference in social welfare between Y" and X' is at most O(7). We have thus shown that in both cases, X' will satisfy all of the desired conditions. The full proof is relegated to Appendix E.
L
It will be useful to introduce two further properties that are immediately satisfied by the definitions
of envy-freeness in expectation and proportionality in expectation. Property 3 guarantees a form of Lipschitz continuity in ya for the constraints. This is unsurprising, the entries in the matrices B (1) for both envy-freeness in expectation and proportionality in expectation are linear in the entries of μ.. Property 4 guarantees that the non-zero entries in the constraint matrices stay the same for all values of μ., which follows directly from Remarks and 2 and the fact that μik is bounded away from 0.
Property 3. There exists K > such that Vy n1² E (a, b)am and Ve 0, if I1+ 1 S then [B(()²) - Be(r))ll1 & Ke.
Observation 2. The envy-freeness in expectation and proportionality in expectation constraints satisfy Property 3.
Property 4. For all μ, pl (a, bjnxm, (i: Be(r)) 003 {i: Be(p'): + 0).
7

---

Observation 3. The envy-freeness in expectation and proportionality in expectation constraints satisfy Property
Recall that Property 2 implies that for every constraint L, either the constraint é has a slack of at least for X' or every player involved in constraint is treated equally under allocation X'. slack of y in the constraint guarantees constraint satisfaction for all jz close to if the constraints are continuous in μ.. Treating every player equally for given constraint also guarantees that the constraints are satisfied for all μ by Property 1. Therefore, Properties I and 2 together with continuity (Property 3) imply that there exists a fractional allocation X' such that the social welfare of X' is close to the social welfare of Y and such that X' not only satisfies the constraints for μ,, but also satisfies the constraints for any nl close J.
4 Algorithm and Regret Bounds
In this section, we present our main result, an explore seaereethee-coommee algorithm which achieves ( regret while maintaining either proportionality in expectation or envy-freent sevy-freeness in expectation. The key step Algorithm
the optimization in LP (3) to guarantee that the fairness constraints are satisfied with high probability. For μ E R4 and
1T" we define the confidence region
+t (x' E IR pitk S 144 S Pak + ea: Vi,k), Note that Algorithm requires solving L.ss with an infinite number of constraints, which we discuss further Section 6.
Algorithm Fair
Require: m. T. (((B((()))))) c)) for / +- to 72/3 do
At time 4, use fractional allocation X UAR
end for
E 72/3 k
Nik
Aik
Nik Lr=
1R, =RA V1, (++)
GA Vlog (27))))(2N1a)
X Solution the following LP:
max X)
s.t. (Be(M), X)F 2 at Vl Vu
Xik =1 Wk
(3)
for l +- T2/3 to T do At time I, use fractional allocation X X. end for
Theorem 1. Suppose are given n. m. T,o, such that 0 < S 1h S for all i [m], k [m]] If ((((e())) ce) = {efc(μ4} or (B)) probability - 1/T satisfies the constraints {(Br(H'), (i) (,)) and achieves regret of Õ ) for constraints
{pe(μ)) then Algorithm I with
Proof sketch. We have already shown in Section 3 that both envy-freeness in expectation and propor- tionality in expectation satisfy Properties 2, 3, and Therefore, it suffices to show that Algorithm 1 achieves ((T2/3) regret for any family of constraints ((BB()))cc))33 that satisfies Properties 1, 2, 3, and 4.
The allocations used during the warm-up steps Algorithm are uniform at random, and therefore these allocations satisfy the constraints (Bee()), for all by Property 1. Because the fractional allocations used in the first 22/3 steps are all UAR, each arm, or (player, item) pair, will be sampled with probability non
1 at each step. This implies by Hoeffding's inequality that with high
probability, No = 2/(3 for all i, k. The i, k entry in the matrix is proportional to VNxx
and

---

therefore ||[|] = ((3) with high probability. Because the value distributions are sub- Gaussian, standard application of Hoeffding's inequality also gives that with high probability, the true mean matrix will be within our confidence region, i.e. n² E ia + 6. To summarize, because we used UAR for the first 22/3 steps, we have that
Pr (Iell S OŌ(T E 21 T
For the rest of the proof we will assume that the high probability event in the equation above holds. The next step is to show that X has ||e|]] per-step regret compared to Y Let K be the Lipschitz constant of Property 3. Using Property with = μr' and y = 2K|]e]] l = Ó(T-1/3) gives that there exists an allocation X' such that the social welfare of X' is only O(Ie[Iaa less than the social welfare of the optimal allocation Yr" and such that every constraint either has slack of at least 2K |K||e]| (option of Property 2) or every player is treated equally in constraint & (option 2 of Property 2). We will now show that X' is solution to LP (3). If option holds for constraint E [T.], then by Property 3, X' will satisfy the constraint (Be(1), ce) for every μ E j c. Formally, if option 1 holds for constraint then for any μ E C,
(Bel)), x') = (Belp), X')F - (Belu") X')') (Bel")), (Be(p) - BB(l"))))))))))))))({))))) 1²) F+ + (Be(""),')) 2 ([Bel"",,)) -Be((1)) Be(lr))l
S X S 1, Vi,
(BBe(m", |K|l
[Property 3]
[Property 2: option 1]
If option 2 holds for constraint [L], then Properties and 4 together guarantee that X' will satisfy the constraint (Be(j), cτ) for every μ. E fi c. Therefore, X' will satisfy all of the constraints (Be(k)) cm) for every μ j e, which implies that X' a solution to LP (3).
Finally, because X is the optimal solution LP (3), X must have higher social welfare than X' under means P. Because "| ~lll S ||e|11, this implies that X must have at most O(lel[a) less social welfare than X' under the true means μ=" An application of the triangle inequality gives that,
( 11) (8 = (Y"", ,M²FF (X' ,', (X) ( (8,1")
= ([k]]l + ||||]])
=
Thus, the total regret for the steps after the warm-up period is Ō(T2/3). The regret of the warm-up period is at most (b - a)/2/3 due to the assumption that the mean values are bounded. We can therefore conclude that the total regret is (TT233), and this completes the proof of regret. Finally, we note that by construction of LP (3), if n E f + e then the chosen fractional allocations X must also satisfy the constraints { (Bac ce) as desired. See Appendix for the full proof.
Lower bounds
The following lower bound shows that Theorem 1 is tight up log factors. An equivalent result holds for proportionality, with the same proof.
Theorem 2. There exists a, b n, such that no algorithm can, for all μ²" E bjxm, both satisfy T2/8 the envy-freeness constraints and achieve regret of less than log(T) with probability at least 1 1/T. The same is true for the proportionality constraints.
Proof sketch. We defer the formal proof to Appendix G and provide brief intuition here.
Suppose there are two item types and players. In this case envy-freeness and proportionality are equivalent, and therefore we will focus on the former. Consider the following two mean value matrices.
2
3 1
2
3
P1
P12
1 1 T 1

---

We will show that no algorithm can with probability 1- 1/T achieve regret of less than 2/33 and satisfy envy-freeness in expectation for both of these distributions. First, note that the expected social welfare maximizing allocation for lui is to give all items of type to player 2 and all items of type 2 to player 1. On the other hand, any envy-free allocation for #2 must give (((T1//3) fraction of items of type player 2. This implies that if an algorithm is unable distinguish between μ41 and μ22, then either the regret will be (((2/35) for μa or the algorithm will not be envy-free for j22-
Therefore, any algorithm that has regret of less than (((2/33 and satisfies envy-freeness for both in and #2 must distinguish betwen μl and pg. The only way to do this is allocate least (2(32/3)
items of type 2 to player 2. However, this will result regret under μr of ((T22/3).
Discussion
We conclude by discussing some limitations and open questions. First, Algorithm involves solving a linear program with an infinite number of linear constraints. Linear programs with an infinite number of constraints (called semi-infinite programs) are well-studied and occur many applications [16, 24). We also note that finite number of (exponentially many) constraints suffices for envy-freeness in expectation and proportionality in expectation by bounding all of the possible extreme values of e. Nevertheless, we opted to avoid this representation because it significantly complicates the presentation of the algorithm. Furthermore, there also exists a polynomial time separation oracle for determining whether allocation satisfies the infinitely many constraints, which would allow techniques such as the Ellipsoid Method [6] to solve the linear program in polynomial time.
Second, while the regret coefficients for proportionality are polynomial in n, a practical limitation of Algorithm for anvy-freeness is that the O term is exponential in n. We expect, however, that the worst-case bound we present Lemma is far from tight. Whether there exists a bound on the regret that is polynomial in n for learning under envy-freeness in expectation constraints is an open question for future work.
The other natural question that remains open for future work is whether regret while maintaining envy-freeness in expectation or proportionality in expectation. If the optimal solution Y"" has a positive slack in every constraint, then an upper confidence bound (UCB) approach would be likely to work. Unfortunately, the fairness constraints for envy-freeness in expectation and proportionality in expectation are often tight for the optimal allocation. Furthermore, the constraints have constant (greater than 1/n) dependence every mean value f might need to be learned with high accuracy even the optimal allocation does not allocate item type & to player
achieve Ö(VT)
every unknown value in the μ matrix. Therefore,
We also note that there exist additional (albeit less prominent) fairness notions for the problem of online fair division, such as equitability, which may satisfy additional properties that allow for lower regret. We leave the question of studying more fairness notions for future work.
Finally, a broader question is whether the connection we have established between multi-armed bandits and online fair division might be leveraged give fresh perspective on additional problems in this area, such as online cake cutting [31].
Acknowledgments and Disclosure of Funding
Procaccia gratefully acknowledges research support by the National Science Foundation under grants IIS-2147 14-2147187, IIS-2229881 and CCF-2007080; and by the Office of Naval Research under grant N00014-20-1-2488. Schiffer was supported by NSF Graduate Research Fellowship. Zhang was supported by an NSF Graduate Research Fellowship.
10

---

References
[1] M. Aleksandrov, Aziz, Gaspers, and T. Walsh. Online fair division: Analysing food bank problem. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pages 2540-2546, 2015.
[2] S. Amani, M. Alizadeh, and C. Thrampoulidis. Linear stochastic bandits under safety constraints. Advances in Neural Information Processing Systems, 32, 2019.
[3] H. Aziz and Mackenzie. A discrete and bounded envy-free cake cutting protocol for any number of agents. In Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS), pages 416-427, 2016.
[4] E. Balkanski, S. Brânzei, D. Kurokawa, and A. D. Procaccia. Simultaneous cake cutting. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI), pages 566-572, 2014.
[5] G. Benadè, A. M. Kazachkov, A. D. Procaccia, A. Psomas, and D. Zeng. Fair and efficient online allocations. Operations Research, 2024. Forthcoming.
[6] R. G. Bland, D. Goldfarb, and M. J. Todd. The ellipsoid method: A survey. Operations Research, 2966) 1981.
[7] S. J. Brams and A. D. Taylor. An envy-free cake division protocol. American Mathematical Monthly, 102(1):9-11, 1995.
[8] E. Carlsson, D. Basu, F. Johansson, and D. Dubhashi. Pure exploration in bandits with linear constraints. In International Conference on Artificial Intelligence and Statistics, pages 334-342. PMLR, 2024.
[9] G. Chen, X. Li, and Y. Ye. Fairer Ip-hased online allocation via analytic center. arXiv preprint arXiv:21 10. 1462/, 2021.
[10] Y. Chen, A. Cuellar, H. Luo, J. Modi, H. Nemlekar, and S. Nikolaidis. Fair contextual multi- armed bandits: Theory and experiments. In Conference on Uncertainty in Artificial Intelligence, pages 181-190. PMLR, 2020.
[11] H. Claure, Chen, J. Modi, M. Jung, and Nikolaidis. Multi-armed bandits with faimess con- straints for distributing resources human teammates. In Proceedings of the 2020 ACM/IEEE International Conference on Human-Rodee Robot Interaction, pages 299-308, 2020.
[12] J. Edmonds and K. Pruhs. Cake cutting really is not piece of cake. In Proceedings of the 17th Anmual
Symposium on Discrete Algorithms (SODA), pages 271 271-278, 2006.
[13] Y. Gal, M. Mash, A. D. Procaccia, and Y. Zick. Which is the fairest (rent division) of them all? Journal of the ACM, 64(6); article 39, 2017.
[14] Goldman and A. D. Procaccia. Spliddit: Unleashing fair division algorithms. SIGecom Exchanges, 13(2):41 1122):1146. 46, 2014.
[15] R. Grazzi, A. Akhavan, Falk, L. Cella, and M. Pontil. Group meritocratic fairness in linear contextual bandits. Advances in Neural Information Processing Systems, 2224392-244044 2022.
[16] R. Hettich and K. Kortanek. Semi-infinite programming: theory, methods, and applications. SIAM review, 35(3):380-429, 1993.
[17] M. Joseph, M. Kearns, J. Morgenstem, S. Neel, and A. Roth. Fair algorithms for infinite and contextual bandits. arXiv:1610.09550 2016.
[18] M. Joseph, M. Kearns, J. H. Morgenstern, and Roth. Fairness learning: Classic and contextual bandits. Advances in Neural Information Processing Systems, 29, 2016.

---

[19] Min Kyung Lee, Daniel Kusbit, Anson Kahng, Ji Tae Kim. Xinran Yuan, Allissa Chan, Daniel See, Ritesh Noothigattu, Siheon Lee, Alexandros Psomas, et al. Webuildai: Participatory framework for algorithmic governance. Proceedings the ACM on human-computer interaction, 3(CSCW):1-35, 2019.
[20] Li, J. Liu, and B. Ji. Combinatorial sleeping bandits with fairnsss constraints. Transactions Network Science and Engineering, 7(3):1799-1833 1817,, 2019.
IEEE
[21] Q. Liu, W. Xu, S. Wang, and Z. Fang. Combinatorial bandits with linear constraints: Beyond knapsacks and fairness. Advances in Neural Information Processing Systems, 35:2997-3010, 2022.
[22] X. Liu, B. Li, P. Shi, and L. Ying. An efficient pesiimisic-oppimistte algorithm for stochastic linear bandits with general constraints. Advances in Neural Information Processing Systems, 34:24075 24086, 2021.
[23] Y. Liu, G. Radanovic, Dimitrakakis, Mandal, and D. C. Parkes. Calibrated fairness in bandits, arXiv preprint arXiv:1707.01877 2017.
[24] M. López and G. Still. Semi-infinite programming. European Journal of Operational Research, 180())4491-518, 2007.
[25] Marios Mertzanidis, Alexandros Psomas, and Paritosh Verma. Automating food drop: The power of two choices for dynamic and fair food allocation, arXiv preprint 44Xiv:2406.06363, 2024.
[26] A. Moradipari. M. Alizadeh, and C. Thrampoulidis. Linear thompson sampling under unknown linear constraints. ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3392-3396. IEEE, 2020.
[27] A. Pacchiano, M. Ghavamzadeh, P. Bartlett, and H. Jiang. Stochastic bandits with linear constraints. In International Conference on Artificial Intelligence and Statistics, pages 2827- 2835. PMLR, 2021.
[28] V. Patil, G. Ghalme, V. Nair, and Y. Narahari. Achieving faireess in the stochastic multi-armed bandit problem. Journal of Machine Learning Research, 22 22177)) 2021.
[29] C. Schumann, Z. Lang, N. Mattei, and J. P. Dickerson. Group faimess in bandit arm selection. arXiv preprint arXiv: 19w.. 022.0380,, 2019.
[30] E. Su. Rental harmony: Spererr' lemma in fair division. American Mathematical Monthly, 106(10):30--92,, 1999.
[31] T. Walsh. Online cake cutting. In Proceedings of the 3rd International Conference on Algorith- mic Decision Theory (ADT), pages 292-305, 2011.
[32] L. Wang, Y. Bai, W. Sun, and T. Joachims. Fairness of exposure in stochastic bandits. In International Conference Machine Learning, pages 16686-10696, PMLR, 2021.
[33] W. Wei, X. Ma, and J. Wang. Fair adaptive experiments. Advances in Neural Information Processing Systems, 36, 2024.
[34] Y. Wu, Z. Zheng, and T. Zhu. Best arm identification with faimness constraints on subpopulations. In 2023 Winter Simulation Conference (WSC), pages 540-551. IEEE, 2023.
[35] Hakuei Yamada, Junpei Komiyama, Kenshi Abe, and Atsushi Twasaki. Learning fair division from bandit feedback. In International Conference Artificial Intelligence and Statistics, pages 3106-3114. PMLR, 2024.
12

---

A Algorithmic Representation of Model
Algorithm 2 [Online Item Allocation]
Require: ALG
1: vi, A <- {}, Hu {
2: for f 1 to T do
3:
X₁ f (-.
4: & ~
5:
Generate item je of type kt (i.e. Vi(i+) N 1), Vi NN)
6:
dt f Sample from (Xt)
7:
A = A// + {ir}
8:
H1 < 11-1+ + (Ke, it, (i)(
9:
end for
10: return A = (AT A2 A%)
B Motivating Fairness in Expectation
In this section, will explore the relationship between envy-freeness in expectation and realized envy, as well as the relationship between requiring envy-freeness in expectation at every time step and only requiring envy-freeness in expectation at the end of round T. For this section, will use the following notation. For any algorithm ALG, we denote X, = (L, as the fractional allocation used time f, and PrALG (i, k, H,) (Xt)ik-
Previous works on fair online allocation of indivisible goods have focused on the faimeess of the final, realized allocation instead of studying fairness in expectation as in Definitions 1 and [5]. We define the realized envy of an allocation below.
Definition 4. The realized envy of allocation A at time 7 is max,,' Vi(A,) Vv(A)).
We show in the following theorems that algorithms which are envy-free in expectation within lTg(T)) factor of being "optimal" in terms of final realized envy. Informally, Theorem 3 shows that in setting, algorithm can with high probability output allocation A(ALG) with realized envy less than Vf. Conversely, Theorem shows that any algorithm ALG that satisfies envy-freeness in expectation will output final allocation A(ALG) with realized envy of at most /T log()) with high probability.
Theorem Suppose μf is known, For any algorithm ALG and for any E [T], with probability at least 1/16 the allocation AT (ALG) has realized envy of more than vF.
proof. Assume there are two players and only one item type, and assume that all values are drawn from (n, 1). Fix log"(T) As in Algorithm 2, define i, {1,2) 2} the player allocated the item at time L. The realized envy of the two players can be written as:
Realized Envy of Player 1 at time
Σ t=
Lizt Vi(lo)
11a vi(ii)
(4)
1=0
Realized Envy of Player 2 at time
Σ
11,= Va(ie)
Σ 1=0
1 V2(lt)
(5)
Let of be the value of the assigned player for item i, and e be the value of the unassigned player for item Note that of, vf ~ N(u, 1), because the time of allocation, ALG does not know either player's 'ss value for the item, and player values are therefore independent of the assignment.
By this coupling argument, Equations (4) and (5) can be rewritten as:
Realized Envy Player at time
Σ
1i 28
Σ 1 2
(6)
13

---

Realized Envy of Player time T
Σ 11:=2 2s
Σ
1 of
(7)
By the Central Limit Theorem, Ei= of and Ei=o 1/ are both N(T p4 T). Therefore, for any with probability at least 1/16, we have that
Σ 1/ Tp VT and
1 2 VT.
1=0
Putting these equations together, we have that
Σ og 227
However, this result with Equations (6) and (7) implies that the envy must be at least vT for any choice of {ir]. Therefore, we have shown that with probability at least 1/16, the envy at time T will be at least V for any possible algorithm.
Theorem 4. Suppose μz is known. Also assume that all of the value distributions are bounded by constant B. If ALG deterministic (i.e. (LG(H,, a deterministic function of H₂) and satisfies envy-freeness in expectation, then with probability o(1/T), the realized envy of A (ALG) at every time T E [T) is at most /F log(T).
proof. We will bound the realized envy of A(ALG) between any two specific players i, i', which will then imply bound the realized envy of A(ALG) by union bound. The key observation is that each round of Algorithm 2 consists of first a random draw from 'D determine the item type ky and then draw from (n, 1J) which determines the player to which the item allocated based on X, AL)(HH). Formally, the 7th item is allocated to player i if
& E (X)eR
Σ (X
Define {urg" =1 as the values of the players for the item at time t. This is the final source of randomness round t. Therefore, the allocation of any player time 7 function of the random variable sequence {(A,, &e, (ver ( )²==))
Let E, represent the envy accrued by player for player up until but not including time 7. Then
E, = Σ Uti Σ 1
("evet (x),,, (X (X),a)) 1
1=0
k=1
= &l(ke, & tww WED))
Now we will apply McDiarmid's inequality to the function ff (f(ke, Et, (rrw in }(o))
First, we show that the bounded condition is satisfied. If {(ke, &,, (uer In = and {(K,, &t folr ) differ only at the tth element for any E [0, r 1). then
f (((K,, Sts (1u Hr ) $ B. Therefore, we can apply McDiarmid's inequality to get that
|/ (((ke, & H
Pr (If (L(ke, & (va )> E [/ (L(ke, &i, (vre ) vFlog(T)) - (ox - (2))
14

---

Since ALG is envy-free in expectation, we know that E [f (f(ks, &e, fue = fore, we must have that
- 0. There-
Pr (f (f(ke, &e, (uw 1>=)) 2 VTlog(T)) < TT-
Taking union bound over all pairs i, i' and all [T], we have that
Pr(3r: : Realized envy at time is 2 v (og(() ) S n 7 = o(1/T).
Therefore, with probability 1 - o(L/T), the realized envy at evert time T is at most V log(T))
Note that Theorem does not contradict the results of Benadè al. [5], who achieve uvyeffreeness of the realized allocation with high probability when the true player values for the items are known at time of allocation (as opposed to our model which only knows the item type). When player values for item Jr. are known before assignment, Theorem 3 does not apply.
We also defined envy-freeness in expectation In some fair division applications, we may only care about "fairness" of the total allocation at the end of the process. Therefore, we could instead only require that no player is envious expectation of any other player at the end of all T rounds. However, Theorem 5 shows that this is equivalent to maintaining envy-freence
constraint which needs hold at every time step t.
expectation at all times E [T') when maximizing social welfare.
Theorem 5. Suppose μ² is known. Let & be the class of all algorithms that are envy-free in expectation and let F be the class of all algorithms which satisfy E[V((A 2 max [V))) for all Then VE[n)
max Elsw(((ATLO) ALGEJ
max (lsw((A(TA)) (A(AL.G)) ALGEE
proof. By definition, & F, which proves one direction of the desired equality. We will now show that for any ALG E F, there exists an algorithm ALG' such that
E/sw (A((AG)))))) Elsw(A(ATGG))
First, observe that by the definition of we have that for all i,
1
ΣΣ Pr (i), Pr(k)
E
ΣΣ
(r H.)aa
(8)
T
ALG
LEITI
[EIT]
By linearity of expectation, Equation (8) equivalent to
1 Σ Σ /
Pr (i,k, H.)dH, usk Pr(k) T
1
Σ
Σ
/
Pr H.)H., Uik Pr(k).
T EE[T] k H. ALG
tE[T à H, ALG
Furthermore, by definition
Essw(ALO (ALG)] E
ss
ΣΣΣ Σ
Pr (i, He)pm Pr(k)
ALG
D
1=1
[E[T]
72
Σ Σ /
Pr (i,k, H.) pax Pr(k) D
H. ALG
1E/27
ΣΣ
Pr (i, H.)dH, Pas Pr Pr(A). ALG
[E|T)
We will construct the algorithm ALG' as follows. Suppose ALG' time-independent and history- independent, such that for all He.
Pr (1, kt H₂) = Σ ALG:
Pr ALG,
H.)AH.
#E[T]
15

---

The expected social welfare of ALG's is
B
B|sw
E
Pr ki,k, Hi) PI(K)
ALG;
i=
[E[2]
E
Σ
Pr ALG.
H.).H, Makk Pr(k)
T
[E
sE(T]
= E
Σ SE[T]
Pr ALG.
(i,k, H.)dHH. Piik (r())
k
B|sw(AL))).
Therefore, ALG and ALG' have the same expected social welfare. Finally, need show that ALG' E. This equivalent to showing that for all t and H,,
E Pr (i, He)saR Pr(k) ALG;
2 Σ Pr (t' k. Hi)pa Pr(k). k
D
ALG;
Starting with the LHS and plugging in the definition of ALG', have that
Σ Pr (i,k, He)pu Pr(k)) ALG'
Σ
Pr (i, H.)ddHspa Pr(k) ALG.
sE(T]
Pr (i,k, H.)dH Pr(kk) ALG. /
Σ Σ
T
D
& sE|T
/
Σ ΣΣΣ
Pr H.),HH) Pr(k) ALG.
[Equation (9)]
b: sE(T]
/
Σ T
Σ
Pr (f, (f,,,, Pr(k)) ALG.
# SElTI
Σ Pr (f', k. HeJaa Pr((), ALG.
D
desired. Therefore, have shown that ALG' E.
Theorem 6. The algorithum which maximizes expected social welfare subject to EFE up to time T is time- inneeinddpennent, iestrr-inndependent, and can be calculated in polynomial time.
proof. By Theorem 5, there exists an optimal algorithm that satisfies envy-freeness in expectation and that is time- imee-nddeenndent and iestrr-indeeenneett To find the best such fractional allocation, all we must do is solve LP (1) with the envy-freeness in expectation constraints.
B.1 Proportionality
Theorems 3-6 also have equivalent forms for proportionality. We define the realized proportionality gap the equivalent of envy for the proportionality constraints. This implies that proportional allocation has non- non-positive proportionality gap.
Definition The realized proportionality gap of allocation time 7 is max; + Σx V((AT) V((AT).
As in Theorems 3 and 4, the following two results give that algorithms which satisfy proportionality in expectation are within log(T') factor of optimal for the realized proportionality gap.
Theorem 7. Suppose μe is known. For any algorithum ALG and for any T E (T), with probability at least 1/16 the allocation AT (ALG) has realized proportionality gap of more than VT.
16

---

proof. As in the proof of Theorem 3, assume there are two players and only one item type, and assume that all values are drawn from (p, 1). Then the realized proportionality gap of the two players can be writeen as:
Realized proportionality gap of Player at time 2
1
Vi(li)
Σ 1=0
1 1
Vi()t)
2
(10)
1
Realized proportionality gap of Player 2 at time
Σ
14=2
vo(ii)
1 11==1
V2(it)
2
1=0
1=0
(11)
These equations only differ from those of realized envy by scalar factor, and therefore the rest of the proof follows exactly as in Theorem 3.
Theorem 8. Suppose μ is known. Also assume that all of the value distributions are bounded by a constant B. If ALG is deterministic (i.e. (H,(H,) is deterministic function of H.) and satisfies proportionality in expectation, then with probability 1 - o()TT), the realized proportionality gap of (AILG) at every time T E [T] is at most vF log(T).
proof. In this proof, we can let E, be the accrued "proportionality gap" of any player i. Then as in Theorem 4, an application of McDiarmid's 's inequality allows us to bound the realized proportionality gap with high probability for all T.
The following two theorems are analogs of Theorem 5 and Theorem 6 for envy-freeness in expec- tation. Together, these theorems imply that maximizing social welfare subject proportionality in expectation at every time step is equivalent to maximizing social welfare subject to proportionality in expectation only at the end of round T.
Theorem 9. Suppose μ is known. Let & be the class of all algorithms that are proportional in
expectation and let F be the class of all algorithms which satisfy [E(V((AT)
Σ [[V((A))
for all i. Then
max E(sw [[sw(A(ALG)] = ALGEF
max E[sw(A(AIA)) (A(ALG))) ALGEE
proof. Suppose ALG E F. We will define ALG' as in Theorem 5 to be
Σ /
(i,k, H.) ALG.
Pr
Pr (1,k, H.)dH. ALG,
SE(T]
By this construction, ALG's E because
Σ
Pr (i, k, He)Jen Pr(k) ALG
D
Σ
Pr (i,k. H. H.)dH.pi (r(k) D
T
ALG.
k
SE[T
/
Σ Σ
d.).Hau Pr( ALG.
Pr
à SE(T]
(d) Pr(k) ALG.
Pr
[ALG E F]
Tn
eE(T"
Σ
Σ SE[T"
Pr (F,k, (.,k,H.)dHHH, Pr(k) ALG.,
Tn
Pr ALG'
(i'k, H. Pr(k).
D
17

---

Because & Ç F and because we showed in Theorem 5 that ALG' and ALG have the same expected social welfare, the desired result follows.
Theorem 10. The algorithum which maximizes expected social welfare subject PE up time T is imme-independent, history-independent, and can be calculated in polynomial time.
proof. By Theorem 9, there exists an optimal algorithm that satisfies proportionality in expectation that is tite--imdeeee indeeeddeenddnt and history-independent To find the best such fractional allocation, all we must do solve LP (1) with the proportionality in expectation constraints.
C
Additional Model Notes
C.1
Choice of 'D
In the body of the puper, we focus on the case when D is the uniform distribution over item types. However, our results generalize any distribution 'D which does not depend on T. In this case, the social welfare of a fractional allocation becomes Σi, Xis Pro(k))u- For a matrix v E RR=
define [V) = v' E Raxm where 1/2 n Pro (k)) paa. For mean values μ², define μ fD(("), Then social welfare of fractional allocation X with means jr" and distribution D is then simply 1. (xx,,') in the uniform ID case. Similarly, the envy-freeness in expectation or proportionality in expectation constraints on X with means μJ¹ and item distribution D can be represented as (Be(k'),X) 2 ce, which is equivalent form to the constraints when D is uniform. Therefore, for arbitrary D we can use Algorithm with only two slight modifications. The first is we must transform the jú, j4, and other components of the linear programs using the funetion fD. The second modification is that we potentially need more exploration steps (larger 7) in the warm-up period to guarantee the same level of estimation of μz, depending the value of min;, & Pry(k.). However, since we require that D does not depend on T, this will not change the overall regret of the algorithm.
C.2 Lower Bound on Means
In this section, we show that the means of player values can be arbitrarily close to zero, then it can be impossible achieve regret of o(T).
Theorem 11. For e > O, there does not exist an algorithm ALG such that for any possible u [0, c) for every t the fractional allocation X, chosen by ALG satisfies envy-freeness in expectation with probability greater than 1/2 and the regret of ALG oT)). The same result also holds for proportionality in expectation.
proof. W.l.o.g. assume that c = 1. The proof also holds for any other constant Suppose the underlying value distributions are Bernoulli, that we have two players and two item types, and assume T 2 2. We will consider two cases for μ² and show that no algorithm can with probability greater than 1/2 satisfy the constraints and have regret of (T)) for both of these cases of p².
First, let
1/72
0
u
and
0.5
0
1/T2
2²
1
0.5
If p or = 122 then player will not have realized value of 1 for any of the T items with probability at least 1/2. Therefore, no algorithm with probability at least 1/2. The only fractional allocation that is envy-free for both μı" = jr and μt" μ=² is the uniform random allocation. However, this allocation has regret (2(T)) for u² = 22 as the best fractional allocation when μr = =1² is the fractional allocation
differentiate between Jr" = nr and n² n12
0 0.5
0.5
This proves the desired result that no algorithm can be envy-free for μ² and have o(T) regret for both possible realizations of n² Similarly, the uniform random allocation the only proportional allocation in this example, and therefore the same result holds.
18

---

D Proof of Theorem 1
Observations 1, 2, and give that the proportionality in expectation constraints and the envy-freeness in expectation constraints satisfy Properties 1,3, and 4 respectively. Lemmas and 2 respectively give that the proportionality in expectation constraints and the envy-freeness in expectation constraints satisfy Property 2. These results combined with Lemma 3 directly prove Theorem 1.
Lemma 3. Let {{(Be(u),c)) } 1) uE(a,6)nx> be a family of constraints that satisfy Properties 3, 4, and 2. Then with probability 1 1/T,, Algorithm satisfies constraints (ee(("))ce))e and has regret of ((T2/3) ) for constraints {(Be(H") c+))
proof. First, we note that the regret of the first 22/3 steps be bounded by
-2/3_1
Σ (Y" """) (X,,))r S ST2/3 a) = O(T2/3).
(12)
By Property I, the uniform random allocation satisfies constraints (B)) ct 2 Therefore, X
satisfies the constraints for all T2/3, Furthermore, because the fractional allocation was uniform at random for the first 22/3 steps, we have that for sufficiently large T,
Pr
||<|22 S nmy nm log (4nm7) . T-1133
1/3
2 Pr Vi [n], [m]. Gs S Vnm log (Anml) - 1/33
T//3
Pr
Vi [n], [m)
2nm
T2/3
T2/3
Pr
Vi E [n]. [m]. 2
nm
2nm
T2/3
2 Pr
Vi [n], (m) >
//
2 nie log()
21 2T
(13)
where the second to last inequality is by Hoeffding's Inequality and union bound. This implies z |ell = (T3333) Because the values are drawn from Sub-Gaussian
that with probability 1 distribution, there exists constant > 0 (which depends on the distribution of the values) such that by Hoeffding's 's inequality.
Pr (Vi E [n], k E [m], |pa - -As S Gx) 2 2nme 2nme-cloge cclos
(AnmT)
clog(4nmm7)
2nm
AnmT
[For sufficiently large T]
2T
(14)
For the rest of this proof, we will assume that
||]]] < Ö(T-1133
(15)
and
Vi [m], [m]] jāsk - uutel S Eik:
(16)
which by Equations (13) and (14) happens with probability 1 - 1/T.
If K is the Lipschitz constant for this family of constraints, then by Equation (15), 2K|/e|| < Ö(T-1/3) 1/3) < "Yo for sufficiently large T. where Yo is from Property 2. Therefore, taking y 2K| in Property gives that there exists some fractional allocation X' such that
(p", y )
(a)=l O(]ee])),
(17)
19

---

and such that for every constraint 8 E [L], either vt, i2 E fi: Be(m)); + 03. X = X/2 or
)))(")),X)) 2 ce + 2K||ell11
(18)
For any μ = e, we have that || - 11 - 2||e|| by Equation (16) and the triangle inequality. By the Lipschitz continuity assumption (Property 3), this implies that for all μ E f
[B(( - Be(r I11 S [
(19)
Therefore, if Equation (18) holds for a constraint L, then for any E A te. (Be(n), = (Be(n), X - (Be(n"), (B)) + (Be()), X
= (Be(n) )e(l")), X²)rr F- + (Be(n"),
2 (Be(n"), (.x)) - -l(((()) - Bel(
[0 S X1 S 1, Vi, k]
2 (Belu"), x² - -2Klell
[Equation (19)]
ce.
[Equation (18)]
Therefore, we have shown that if Equation (18) holds for constraint L, then the fractional allocation
X' satisfies constraint (Be(u), Cx) for μ E f fee e. If Equation (18) does not hold for a constraint l, then Vii, i2 {i: Be(r(); j 0). X X Because {i: Be(x"), ); o 0} {i: Br),); o 0} by Property 4, this implies by Property that (Be(u), X')r 2 for all Therefore, we have shown that X' satisfies
()(()))))))22 for all μ E f 6, and thus X' satisfies the constraints in LP (3).
Because X is the optimal solution LP (3), we have that (X' 1), S (8,
By Equation (16), this implies that
(X' ,1) $ ||cl-
(20)
Therefore,
(Y" 1 18, 1r))" (Y" ,#"rr (x"""")++ + (X' "²"""">" - (8,
s 0 ([ell + ||e|])
[Equations (17) and (20)]
< 1/3)
[Equation (15)
(21)
Combining with Equation (12), this gives a total regret of
(Y ,,")""""0000"""""0"""""" (x',,") 0(22/33 Σ (YYH (r"",,") (X' (x,,"))))
[Equation (12)
T2/3
O(T2/8) + T- Ö(T-1/3)
[Equation (21))
O(T2/33
Lastly, must show that the constraints are satisfied by the fractional allocation used by the algorithm for 2 T2/3 This is because if Equation (16) holds, then any solution to LP (3) must satisfy the constraints (BBg(""), for all t 2 72/3 will satisfy these constraints. Recall that all of the above relies on Equations (16) and (15) holding, which happens with probability 1 1/T as desired.
and therefore the fractional allocation used by the algorithm
E Proof of Lemma 2
For proportionality in expectation, LP (1) can be rewritten the following linear program.
YH = arg max (X,1)r
s.t. X, 44 -1 -11lulla 2
Vi e [n]
Σ X, =1 Vk
(22)
In order to show that the proportionality constraints satisfy Property 2, we want to construct an X" such that
20

---

1. X' decreases the social welfare relative to Y by O(r) and
2. For every constraint i [n], either X' UAR
X 14 |mall 2 7-
(23)
I.P (22) has n constraints, one corresponding to each player. Define
|| S Y!" #4 n
(24)
S; is the slack on the ith constraint when using the optimal solution YH. Now we have two cases depending on Ei= St, the total amount of slack across all n players.
Case 1: Ei= S S m
Let X' UAR This will result in decrease of social welfare of at most 2 !ny compared to Y". To see why, note that the slack of constraint is equivalent to how much player i prefers their fractional allocation in Y to UAR. Therefore, switching UAR from YP decreases the total social welfare by S2 per player, and therefore decreases the total social welfare by Σ S, S a nry O Furthermore, X" UAR clearly satisfies the other condition because every player is treated equally.
Case 2: Ei= S ny
Intuitively, in this case we want redistribute the slack from the constraints with a lot of slack the constraints without much slack. To do this, construct X' as follows. Define
Y
S.
TCY
A.k
(25)
YP
21==1
Sy
0
By construction, we have that
n1
Aik
(26)
(=1 k=1
Because Σ S fny, we also have that
S. Se
ny
S b
(27)
Ee
Furthermore, for every S; S Y!" m4 by definition of S.. Because Mlik S this implies that
S. S >i Yd With Equation (27), this implies that Σ, b
n7
Y With Equation
S
(25), this implies that Ask S Y Finally, note that
Y.
S
ny
D. 1
[Equation (25)]
Σ k== SI
Σ
Σ/=
Sq
m
k= Mi
S
[Equation (27))
Ex= Y
Dk=1 YH
S.
[10 S b]
Y
k
Sr.
(28)
Now we are ready to construct X'. Let
X = Yill
Au +
Σ
Ark-
(29)
v=1
In order for this be valid allocation, we need that X/2, 2 which true because we showed above that A < Y.u. We also need that Ei= X/33 = 1, which follows from
n X1
n
Y
Au
Avk
Σ
au +
Σ A rk = 1.
n F=1
===1
21

---

Next, we will show that Equation (23) is satisfied for all for fractional allocation X". Starting with the left hand side of Equation (23), we have
1 X p4 72
11
M
1
y 14 D. p4
A Pkpai
||
[Eq (29)]
Th
t==1
= S, - A, +
Ap 14
[Eq (24)]
1
Σ Y=1
A 1
[Eq (28)]
n m
AvR
[aak 2 a]
n1
7
[Eq (26)
Furthermore, we can bound the decrease in social welfare between fractional allocation X' and Y
by
(Y FF)F (X', ,1)F (Y
X' p)F
A Pi
[Equation (29)
i=
b An
[aa S 6]
k1
ny.
[Equation (26)
Therefore, we have shown that X' has the desired properties, and thus the proportionality constraints satisfy Property 2.
F Proof of Lemma
For Section F only, we will assume w.l.o.g. that 1 and that b > 1. This is without loss of generality because envy-freeness in expectation constraints and social welfare are both scale invariant. Therefore, scaling every player's 's values (and mean values) by 1/a will give an equivalent problem where a = 1.
To prove Lemma 1, will show that we can transform YP into a fractional allocation X' which satisfies Property 2 through Algorithm 3. Algorithm iterates over the following types of 'envy-with-slack graphs, which track whether player prefers their allocation by at least a over another player's allocation.
Definition 6. Let create-slack graphh,, X, a)) be the subroutine which returns the directed graph with vertices N and edges generated follows. Suppose G = sreate-slack-graph(ee directed edge from i to exists in G and only if
Then
(Xi, p.) (Xv, mi) < a.
At high level, Algorithm 3 constructs 'envy-with-slack graphs with progressively smaller a. with a 2 y for all iterations. The algorithm operates on sets of nodes called equivalence classes, where every pair of nodes in an equivalence class has the same allocation. We represent the set of equivalence classes in a fractional allocation X as S(X).
Definition Let S(X) be the set of equivalence classes of fractional allocation X, where two nodes i are part of the same equivalence class S e S(X) if and only if X; Xg.
22

---

Algorithm 3 generally makes progress by either 1) merging two equivalence classes, or 2) removing an edge from the graph. We formalize this model below.
Each iteration r begins with some allocation X and slack value a". Algorithm 3 then generates from these parameters directed graph G create-slack-grape with-slack' graph for allocation X" given means As in standard graph notation, for graph G we define (G) as the vertices of G and (GG) the edges of G. Each edge e (i, E E(G") has weight w, = (Xi, (t. head in S and tail in N' S, and similarly, we use 8 (S) to represent the edges with tail in S and head in M For notational convenience, we let (i) 5 ({+)), and 8 (i) 5+ (fi)). Throughout this section, we will use the notation sw (X, 14) (X,
X ; a,),, which is the "envy-
For set of vertices S, we use 8 (S) to represent the edges with
An overview of the algorithm is as follows. each iteration, Algorithm 3 generally performs one of three operations and removes edge by decreasing a. First, if there exists equivalence class S with at least one incoming edge but no outgoing edges, then operation remove-incoming-egee transfers allocation probability from nodes in S all other nodes. If such equivalence class does not exist, then Algorithm 3 finds specific type of cycle in the 'envy-with-slack graph. If there exists some node which has an edge some but not all of the nodes in the cycle, then operation cycle-shift gives each node in the cycle half of its current allocation and half of the next node's allocation. If such a node does not exist and all edges the graph have low enough weight, then operation werage-clique instead creates new equivalence class by merging all equivalence classes that the nodes in the cycle belong to. Such a merge may lead to envy, which is removed by a call to Algorithm& 4. We define each of the three operations formally below, where each operation returns new allocation X'.
Definition 8. Let S E S(X). Define Xss = Xix for every i E S. Let remove-incomingg edge(S, a, X) be the subroutine which returns X', where
(n - 1-1S))aXS ViES
X #k
Xs
2bn Exe Xsw
and
S
Xax + X/x
ViENYS
2bn Σx XSs
Definition 9. Let C' be cycle in graph G create-slack sreate-slackggrap((uu. X, a) and next(i) be the node which points to in C. Then the subroutine cycle-shift(C, X) returns X', where
X Xik + X nixt((ikk
ViEV(C)
X = Xik
ViENNV(C)
Definition 10. Let Q clique in graph G create-slackgraapp(. a). Then the subroutine average-clique((, X) returns X', where
X Eveq X
ViEQ
1Q1
X/x X
ViENIQ
We also define two intermediary operations. Note that the arg min function may return the empty set, a singleton, or set with multiple elements.
Definition 11. Let = create-slack (1,phhu,XX.c a) with edge set E. For each equivalence class
S E S(X), let Eş arg min i (S) Wes where the size of Es may be Es Es, and let G" (N, E"). Then the subroutine find-specialccycle(,, S(X)) returns cycle C of G" where (CC) contains at most one member of each equivalence class S E S(X) (and returns no such cycle exists).
> 1. Let E'
23

---

Definition 12.
Let G = create-slack create-slack-graph(,, graph(u,, x,a) and let U
C N.
Let
distribute-equallyy (U, X) be the subroutine which returns X where
X = (1 -1- 1N-NU 3)-
Xsk
VieU
x Xik + 3 Σ XyR
ViENU
PEU
We are now ready present Algorithm 3.
Algorithm 3 Achieving Envy with Slack
Require Y 14
Let a <- 7 (e log(1bn ++* (2n] X YH, G create-slack- X , 0.
while [uu, v) E ( s.t. u. are in different equivalence classes do
if 3 8 E S s.t. (8) + 0 and (8) then
> -x++ remove-incoming iimoove-nncomingeedee$S.. xx)
>> a r+1 a'
else
t> C = findd-peccallcccleeC"" S(X"))
3 N and Ri, E (C) such that (u, i) F and (u, & then
> x cycle-shift(C., X²)
D r+1 a
else if 3 e E ((G")
s.t. We 2 4bn then
D X X"
D a rl Iont
n²
clse
D S' = ESS SNV(C)
D Q = USES
X average-Clique(Q.xX)
D avvg o"
π D Gavg create-slack-gran
X vv8) // Gavg defined for analysis only.
D X' X
D G' create-slack graph
while Ze E'''") do
>> X' remove-envy(u, X')
b G = create-slackggraph(1,, X*,0)
end while
D X X"
a+1 ng
2
end if
end if
>> Gr+1 + create-scckkgrrpppi ,r+t1)
br=r+1
end while return X
Algorithm 3 calls remove-envy, which is equivalent calling Algorithm 4. Algorithm 4 will require the following definition.
Definition 13. Let create-non-negatiiveenyy gnay be the subroutine which returns the directed graph with vertices N and edges generated as follows. Suppose G cratee.on-ngaaiieeemyyygpp... X). Then directed edge from to i' exists in G if and only if (X,, (Xv, p4)
Note that this definition is exactly the same that of create-slack X,0), except with weak instead of a strict inequality. We now present Algorithm 4.
We begin by proving some helpful lemmas. It will be convenient to define the following term.

---

Algorithm 4 Remove Envy (also referred to subroutine remove-envy(ys )"))
Require μ4, Xo
Let G < - if [e E(G"): : We < 0] =0 then
+- 0.
return X
end if
> Choose (u, v) E fe E E(G") we <0)
D U + {e' E E(G'): W(u,v") <0}
while ((,o)) < and and there does not exist cycle in G" containing (u, v) do
V.iEU.3. PEN'U,
min (3 s.t. carribute-quulll((1) (U,,,,,,,,, 3,x")) returns X' where (X,44) (X), mi)
3, 3 s.t. distribute-sqaally(U...8. returns X' where (X Mu) = (Xp, Uu)
> 1* arg (())u 3,
> X distribute-equally(U.....
U U U
G f cratte-noonngggtteeeeeerrppaaaa.
++++1
end while
if W(n,,)) then
C t cycle in G" containing vu
// Let prev(i) and next(i) be the nodes before and after in C, respectively. Vii V(C), next())
else
> X'
=x=A X"
end return X'
Definition 14. Let X be an envy-free fractional allocation for if for all i, E N,
(X,; pb) (Xv, pa) 0.
Lemma 4. Lel X be an envy-free fractional allocation for ps and let G create-slack-rraphti. X, (x) with edge set E. Suppose that there exists some equivalence class SE S(X) such that 8 (S) + 0 and 8 (S) 0 in G, and let X'
Sowp:eeeiinomineeeeeee........ X).
Let G' create-slack create-slack-grapp(u.... gr,ph(u, X', a/2b) with edge set E". Then E'I < |E
proof. We first show that if an edge E, then E'. Note that for any i such that (i, $ E.
(X, p:) (Nv, (4) 2 a
Therefore, to show that an edge (i, not in E is also not in E', it suffices to show that (X,, p4)
(X,,, uu) 2 (Xi, uu) - (u).
The subroutine remove-incoming-dgel a, X) only transfers weight from S to NYS, which implies that no node N will gain an edge to a node S. Formally,
(X,, pv) (Xi, > (Xe,pr) (X,, Si'
(30)
Every pair of nodes i E S has their fractional allocation reduced by the amount,
(X,,4) (X,, (4) = (X,,4)) (X,,14) Vi,i S.
(31)
Similarly, every pair of nodes i, E NVS has their fractional allocation increased by the same amount, so
(X. - (X,, u4) = (X,,))) (Xe, Vi,i N
(32)
Finally, observe that for any E and / NYS.
(.) - -X/s, = (KirHh)
Σ
(n (S))eess
(X
Σ
|S|a XSsKs
2bn Ex Xss
26n Σv X Sk
ke[m)
ke(m
25

---

nax
(i) - mi)
2bm Exs Xsw
kE(m]
noX
2 (x)
Σ
2n Σn XSw
kE/m]
(X,
(Xv,
a
IV
2b
where the second inequality is because (i,t) & E. Therefore, by definition of G', (1,1) & E'.
Recall that 8 (S) * in G. We will now show that 8 (S) = 0 in G'. Observe that for S and i' E SN
(v) (X(.He) (Xe) + E
|SlaXskftkk
(Xx. - Σ
(n aa SKHHER
2bn
Ex Xsk
2bn En sk
ke(m)
ke(m]
naXsHHek
= (X - (x,,140) +
2dn EE XSM
kE[m]
(XysMe) (Xi, 2b
26
Therefore, ()) & E, which implies (S) = 0 in G". We conclude that all edges in E' exist in E, and at least one edge in E. does not exist E', which implies that EE < [F..
Lemma 5. Let X be an envy-free fractional allocation for pb, and let G preate-slcck-graphle X. .x) with edge set E. Suppose that there exists some equivalence class S S(X) such that (S()) # 9 and 8* (S) = in G, and let X' (erpoveeiiiomingeeee(.......... X... Then X' is envy-free allocation for μ.
proof. Let G create-slack grackkgrrapppaa (1,, X', a 226 with edge set E'. It suffices to show that W. 2
0 Ve E F.. By Lemma 4, if an edge (f, ('))) $ F., then
(X,, pb) - (X, ps) 2 26 2.
Consider any i E S and i' E N'S.. Then there must not exist edge (i, E E by assumption.
Also by assumption, for any i, such that (i, E E, we have that (X,, p4) (Xe.u:) 2 0. By direct application of Equations (30), (31), and (32), we can conclude that (4) - (X 14) 0 as well.
Lemma 6. Let G = createslack-graphi(,... X, with edge set E. Suppose that there ex-
ists some equivalence class S E S(X) such that (S) # 0 and 8+ (*()) = @ in G, and let
X' = commoveinccoming-ddeee a, X). Then
sw(X - sw ,1) S an
2
proof. Observe that
sw(X', = Σ (X/ + Σ (X)m)
SES
SEN'S
(n - aS
(X,,1)) + Σ (8.14)
2bm k. XSK
1E5
iENYS
26

---

(X), +
E (Xi.th)
2b En Xss
iENYS
E
(Ki,
2b Σb XSM iES
N
E (X..1)
a
XskPak
2b 2b XSM
N
iES ΣΣ>
2 Σ (X..4)
Xsk
2 ② XSW
N
iES
alsl
sw(X,
2 sw(X
This implies that
Sw( (8, 1)) -ww(s'' (X',,,,, S an
2
Lemma 7. Let X be envy-free fractional allocation for μ and lei G create-slack-raaph(i X, with edge set E. Let C' = hindsppecial-cycle SXX) and suppose there exists a node such that for i, E V(C), (u, E and (u,i') & E. Let X' =cyle-shift(,,X) and let G' saace-slack-graphlee X', a/2) with edge set E'. Then EE E
proof. We first show that if edge & E, then &f |E"|. Suppose that i V(C), N, and edge (i, & E. Then
1
1
(X,, pa) (x)
(X p.)
2 (X)exx()) p1) - (Xe, pi)
2
1
1
(X m4)
(Xv, (Xv,
2
2
((x,, m4) - -Xv,
(33)
2
a
2'
Now, suppose that i, & VCC and edge (i, & E. Then
(X), (X), (4) = (X,, ms) - (Xp, ps) 2 a.
(34)
Finally, suppose that i E VCC), E (VV(C), and edge (i' & E. Then
(Xp, (X),ur) (Xp, (xi:He) (X (Xnect())s (er)
(1Xv, ((X,,,0) 14) - (X,, 1
((Xv, (X nexx(()): 12))
(35)
2 (a) + 1
22(0)
2
We have shown that if e E E', then e E E. Now we will show that there exists at least one edge such that e E E, but & E", Consider the node u described the lemma statement, and let E VCC) be some node such that i E E but (u, next(i)) & E. Suppose that u & VCC). Then
1 (Xi,, Mu) 2. (X (xnex(()) (eoat(t)=10 Ma)
(X,, (x)) (x). = (Xu:
2
((Xus (Xir)un) + ((Xus Hu) (Xnest(s)s Hu))
27

---

1
1
2
(a)
+ (0)
2
2
2
Suppose that V(C). Then
1
1
Mu) (X Hm)
(uu, Mma) + (Xnextu):HHi) Un)
(Xis Mu) (eeexttt) Mu?
2
2
1
( (Xur Ma)
(Xi: + 7 ((Xnex((w) (u) (Xeext()); Hu))
2
1
1
2 (a) + 2 (0)
This implies that (u, i) & E', as desired.
f Lemma Let X be an envy-free fractional allocation for y and let G create-slack-graph(i x,
with edge set F. Let C = find-specialccyleeG...5 ((X)) and let X' = Cycle-shift(CC, X). Then X' is an envy-free allocation for (s.
proof. Let G create- sreate-slackkgrapph/ X', a/2) with edge set E'. It suffices to show that we for e EY. By Lemma 7, if an edge (i, & E, then
(X, (X,, (4) 2 9 20 0.
Recall that by assumption, for any i, such that (i, it) E F, (Ni, - (Xp, 2 0. Suppose that i E V(C), N, and (i, i') E. Then by Equation (33),
1
(X) na) - (X, m.) 2 (X,, p4) - (X p4) 2 0.
2
Suppose instead that i, & V(C) and edge (i, E E. Then by Equation (34),
(X) (X,, Mi) (X,, ps) - (Xv, pi) 0.
Finally, suppose that i V(C), 8' E N\V(C). and edge (i', E E. Then by Equation (35),
(X,, (x) - (X),uv)
((xv, ((x,uz) - (X,, + ((xe.ue) (Xnextt)::11)
2
1
2 2 (0) + (0)
0.
Lemma 9. Let X be an fractiooa allocation for and let G = create-slackkgraphhee X, with edge set E. Let findsspecial-oyde((..(()))) and let X' cycle-shift X). Then
sw(X, sw(X',,X (x),)) < no
2
proof. Observe that
sw(X', = Σ (x),)) Σ (X).4)
(EV(C)
VEN(V(C)
1
Σ ((X,,)) (Xnext p4)
Σ
(Xi14)
2
(EV(C)
VENiV(C)
Σ
((X,,))) + (X614) -0)
Σ
(8G14
2
(EV(C)
(ENVV(C)
28

---

E
(XL)) -
E (Xc.
(EV(C)
iEN(V(C)
Σ
((x1s1s) 2
Σ ((X6)5) - 2)
(EV(C)
(ENiV(C)
Σ (x)
na
2
IEN
This implies that
sw( (W, 14) - sw ,1) - no 2
Lemma 10. Let X be an envy-free fractional allocation for μ. Let G = create-slack-graph//t X, a) with edge set E, and let Q be clique in G. Let X' average-ciquee (Q, X) and G' create-slack-graphii. X', a//)), with E' the edge set of G'. Then E' < [B]
proof. suffices show that an edge e E, then e |E'| if e Q. then edge (i, i') must be in E, as Q is clique. Suppose that i, E N and (i,2') & E. Then
(X) (X2, (4: = (x), - (Xp: pi) 2 a. Now, suppose that i E Q, E N,Q, and (i, $ E. Then
(X/.)) - X2.
1
(Xpr.H)) PEEQ
(Xe,
1Q1
191-1)
(X m4)
(Xp,pa)
[Q|
(191-1)
[1]
[Q1
n
Finally, suppose that i Q, N and (i',) & E. Then
(X), - (X(.Pu) (K),
Σ
(Xer pe)
[Q1
PEEQ
Σ (Kr, - (Xer,ux)
Q
MEEQ
(Xr,uv) - (Xi, +
Σ
(e, (X.r, .ws)
(Xpr,ss))
[Q]
(1"
1
(a + 0)
7
Q
n
Lemma 11. Let X be an envy-free fractional allocation for μ. Let G create-slackgrapp((( X, with edge set E, and let Q be a clique in G. Let X' = average-clique((. X). Then
(X), (X),,44 -a Vi,i Vi,i' N. N.
29

---

proof. First, suppose i' E NQQQ and E N. Then
(x) (x, 2
min (Xv, /2) - (Xpm, 2 0. MEN
Suppose instead that i, 1' Q. Then
(X), (Xi O.
Finally, suppose that i E Q. NQQ. Then
(4) - (X
1
Σ (Xem)u))
(Xe;
[2]
PEQQ
(X 14)
(111)
12 101--1
- (X);)1))
1Q]
[Q] -1
0 -
[Q]
-
Lemma 12. Lei G = create- create-slack-raphii X, a)) with edge set E, and let Q be clique in G. Let X' average- (Qquuee Then
sw(X, sw(X' 14) S n..
proof. Observe that
sw (X' ,1)
Σ (X) Σ (X).m)
iEQ
iENiQ
((Xi, -a) + Σ (Xi,
iEQ
VENiQ
((1,, (.) a)
iN
2 Sw( sw(X,
(X, (4) - n az
Rearranging, this implies that
sw(X, sw(X', 11) a.
Lemma 13. Let G = create-slack-graphhie X, with edge set E, and let X' remove-envy(u..X) Further let G' create--lack- graphhac X', 0) with edge set E'. Then JE" EE.
proof. First, show that if edge & E, then & E". In other words, will show that no new edges with positive envy (negative weight) are added. Observe that within the while loop, remove-envy distributes 3g- from set U to NAU. If at the beginning of the while loop 3i E U such that w, 0 for some N'U then 8,. = 0 and i' is added to U. Otherwise, by definition 8 most the minimum fraction that the set U needs give away in order create new envy edge between any node U and node E NAU. Therefore, distribute-equally cannot create new edge with positive envy by choice of Bi+, which implies that could have been created by the end of the while loop. Now, suppose that W(.v)) < 0 at the end of the while loop. Then there is cycle C' in G" containing (u, v). Then for every i, (X{, p4) 2 (4). The total set of allocations has not changed, so no positive envy is introduced.
edge with positive envy
Now, we show that there exists an edge e E such that e & F'. That is, we show that we have removed some edge with positive envy. If ((..)) = 0 at the end of the while loop, then (u, v) e E
30

---

and (u, v) & E' so we are done. Otherwise, there is a cycle in G" containing (u, v). As the overall set of allocations has not changed and (Xo,, (b,) (Xu,Hun Hv) 0, we must have
j E V(C) s.t. (u) (u) < 0 < V(C) s.t. (Xi, (Xu, < 2/. Therefore, there exists some edge (u, for i V(C) such that e E but E'.
Lemma 14. Let G create grapcck,grap(,,,.. X, with edge set E. Suppose that 4bn I (Xi, ms) - p4) Vi N.
Let X = X and define x remove-envy(j, (1, x1-1). Then for all i, (X (x) (x!-1
,ww) S +
In
proof. We first prove by induction on l that for all
S (X m4) - (Xf, u4) Vi
The base case is true by assumption. Now consider any &. By the inductive hypothesis, we have that for all i, E N, Ion S (x. p4) (x .4). Suppose for contradiction that there exists some i' E N such that Tom (X, p4) - (X,, (k:). This means that the envy of i for i' must have increased to more than during 46m in the 5th call to remove-envy, The only way for the envy of for
i' increase in remove-envy is if E U, E NAU, and B,- 0. If (X;-1 mu) (x--1 (4) S then 3;-- O. Therefore, we must have (x--1, 14) (x (.) > O. However, by our choice of B:-, i' must then be added to U before becomes envious of i'. Therefore, it is not possible for the envy of for to have increased to more than āboe in the 5th call to remove-envy.
a
We now prove the main lemma. Consider any t. One stopping condition of the while loop in remove-envy is when v(,)) = (Xi, mu) - (X,: (a)) O. Observe that U and u E NV for all iterations in the while loop. This implies that u allocation is always increasing, while v's allocation always decreasing. The increase u's utility therefore most u's current envy towards v's allocation in X--1, which is upper bounded by abn by the induction proof above. Formally,
(w) (X--1, ,u)) S (X--1 pu) (X6-1 pu))
(36)
4lm
Furthermore, over the course of remove-envy, the allocation of node u is increased at least as much as that of any other node i, i.e.
(X x
uk 2 (X) 1) Vi N, E [m].
This is because u is always member of N\U. Therefore, for any i E N,
(x) - (X--1 pe) S b. 4bm3
a
4n3
is the largest possible utility ratio between two nodes.
Again by applying Equation (36) and because b is the largest possible utility ratio between two nodes, for any i E [N]. the utility of i' for the allocation transferred from i is most b 36n in. Node i could have transferred to at most nodes during remove-envy, which implies that node i' has utility of most n & remove-envy. Therefore,
and + for all of the allocation transferred away from node during
(x) (Xf-1 ,pp 2
a 4n²
ViEN.
Lemma 15. Let G create-slack grapkkgggphhh,hh X, 0) with edge set E. Suppose that
4bn < (X,, m1) - (Xv,p4) Vi,i' E N.
Let X = X and define X remove-envy(u. Xt-1), Then for all i, and for all e S n²,
sw(X", 11) sw(x', ,p) <
31

---

proof. Consider some t. By Lemma 14 we know that
(X) p4) (x!-1 p4)
ViEA N.
4n
Applying the above once for each node, we obtain
sw (X (1) Σ (X)
IEN
2 (x1, 4n
iEN
2 sw sws8 (Xt-) [1) n1
4n
Rearranging, this implies that
sw(X 1-1 .4) sw(x' , 1e) -
4n
Because l S
n²? sn?,
we therefore must have
sw(X0, 11) -sw sw(X ,1) -
na
4
Lemma 16. Let G create-slack-graphii x,a) with edge set E. Suppose that for S E S(X), if (S) & 0, then 8+ (5) Further suppose that
(Xi,4) (X) Vi EN
Abn
Let X X and define X remove-envy(y,, X(-1). Finally, for S n² let G' create-slack create-slackgraap((.... X 2) with edge E'. Then |E' < 1E%.
proof. It suffices to show that if an edge (i, & E, then (i, f') & E., By Lemma 14, in each call to remove-envy. the utility of i for the allocation of decreases by at most an Therefore,
(xt, pb) - (xP, m.) 2
4n 4'
Again by Lemma 14, in each call to remove-envy, the utility of for the allocation of i' increases by most 4ms- Therefore,
(X) pa) (X&, H4) S e.
4n 4n
Putting both equations together, we have
(X (X), 2 (X2, 14) 4
(1x2) (18,,1)) 14)
Ok
4n
(X9, 14) (XX, m4) a
4n
2
as desired.
Lemma 17. Let X" remove-envy(j,X)) Then (S(X') (S(X).
proof. suffices show that no equivalence class S S(X) becomes smaller (i.e. strictly loses members) during remove-envy. First, suppose for contradiction that S first becomes smaller during the while loop during iteration r. Then in iteration r, it must be the case that S n U A and S (N) * 0. otherwise the allocation of each member of S would have changed by the same amount. Furthermore, must be the case that in iteration r, 8,- > otherwise no allocation would have been transferred. In iteration r, consider some i (S and i' e (Sn (NVU)). Then 3 0.
32

---

as begins iteration r with zero envy towards i'. Because B1- I min; Sr, this means 3,- S O. which a contradiction. Therefore, no equivalence class S becomes smaller during the while loop. To conclude the proof, we observe that in the cycle elimination step after the while loop, the total set of allocations remains the same, which implies that the set of equivalence classes remains the same as
well.
L
We are finally ready to prove Lemma 1.
Proof of Lemma I. We first prove by induction that every iteration r starts with an envy-free allocation X". The base case is satisfied because X = Y", and Y is envy-free by definition. Now, suppose that the inductive hypothesis holds for all iterations up to and including r. We will show that iteration r r+1 1 starts with an envy-free allocation. If X = X", then we can directly invoke the inductive hypothesis for iteration r. Otherwise, suppose that remove-incoming-eeee Algorithm 3. Then by Lemma 5, iteration + 1 starts with an envy-free allocation. Suppose instead that cycle-shift was called in iteration r. Then by Lemma 8, iteration r + starts with an envy-free allocation. Finally, suppose that average-clique was called in iteration r. Then the remove-envy is called repeatedly as long as there exists an edge with negative weight in E(G"). By Lemma 13, each call to remove-envy removes edge with negative weight from E("",, ), and adds new edges with negative weight. There are a finite number of edges in F(G"), so this loop terminates. Therefore, iteration starts with envy-free allocation.
was called in iteration r of
Next, we prove that in every iteration, either an edge is removed from the envy-with-slack graph, or the number of equivalence classes decreases. Formally, for two iterations and r + 1, we prove that either
1. [E( > [B(G++1) or
2. L(G') 2 |)) and [S(X)] [S(X*+1))
If rermove-incooinngeeee edge is called in iteration of Algorithm 3, then by Lemma 4 we have EE(
|F(G++1)] If cycle-shift is called in iteration then by Lemma 7 we have |F(G")| > G(
Ie E F(G") s.t. We 2 abn then e E F(G")) but e & F((G++1). Furthermore, e' & F(G)), then e' & E(G as X X Therefore, we have |E(G") > |E(G++1)).
Finally, suppose average-clique is called in iteration r on clique Q. Recall that G
create-slack-graphl average-clique(), a²)) ). By Lemma 10, we know that [E(G")] > [E(G*V)]. The number of edges in E(Gav8) is at most n² so remove-envy will be called at most n²
times by Lemma 13. Because average-clique was called, we know that We < a" Ve E E(G"). By Lemma 11 with o" 4bn
4bm+
(X (u) - (X ,.)) 2 abm
Vi,i'
4bn
Therefore, we can apply Lemma 16 with a av to conclude that [E(G++I)| I |E(G < [E(G")]- Finally, observe that because C' included members of at least two equivalence classes, the operation average-clique strictly decreased the number of equivalence classes. By Lemma 17, operation remove-envy does not increase the number of equivalence classes. Therefore, |S(X")
|8(X++1)] ].
We now prove that the algorithm terminates with an X" which satisfies Proposition 2. Each iteration either removes edge merges two equivalence classes. Because the maximum number of edges is n² and the number of equivalence classes is n, Algorithm terminates in at most n² iterations. We need to show that Algorithm 3 terminates with a" 2 y. If an iteration does not call remove-envy, then edge is removed and a=*1 a² r does call remove-envy, then a r+1 ax" There can be at most n such iterations which call
4bn4 There can be at most n² such iterations. If an iteration
2n
remove-envy between every iteration which does not call remove-envy, for a total of at most n iterations. Therefore,
a² (4b (2n)m² en log (bb + log(2n)
a
Choosing og = 7 re" lo (4 +n (n)( thus implies that ar 2 for every iteration r if 7' (e" log(1bn")+n) log(2n)) < 1. Therefore, we set 70 en? log( = log(2n).
33

---

Finally, we need to show that Algorithm 3 does not significantly decrease the social welfare. By Lemmas 6, and 12, we know that each of the operations iomove-incoming-eeee average-clique change the social welfare by at most (()). Each of these operations is called at most n times. Each of remove-incoming-edg. and sycle-shift are called most once for each edge, or at most n² times. Operation average-clique is called at most times for each edge, or at most n times. Finally, Lemma 15 bounds the total social welfare loss from all calls to remove-envy between any two calls to average-clique by O Therefore, sw(Y", uu) sw sw(X", μ4) 0(7), desired. O
cycle-shift, and
34

---

G Proof of Theorem
proof. Let a = 1, b = 3, nt 2, and m 2, and assume that the distributions values are all normal distributions with variance 1. For n. = 2. envy-freeness and proportionality and therefore we will focus on the former. Define = T-1/3, We will prove the desired result by contradiction. Assume there exists an algorithm ALG such that for any Jr E [a, bj2x2, the probability that the algorithm satisfies the envy-freeness constraints and has regret of less than log(T)
equivalent,
T2/8 is least
1 1-1/1 1/T.
Consider the following two matrices.
2
3
2
3
12 =
1+E
Define P1 as the distribution of the full history Hr when using algorithm ALG when μ p1- Define Pg as the equivalent distribution when μ U2-
We will proceed according the following proof sketch. First, will show that if Jr j41, then ALG with constant probability allocates ( items of type 2 to player (Lemma 18). We next upper bound the total variation distance between Pj and Pz. When two distributions are sufficiently close in total variation distance, then event that has constant probability under one distribution also has constant probability under the other distribution. Therefore, Lemma 18 and the closeness in TV distance of P1 and P2 together imply that if μ= = 122 then ALG with constant probability allocates ((T2/3) items of type 2 to player 2. When ALG allocates ((T2/3) items of type 2 to player then ALG cannot satisfy the envy-freeness constraints for μ22 Therefore, the previous two sentences together imply that with constant probability, ALG will not satisfy the envy-freeness constraints for all & when f μ2, which is a contradiction.
Lemma 18. Using the notation defined above,
Ep, [N < 2/3
and
T2/3 log(T))
Pr P
X
< 1/8.
(37)
Intuitively, both equations in Lemma 18 bound how many times an item of type 2 is allocated to player 2. The first equation bounds in expectation while the second equation bounds elements of the fractional allocations X The proof of Lemma 18 is given in Appendix G.I.
Lemma 19. Using the notation from above,
KI,(PI, P2) = Ep NZ) KT. (N1, +
proof. Define fl as the probability density function (pdf) of A (((())) 1) and fa. as the pdf of (((22)a 1). We let fx(m..)) be the pdf normal distribution with mean and variance o².
For any history Hy = {Kkg ig, ve)) recall that X is the fractional allocation chosen by ALG at time given history H4, Then have that for any HT
T-1 II 1=0
PI(H))
x! K
f. Fikk(( (vi))
The 1/m term comes from item f having 1/m probability of being of type kg. The X X is the probability that ALG allocates the item of type hn to player i, at time and finally f1, (vx) the probability of seeing value ei given that the item of type hi was allocated to player it Similarly, we have that
T-1
P2(HT)=
II
- x m
X (vt)
1=0
35

---

Therefore, we have that
(H(HT)
KL(P1, = EH
log
P2(HT)
II m
X!
be Lake (ike (1z))
E
log
I de lake (wb)
(Frede (24)
log
(Juch (w+)
Picks (1t) 1=0 Phiks (vx)
log
(N((11)(VR))
=EHyoP
log
II
(N(1+4.)(11)) ((11,)))(2222)
[N(L.)((V))
log
[N(1+e,1)(14))
(1)
(NIUHeLs(ON)) )
(N
EHT
1 ((()))))(222)) log
1 ((()k))=2222) E log (vcaalle)
)
EHtoP
1 (2))) BV-A(U,)) log fN(A))())
I (N(I+))()))
EH
Σ EHapP [166.)))(222) (N(, + 1))]
(L( + EHT
1 (22.))))222))
KLL 1),N(1 + 1))
[N2]]
We can use Lemma 18 and Lemma 19 to bound the KL-divergence between Pt and Pa by
Ep, [N 1
KL(P,, P2) = Ep, N KL.
(38)
We next need the following result from probability theory that is consequence of the Bretagnolle- Huber inequality.
Lemma 20, For any two probability distributions p and q defined on the same space and for any measurable event F in this space,
P(FC) q(F) > ze KL(p.g)
proof. For any probability distributions p and q, we have by the Eeltagnoll--Huber incquality that
drv 9) $ 1
1
kL(p.9)
2
36

---

For any event F,
(p) 2 -
((F) ((F) = =1 1 - (FF).
Combining the above equations gives that
p(F + ((F) 2 2
KK(pp.]
(39)
Taking p = Pi, P2 and F = - X <
T2/3
in Lemma 20, we have by Equation (38)
(T)
that
Pr P
--1
X
T2/3
+ Pr F3
X V
T2/3
1
-K((P. 2 1/4.
(40)
log (T)
log(T))
2
Combining Equation (37) with Equation (40) gives
2 log(T)
Pr
Σ
X
2 1/8.
(41)
If Io X <
TT then there must exist some time f such that X S log(T)
72/3
T 1/3
If X S T-1/3
log(T)
then player 2's envy in expectation at time for player 1 under #22 (for sufficiently large 7) is
X + (1 + X
X + + = (1 x22) (1 (1 + X 1 X +
= 2 2x 21 (1
2 E - 2-222 +
21 27 1/3 (0-113311+)) (1++
2
log(T)
2T 2T 1/3-1/3(1 + 1T
-T
log(T')
0,
implying that X does not satisfy the envy-freeness in expectation constraints under ura. Therefore, Equation (41) implies that
T2/3
Pr(EFE for μa not satisfied) 2 Pr P22
Σ
X
> 1/8.
(42)
lTg(T)
This contradicts the assumption that ALG satisfies the envy-freeness in expectation constraints for H2 with probability at least 1/T when μ* = 122.
G.1 Proof of Lemma 18
proof. Define E as the event that the algorithm ALG satisfies the envy-free expectation constraints
for μn and has regret less than T2/8
Tng[7] for μ²" μr By assumption, Prp, (E) 2 1/T.
If μ² P1, then the social welfare maximizing envy-free allocation is
yP 0 1
1 0
Furthermore, a fractional allocation X satisfies envy-freeness in expectation for μr only if
X + X 1.
(43)
Therefore, for any X that satisfies envy-freeness in expectation for P1, the regret at time is (Y 4²) (x*, p²)F 4- -2x 3x12 + X X
37

---

- (2(1 ((1-x2)) (2(1-22)) +31 x22) + + X222
--14 X21 +
2 X-2
[Equation (43)
This implies that the regret when μ = μ1 of ALG when ALG satisfies envy-freeness in expectation for μn is
T-1 E(x* p0)
T-1
T (YM "Y"(",,))) F
X
1
1=0
T2/3
By definition, under event E, the regret of ALG for μr μi is at most log(T) and ALG satisfies the envy-freeness in expectation constraints for μn, Therefore, the previous equation implies that under event E,
T2/3
Σ X
(44)
ITg
Recall that N2. is the number of times item of type 2 is allocated to player 2. Equation (44) implies that
T2/3
Ep [N ES = Ep.
X
I
log(T))
This implies that for sufficiently large T,
Ep, [N = Ep, [
Pr((E) + Ep, Pa
P1
P1
< Ep. [N
E +
T
T2/3 log(T)
+1
$ 72/3
(45)
Equation (44) also implies that for sufficiently large T,
T-1
T2/3
Pr
X
2
21 > 7/8.
(46)
log(T)
R
T
Taking the complement of this equation proves Equation (37).
38

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our main claim is a saplore-hen-comeee algorithm which achieves ((72/3) regret while maintaining envy-freeness or proportionality in expectation. In our body, provide an algorithm that does so and a proof sketch, with the full proof in Appendix D.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of our results are discussed in the discussion section of the
paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex. system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
39

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions for the main theoretical results are clearly stated in the model section and the theorem statements. Proof sketches of the main results appear in the body, while formal proofs are included in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Thcorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
This paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
40

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This paper does not include any experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cr cc/ for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: hatooo//c/guideeeddeuuuiiiiii http///oeesiiiiiiooooooooooooooe
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [NA]
Justification: This paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
41

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This paper does not include any experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: : httppp/ceeppppeeecccccccccieeeie
42

---

Answer: [Yes]
Justification:
All conditions in the code of ethics are met.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discusses positive societal impacts in applications like food alloca- tion. There are no (plausible) negative societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper does not include any datasets or trained models that can be misused.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring
43

---

that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This paper does any existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
44

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: This paper does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
45


Reviews:
[{"review_id": "CQc9Fvw5GR", "reviewer": "Reviewer_Mvzr", "summary": "In this work, the authors consider the problem of maximising the total utility in online fair allocation settings, where: \n(i) T items having types in set [m] arrive online in T distinct rounds; (ii) the value $V_{i}(t)$ that each agent $i$ assigns to each item $t\\in [T]$, when its type is $k$, is independently drawn from a sub-Gaussian distribution with unknown mean $\\mu_{i,k}^*$; (iii) for each item that arrives online, its type is known, and based on this information and previous observations, it must be irrevocably assigned to some agent; (iv) the value $V_{i}(t)$ of each item $t$  can only be observed after it has been assigned, and this information allows the estimation of the unknown probability distributions as $t = 1, \\ldots, T$ varies.\n\nThe authors design an Explore-Then-Commit algorithm that maximises the total utility of the various players over $T$ rounds, with a regret of the order $\\tilde{O}(T^{2/3})$, where the maximisation is constrained by achieving fairness properties (envy-freeness or proportionality) in expected value, with high probability.", "questions": "No questions.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-This paper introduces an interesting setting of online fair allocation, where techniques derived from bandit algorithms are applied to the case where valuations are distributed according to unknown distributions.\n-The approaches considered in Lemmas 1 and 2, which characterise fairness properties robust to small uncertainties in the underlying distribution, are interesting and novel.\n-The paper certainly required a considerable technical effort.", "weaknesses": "I believe that the results could be written and presented more effectively (see the major comments below). Another minor criticism is that, although the results provided in Lemmas 1 and 2 are quite novel and there has been a considerable technical effort in writing the complete version, the results obtained are somewhat expected within the field of bandit algorithms and follow standard approaches.\n\nMajor comments:\n\n-It should be highlighted from the beginning that the allocations returned by the algorithm are envy-free in expectation, but with high probability (that is, not always).\n-The matrix notation could sometimes be avoided in favour of explicitly listing the various constraints.\n-It would be clearer to present the main algorithm right from the start and explain informally how the various properties come into play.\n-The fact that the presented LP has infinite constraints is mentioned in the conclusion. I suggest providing more details in the technical section.\n\nMinor comments:\n\n-The acronyms efe and pe are not defined (despite clear from the context). \n-Remark 1: specify that the rows different from i and i' are composed of zeros only.\n-Claims of Lemma 1 and Lemma 2: satisfy -> satisfies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> I believe that the results could be written and presented more effectively (see the major comments below). [...] -It should be highlighted from the beginning that the allocations returned by the algorithm are envy-free in expectation, but with high probability (that is, not always). -The matrix notation could sometimes be avoided in favour of explicitly listing the various constraints. -It would be clearer to present the main algorithm right from the start and explain informally how the various properties come into play. -The fact that the presented LP has infinite constraints is mentioned in the conclusion. I suggest providing more details in the technical section.\n\nThank you for your helpful comments! We will try to incorporate your presentational comments into the final version of the paper to make the exposition clearer. We will make sure to explicitly clarify that the algorithms are envy-free with high probability (in fact, no algorithm can do better than that and still have sub-linear regret). We will also add more discussion of the LP with infinite constraints near the algorithm and make it clear that it is still possible to find the solution in polynomial time.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5zbCiOBB5I", "reviewer": "Reviewer_MmvH", "summary": "The authors study an online fair division problem where items arrive online and need to be assigned to agents to maximize welfare while satisfying one of envy-freeness or proportionality. The novel consideration in their model is that the item valuations are drawn from an unknown distribution. They approach this as both a learning problem as well as an allocation problem. They provide a simple algorithm with small regret compared to an algorithm that knew the distributions beforehand. They also prove several structural results regarding their model.", "questions": "Is it possible to achieve non-trivial regret in the setting where the valuations of the agents are not independent? In the motivating example of the food pantry, if a delivered food item is of bad quality, the agents might all lower their valuation of this item together.", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The model is quite interesting, as are their results. The proofs are involved, and might be of independent interest.", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Is it possible to achieve non-trivial regret in the setting where the valuations of the agents are not independent? In the motivating example of the food pantry, if a delivered food item is of bad quality, the agents might all lower their valuation of this item together.\n\nThis is definitely an interesting extension. By linearity of expectation, we would expect that correlation between arms does not change the regret of the algorithm. Similarly, because the fairness constraints are linear, correlation between players would probably not affect the envy-freeness in expectation constraints. However, the correlated arms could potentially allow the algorithm to learn faster (have lower regret) if the algorithm can extract information from the correlation.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sjiRQn8DEK", "reviewer": "Reviewer_V1uC", "summary": "The paper studies online fair division of indivisible items, where items arrive one at a time, and each item must be permanently assigned to a player upon arrival. Player utilities are initially unknown and must be learned via bandit-style feedback: there are a finite number of types of goods, and each player’s value for a good of type k is drawn independently from a distribution D_k. The authors aim to maximize utilitarian welfare (the sum of utilities) while satisfying a hard constraint of either envy-freeness in expectation (EFE) or proportionality in expectation (PE).\n\nEFE and PE are evaluated with respect to the randomized allocation on each time step. That is, before observing the type of the new item, the learner proposes a randomized allocation X_t which determines how the item will be allocated for each possible type. Each X_t is required to satisfy the fairness constraint (EFE and PE), not the cumulative realized allocation. I initially found this rather unintuitive, but the authors effectively justify this choice by showing that:\n1. Any EFE algorithm achieves realized cumulative envy at most $\\sqrt{T} \\log(T)$, while optimal is at least $\\sqrt{T}$.\n2. EFE at each time step does not cause any welfare loss compared to only requiring EFE at the end.\n\nThe main result is a simple explore-then-commit algorithm which is EFE or PE while achieving regret $\\tilde{O}(T^{2/3})$ wrt welfare. \n\nAlong the way, the authors prove that the EFE and PE constraints satisfy the following property: either all players receive the same allocation, or the constraint can be satisfied with slack. This novel result formalizes the intuition that the “hardest case” for fair division is when all agents have the same utilities. EFE/PE can trivially be satisfied in that case by the uniform allocation, and in all other cases, EFE/PE can be satisfied with slack.", "questions": "Do you agree with my criticisms of the food bank analogy? Is there a different real-world situation that you believe is captured by your mathematical model? More broadly, do you believe that your mathematical model provides real-world insights, and if so, what are they?\n\nBelow is feedback that you're welcome to take or leave. I don't expect responses, even though some are phrased as questions.\n1. I would suggest naming Property 2 so that I don’t have to keep calling it the either-uniform-allocation-or-slack property :)\n2. “This distribution is independent of both player i’s distributions for other item types and other players’ distributions.” Distributions can’t really be independent; I think this should state that samples from those distributions are independent.\n3. “Intuitively, this is equivalent to assuming that players have non-zero values for all item types and that their values have a finite upper bound.” I don’t think this is quite right. Assuming non-zero values would just require mu_{ik}^* > 0. I would describe this assumption as saying that the distribution means are “well-conditioned”.\n4. Definitions 1 and 2: mu_i^* is a vector, right? I don’t think this was ever explicitly defined. (Only mu^* and mu_{ik}^* were, I think.) The definitions are also missing “for all i”.\n5. “proof” should be capitalized at the start of proofs\n6. Why not just use gamma_0 in Property 2? Why have for all gamma < gamma_0?\n7. Is it intentional for the “2” in C_{P2} to be a hyperlink to property 2?\n8. Consider mentioning the actual value of (or a bound on) gamma_0 is for each property?\n9. For readability in Algorithm 1, consider writing indicator variables as \\mathbb{1}(stuff) instead of \\mathbb{1}_{stuff}.\n10. The notation “\\mu in \\hat{\\mu} \\pm \\varepsilon” is non-standard to my knowledge. Consider “\\mu in [\\hat{\\mu} - \\varepsilon, \\hat{\\mu} + \\varepsilon]”\n11. I found lines 154-178 to be quite compelling and and also quite important. Consider making this its own subsection? And maybe even including some of the Theorem statements from Appendix B?\n12. I really like lines 323-330.", "limitations": "The authors thoroughly discussed the technical limitations of their work, but did not discuss what I see as the greatest limitation: the weak motivation of the problem and the potential lack of real-world insights.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The presentation is clear and accessible. Although some of the modeling choices felt initially unintuitive, the authors did an excellent job of justifying those choices, as discussed above. The main result is satisfying, both in terms of the simple explore-then-commit algorithm and the regret bound. Essentially, the authors successfully solved the problem they chose to study.\n\nI found the either-uniform-allocation-or-slack property (and the result that EFE and PE satisfy it) to be quite interesting as well. This result captures an important intuition in a simple way. The authors argue that this property may be of independent interest, and I agree.", "weaknesses": "Although I think the problem is reasonable and meshes well with prior work, I question whether the mathematical model has any real-world relevance. The authors use a running example of a food bank with multiple branches, with the idea that unpredictable perishable donations must be allocated immediately and fairly among the branches. I have several problems with this analogy:\n1. Surely food banks wish to allocate according to need without worrying that one branch might “envy” another if the second branch simply has higher need?\n2. The paper assumes additive utility, and each branch’s utility would be extremely non-additive (no one needs infinite cereal).\n3. It’s hard to imagine the donations being so unpredictable.\nTo be clear: I’m not claiming that a mathematical model must perfectly match reality in order to provide real-world insights. But this paper’s model seems only tenuously connected to the real-world scenario that is used as motivation. If the authors have further justification for the food bank analogy, I would be interested to hear it.\n\nTo me, the most compelling story in this paper actually centers on the either-uniform-allocation-or-slack property. The authors establish this intuitive but nontrivial property, and demonstrate how it can be applied in a bandit context. I can easily imagine this property being useful for other fair division problems that might have more real-world relevance.\n\nThis is more minor, but I think the citation below is quite relevant and should be discussed along with Benadè et al.\n\nHakuei Yamada, Junpei Komiyama, Kenshi Abe, and Atsushi Iwasaki. Learning fair division from bandit feedback. International Conference on Artificial Intelligence and Statistics, 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for all of your helpful feedback! We will make sure to incorporate your suggestions into the final version. Below, we address your questions about the motivating example.\n\n> Do you agree with my criticisms of the food bank analogy? Is there a different real-world situation that you believe is captured by your mathematical model? More broadly, do you believe that your mathematical model provides real-world insights, and if so, what are they?\n\nWhile this paper is primarily a theoretical contribution, we do believe that the food bank analogy is a reasonable application, and we would like to provide some further justification for this use case.\n\nIn online fair division, the food bank redistribution problem is a canonical example that has been studied extensively theoretically and in practice. In fact, a recent work [1] describes a partnership with a program in Indiana that redistributes \"rejected truckloads of food\". The program, known as \"Food Drop\", allocates 10,000+ lbs of rejected food per month to food banks.  As in our setting, the rejected food is an online and unpredictable process, and therefore this application requires an online algorithm. [1] focuses on practical algorithms that allocate the food fairly among the different food banks, and they use envy-freeness as the fairness metric. [1] does not discuss how to incorporate feedback/learning into the fair algorithms, which is one of our main contributions.\n\n> Surely food banks wish to allocate according to need without worrying that one branch might “envy” another if the second branch simply has higher need?\n\nIn the aforementioned application of online fair division (which explicitly aims for envy-freeness), there are many locations that all have relatively equal need. Similarly, we are assuming that all players (food banks) start with the same amount of need, which can for example be achieved by first normalizing by number of customers. With that in mind, envy-freeness can be seen as preventing situations where the need of a food bank aren't met when it was possible to meet them. For example, if one food bank needs tomatoes and another doesn't, allocating the tomatoes to the former food bank wouldn't create envy, whereas allocating them to the latter (thereby not meeting the needs of the former) would.  \n\n> The paper assumes additive utility, and each branch’s utility would be extremely non-additive (no one needs infinite cereal).\n\nThis is an excellent point. Additive utility is a standard assumption for online fair division due to the difficulty of studying non-linear utilities — unfortunately, even in online fair division without learning, there is not much previous work analyzing non-additive utilities. Studying non-additive utilities in online fair division would certainly be an interesting problem. That being said, if donations are delivered at most once a week and all of the donations are used between deliveries, then additive utilities may actually be a reasonable assumption.\n\n> It’s hard to imagine the donations being so unpredictable.\n\nWe expect that donations to food banks are pretty random; for example, grocery store donations depend on what is left at the end of the day, which is highly variable. However, there also exists an equivalent way to phrase our problem that does not involve unpredictable donations. Instead of receiving an item of a random type at each time as in our paper, we instead receive a (non-random) bundle of items at each time that has an equal amount of all item types. For example, instead of there being 1/2 chance of receiving a pound of apples and 1/2 chance of receiving a pound of oranges, we could instead have 100% chance of receiving 1 pound of apples and 1 pound of oranges, which can be allocated to the same or different players. This formulation is actually equivalent to our problem due to the linearity of expectation, and the exact same algorithms and results hold.\n\nWe hope the above discussion helped clarify your concerns with the food bank motivating example. If you found this discussion helpful, we would also be happy to include more discussion of the application in the final paper.\n\n\n[1] Marios Mertzanidis, Alexandros Psomas, and Paritosh Verma. \"Automating Food Drop: The Power of Two Choices for Dynamic and Fair Food Allocation.\" arXiv preprint arXiv:2406.06363 (2024).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all the reviewers for their time and comments! We respond to specific comments in the individual rebuttals below.

Shortly after submitting our paper, we found a simple lower bound which shows that for our setting, no algorithm can do better than the ones we presented. We plan to include this in the revision and we believe the new result will strengthen the paper. We include a brief discussion here in case the reviewers are interested, but please feel free to ignore this section if not.

A weakness of the current paper (as acknowledged in the discussion section) is that perhaps a more sophisticated algorithm such as UCB or Thompson Sampling would be able to achieve a better regret of $\tilde{O}(\sqrt{T})$. However, we are actually able to show that $\tilde{O}(T^{2/3})$ is the best that any algorithm can do with a very simple example, given below.

The example and informal proof is as follows. Suppose there are two item types and two players. In this case envy-freeness and proportionality are equivalent, and therefore we will focus on the former. Consider the following two value matrices (with rows = players, columns = item types).

$\mu_1 = \\begin{bmatrix}
        2 & 3 \\\\
       1 & 1 
        \\end{bmatrix}$

$    \mu_2 = \\begin{bmatrix}
        2 & 3 \\\\
        1 & 1 +T^{-1/3}.
        \\end{bmatrix}$

We can show that no algorithm can with probability $1-1/T$ achieve regret of less than $\tilde{\Omega}(T^{2/3})$ and satisfy envy-freeness in expectation for both of these distributions. First, note that the expected social welfare maximizing allocation for $\mu_1$ is to give all items of type 1 to player 2 and all items of type 2 to player 1. On the other hand, any envy-free allocation for $\mu_2$ must give $\tilde{\Omega}(T^{-1/3})$ fraction of items of type 2 to player 2. This implies that if an algorithm is unable to distinguish between $\mu_1$ and $\mu_2$, then either the regret will be $\tilde{\Omega}(T^{2/3})$ for $\mu_1$ or the algorithm will not be envy-free for $\mu_2$.

Therefore, any algorithm that has regret of less than $\tilde{\Omega}(T^{2/3})$ and satisfies envy-freeness for both $\mu_1$ and $\mu_2$ must distinguish betwen $\mu_1$ and $\mu_2$. The only way to do this is to allocate at least $\tilde{\Omega}(T^{2/3})$ items of type $2$ to player 2. However, this will result in regret under $\mu_1$ of $\tilde{\Omega}(T^{2/3})$.

A more rigorous version of this argument using standard techniques for lower bounds in multi-armed bandit problems would be included in the final paper.

Meta-review: The paper analyzes an interesting setting on online allocation constrained to return envy-free allocations. The setting is interesting and novel. The adopted techniques are also interesting and require non-trivial effort. Results are relevant. The presentation of the paper can be improved by a better organization of the content and a more detailed discussion about some of the assumption (see, e.g., additivity).
Decision: Accept (spotlight)