Honor Among Bandits: No-Regret Learning for Online Fair Division

Authors: ariel d procaccia
benjamin  schiffer
shirley  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 23:06:02

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.

Main paper: 
 introduction: 
 Fair allocation of indivisible goods is a fundamental problem with a wide range of applications; implemented algorithms for this task have been 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 a 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 are 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 a slightly weaker notion, which requires only that each of the n players receive at least a 1/n fraction of their total value for all items. Finding a solution which is envy-free or proportional is often interesting in and of itself, as can be seen from many previous results in fair division [7, 30, 12, 3] . In cases where there may exist multiple envy-free or proportional allocations, however, a natural goal is then to find the best solution among such allocations [13] . In our work, we evaluate the quality of a 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 a probabilistic approach to 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 a 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 a 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 if and only if that player receives the item. This problem can be viewed as a 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 a 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 fairness 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.Our main result is that there exists a simple optimization-based explore-then-commit algorithm that achieves Õ(T 2/3 ) regret and maintains envy-freeness in expectation (Algorithm 1 and Theorem 1). A variant of the same algorithm achieves Õ(T 2/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.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 on fundamental properties of these fairness notions. One observation is that our fairness 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 envyfreeness, and the combinatorial algorithm that achieves it (Lemma 1) should be of independent interest to researchers in fair division.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, or 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 our 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 constraintsinstead, 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 multiarmed bandits with constraints. One notion of fairness in multi-armed bandits is 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 is not pulled with higher probability than a better arm. Their definition of fairness is actually incompatible with maintaining envy-freeness (or proportionality), because maintaining envy-freeness may require allocating an item to a player with lower value to prevent envy. Another common fairness constraint in multi-armed bandits is that every arm receives a minimum fraction of pulls [10, 11, 20, 28] . This notion of fairness is also not compatible with envy-freeness because the optimal envy-free allocation may never give a 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 envy-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 a single constraint and specifically show that if there is positive slack in the optimal solution, then Õ(T 1/2 ) regret is possible. If there is zero slack, however, their algorithm only achieves Õ(T 2/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 a 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 our model as we consider constraints that must hold at every time step. Finally, there is a branch of multi-armed 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 a safety gap that fairness constraints such as envy-freeness may not guarantee [27] .Practical Motivation. Mertzanidis et al. [25] apply online fair division algorithms through a partnership with a 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 or 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.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 explore-then-commit algorithm which achieves Õ(T 2/3 ) regret while maintaining envy-freeness or proportionality in expectation. In our body, we 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 in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in 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.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
model: 
 In this section we introduce our basic setting and terminology.Suppose we have a set of players N = [n] and a set of object types M = [m]. Given a set of T indivisible items, an allocation A = (A 1 , ..., A n ) is a partition of the T items among the n players, where player i receives the items in A i . In our model, we assume that every item j has a type k(j) ∈ [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 a sub-Gaussian distribution with mean µ * ik . Player values are assumed to be independent across both players and items. We will often refer to µ * i as the vector of mean values for player i. For a specific item j, we denote player i's value for item j as V i (j), and similarly, player i's value for their allocationA i as V i (A i ) = j∈Ai V i (j). The (utilitarian) social welfare of an allocation A is sw(A) = n i=1 V i (A i ).We consider algorithms in the following online setting. At each time step t ∈ [T ], an item j t of type k t arrives, where k t ∼ D, for some known distribution D supported on [m]. We will assume that D = Unif([m]), 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.1. The algorithm observes the item type k t , and must then immediately allocate the item j t to a player i t , at which time the algorithm observes that player's value V it (j t ). Note that the algorithm does not observe any other player's value for item j t . The high-level goal is to allocate these items in a manner that maximizes the social welfare of the final allocation of all T items. We denote X ∈ R n×m as a valid fractional allocation if i X ik = 1 for every k ∈ [m]. One valid fractional allocation we will often refer to is the uniform at random allocation (UAR), where every entry is 1 n . At every time-step t, before observing k t , the allocation algorithm ALG takes as input the history H t = {(k t ′ , i t ′ , V i t ′ (j t ′ )) : t ′ < t} and returns a fractional allocation X t = ALG(H t ), where (X t ) ik represents the probability of allocating the item to player i if the item is of type k. If the next item is of type k t , then the algorithm allocates the item randomly among the n players according to the distribution induced by the k th t column of X t , i.e. (X ⊤ t ) kt . Therefore, the t th item is allocated to player i with probability (X t ) ikt . We denote the final realized allocation that ALG returns as A(ALG), and the corresponding partial allocation up to time τ as 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 ≤ µ * ik ≤ b. This assumption is necessary because if we allow the means of values to be arbitrary close to zero, then it can be impossible to achieve regret of o(T ). This is formalized in Theorem 11 in Appendix C.2.We will primarily use two metrics of fairness to evaluate an online allocation algorithm ALG: envyfreeness in expectation and proportionality in expectation. Both are defined below. For two vectors x, y ∈ R n , we use ⟨x, y⟩ = x • y to represent the dot product of the two vectors. Definition 1. Let X t = ALG(H t ) be the fractional allocation used by algorithm ALG at time t given history H t . Then ALG satisfies envy-freeness in expectation (EFE) if for all t and all H t ,(X t ) i • µ * i ≥ max i ′ ∈[n] (X t ) i ′ • µ * i for all i. Definition 2. Let X t = ALG(H t )be the fractional allocation used by algorithm ALG at time t given history H t . Then ALG satisfies proportionality in expectation (PE) if for all t and all historiesH t , (X t ) i • µ * i ≥ 1 n i ′ ∈[n] (X t ) i ′ • µ * i for all i.Intuitively, envy-freeness in expectation is equivalent to maintaining that at every time step t and before observing the item type k t , no player prefers the fractional allocation of any other player in X t . Similarly, proportionality in expectation is equivalent to maintaining that at every time step t and before observing the item type k t , the expected value of every player for their fractional allocation is at least 1/n times that player'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 envy-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 thanT . Note that Benadè et al. [5] show that in the adversarial setting, no algorithm can guarantee o( √ T ) realized envy. Conversely, they also show that when values are generated randomly and observed before allocation, there exists an algorithm that can guarantee o(1) realized envy with high probability. Theorem 3 shows that when values are still generated randomly but are unknown at the time of allocation (as in our setting), no algorithm can guarantee o( √ T ) realized envy with high probability. We complement Theorem 3 with Theorem 4, which shows that any algorithm ALG that satisfies envy-freeness in expectation will output a final allocation A(ALG) with realized envy of at mostT log(T ) with high probability. Therefore, envy-free in expectation algorithms are within a log(T ) 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 to 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 is equivalent to maintaining envy-freeness in expectation at all times t ∈ [T ] when maximizing social welfare. A key step of our proof of Theorem 5 is showing that for every time-or history-dependent algorithm ALG which achieves envy-freeness in expectation at the end of T rounds, there exists another algorithm ALG ′ that is time-and history-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 fairness notions as linear constraints, in the spirit of prior work in fair division [4] . Formally, define ⟨A, B⟩ F as the Frobenius inner product of matrices A and B. For B ∈ R n×m , c ∈ R, and a fractional allocation X, we represent the linear constraint ⟨B, X⟩ F ≥ c as the tuple (B, c). A fractional allocation X satisfies a set of L linear constraints {(B ℓ , c ℓ )} L ℓ=1 if for all ℓ ∈ [L], ⟨B ℓ , X⟩ F ≥ c ℓ . Because the constraints represent "fairness in expectation" relative to the mean values, we will explicitly let the constraint matrix B ℓ (µ * ) be a function of the mean value matrix µ * . Therefore, we will consider sets of constraints of the form {(B ℓ (µ * ), c ℓ )} L ℓ=1 . Because these constraints are functions of µ, we will also refer to families of constraints {(B ℓ (µ), c ℓ )} L ℓ=1 µ . The following two remarks show how envy-freeness in expectation and proportionality in expectation can be represented within this framework.Remark 1. For every ℓ ∈ [n 2 ], construct B efe ℓ (µ * ) as follows. Define i = ⌈ ℓ n ⌉ and i ′ = (ℓ mod n) + 1. For every k ∈ [K], let (B efe ℓ (µ * )) ik = µ * ik and (B efe ℓ (µ * )) i ′ k = -µ * ik . For all i ′′ ̸ ∈ {i, i ′ }, let (B efe ℓ (µ * )) i ′′ = 0.Then the envy-freeness in expectation constraints for mean µ * as defined in Definition 1 correspond to efe(µ* ) := {(B efe ℓ (µ * ), 0)} n 2 ℓ=1 . Remark 2. For every ℓ ∈ [n], construct B pe ℓ (µ * ) as follows. For every k ∈ [m], (B pe ℓ (µ * )) ℓk = (n-1) n • µ * ℓk and (B pe ℓ (µ * )) ik = -1 n • µ * ℓk for every i ̸ = ℓ.Then the proportionality in expectation constraints for mean µ * as defined in Definition 2 correspond to pe(µ * ) = {(B pe ℓ (µ * ), 0)} n ℓ=1 .An algorithm ALG satisfies constraints {(B ℓ (µ * ), c ℓ )} L ℓ=1 if for all t ∈ [T ], the fractional allocation X t used by ALG at time t satisfies the constraints {(B ℓ (µ * ), c ℓ )} L ℓ=1 . When µ * is known, the expected social welfare can be directly optimized over all algorithms ALG that satisfy constraints{(B ℓ (µ * ), c ℓ )} L ℓ=1. This problem is equivalent to solving LP (1) with µ = µ * and using the solution Y µ * as the fractional allocation for all time steps.EQUATIONWhen µ * is unknown, we define the regret of an algorithm ALG as follows. Note that the baseline algorithm in this definition of regret is the optimal allocation algorithm under the constraints when µ * is known.Definition 3. Let Y µ * be the solution to LP (1) for µ = µ * . Let X t = ALG(H t ) be the fractional allocation used by algorithm ALG at time t given history H t . Then the T -step regret of ALG for constraints{(B ℓ (µ * ), c ℓ } L ℓ=1 is T • ⟨Y µ * , µ * ⟩ F - T -1 t=0 ⟨X t , µ * ⟩ F .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 1. Suppose we are given n, m, T, a, b such that 0< a ≤ µ * ik ≤ b for all i ∈ [n], k ∈ [m]. Given a family of fairness constraints {(B ℓ (µ), c ℓ )} L ℓ=1 µ representing either envy-freeness in expectation or proportionality in expectation, the goal is to construct an algorithm ALG such that with probability 1 -1/T , X t = ALG(H t ) satisfies the constraints (B ℓ (µ * ), c ℓ )} L ℓ=1 for all t ∈ [T ] and the regret of ALG for constraints (B ℓ (µ * ), c ℓ )} L ℓ=1 is o(T ). Note that the o(T ) regret in Problem 1 will be Õ(T 2/3 ) 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.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 out 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 on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.• The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text 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, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best• The full details can be provided either with the code, in appendix, or as supplemental material. 
fairness machinery: 
 Our goal in this section is to establish novel, fundamental properties of envy-freeness and proportionality in expectation, which will serve as a crucial part of the machinery underlying our regret bounds.In the context of fairness, a natural assumption is that if a group of individuals are treated equally, then that group is considered to be treated fairly. In that spirit, our first key property is as follows.Property 1. For any ℓ ∈ [L], suppose that a fractional allocation X ∈ R n×m satisfies X i1 = X i2 , ∀i 1 , i 2 ∈ {i : B ℓ (µ) i ̸ = 0}. Then ⟨B ℓ (µ), X⟩ F ≥ c ℓ .Informally, a set of constraints satisfies Property 1 if for any constraint in the set, the constraint is 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 1 because any two players with equal allocations are never envious of each other. Proportionality in expectation also satisfies Property 1, 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 Y µ , 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 ) γ 0 and C P2 > 0 such that for any γ < γ 0 and any µ, there exists a fractional allocation X ′ such that ⟨X ′ , µ⟩ F ≥ ⟨Y µ , µ⟩ F -C P2 γ, and such that for each ℓ ∈ [L], either1. ⟨B ℓ (µ), X ′ ⟩ F ≥ c ℓ + γ or 2. ∀i 1 , i 2 ∈ {i : B ℓ (µ) i ̸ = 0}, X ′ i1 = X ′ i2 . 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 'envy-with-slack-α' graphs, which track whether a player prefers their allocation by at least α over another player's allocation. More specifically, given parameters µ, X, and α, the corresponding 'envy-with-slack' graph has vertices N and edge set E such that a directed edge from i to i ′ exists if and only ifX i • µ i -X i ′ • µ i < α. The weight of each such edge is X i • µ i -X i ′ • µ i .At a high level, Algorithm 3 constructs 'envy-with-slack-α' graphs with progressively smaller α, with α ≥ γ 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.An overview of the algorithm is as follows. In each iteration, Algorithm 3 generally performs one of three operations and decreases α. First, if there exists an equivalence class S with at least one incoming edge but no outgoing edges, then operation remove-incoming-edge 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 'envy-with-slack' graph. The directed cycle is chosen so that the outgoing edge of each node i in the cycle is among i's outgoing edges with minimal weight. Therefore, each node i in the cycle is pointing to an i ′ ∈ N for whom i has the least slack. If there exists some node i * ∈ 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 a 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 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-slack' graph. Furthermore, Algorithm 4 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 a 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 n, so an edge must be removed from the 'envy-with-slack' graph every n iterations. There are at most n 2 edges, and the algorithm therefore terminates in at most n 3 iterations with an allocation which satisfies Property 2. For the numerous details, see Appendix F. Lemma 2. The family of proportionality in expectation constraints satisfies Property 2.Proof sketch. Define the slack S i 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 a 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.If the amount of total slack across all n players is less than bnγ a , then we take X ′ = UAR. Note that the total slack is equivalent to the change in social welfare between Y µ and UAR. Therefore, because the total slack was less than bnγ a , the difference in social welfare between Y µ and UAR is at most bnγ a which is O(γ). Furthermore, by definition the UAR allocation satisfies option 2 of Property 2 for all constraints ℓ.If the amount of total slack is greater than bnγ a , then we construct X ′ from Y µ by transferring allocation away from players with slack greater than the required γ and redistributing this allocation so that every player has slack of at least γ. Specifically, each player i loses ∆ ik of their allocation for item k, where∆ ik := Y µ ik m k ′ =1 Y µ ik ′ • S i n i ′ =1 S i ′ • nγ a .The allocation X ′ is then constructed asEQUATIONIntuitively, this can be viewed as each player putting a part of their allocation (proportional to S i • γ) into a communal "pot." The pot, consisting ofn i ′ =1 ∆ i ′ kfor item k, is then divided evenly among all n players to form X ′ . By construction, no player loses more than S i social welfare when the pot is created, and every player receives at least γ 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 γ, i.e. each player has a slack of at least γ for X ′ . Furthermore, the total difference in social welfare between Y µ and X ′ is at most O(γ). We have thus shown that in both cases, X ′ will satisfy all of the desired conditions. The full proof is relegated to Appendix E.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 µ for the constraints. This is unsurprising, as the entries in the matrices B ℓ (µ) 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 1 and 2 and the fact that µ ik is bounded away from 0.Property 3. There exists a K > 0 such that ∀µ 1 , µ 2 ∈ [a, b] n×m and ∀ϵ > 0, if ∥µ 1 -µ 2 ∥ 1 ≤ ϵ then ∥B ℓ (µ 1 ) -B ℓ (µ 2 )∥ 1 ≤ Kϵ.Observation 2. The envy-freeness in expectation and proportionality in expectation constraints satisfy Property 3.Property 4. For all µ, µ ′ ∈ [a, b] n×m , {i : B ℓ (µ) i ̸ = 0} = {i : B ℓ (µ ′ ) i ̸ = 0}.Observation 3. The envy-freeness in expectation and proportionality in expectation constraints satisfy Property 4.Recall that Property 2 implies that for every constraint ℓ, either the constraint ℓ has a slack of at least γ for X ′ or every player involved in constraint ℓ is treated equally under allocation X ′ . A slack of γ in the constraint guarantees constraint satisfaction for all µ ′ close to µ if the constraints are continuous in µ. Treating every player equally for a given constraint also guarantees that the constraints are satisfied for all µ ′ by Property 1. Therefore, Properties 1 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 µ ′ close to µ. 
algorithm and regret bounds: 
 In this section, we present our main result, an explore-then-commit algorithm which achieves Õ(T 2/3 ) regret while maintaining either proportionality in expectation or envy-freeness in expectation. The key step in Algorithm 1 is the optimization in LP (3) to guarantee that the fairness constraints are satisfied with high probability. For µ ∈ R n×m+ and ϵ ∈ R n×m + , we define the confidence region µ ± ϵ = {µ ′ ∈ R n×m : µ ik -ϵ ik ≤ µ ′ ik ≤ µ ik + ϵ ik ∀i, k}.Note that Algorithm 1 requires solving LPs with an infinite number of constraints, which we discuss further in Section 6.EQUATIONfor t ← T 2/3 to T -1 do At time t, use fractional allocation X t = X. end for Theorem 1. Suppose we are given n, m, T, a, b such that 0 < a ≤ µ * ik ≤ b for all i ∈ [n], k ∈ [m]. If {{(B ℓ (µ), c ℓ )} L ℓ=1 } µ = {efe(µ)} µ or {{(B ℓ (µ), c ℓ )} L ℓ=1 } µ = {pe(µ)} µ , then Algorithm 1 with probability 1 -1/T satisfies the constraints {(B ℓ (µ * ), c ℓ )} L ℓ=1 and achieves regret of Õ(T 2/3 ) for constraints {(B ℓ (µ * ), c ℓ )} L ℓ=1 .Proof sketch. We have already shown in Section 3 that both envy-freeness in expectation and proportionality in expectation satisfy Properties 1, 2, 3, and 4. Therefore, it suffices to show that Algorithm 1 achieves Õ(T 2/3 ) regret for any family of constraints {{(B ℓ (µ), c ℓ )} L ℓ=1 } µ that satisfies Properties 1, 2, 3, and 4.The allocations used during the warm-up steps of Algorithm 1 are uniform at random, and therefore these allocations satisfy the constraints {(B ℓ (µ), c ℓ )} L ℓ=1 for all µ by Property 1. Because the fractional allocations used in the first T 2/3 steps are all UAR, each arm, or (player, item) pair, will be sampled with probability 1 nm at each step. This implies by Hoeffding's inequality that with high probability, N ik = Ω(T 2/3 ) for all i, k. The i, k entry in the ϵ matrix is proportional to1 √ N ik, and therefore ∥ϵ∥ 1 = Õ(T -1/3 ) with high probability. Because the value distributions are sub-Gaussian, a standard application of Hoeffding's inequality also gives that with high probability, the true mean matrix will be within our confidence region, i.e. µ * ∈ μ ± ϵ. To summarize, because we used UAR for the first T 2/3 steps, we have thatPr ∥ϵ∥ 1 ≤ Õ(T -1/3 ), µ * ∈ μ ± ϵ ≥ 1 - 1 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 ∥ϵ∥ 1 per-step regret compared to Y µ * . Let K be the Lipschitz constant of Property 3. Using Property 2 with µ = µ * and γ = 2K∥ϵ∥ 1 = Õ(T -1/3 ) gives that there exists an allocation X ′ such that the social welfare of X ′ is only O(∥ϵ∥ 1 ) less than the social welfare of the optimal allocation Y µ * and such that every constraint ℓ either has slack of at least 2K∥ϵ∥ 1 (option 1 of Property 2) or every player is treated equally in constraint ℓ (option 2 of Property 2). We will now show that X ′ is a solution to LP (3). If option 1 holds for constraint ℓ ∈ [L], then by Property 3, X ′ will satisfy the constraint (B ℓ (µ), c ℓ ) for every µ ∈ μ ± ϵ. Formally, if option 1 holds for constraint ℓ, then for any µ ∈ μ ± ϵ,⟨B ℓ (µ), X ′ ⟩ F = ⟨B ℓ (µ), X ′ ⟩ F -⟨B ℓ (µ * ), X ′ ⟩ F + ⟨B ℓ (µ * ), X ′ ⟩ F = ⟨B ℓ (µ) -B ℓ (µ * ), X ′ ⟩ F + ⟨B ℓ (µ * ), X ′ ⟩ F ≥ ⟨B ℓ (µ * ), X ′ ⟩ F -∥B ℓ (µ) -B ℓ (µ * )∥ 1 [0 ≤ X ′ ik ≤ 1, ∀i, k] ≥ ⟨B ℓ (µ * ), X ′ ⟩ F -2K∥ϵ∥ 1 [Property 3] ≥ c ℓ .[Property 2: option 1]If option 2 holds for constraint ℓ ∈ [L], then Properties 1 and 4 together guarantee that X ′ will satisfy the constraint (B ℓ (µ), c ℓ ) for every µ ∈ μ ± ϵ. Therefore, X ′ will satisfy all of the constraints {B ℓ (µ), c ℓ } L ℓ=1 for every µ ∈ μ ± ϵ, which implies that X ′ is a solution to LP (3). Finally, because X is the optimal solution to LP (3), X must have higher social welfare than X ′ under means μ. Because ∥µ * -μ∥ 1 ≤ ∥ϵ∥ 1 , this implies that X must have at most O(∥ϵ∥ 1 ) less social welfare than X ′ under the true means µ * . An application of the triangle inequality gives that,⟨Y µ * , µ * ⟩ F -⟨ X, µ * ⟩ F = ⟨Y µ * , µ * ⟩ F -⟨X ′ , µ * ⟩ F + ⟨X ′ , µ * ⟩ F -⟨ X, µ * ⟩ F = Õ (∥ϵ∥ 1 + ∥ϵ∥ 1 ) = Õ(T -1/3 ).Thus, the total regret for the steps after the warm-up period is Õ(T 2/3 ). The regret of the warm-up period is at most (b -a)T 2/3 due to the assumption that the mean values are bounded. We can therefore conclude that the total regret is Õ(T 2/3 ), and this completes the proof of regret. Finally, we note that by construction of LP (3), if µ * ∈ μ ± ϵ then the chosen fractional allocations X must also satisfy the constraints {(B ℓ (µ * ), c ℓ )} L ℓ=1 as desired. See Appendix D for the full proof. 
lower bounds: 
 The following lower bound shows that Theorem 1 is tight up to log factors. An equivalent result holds for proportionality, with the same proof.Theorem 2. There exists a, b, n, m such that no algorithm can, for all µ * ∈ [a, b] n×m , both satisfy the envy-freeness constraints and achieve regret of less than T 2/3 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 two 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.µ 1 = 2 3 1 1 µ 2 = 2 3 1 1 + T -1/3We will show that no algorithm can with probability 1 -1/T achieve regret of less than Ω(T 2/3 ) and satisfy envy-freeness in expectation for both of these distributions. First, note that the expected social welfare maximizing allocation for µ 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 µ 2 must give Ω(T -1/3 ) fraction of items of type 2 to player 2. This implies that if an algorithm is unable to distinguish between µ 1 and µ 2 , then either the regret will be Ω(T 2/3 ) for µ 1 or the algorithm will not be envy-free for µ 2 .Therefore, any algorithm that has regret of less than Ω(T 2/3 ) and satisfies envy-freeness for both µ 1 and µ 2 must distinguish betwen µ 1 and µ 2 . The only way to do this is to allocate at least Ω(T 2/3 ) items of type 2 to player 2. However, this will result in regret under µ 1 of Ω(T 2/3 ). 
discussion: 
 We conclude by discussing some limitations and open questions. First, Algorithm 1 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 in many applications [16, 24] . We also note that a 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 ϵ. 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 an 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 1 for envy-freeness is that the Õ term is exponential in n. We expect, however, that the worst-case bound we present in Lemma 1 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 we can achieve Õ( √ T ) 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 a constant (greater than 1/n) dependence on every unknown value in the µ * matrix. Therefore, every mean value µ * ik might need to be learned with high accuracy even if the optimal allocation does not allocate item type k to player i.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 to give a fresh perspective on additional problems in this area, such as online cake cutting [31] .Algorithm 2 [Online Item Allocation] Require: ALG 1: ∀i, A 0 i ← {}, H 0 ← {} 2: for t ← 1 to T do 3: X t ← ALG(H t ) 4: k t ∼ D 5: Generate item j t of type k t (i.e. V i (j t ) ∼ N (µ * ikt , 1), ∀i ∈ N ) 6: i t ← Sample from (X t ) ⊤ kt 7: A t it = A t-1 it + {j t } 8: H t ← H t-1 + (k t , i t , V it (j t )) 9: end for 10: return A = (A T 1 , A T 2 , ..., A T n )In this section, we 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, we will use the following notation. For any algorithm ALG, we denote X t = ALG(H t ) as the fractional allocation used at time t, and Pr ALG (i, k, H t ) := (X t ) ik .Previous works on fair online allocation of indivisible goods have focused on the fairness of the final, realized allocation instead of studying fairness in expectation as in Definitions 1 and 2 [5] . We define the realized envy of an allocation below.A at time τ is max i,i ′ V i (A τ i ′ ) -V i (A τ i ).We show in the following theorems that algorithms which are envy-free in expectation are within a log(T ) factor of being "optimal" in terms of final realized envy. Informally, Theorem 3 shows that in our setting, no algorithm can with high probability output an allocation A(ALG) with realized envy less than √ t. Conversely, Theorem 4 shows that any algorithm ALG that satisfies envy-freeness in expectation will output a final allocation A(ALG) with realized envy of at most √ T log(T ) with high probability.Theorem 3. Suppose µ * is known. For any algorithm ALG and for any τ ∈ [T ], with probability at least 1/16 the allocation A τ (ALG) has realized envy of more than √ τ .proof. Assume there are two players and only one item type, and assume that all values are drawn from N (µ, 1). Fix τ ≥ log 2 (T ). As in Algorithm 2, define i t ∈ {1, 2} as the player allocated the item at time t. The realized envy of the two players can be written as:EQUATIONRealized Envy of Player 2 at time τ = τ t=0EQUATION)Let v a i be the value of the assigned player for item i, and v u i be the value of the unassigned player for item i. Note that v a i , v u i ∼ N (µ, 1), because at the time of allocation, ALG does not know either player's 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:EQUATIONBy the Central Limit Theorem, τ i=0 v a i and τ i=0 v u i are both N (τ • µ, τ ). Therefore, for any τ , with probability at least 1/16, we have thatτ t=0 v a t ≤ τ µ - √ τ and τ t=0 v u t ≥ τ µ + √ τ .Putting these equations together, we have thatτ t=0 v a t + 2 √ τ ≤ τ t=0 v u t .However, this result with Equations ( 6) and ( 7) implies that the envy must be at least √ τ for any choice of {i t }. Therefore, we have shown that with probability at least 1/16, the envy at time τ will be at least √ τ for any possible algorithm. proof. We will bound the realized envy of A(ALG) between any two specific players i, i ′ , which will then imply a bound on the realized envy of A(ALG) by a union bound. The key observation is that each round of Algorithm 2 consists of first a random draw from D to determine the item type k t and then a draw from ξ t ∼ Unif([0, 1]) which determines the player to which the item is allocated based on X t = ALG(H t ). Formally, the t th item is allocated to player i ifξ t ∈ i-1 i ′′ =1 (X t ) i ′′ kt , i i ′′ =1 (X t ) i ′′ kt .Define {v ti ′′ } n i ′′ =1 as the values of the players for the item at time t. This is the final source of randomness in round t. Therefore, the allocation of any player at time τ is a function of the random variable sequence {(k t , ξ t , {v ti ′′ } n i ′′ =1 )} τ -1 t=0 . Let E τ represent the envy accrued by player i for player i ′ up until but not including time τ . ThenE τ = τ -1 t=0 v ti • m k=1 1 kt=k • 1 ξt∈[ i ′ -1 s=1 (Xt) sk t , i ′ s=1 (Xt) sk t ] -1 ξt∈[ i-1 s=1 (Xt) sk t , i s=1 (Xt) sk t ] := f {(k t , ξ t , {v ti ′′ } n i ′′ =1 )} τ -1 t=0 .f {(k t , ξ t , {v ti ′′ } n i ′′ =1 )} τ -1 t=0 . First, we show that the bounded condition is satisfied. If {(k t , ξ t , {v ti ′′ } n i ′′ =1 )} τ -1 t=0 and {(k ′ t , ξ ′ t , {v ′ ti ′′ } n i ′′ =1 )} τ -1 t=0 differ only at the s th element for any s ∈ [0, τ -1], then f {(k t , ξ t , {v ti ′′ } n i ′′ =1 )} τ -1 t=0 -f {(k ′ t , ξ ′ t , {v ti ′′ } n i ′′ =1 )} τ -1 t=0 ≤ B.Therefore, we can apply McDiarmid's inequality to get thatPr f {(k t , ξ t , {v ti ′′ } n i ′′ =1 )} τ -1 t=0 -E f {(k t , ξ t , {v ti ′′ } n i ′′ =1 )} τ -1 t=0 ≥ √ τ log(T ) ≤ e -log 2 (T )/(2B 2 ) ≤ T -log(T )/(2B 2 ) .Since ALG is envy-free in expectation, we know thatE f {(k t , ξ t , {v ti ′′ } n i ′′ =1 )} τ -1 t=0 ≤ 0.Therefore, we must have thatPr f {(k t , ξ t , {v ti ′′ } n i ′′ =1 )} τ -1 t=0 ≥ √ τ log(T ) ≤ T -log(T )/(2B 2 ) .Taking a union bound over all pairs i, i ′ and all τ ∈ [T ], we have thatPr(∃τ : Realized envy at time τ is ≥ √ τ log(T ) ) ≤ n 2 T • T -2 log(T )/b 2 = o(1/T ).Therefore, with probability 1 -o(1/T ), the realized envy at evert time τ is at most √ τ log(T ).Note that Theorem 3 does not contradict the results of Benadè et al. [5] , who achieve envy-freeness 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 j t are known before assignment, Theorem 3 does not apply.We also defined envy-freeness in expectation as a constraint which needs to hold at every time step t.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 in expectation of any other player at the end of all T rounds. However, Theorem 5 shows that this is equivalent to maintaining envy-freeness in expectation at all times t ∈ [T ] when maximizing social welfare.Theorem 5. Suppose µ * is known. Let E be the class of all algorithms that are envy-free in expectation and let F be the class of all algorithms which satisfyE[V i (A T i )] ≥ max i ′ ∈[n] E[V i (A T i ′ )] for all i. Then max ALG∈F E[sw(A(ALG))] = max ALG∈E E[sw(A(ALG))].proof. By definition, E ⊆ F, which proves one direction of the desired equality. We will now show that for any ALG ∈ F, there exists an algorithm ALG ′ ∈ E such thatE[sw(A(ALG ′ ))] = E[sw(A(ALG))].First, observe that by the definition of F, we have that for all i, i ′ ,EQUATION)By linearity of expectation, Equation ( 8) is equivalent toEQUATIONFurthermore, by definitionE[sw(ALG)] = E   n i=1 t∈[T ] k Pr ALG (i, k, H t )µ ik Pr D (k)   = n i=1 t∈[T ] k Ht Pr ALG (i, k, H t )dH t • µ ik • Pr D (k) = n i=1 k   t∈[T ] Ht Pr ALG (i, k, H t )dH t   • µ ik • Pr D (k).We will construct the algorithm ALG ′ as follows. Suppose ALG ′ is time-independent and historyindependent, such that for all t, H t ,Pr ALG ′ t (i, k, H t ) = 1 T s∈[T ] Pr ALGs (i, k, H s )dH s .The expected social welfare of ALG ′ isE[sw(ALG ′ )] = E   n i=1 t∈[T ] k Pr ALG ′ t (i, k, H t )µ ik Pr D (k)   = E   n i=1 t∈[T ] k 1 T s∈[T ] Pr ALGs (i, k, H s )dH s • µ ik • Pr D (k)   = E   n i=1 k   s∈[T ] Pr ALGs (i, k, H s )dH s   • µ ik • Pr D (k)   = E[sw(ALG)].Therefore, ALG and ALG ′ have the same expected social welfare. Finally, we need to show that ALG ′ ∈ E. This is equivalent to showing that for all t and H t ,k Pr ALG ′ t (i, k, H t )µ ik Pr D (k) ≥ k Pr ALG ′ t (i ′ , k, H t )µ ik Pr D (k).Starting with the LHS and plugging in the definition of ALG ′ , we have thatk Pr ALG ′ t (i, k, H t )µ ik Pr D (k) = k 1 T s∈[T ] Pr ALGs (i, k, H s )dH s µ ik Pr D (k) = 1 T k s∈[T ] Pr ALGs (i, k, H s )dH s µ ik Pr D (k) ≥ 1 T k s∈[T ]PrALGs (i ′ , k, H s )dH s µ ik Pr D (k) [Equation (9)] = k 1 T s∈[T ]PrALGs (i ′ , k, H s )dH s µ ik Pr D (k) = k Pr ALG ′ t (i ′ , k, H t )µ ik Pr D (k),as desired. Therefore, we have shown that ALG ′ ∈ E. Theorem 6. The algorithm which maximizes expected social welfare subject to EFE up to time T is time-independent, history-independent, 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-independent and history-independent. To find the best such fractional allocation, all we must do is solve LP (1) with the envy-freeness in expectation constraints.Theorems 3-6 also have equivalent forms for proportionality. We define the realized proportionality gap as the equivalent of envy for the proportionality constraints. This implies that a proportional allocation has non-positive proportionality gap.Definition 5. The realized proportionality gap of allocation A at time τ is max i1 n i ′ V i (A τ i ′ ) - V i (A τ i ).As in Theorems 3 and 4 , the following two results give that algorithms which satisfy proportionality in expectation are within a log(T ) factor of optimal for the realized proportionality gap. Theorem 7. Suppose µ * is known. For any algorithm ALG and for any τ ∈ [T ], with probability at least 1/16 the allocation A τ (ALG) has realized proportionality gap of more than √ τ .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 N (µ, 1). Then the realized proportionality gap of the two players can be written as:Realized proportionality gap of PlayerEQUATIONRealized proportionality gap of Player 2 at time τ = 1 2 τ t=0EQUATION) These equations only differ from those of realized envy by a 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. ALG(H t ) is a deterministic function of H t ) and satisfies proportionality in expectation, then with probability 1 -o(1/T ), the realized proportionality gap ofA τ (ALG) at every time τ ∈ [T ] is at most √ τ log(T ).proof. In this proof, we can let E t be the accrued "proportionality gap" of any player i. Then as in Theorem 4, an application of McDiarmid's inequality allows us to bound the realized proportionality gap with high probability for all τ .The following two theorems are analogs of Theorem 5 and Theorem 6 for envy-freeness in expectation. Together, these theorems imply that maximizing social welfare subject to 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 E be the class of all algorithms that are proportional in expectation and let F be the class of all algorithms which satisfyE[V i (A T i )] ≥ 1 n i ′ ∈[n] E[V i (A T i ′ )]for all i. Then max proof. Suppose ALG ∈ F. We will define ALG ′ as in Theorem 5 to bePr ALG ′ t (i, k, H t ) = 1 T s∈[T ] Pr ALGs (i, k, H s )dH s . By this construction, ALG ′ ∈ E because k Pr ALG ′ t (i, k, H t )µ ik Pr D (k) = k 1 T s∈[T ] Pr ALGs (i, k, H s )dH s µ ik Pr D (k) = 1 T k s∈[T ] Pr ALGs (i, k, H s )dH s µ ik Pr D (k) ≥ 1 T n n i ′ =1 k s∈[T ] Pr ALGs (i ′ , k, H s )dH s µ ik Pr D (k) [ALG ∈ F] = n i ′ =1 k 1 T n s∈[T ] Pr ALGs (i ′ , k, H s )dH s µ ik Pr D (k) = 1 n n i ′ =1 k Pr ALG ′ t (i ′ , k, H t )µ ik Pr D (k).Because E ⊆ 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 algorithm which maximizes expected social welfare subject to PE up to time T is time-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 time-independent and history-independent. To find the best such fractional allocation, all we must do is solve LP (1) with the proportionality in expectation constraints.C.1 Choice of DIn the body of the paper, we focus on the case when D is the uniform distribution over item types. However, our results generalize to any distribution D which does not depend on T . In this case, the social welfare of a fractional allocation X becomes i,kX ik Pr D (k)µ ik . For a matrix ν ∈ R n×m , define f D (ν) = ν ′ ∈ R n×m , where ν ′ ik = n • Pr D (k) • µ ik . For mean values µ * , define µ ′ = f D (µ * ).Then social welfare of a fractional allocation X with means µ * and distribution D is then simply 1 n ⟨X, µ ′ ⟩ F as in the uniform D case. Similarly, the envy-freeness in expectation or proportionality in expectation constraints on X with means µ * and item distribution D can be represented as ⟨B ℓ (µ ′ ), X⟩ F ≥ c ℓ , which is an equivalent form to the constraints when D is uniform. Therefore, for arbitrary D we can use Algorithm 1 with only two slight modifications. The first is we must transform the μ, µ, and other components of the linear programs using the function f D . The second modification is that we potentially need more exploration steps (larger T ) in the warm-up period to guarantee the same level of estimation of µ * , depending on the value of min i,k Pr D (k). However, since we require that D does not depend on T , this will not change the overall regret of the algorithm.In this section, we show that if the means of player values can be arbitrarily close to zero, then it can be impossible to achieve a regret of o(T ).Theorem 11. For ϵ > 0, there does not exist an algorithm ALG such that for any possible µ * ∈ [0, ϵ] n×m , for every t the fractional allocation X t chosen by ALG satisfies envy-freeness in expectation with probability greater than 1/2 and the regret of ALG is o(T ). The same result also holds for proportionality in expectation. proof. W.l.o.g. assume that ϵ = 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. 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 o(T ) for both of these cases of µ * . First, letEQUATIONµ 2 = 0 1/T 2 1 0.5 .If µ * = µ 1 or µ * = µ 2 , then player 1 will not have a realized value of 1 for any of the T items with probability at least 1/2. Therefore, no algorithm can differentiate between µ * = µ 1 and µ * = µ 2 with probability at least 1/2. The only fractional allocation that is envy-free for both µ * = µ 1 and µ * = µ 2 is the uniform at random allocation. However, this allocation has regret of Ω(T ) for µ * = µ 2 , as the best fractional allocation when µ * = µ 2 is the fractional allocationY µ 2 = 0 0.5 1 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 µ * . Similarly, the uniform at random allocation is the only proportional allocation in this example, and therefore the same result holds.Observations 1, 2, and 3 give that the proportionality in expectation constraints and the envy-freeness in expectation constraints satisfy Properties 1, 3, and 4 respectively. Lemmas 1 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 {(B ℓ (µ), c ℓ )} L ℓ=1 µ∈[a,b] n×m be a family of constraints that satisfy Properties 1, 3, 4, and 2. Then with probability 1 -1/T , Algorithm 1 satisfies constraints {(B ℓ (µ * ), c ℓ )} L ℓ=1 and has regret of Õ(T 2/3 ) for constraints {(B ℓ (µ * ), c ℓ )} L ℓ=1 .proof. First, we note that the regret of the first T 2/3 steps can be bounded byEQUATION)By Property 1, the uniform at random allocation satisfies constraints {(B ℓ (µ), c ℓ } L ℓ=1 . Therefore, X t satisfies the constraints for all t < T 2/3 . Furthermore, because the fractional allocation was uniform at random for the first T 2/3 steps, we have that for sufficiently large T ,EQUATIONwhere the second to last inequality is by Hoeffding's Inequality and a union bound. This implies that with probability 1 -1 2T , ∥ϵ∥ 1 = Õ(T -1/3 ). Because the values are drawn from a Sub-Gaussian distribution, there exists a constant c > 0 (which depends on the distribution of the values) such that by Hoeffding's inequality,Pr (∀i ∈ [n], k ∈ [m], |μ ik -µ * ik | ≤ ϵ ik ) ≥ 1 -2nme -c log 2 (4nmT ) ≥ 1 -2nm 1 4nmT c log(4nmT ) ≥ 1 - 1 2T.[For sufficiently large T ] (14) For the rest of this proof, we will assume thatEQUATIONwhich 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∥ϵ∥ 1 ≤ Õ(T -1/3 ) ≤ γ 0 for sufficiently large T , where γ 0 is from Property 2. Therefore, taking γ = 2K∥ϵ∥ 1 in Property 2 gives that there exists some fractional allocation X ′ such thatEQUATIONand such that for every constraint ℓ ∈EQUATIONFor any µ ∈ μ ± ϵ, we have that ∥µ -µ * ∥ 1 ≤ 2∥ϵ∥ 1 by Equation ( 16) and the triangle inequality. By the Lipschitz continuity assumption (Property 3), this implies that for all µ ∈ μ ± ϵ,EQUATIONTherefore, if Equation ( 18) holds for a constraint ℓ, then for any µ ∈ μ ± ϵ,⟨B ℓ (µ), X ′ ⟩ F = ⟨B ℓ (µ), X ′ ⟩ F -⟨B ℓ (µ * ), X ′ ⟩ F + ⟨B ℓ (µ * ), X ′ ⟩ F = ⟨B ℓ (µ) -B ℓ (µ * ), X ′ ⟩ F + ⟨B ℓ (µ * ), X ′ ⟩ F ≥ ⟨B ℓ (µ * ), X ′ ⟩ F -∥B ℓ (µ) -B ℓ (µ * )∥ 1 [0 ≤ X ′ ik ≤ 1, ∀i, k] ≥ ⟨B ℓ (µ * ), X ′ ⟩ F -2K∥ϵ∥ 1 [Equation (19)] ≥ c ℓ .[Equation (18) ] Therefore, we have shown that if Equation ( 18) holds for a constraint ℓ, then the fractional allocation X ′ satisfies constraint (B ℓ (µ), c ℓ ) for all µ ∈ μ ± ϵ. If Equation ( 18) does not hold for a constraint ℓ,then ∀i 1 , i 2 ∈ {i : B ℓ (µ * ) i ̸ = 0}, X ′ i1 = X ′ i2 . Because {i : B ℓ (µ * ) i ̸ = 0} = {i : B ℓ (µ) i ̸ = 0}by Property 4, this implies by Property 1 that ⟨B ℓ (µ), X ′ ⟩ F ≥ c ℓ for all µ. Therefore, we have shown that X ′ satisfies {(B ℓ (µ), c ℓ )} L ℓ=1 for all µ ∈ μ ± ϵ, and thus X ′ satisfies the constraints in LP (3). Because X is the optimal solution to LP (3), we have that⟨X ′ , μ⟩ F ≤ ⟨ X, μ⟩ F .By Equation ( 16), this implies thatEQUATIONTherefore,⟨Y µ * , µ * ⟩ F -⟨ X, µ * ⟩ F = ⟨Y µ * , µ * ⟩ F -⟨X ′ , µ * ⟩ F + ⟨X ′ , µ * ⟩ F -⟨ X, µ * ⟩ F ≤ O (∥ϵ∥ 1 + ∥ϵ∥ 1 )[Equations ( 17) and ( 20)]≤ Õ(T -1/3 ).[Equation ( 15)]Combining with Equation ( 12), this gives a total regret ofT -1 t=0 ⟨Y µ * , µ * ⟩ F -⟨X t , µ * ⟩ F ≤ O(T 2/3 ) + T t=T 2/3 ⟨Y µ * , µ * ⟩ F -⟨X t , µ * ⟩ F [Equation (12)] = O(T 2/3 ) + T • Õ(T -1/3 ) [Equation (21)]= Õ(T 2/3 ).Lastly, we must show that the constraints are satisfied by the fractional allocation used by the algorithm for t ≥ T 2/3 . This is because if Equation ( 16) holds, then any solution to LP (3) must satisfy the constraints {(B ℓ (µ * ), c ℓ } L ℓ=1 , and therefore the fractional allocation used by the algorithm for all t ≥ T 2/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.For proportionality in expectation, LP (1) can be rewritten as the following linear program.EQUATIONIn order to show that the proportionality constraints satisfy Property 2, we want to construct an X ′ such that 1. X ′ decreases the social welfare relative to Y µ by O(γ) and 2. For every constraint i ∈ [n], either X ′ = UAR orEQUATIONLP (22) has n constraints, one corresponding to each player. DefineEQUATION)S i is the slack on the ith constraint when using the optimal solution Y µ . Now we have two cases depending on n i=1 S i , the total amount of slack across all n players. Case 1:n i=1 S i ≤ ba nγ Let X ′ = UAR. This will result in an decrease of social welfare of at most b a nγ compared to Y µ . To see why, note that the slack of constraint i is equivalent to how much player i prefers their fractional allocation in Y µ to UAR. Therefore, switching to UAR from Y µ decreases the total social welfare by S i per player, and therefore decreases the total social welfare byn i=1 S i ≤ b a nγ = O(γ). Furthermore, X ′ = UAR clearly satisfies the other condition because every player is treated equally.n i=1 S i > ba nγ Intuitively, in this case we want to redistribute the slack from the constraints with a lot of slack to the constraints without much slack. To do this, construct X ′ as follows. DefineEQUATIONBy construction, we have thatEQUATION)Because n i=1 S i ≥ b a nγ, we also have thatEQUATIONFurthermore, for every i,S i ≤ Y µ i • µ i by definition of S i . Because µ ik ≤ b, this implies that Si b ≤ m k=1 Y µ ik . With Equation (27), this implies that Si i ′ S i ′ • nγ a ≤ m k=1 Y µ ik .With Equation (25) , this implies that ∆ ik ≤ Y µ ik . Finally, we note thatEQUATION)Now we are ready to construct X ′ . LetEQUATION)In order for this to be a valid allocation, we need that X ′ ik ≥ 0, which is true because we showed above that ∆ ik ≤ Y µ ik . We also need thatn i=1 X ′ ik = 1, which follows from n i=1 X ′ ik = n i=1 Y µ ik -∆ ik + 1 n n i ′ =1 ∆ i ′ k = 1 - n i=1 ∆ ik + n i ′ =1 ∆ i ′ k = 1.Next, we will show that Equation ( 23) is satisfied for all i for fractional allocation X ′ . Starting with the left hand side of Equation ( 23), we haveX ′ i • µ i - 1 n ∥µ i ∥ 1 = Y µ i • µ i -∆ i • µ i + m k=1 1 n n i ′ =1 ∆ i ′ k µ ik - 1 n ∥µ i ∥ 1 [Eq (29)] = S i -∆ i • µ i + 1 n n i ′ =1 ∆ i ′ • µ i [Eq (24)] ≥ 1 n n i ′ =1 ∆ i ′ • µ i [Eq (28)] ≥ a n n i ′ =1 m k=1 ∆ i ′ k [µ ik ≥ a] = γ.[Eq (26) ] Furthermore, we can bound the decrease in social welfare between fractional allocation X ′ and Y µ by⟨Y µ , µ⟩ F -⟨X ′ , µ⟩ F = ⟨Y µ -X ′ , µ⟩ F ≤ n i=1 ∆ i • µ i [Equation (29)] ≤ b n i=1 m k=1 ∆ ik [µ ik ≤ b] ≤ b a nγ.[Equation (26) ] Therefore, we have shown that X ′ has the desired properties, and thus the proportionality constraints satisfy Property 2.For Section F only, we will assume w.l.o.g. that a = 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 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 Y µ into a fractional allocation X ′ which satisfies Property 2 through Algorithm 3. Algorithm 3 iterates over the following types of 'envy-with-slack' graphs, which track whether a player prefers their allocation by at least α over another player's allocation.Definition 6. Let create-slack-graph(µ, X, α) be the subroutine which returns the directed graph with vertices N and edges generated as follows. Suppose G = create-slack-graph(µ, X, α). Then a directed edge from i to i ′ exists in G if and only if⟨X i , µ i ⟩ -⟨X i ′ , µ i ⟩ < α.At a high level, Algorithm 3 constructs 'envy-with-slack' graphs with progressively smaller α, with α ≥ γ 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 7. Let S(X) be the set of equivalence classes of fractional allocation X, where two nodes i, i ′ are part of the same equivalence class S ∈ S(X) if and only ifX i = X i ′ .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 r and a slack value α r . Algorithm 3 then generates from these parameters a directed graph G r = create-slack-graph(µ, X r , α r ), which is the 'envywith-slack' graph for allocation X r given means µ. As in standard graph notation, for a graph G we define V (G) as the vertices of G and E(G) as the edges of G. Each edge e = (i, i ′ ) ∈ E(G r ) has a weight w e = ⟨X i , µ i ⟩ -⟨X i ′ , µ i ⟩. For a set of vertices S, we use δ + (S) to represent the edges with head in S and tail in N \S, and similarly, we use δ -(S) to represent the edges with tail in S and head in N \S. For notational convenience, we let δ -(i) = δ -({i}), and δ + (i) = δ + ({i}). Throughout this section, we will use the notation sw(X, µ) = ⟨X, µ⟩ F .An overview of the algorithm is as follows. In each iteration, Algorithm 3 generally performs one of three operations and removes an edge by decreasing α. First, if there exists an equivalence class S with at least one incoming edge but no outgoing edges, then operation remove-incoming-edge transfers allocation probability from nodes in S to all other nodes. If such an equivalence class does not exist, then Algorithm 3 finds a specific type of cycle in the 'envy-with-slack' graph. If there exists some node 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. If such a node does not exist and all edges in the graph have low enough weight, then operation average-clique instead creates a 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 a new allocation X ′ .Definition 8. Let S ∈ S(X). Define X Sk = X ik for every i ∈ S. Let remove-incoming-edge(S, α, X) be the subroutine which returns X ′ , whereX ′ ik = X ik - (n -|S|)αX Sk 2bn k ′ X Sk ′ ∀ i ∈ S and X ′ ik = X ik + |S|αX Sk 2bn k ′ X Sk ′ ∀ i ∈ N \S Definition 9.Let C be a cycle in a graph G = create-slack-graph(µ, X, α) and next(i) be the node which i points to in C. Then the subroutine cycle-shift(C, X) returns X ′ , whereX ′ ik = X ik + X next(i)k 2 ∀ i ∈ V (C) X ′ ik = X ik ∀ i ∈ N \V (C)Definition 10. Let Q be a clique in a graph G = create-slack-graph(µ, X, α). Then the subroutine average-clique(Q, X) returns X ′ , whereX ′ ik = i ′ ∈Q X i ′ k |Q| ∀ i ∈ Q X ′ ik = X ik ∀ i ∈ N \QWe also define two intermediary operations. Note that the arg min function may return the empty set, a singleton, or a set with multiple elements.Definition 11. Let G = create-slack-graph(µ, X, α) with edge set E. For each equivalence class S ∈ S(X), let E S = arg min e∈δ + (S) w e , where the size of E S may be 0, 1, or > 1. Let E ′ = S E S , and let G ′ = (N, E ′ ). Then the subroutine find-special-cycle(G, S(X)) returns a cycle C of G ′ where V (C) contains at most one member of each equivalence class S ∈ S(X) (and returns ∅ if no such cycle exists).Definition 12. Let G = create-slack-graph(µ, X, α) and let U ⊂ N . Let distribute-equally(U, β, X) be the subroutine which returns X ′ , whereX ′ ik = (1 -|N \U | • β) • X ik ∀ i ∈ U X ′ ik = X ik + β • i ′ ∈U X i ′ k ∀ i ∈ N \UWe are now ready to present Algorithm 3.Require Y µ , µ Let α 0 ← γ • (e n 2 log(4bn 4 )+n 3 log(2n) , X 0 ← Y µ , G 0 ← create-slack-graph(µ, X 0 , α 0 ), r ← 0. while ∃(u, v) ∈ E(G r ) s.t. u, v are in different equivalence classes do if ∃ S ∈ S(X r ) s.t. δ -(S) ̸ = ∅ and δ + (S) = ∅ then ▷ X r+1 = remove-incoming-edge(S, α r , X r ) ▷ α r+1 = α r 2b else ▷ C = find-special-cycle(G r , S(X r )) if ∃ u ∈ N and ∃i, i ′ ∈ V (C) such that (u, i) ∈ E and (u, i ′ ) / ∈ E then ▷ X r+1 = cycle-shift(C, X r ) ▷ α r+1 = α r 2 else if ∃ e ∈ E(G r ) s.t. w e ≥ α r 4bn 4 then ▷ X r+1 = X r ▷ α r+1 = α r 4bn 4 else ▷ S ′ = {S ∈ S(X r ) : S ∩ V (C) ̸ = ∅} ▷ Q = S∈S ′ S ▷ X avg = average-clique(Q, X r ) ▷ α avg = α r n▷ G avg = create-slack-graph(µ, X avg , α avg ) // G avg defined for analysis only.▷ X ′ = X avg ▷ G ′ = create-slack-graph(µ, X ′ , 0) while ∃e ∈ E(G ′ ) do ▷ X ′ = remove-envy(µ, X ′ ) ▷ G ′ = create-slack-graph(µ, X ′ , 0) end while ▷ X r+1 = X ′ ▷ α r+1 = α avg 2 end if end if ▷ G r+1 ← create-slack-graph(µ, X r+1 , α r+1 ) ▷ r = r + 1 end while return X rAlgorithm 3 calls remove-envy, which is equivalent to calling Algorithm 4. Algorithm 4 will require the following definition. Definition 13. Let create-non-negative-envy-graph(µ, X) be the subroutine which returns the directed graph with vertices N and edges generated as follows.Suppose G = create-non-negative-envy-graph(µ, X). Then a directed edge from i to i ′ exists in G if and only if⟨X i , µ i ⟩ -⟨X i ′ , µ i ⟩ ≤ 0.Note that this definition is exactly the same as that of create-slack-graph(µ, X, 0), except with a weak instead of a strict inequality. We now present Algorithm 4.Remove Envy (also referred to as subroutine remove-envy(µ, X 0 ))Require µ, X 0 Let G 0 ← create-non-negative-envy-graph(µ, X 0 ), r ← 0. if {e ∈ E(G 0 ) : w e < 0} = 0 then return X 0 end if ▷ Choose (u, v) ∈ {e ∈ E(G 0 ) : w e < 0} ▷ U ← {v ′ ∈ E(G 0 ) : w (u,v ′ ) < 0} while w (u,v) < 0 and there does not exist a cycle in G r containing (u, v) do ▷ ∀ i ∈ U , β i = min i ′ ∈N \U,β≥0 β s.t. distribute-equally(U, β, X r ) returns X ′ where ⟨X ′ i , µ i ⟩ = ⟨X ′ i ′ , µ i ⟩ ▷ β u = β s.t. distribute-equally(U, β, X r ) returns X ′ where ⟨X ′ u , µ u ⟩ = ⟨X ′ v , µ u ⟩ ▷ i * = arg min i∈({u}∪U ) β i ▷ X r+1 = distribute-equally(U, β i * , X r ) ▷ U = U ∪ {i * } ▷ G r+1 ← create-non-negative-envy-graph(µ, X r+1 ) ▷ r = r + 1 end while if w (u,v) < 0 then ▷ C ← cycle in G r containing (u, v) //Let prev(i) and next(i) be the nodes before and after i in C, respectively.▷ ∀ i ∈ V (C), X ′ i = X r next(i) else ▷ X ′ = X r end if return X ′ Definition 14.Let X be an envy-free fractional allocation for µ if for all i, i ′ ∈ N ,⟨X i , µ i ⟩ -⟨X i ′ , µ i ⟩ ≥ 0.Lemma 4. Let X be an envy-free fractional allocation for µ, and let G = create-slack-graph(µ, X, α) with edge set E. Suppose that there exists some equivalence class S ∈ S(X) such that δ -(S) ̸ = ∅ and δ + (S) = ∅ in G, and let X ′ = remove-incoming-edge(S, α, X).Let G ′ = create-slack-graph(µ, X ′ , α/2b) with edge set E ′ . Then |E ′ | < |E|.proof. We first show that if an edge e / ∈ E, then e / ∈ E ′ . Note that for any i, i ′ such that (i, i ′ ) / ∈ E,⟨X i , µ i ⟩ -⟨X i ′ , µ i ⟩ ≥ α > α 2b .Therefore, to show that an edge(i, i ′ ) not in E is also not in E ′ , it suffices to show that ⟨X ′ i , µ i ⟩ - ⟨X ′ i ′ , µ i ⟩ ≥ ⟨X i , µ i ⟩ -⟨X i ′ , µ i ⟩.The subroutine remove-incoming-edge(S, α, X) only transfers weight from S to N \S, which implies that no node in N \S will gain an edge to a node in S. Formally,EQUATIONEvery pair of nodes i, i ′ ∈ S has their fractional allocation reduced by the same amount, soEQUATIONSimilarly, every pair of nodes i, i ′ ∈ N \S has their fractional allocation increased by the same amount, soEQUATIONFinally, we observe that for any i ∈ S and i ′ ∈ N \S,⟨X ′ i , µ i ⟩ -⟨X ′ i ′ , µ i ⟩ =   ⟨X i , µ i ⟩ - k∈[m] (n -|S|)αX Sk µ ik 2bn k ′ X Sk ′   -   ⟨X i ′ , µ i ⟩ + k∈[m] |S|αX Sk µ ik 2bn k ′ X Sk ′   = ⟨X i , µ i ⟩ -⟨X i ′ , µ i ⟩ - k∈[m] nαX Sk µ ik 2bn k ′ X Sk ′ ≥ ⟨X i , µ i ⟩ -⟨X i ′ , µ i ⟩ - k∈[m] nαX Sk 2n k ′ X Sk ′ = ⟨X i , µ i ⟩ -⟨X i ′ , µ i ⟩ - α 2 ≥ α - α 2 ≥ α 2b .where the second inequality is because(i, i ′ ) ̸ ∈ E. Therefore, by definition of G ′ , (i, i ′ ) / ∈ E ′ . Recall that δ -(S) ̸ = ∅ in G. We will now show that δ -(S) = ∅ in G ′ . Observe that for i ∈ S and i ′ ∈ N \S, ⟨X ′ i ′ , µ i ′ ⟩ -⟨X ′ i , µ i ′ ⟩ =   ⟨X i ′ , µ i ′ ⟩ + k∈[m] |S|αX Sk µ i ′ k 2bn k ′ X Sk ′   -   ⟨X i , µ i ′ ⟩ - k∈[m] (n -|S|)αX Sk µ i ′ k 2bn k ′ X Sk ′   = ⟨X i ′ , µ i ′ ⟩ -⟨X i , µ i ′ ⟩ + k∈[m] nαX Sk µ i ′ k 2bn k ′ X Sk ′ ≥ ⟨X i ′ , µ i ′ ⟩ -⟨X i , µ i ′ ⟩ + α 2b ≥ α 2b . Therefore, (i ′ , i) / ∈ E, which implies δ -(S) = ∅ in G ′ .We conclude that all edges in E ′ exist in E, and at least one edge in E does not exist in E ′ , which implies that |E ′ | < |E|. Lemma 5. Let X be an envy-free fractional allocation for µ, and let G = create-slack-graph(µ, X, α) with edge set E. Suppose that there exists some equivalence class S ∈ S(X) such that δ -(S) ̸ = ∅ and δ + (S) = ∅ in G, and let X ′ = remove-incoming-edge(S, α, X). Then X ′ is an envy-free allocation for µ.proof. Let G ′ = create-slack-graph(µ, X ′ , α/2b) with edge set E ′ . It suffices to show that w e ≥ 0 ∀e ∈ E ′ . By Lemma 4, if an edge (i, i ′ ) / ∈ E, then⟨X ′ i , µ i ⟩ -⟨X ′ i ′ , µ i ⟩ ≥ α 2b ≥ 0.Consider any i ∈ S and i ′ ∈ N \S. Then there must not exist an edge (i, i ′ ) ∈ E by assumption. Also by assumption, for any i, i ′ such that (i, i ′ ) ∈ E, we have that ⟨X i , µ i ⟩ -⟨X i ′ , µ i ⟩ ≥ 0. By a direct application of Equations ( 30), (31) , and (32), we can conclude that⟨X ′ i , µ i ⟩ -⟨X ′ i ′ , µ i ⟩ ≥ 0 as well.Lemma 6. Let G = create-slack-graph(µ, X, α) with edge set E. Suppose that there exists some equivalence class S ∈ S(X) such that δ -(S) ̸ = ∅ and δ + (S) = ∅ in G, and letX ′ = remove-incoming-edge(S, α, X). Then sw(X, µ) -sw(X ′ , µ) ≤ αn 2 . proof. Observe that sw(X ′ , µ) = i∈S ⟨X ′ i , µ i ⟩ + i∈N \S ⟨X ′ i , µ i ⟩ ≥ i∈S 1 - (n -|S|)α 2bn k ′ X Sk ′ • ⟨X i , µ i ⟩ + i∈N \S ⟨X i , µ i ⟩ ≥ i∈S 1 - α 2b k ′ X Sk ′ • ⟨X i , µ i ⟩ + i∈N \S ⟨X i , µ i ⟩ = i∈[N ] ⟨X i , µ i ⟩ - α 2b k ′ X Sk ′ i∈S ⟨X i , µ i ⟩ = i∈[N ] ⟨X i , µ i ⟩ - α 2b k ′ X Sk ′ i∈S k X Sk µ ik ≥ i∈[N ] ⟨X i , µ i ⟩ - α 2 k ′ X Sk ′ i∈S k X Sk = sw(X, µ) - α|S| 2 ≥ sw(X, µ) - αn 2 .This implies that sw(X, µ) -sw(X ′ , µ) ≤ αn 2 .Lemma 7. Let X be an envy-free fractional allocation for µ and let G = create-slack-graph(µ, X, α) with edge set E. Let C = find-special-cycle(G, S(X)) and suppose there exists a node u such that for i, iEQUATIONEQUATIONFinally, suppose that i ∈ V (C), i ′ ∈ N \V (C), and edge (i ′ , i) / ∈ E. ThenEQUATION≥ 1 2 (α) + 1 2 (0) = α 2 .We have shown that if e ∈ E ′ , then e ∈ E. Now we will show that there exists at least one edge e such that e ∈ E, but e / ∈ E ′ . Consider the node u described in the lemma statement, and let i ∈ V (C) be some node such that (u, i)∈ E but (u, next(i)) / ∈ E. Suppose that u / ∈ V (C). Then ⟨X ′ u , µ u ⟩ -⟨X ′ i , µ u ⟩ = ⟨X u , µ u ⟩ - 1 2 ⟨X i , µ u ⟩ - 1 2 ⟨X next(i) , µ u ⟩ = 1 2 (⟨X u , µ u ⟩ -⟨X i , µ u ⟩) + 1 2 (⟨X u , µ u ⟩ -⟨X next(i) , µ u ⟩) ≥ 1 2 (α) + 1 2 (0) = α 2 .Suppose that u ∈ V (C). Then⟨X ′ u , µ u ⟩ -⟨X ′ i , µ u ⟩ = 1 2 ⟨X u , µ u ⟩ + 1 2 ⟨X next(u) , µ u ⟩ - 1 2 ⟨X i , µ u ⟩ - 1 2 ⟨X next(i) , µ u ⟩ = 1 2 (⟨X u , µ u ⟩ -⟨X i , µ u ⟩) + 1 2 (⟨X next(u) , µ u ⟩ -⟨X next(i) , µ u ⟩) ≥ 1 2 (α) + 1 2 (0) = α 2 .This implies that (u, i) / ∈ E ′ , as desired.Lemma 8. Let X be an envy-free fractional allocation for µ and let G = create-slack-graph(µ, X, α) with edge set E. Let C = find-special-cycle(G, S(X)) and let X ′ = cycle-shift(C, X). Then X ′ is an envy-free allocation for µ.proof. Let G ′ = create-slack-graph(µ, X ′ , α/2) with edge set E ′ . It suffices to show that w e ≥ 0 for all e ∈ E ′ . By Lemma 7, if an edge (i, i ′ ) / ∈ E, then⟨X ′ i , µ i ⟩ -⟨X ′ i ′ , µ i ⟩ ≥ α 2 ≥ 0. Recall that by assumption, for any i, i ′ such that (i, i ′ ) ∈ E, ⟨X i , µ i ⟩ -⟨X i ′ , µ i ⟩ ≥ 0. Suppose that i ∈ V (C), i ′ ∈ N , and (i, i ′ ) ∈ E.Then by Equation (33) ,⟨X ′ i , µ i ⟩ -⟨X ′ i ′ , µ i ⟩ ≥ 1 2 (⟨X i , µ i ⟩ -⟨X i ′ , µ i ⟩) ≥ 0.Suppose instead that i, i ′ / ∈ V (C) and edge (i, i ′ ) ∈ E. Then by Equation (34) ,⟨X ′ i , µ i ⟩ -⟨X ′ i ′ , µ i ⟩ = ⟨X i , µ i ⟩ -⟨X i ′ , µ i ⟩ ≥ 0.Finally, suppose that i ∈ V (C), i ′ ∈ N \V (C), and edge (i ′ , i) ∈ E. Then by Equation (35) ,⟨X ′ i ′ , µ i ′ ⟩ -⟨X ′ i , µ i ′ ⟩ = 1 2 (⟨X i ′ , µ i ′ ⟩ -⟨X i , µ i ′ ⟩) + 1 2 (⟨X i ′ , µ i ′ ⟩ -⟨X next(i) , µ i ′ ⟩) ≥ 1 2 (0) + 1 2 (0) = 0.Lemma 9. Let X be an envy-free fractional allocation for µ and let G = create-slack-graph(µ, X, α) with edge set E. Let C = find-special-cycle(G, S(X)) and letEQUATIONThis implies that sw(X, µ) -sw(X ′ , µ) ≤ nα 2 .Lemma 10. Let X be an envy-free fractional allocation for µ. Let G = create-slack-graph(µ, X, α) with edge set E, and let Q be a clique in G. Let X ′ = average-clique(Q, X) andG ′ = create-slack-graph(µ, X ′ , α/n), with E ′ the edge set of G ′ . Then |E ′ | ≤ |E|. proof. It suffices to show that if an edge e / ∈ E, then e / ∈ |E ′ |. If i, i ′ ∈ Q, then edge (i, i ′ ) must be in E, as Q is a clique. Suppose that i, i ′ ∈ N \Q and (i, i ′ ) ̸ ∈ E. Then ⟨X ′ i , µ i ⟩ -⟨X ′ i ′ , µ i ⟩ = ⟨X i , µ i ⟩ -⟨X i ′ , µ i ⟩ ≥ α. Now, suppose that i ∈ Q, i ′ ∈ N \Q, and (i, i ′ ) / ∈ E. Then ⟨X ′ i , µ i ⟩ -⟨X ′ i ′ , µ i ⟩ = 1 |Q|   i ′′ ∈Q ⟨X i ′′ , µ i ⟩   -⟨X i ′ , µ i ⟩ ≥ ⟨X i , µ i ⟩ -α |Q| -1 |Q| -⟨X i ′ , µ i ⟩ ≥ α -α |Q| -1 |Q| ≥ α n .Finally, suppose that i ∈ Q, i ′ ∈ N \Q, and (i ′ , i) / ∈ E. Then⟨X ′ i ′ , µ i ′ ⟩ -⟨X ′ i , µ i ′ ⟩ = ⟨X i ′ , µ i ′ ⟩ - 1 |Q|   i ′′ ∈Q ⟨X i ′′ , µ i ′ ⟩   = 1 |Q|   i ′′ ∈Q ⟨X i ′ , µ i ′ ⟩ -⟨X i ′′ , µ i ′ ⟩   = 1 |Q|   ⟨X i ′ , µ i ′ ⟩ -⟨X i , µ i ′ ⟩ + {i ′′ ∈Q:i ′′ ̸ =i} ⟨X i ′ , µ i ′ ⟩ -⟨X i ′′ , µ i ′ ⟩   ≥ 1 n (α + 0) ≥ α n .Lemma 11. Let X be an envy-free fractional allocation for µ. Let G = create-slack-graph(µ, X, α) with edge set E, and let Q be a clique in G. Let X ′ = average-clique(Q, X). Then⟨X ′ i , µ i ⟩ -⟨X ′ i ′ , µ i ⟩ ≥ -α ∀i, i ′ ∈ N.proof. First, suppose i ′ ∈ N \Q and i ∈ N . Then⟨X ′ i ′ , µ i ′ ⟩ -⟨X ′ i , µ i ′ ⟩ ≥ min i ′′ ∈N ⟨X i ′ , µ i ′ ⟩ -⟨X i ′′ , µ i ′ ⟩ ≥ 0. Suppose instead that i, i ′ ∈ Q. Then ⟨X ′ i ′ , µ i ′ ⟩ -⟨X ′ i , µ i ′ ⟩ = 0. Finally, suppose that i ∈ Q, i ′ ∈ N \Q. Then ⟨X ′ i , µ i ⟩ -⟨X ′ i ′ , µ i ⟩ = 1 |Q|   i ′′ ∈Q ⟨X i ′′ , µ i ⟩   -⟨X i ′ , µ i ⟩ ≥ ⟨X i , µ i ⟩ -α |Q| -1 |Q| -⟨X i ′ , µ i ⟩ ≥ 0 -α |Q| -1 |Q| ≥ -α.Lemma 12. Let G = create-slack-graph(µ, X, α) with edge set E, and let Q be a clique in G. LetX ′ = average-clique(Q, X). Then sw(X, µ) -sw(X ′ , µ) ≤ n • α. proof. Observe that sw(X ′ , µ) = i∈Q ⟨X ′ i , µ i ⟩ + i∈N \Q ⟨X ′ i , µ i ⟩ ≥ i∈Q (⟨X i , µ i ⟩ -α) + i∈N \Q ⟨X i , µ i ⟩ ≥ i∈N (⟨X i , µ i ⟩ -α) ≥ sw(X, µ) -n • α.Rearranging, this implies that sw(X, µ) -sw(X ′ , µ) ≤ n • α.Lemma 13. Let G = create-slack-graph(µ, X, 0) with edge set E, and let X ′ = remove-envy(µ, X). Further letG ′ = create-slack-graph(µ, X ′ , 0) with edge set E ′ . Then |E ′ | < |E|.proof. First, we show that if an edge e / ∈ E, then e / ∈ E ′ . In other words, we will show that no new edges with positive envy (negative weight) are added. Observe that within the while loop, remove-envy distributes β i * from a set U to N \U . If at the beginning of the while loop ∃i ∈ U such that w i,i ′ < 0 for some i ′ ∈ N \U , then β i * = 0 and i ′ is added to U . Otherwise, by definition β i * is at most the minimum fraction that the set U needs to give away in order to create a new 0 envy edge between any node in U and a node i ′ ∈ N \U . Therefore, distribute-equally cannot create a new edge with positive envy by our choice of β i * , which implies that no new edge with positive envy could have been created by the end of the while loop. Now, suppose that w (u,v) < 0 at the end of the while loop. Then there is a cycle C in G r containing (u, v). Then for every i, ⟨X ′ i , µ i ⟩ ≥ ⟨X r i , µ i ⟩. The total set of allocations has not changed, so no positive envy is introduced. Now, we show that there exists an edge e ∈ E such that e / ∈ E ′ . That is, we show that we have removed some edge with positive envy. If w (u,v) = 0 at the end of the while loop, then (u, v) ∈ E proof. Consider some ℓ. By Lemma 14 we know that⟨X ℓ i , µ i ⟩ -⟨X ℓ-1 i , µ i ⟩ ≥ - α 4n 2 ∀ i ∈ N.Applying the above once for each node, we obtainsw(X ℓ , µ) = i∈N ⟨X ℓ i , µ i ⟩ ≥ i∈N ⟨X ℓ i , µ i ⟩ - α 4n 2 ≥ sw(X ℓ-1 , µ) -n • α 4n 2 . Rearranging, this implies that sw(X ℓ-1 , µ) -sw(X ℓ , µ) ≤ α 4n .Because ℓ ≤ n 2 , we therefore must have sw(X 0 , µ) -sw(X ℓ , µ) ≤ nα 4 .Lemma 16. Let G = create-slack-graph(µ, X, α) with edge set E. Suppose that for S ∈ S(X), if δ -(S) / ∈ ∅, then δ + (S) / ∈ ∅. Further suppose that-α 4bn 3 ≤ ⟨X i , µ i ⟩ -⟨X i ′ , µ i ⟩ ∀i, i ′ ∈ N Let X 0 = X and define X ℓ = remove-envy(µ, X ℓ-1 ). Finally, for ℓ ≤ n 2 let G ′ = create-slack-graph(µ, X ℓ , α 2 ) with edge set E ′ . Then |E ′ | ≤ |E|.proof. It suffices to show that if an edge (i, i ′ ) / ∈ E, then (i, i ′ ) / ∈ E ′ . By Lemma 14, in each call to remove-envy, the utility of i for the allocation of i decreases by at most α 4n 2 . Therefore,⟨X ℓ i , µ i ⟩ -⟨X 0 i , µ i ⟩ ≥ ℓ • - α 4n 2 ≥ - α 4 .Again by Lemma 14, in each call to remove-envy, the utility of i for the allocation of i ′ increases by at most α 4n 3 . Therefore,⟨X ℓ i ′ , µ i ⟩ -⟨X 0 i ′ , µ i ⟩ ≤ ℓ • α 4n 3 ≤ α 4n .Putting both equations together, we have⟨X ℓ i , µ i ⟩ -⟨X ℓ i ′ , µ i ⟩ ≥ ⟨X 0 i , µ i ⟩ - α 4 -⟨X 0 i ′ , µ i ⟩ + α 4n = ⟨X 0 i , µ i ⟩ -⟨X 0 i ′ , µ i ⟩ - α 4 - α 4n ≥ α - α 2 = α 2 as desired. Lemma 17. Let X ′ = remove-envy(µ, X). Then |S(X ′ )| ≤ |S(X)|.proof. It suffices to 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 ∩ U ̸ = ∅ and S ∩ (N \U ) ̸ = ∅, otherwise the allocation of each member of S would have changed by the same amount. Furthermore, it must be the case that in iteration r, β i * > 0, otherwise no allocation would have been transferred. In iteration r, consider some i ∈ (S ∩ U ) and i ′ ∈ (S ∩ (N \U )). Then β i = 0, as i begins iteration r with zero envy towards i ′ . Because β i * ≤ min i β i , this means β i * ≤ 0, which is 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.We are finally ready to prove Lemma 1.Proof of Lemma 1. We first prove by induction that every iteration r starts with an envy-free allocation X r . The base case is satisfied because X 0 = 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 + 1 starts with an envy-free allocation. If X r+1 = X r , then we can directly invoke the inductive hypothesis for iteration r. Otherwise, suppose that remove-incoming-edge was called in iteration r of Algorithm 3. Then by Lemma 5, iteration r + 1 starts with an envy-free allocation. Suppose instead that cycle-shift was called in iteration r. Then by Lemma 8, iteration r + 1 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 an edge with negative weight from E(G ′ ), and adds no new edges with negative weight. There are a finite number of edges in E(G ′ ), so this loop terminates. Therefore, iteration r + 1 starts with an envy-free allocation.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 r and r + 1, we prove that either1. |E(G r )| > |E(G r+1 )| or 2. |E(G r )| ≥ |E(G r+1 )| and |S(X r )| > |S(X r+1 )|. If remove-incoming-edge is called in iteration r of Algorithm 3, then by Lemma 4 we have |E(G r )| > |E(G r+1 )|. If cycle-shift is called in iteration r, then by Lemma 7 we have |E(G r )| > |E(G r+1 )|. If ∃ e ∈ E(G r ) s.t. w e ≥ α 4bn 4 , then e ∈ E(G r ) but e / ∈ E(G r+1 ). Furthermore, if e ′ / ∈ E(G r ), then e ′ / ∈ E(G r+1 ) as X r = X r+1 . Therefore, we have |E(G r )| > |E(G r+1 )|.Finally, suppose average-clique is called in iteration r on clique Q. Recall that G avg = create-slack-graph(µ, average-clique(Q, X r ), α avg ). By Lemma We now prove that the algorithm terminates with an X r which satisfies Proposition 2. Each iteration either removes an edge or merges two equivalence classes. Because the maximum number of edges is n 2 and the number of equivalence classes is n, Algorithm 3 terminates in at most n 3 iterations. We need to show that Algorithm 3 terminates with α r ≥ γ. If an iteration r does not call remove-envy, then an edge is removed and α r+1 ≥ α r 4bn 4 . There can be at most n 2 such iterations. If an iteration r does call remove-envy, then α r+1 = α r 2n . There can be at most n such iterations which call remove-envy between every iteration which does not call remove-envy, for a total of at most n 3 iterations. Therefore,α r ≥ α 0 (4bn 4 ) n 2 • (2n) n 3 =α 0 e n 2 log(4bn 4 )+n 3 log(2n) .Choosing α 0 = γ • (e n 2 log(4bn 4 )+n 3 log(2n) ) thus implies that α r ≥ γ for every iteration r if γ • (e n 2 log(4bn 4 )+n 3 log(2n) ) ≤ 1. Therefore, we set γ 0 = e -n 2 log(4bn 4 )-n 3 log(2n) . Finally, we need to show that Algorithm 3 does not significantly decrease the social welfare. By Lemmas 6, 9 and 12, we know that each of the operations remove-incoming-edge, cycle-shift, and average-clique change the social welfare by at most O(γ). Each of these operations is called at most n 3 times. Each of remove-incoming-edge and cycle-shift are called at most once for each edge, or at most n 2 times. Operation average-clique is called at most n times for each edge, or at most n 3 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 µ , µ) -sw(X r , µ) = O(γ), as desired.proof. Let a = 1, b = 3, n = 2, and m = 2, and assume that the distributions of values are all normal distributions with variance 1. For n = 2, envy-freeness and proportionality are equivalent, 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 µ * ∈ [a, b] 2×2 , the probability that the algorithm satisfies the envy-freeness constraints and has regret of less than T 2/3 log(T ) is at least 1 -1/T . Consider the following two matrices.µ 1 = 2 3 1 1 µ 2 = 2 3 1 1 + ϵDefine P 1 as the distribution of the full history H T when using algorithm ALG when µ * = µ 1 . Define P 2 as the equivalent distribution when µ * = µ 2 .We will proceed according to the following proof sketch. First, we will show that if µ * = µ 1 , then ALG with constant probability allocates Õ(T 2/3 ) items of type 2 to player 2 (Lemma 18). We next upper bound the total variation distance between P 1 and P 2 . When two distributions are sufficiently close in total variation distance, then an 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 P 1 and P 2 together imply that if µ * = µ 2 , then ALG with constant probability allocates Õ(T 2/3 ) items of type 2 to player 2. When ALG allocates Õ(T 2/3 ) items of type 2 to player 2, then ALG cannot satisfy the envy-freeness constraints for µ 2 . Therefore, the previous two sentences together imply that with constant probability, ALG will not satisfy the envy-freeness constraints for all t when µ * = µ 2 , which is a contradiction. Lemma 18. Using the notation defined above,EQUATIONIntuitively, 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 t . The proof of Lemma 18 is given in Appendix G.1.Lemma 19. Using the notation from above,KL(P 1 , P 2 ) = E P1 [N T 22 ] • KL N (1, 1), N (1 + ϵ, 1)proof. Define f 1 ik as the probability density function (pdf) of N ((µ 1 ) ik , 1) and f 2 ik as the pdf of N ((µ 2 ) ik , 1). We let f N (µ,σ 2 ) be the pdf of a normal distribution with mean µ and variance σ 2 .T = {(k t , i t , v t )} T -1t=0 , recall that X t is the fractional allocation chosen by ALG at time t given history H t . Then we have that for anyH T P 1 (H T ) = T -1 t=0 1 m X t itkt f 1 itkt (v t ) ,The 1/m term comes from item t having a 1/m probability of being of type k t . The X t itkt is the probability that ALG allocates the item of type k t to player i t at time t, and finally f 1 itkt (v t ) is the probability of seeing value v t given that the item of type k t was allocated to player i t . Similarly, we have thatP 2 (H T ) = T -1 t=0 1 m X t itkt f 2 itkt (v t ) .Therefore, we have thatKL(P 1 , P 2 ) = E H T ∼P1 log P 1 (H T ) P 2 (H T ) = E H T ∼P1 log T -1 t=0 1 m X t itkt f 1 itkt (v t ) T -1 t=0 1 m X t itkt f 2 itkt (v t ) = E H T ∼P1 log T -1 t=0 f 1 itkt (v t ) T -1 t=0 f 2 itkt (v t ) = E H T ∼P1 log T -1 t=0 f 1 itkt (v t ) f 2 itkt (v t ) = E H T ∼P1   log   t:(it,kt)=(2,2) f N (1,1) (v t ) f N (1+ϵ,1) (v t )     = E H T ∼P1   t:(it,kt)=(2,2) log f N (1,1) (v t ) f N (1+ϵ,1) (v t )   = T -1 t=0 E H T ∼P1 1 (it,kt)=(2,2) log f N (1,1) (v t ) f N (1+ϵ,1) (v t ) = T -1 t=0 E H T ∼P1 1 (it,kt)=(2,2) E log f N (1,1) (v t ) f N (1+ϵ,1) (v t ) 1 (it,kt)=(2,2) = T -1 t=0 E H T ∼P1 1 (it,kt)=(2,2) E v∼N (1,1) log f N (1,1) (v) f N (1+ϵ,1) (v) = T -1 t=0 E H T ∼P1 1 (it,kt)=(2,2) • KL (N (1, 1), N (1 + ϵ, 1)) = KL (N (1, 1), N (1 + ϵ, 1)) E H T ∼P1 T -1 t=0 1 (it,kt)=(2,2) = KL (N (1, 1), N (1 + ϵ, 1)) E H T ∼P1 N T 22 .We can use Lemma 18 and Lemma 19 to bound the KL-divergence between P 1 and P 2 byEQUATION)We next need the following result from probability theory that is a 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(F C ) + q(F ) ≥ 1 2 e -KL(p,q) .proof. For any probability distributions p and q, we have by the Bretagnolle-Huber inequality thatd TV (p, q) ≤ 1 - 1 2 e -KL(p,q) .For any event F ,d TV (p, q) ≥ |p(F ) -q(F )| ≥ p(F ) -q(F ) = 1 -p(F C ) -q(F ).Combining the above equations gives thatEQUATIONTaking p = P 1 , q = P 2 and , then player 2's envy in expectation at time t for player 1 under µ 2 (for sufficiently large T ) isF = T -1 t=0 X t 22 ≤ T 2/X t 11 • 1 + X t 12 (1 + ϵ) -X t 21 • 1 -X t 22 (1 + ϵ) = (1 -X t 21 ) • 1 + (1 -X t 22 )(1 + ϵ) -X t 21 • 1 -X t 22 (1 + ϵ) = 2 + ϵ -2X t 21 -2X t 22 (1 + ϵ) ≥ ϵ -2X t 22 (1 + ϵ) ≥ ϵ - 2T -1/3 (1 + ϵ) log(T )= T -1/3 -2T -1/3 (1 + T -1/3 ) log(T ) > 0, implying that X t does not satisfy the envy-freeness in expectation constraints under µ 2 . Therefore, Equation (41) implies that Pr P2 (EFE for µ 2 not satisfied) ≥ Pr This contradicts the assumption that ALG satisfies the envy-freeness in expectation constraints for µ 2 with probability at least 1 -1/T when µ * = µ 2 .G.1 Proof of Lemma 18 proof. Define E as the event that the algorithm ALG satisfies the envy-free in expectation constraints for µ 1 and has regret less than T 2/3 log(T ) for µ * = µ 1 . By assumption, Pr P1 (E) ≥ 1 -1/T . If µ * = µ 1 , then the social welfare maximizing envy-free allocation isY µ1 = 0 1 1 0 .Furthermore, a fractional allocation X t satisfies envy-freeness in expectation for µ 1 only ifEQUATIONTherefore, for any X t that satisfies envy-freeness in expectation for µ 1 , the regret at time t is ⟨Y µ1 , µ * ⟩ F -⟨X t , µ * ⟩ F = 4 -(2X This implies that the regret when µ * = µ 1 of ALG when ALG satisfies envy-freeness in expectation for µ 1 isT • ⟨Y µ1 , µ * ⟩ F - T -1 t=0 ⟨X t , µ * ⟩ F ≥ T -1 t=0 X t 22 .By definition, under event E, the regret of ALG for µ * = µ 1 is at most T 2/3 log(T ) and ALG satisfies the envy-freeness in expectation constraints for µ 1 . the previous equation implies that under event E,EQUATION)Recall that N T 22 is the number of times item of type 2 is allocated to player 2. Equation (44) implies thatE P1 [N T 22 | E] = E P1 T -1 t=0 X t 22 | E ≤ T 2/3 log(T ) .This implies that for sufficiently large T , E P1 [N T 22 ] = E P1 [N T 22 | E] PrTaking the complement of this equation proves Equation (37).NeurIPS Paper Checklist 
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, confidence intervals, or statistical significance tests, at 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 to 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 or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce 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 paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 a cycle with non-positive slack). Each node in the cycle is then given the allocation of the nextWe begin by proving some helpful lemmas. It will be convenient to define the following term. 
 
 Appendix:  


Decision: 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).

Reviews: review: paper_summary: paper_summary: In this work, the authors consider the problem of maximising the total utility in online fair allocation settings, where: 
(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.

The 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.
strength_weakness: strength_weakness: 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.

Major comments:

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

Minor comments:

-The acronyms efe and pe are not defined (despite clear from the context). 
-Remark 1: specify that the rows different from i and i' are composed of zeros only.
-Claims of Lemma 1 and Lemma 2: satisfy -> satisfies.
questions: questions: No questions.
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: N/A
questions: 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: limitations: N/A
paper_summary: paper_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).

EFE 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:
1. Any EFE algorithm achieves realized cumulative envy at most $\sqrt{T} \log(T)$, while optimal is at least $\sqrt{T}$.
2. EFE at each time step does not cause any welfare loss compared to only requiring EFE at the end.

The main result is a simple explore-then-commit algorithm which is EFE or PE while achieving regret $\tilde{O}(T^{2/3})$ wrt welfare. 

Along 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.
strength_weakness: strength_weakness: 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:
1. 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?
2. The paper assumes additive utility, and each branch’s utility would be extremely non-additive (no one needs infinite cereal).
3. It’s hard to imagine the donations being so unpredictable.
To 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.

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

This is more minor, but I think the citation below is quite relevant and should be discussed along with Benadè et al.

Hakuei Yamada, Junpei Komiyama, Kenshi Abe, and Atsushi Iwasaki. Learning fair division from bandit feedback. International Conference on Artificial Intelligence and Statistics, 2024.
questions: 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?

Below is feedback that you're welcome to take or leave. I don't expect responses, even though some are phrased as questions.
1. I would suggest naming Property 2 so that I don’t have to keep calling it the either-uniform-allocation-or-slack property :)
2. “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.
3. “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”.
4. 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”.
5. “proof” should be capitalized at the start of proofs
6. Why not just use gamma_0 in Property 2? Why have for all gamma < gamma_0?
7. Is it intentional for the “2” in C_{P2} to be a hyperlink to property 2?
8. Consider mentioning the actual value of (or a bound on) gamma_0 is for each property?
9. For readability in Algorithm 1, consider writing indicator variables as \mathbb{1}(stuff) instead of \mathbb{1}_{stuff}.
10. The notation “\mu in \hat{\mu} \pm \varepsilon” is non-standard to my knowledge. Consider “\mu in [\hat{\mu} - \varepsilon, \hat{\mu} + \varepsilon]”
11. 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?
12. I really like lines 323-330.
limitations: 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.

Comments: title: Rebuttal
comment: Thank you very much for your comment. We appreciate your take-aways from the entire discussion and are happy to follow your suggestions.

> In light of the above comments, I will increase my score by one point.

Just in case this somehow fell through the cracks, we believe the change (from 6 to 7) isn't reflected in your current score.
I have read the authors' response carefully, and I am satisfied with their reply. 

I strongly believe that the rationale behind the considered setting will be even more exhaustive in the revised version. Moreover, although the case of additive functions is more restrictive compared to general monotone functions, I do not think this is an issue, as this setting is one of the most studied in the field and is well established in the literature. However, I believe that the interest in this setting should not be justified by the fact that the more general setting is difficult or not possible in online learning. Finally, I think that the tight lower bound presented by the authors deserves to be mentioned in the new version (including the complete proof in the appendix), as it further justifies the approach obtained for the upper bound. 

In light of the above comments, I will increase my score by one point.
I think the frequency argument is reasonable. More generally, I think some empirical work may be warranted to determine the extent to which utilities are in fact additive, since as you say, this is quite a common assumption in this area. I understand that that's beyond the scope of the current submission, of course.
Your response is greatly appreciated. We're happy to follow your suggestion and discuss Food Drop.

> The fact that the assumption is standard doesn't make it realistic. And the fact that non-linear utilities are challenging to analyze doesn't make the actual utilities additive.

This is well taken. Not to belabor the point, but perhaps the argument we briefly mentioned about the frequency of allocations is more compelling. For example, in the food allocation data of Lee et al. (2019), there were a total of 1760 donations from 169 donors over the course of five months, and 277 organizations received donations. This means that organizations receive donations every 3-4 weeks on average, suggesting that the donations can largely be regarded as independent. 

Min Kyung Lee, Daniel Kusbit, Anson Kahng, Ji Tae Kim, Xinran Yuan, Allissa Chan, Daniel See, Ritesh Noothigattu, Siheon Lee, Alexandros Psomas, Ariel D. Procaccia: WeBuildAI: Participatory Framework for Algorithmic Governance. Proc. ACM Hum. Comput. Interact. 3(CSCW): 181:1-181:35 (2019)
I mostly find the authors' response compelling, and I will raise my score by 1 point under the assumption that the further justification for their mathematical model is incorporated into the final version of the paper. The most compelling point in my opinion is the existence of a real application that matches this mathematical model, and I would recommend the authors discuss Food Drop explicitly in the final version.

I will briefly mention that I find this aspect of their response unconvincing
> Additive utility is a standard assumption for online fair division due to the difficulty of studying non-linear utilities

The fact that the assumption is standard doesn't make it realistic. And the fact that non-linear utilities are challenging to analyze doesn't make the actual utilities additive.