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,28,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 [29,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.
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,22]. 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,19,26]. 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,27,30,32].
Wei et al. [31] 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,24]. 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 [20,21]. 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 [25].
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 . This distribution is independent of both player i's distributions for other item types and other players' distributions. 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 allocation
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
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. 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. 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 10 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 ,
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 histories
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 2 shows that in our setting, no algorithm can with high probability output an allocation A(ALG) with realized envy less than √ T . 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 2 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 2 with Theorem 3, which 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. 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 4 (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 4 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.
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.
When µ * 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
We are now ready to present the formal problem statement. Problem 1. Suppose we are given n, m, T, a, b such that 0
. 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.
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 ℓ ∈
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 a γ 0 such that for any γ < γ 0 and any µ, there exists a fractional allocation X ′ such that ⟨X ′ , µ⟩ F ≥ ⟨Y µ , µ⟩ F -C P2 γ for constant C P2 > 0, and such that for each ℓ ∈ [L], either
The envy-freeness in expectation constraints satisfy 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 if
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 4 removes envy from at least one edge. Algorithm 4 does so by first carefully redistributing allocation among the nodes until there exists a cycle where each node has non-negative envy (which is equivalent to a cycle with non-positive slack). Each node in the cycle is then given the allocation of the next node in the cycle. We prove that each call to Algorithm 4 decreases the number of edges with envy, while not increasing the number of edges in the 'envy-with-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 proportionality in expectation constraints satisfy 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
The allocation X ′ is then constructed as
Intuitively, this can be viewed as each player putting a part of their allocation (proportional to S i • γ) into a communal "pot." The pot, consisting of
for 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
Observation 2. The envy-freeness in expectation and proportionality in expectation constraints satisfy Property 3.
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 µ.
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
for t ← T 2/3 to T -1 do At time t, use fractional allocation X t = X. end for 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 to
, 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 that
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 µ ∈ μ ± ϵ,
[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,
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.
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,23].
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 [29].
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. Definition 4. The realized envy of allocation A at time
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 2 shows that in our setting, no algorithm can with high probability output an allocation A(ALG) with realized envy less than √ t. Conversely, Theorem 3 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 2. 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:
Realized Envy of Player
Realized Envy of Player 2 at time τ = τ t=0
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:
By 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
Putting these equations together, we have that
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.
Theorem 3. 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 envy-freeness in expectation, then with probability 1 -o(1/T ), the realized envy of A τ (ALG) at every time τ ∈ [T ] is at most √ τ log(T ).
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
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 τ . Then
Therefore, we can apply McDiarmid's inequality to get that
≤ T -log(T )/(2B 2 ) .
Since ALG is envy-free in expectation, we know that
Therefore, we must have that
Taking a union bound over all pairs i, i ′ and all τ ∈ [T ], we have that
Therefore, with probability 1 -o(1/T ), the realized envy at evert time τ is at most √ τ log(T ).
Note that Theorem 2 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 2 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 4 shows that this is equivalent to maintaining envy-freeness in expectation at all times t ∈ [T ] when maximizing social welfare. Theorem 4. 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 satisfy
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 that
First, observe that by the definition of F , we have that for all i, i ′ ,
By linearity of expectation, Equation ( 8) is equivalent to
Furthermore, by definition
We will construct the algorithm ALG ′ as follows. Suppose ALG ′ is time-independent and historyindependent, such that for all t, H t ,
The expected social welfare of ALG ′ is
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 ,
Starting with the LHS and plugging in the definition of ALG ′ , we have that
as desired. Therefore, we have shown that ALG ′ ∈ E.
Theorem 5. 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 4, 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 2-5 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 i
As in Theorems 2 and 3 , 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 6. 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 2, 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 Player
Realized proportionality gap of Player 2 at time τ = 1 2 τ t=0
) 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 2.
Theorem 7. 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 of A τ (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 3, 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 4 and Theorem 5 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 8. 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 satisfy
proof. Suppose ALG ∈ F . We will define ALG ′ as in Theorem 4 to be
Because E ⊆ F and because we showed in Theorem 4 that ALG ′ and ALG have the same expected social welfare, the desired result follows.
Theorem 9. 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 8, 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.
In 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,k
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 10. 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, let
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 allocation
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.
] 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 by
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 ,
where 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,
For the rest of this proof, we will assume that
which by Equations ( 13) and ( 14) happens with probability 1 -1/T .
If K is the Lipschitz constant for this family of constraints, then by Equation ( 15), 2K∥ϵ∥ 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 that
and such that for every constraint ℓ ∈
For 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 µ ∈ μ ± ϵ,
Therefore, if Equation ( 18) holds for a constraint ℓ, then for any µ ∈ μ ± ϵ,
[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 ℓ,
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
By Equation ( 16), this implies that
Therefore,
).
[Equation ( 15)]
Combining with Equation ( 12), this gives a total regret of
= Õ(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.
In 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 or
LP (22) has n constraints, one corresponding to each player. Define
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:
a 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 by
. Furthermore, X ′ = UAR clearly satisfies the other condition because every player is treated equally.
Case 2:
a 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. Define
By construction, we have that
Because
Furthermore, for every i,
With Equation (25), this implies that ∆ ik ≤ Y µ ik . Finally, we note that
Now we are ready to construct X ′ . Let
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 that
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 have
[Eq (26)] Furthermore, we can bound the decrease in social welfare between fractional allocation X ′ and Y µ by
[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
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 if
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 ′ , where
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 ′ , where
Definition 10. Let Q be a clique in a graph G = create-slack-graph(µ, X, α). Then the subroutine average-clique(Q, X) returns X ′ , where
We 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).
Algorithm 4 Remove Envy (also referred to as subroutine remove-envy(µ, X 0 ))
while w (u,v) < 0 and there does not exist a cycle in G r containing (u, v) do
// Let prev(i) and next(i) be the nodes before and after i in C, respectively.
We begin by proving some helpful lemmas. It will be convenient to define the following term. 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).
proof. We first show that if an edge e / ∈ E, then e / ∈ E ′ . Note that for any i, i ′ such that (i, i ′ ) / ∈ E,
Therefore, to show that an edge (i, i ′ ) not in E is also not in E ′ , it suffices to show that
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,
Every pair of nodes i, i ′ ∈ S has their fractional allocation reduced by the same amount, so
Similarly, every pair of nodes i, i ′ ∈ N \S has their fractional allocation increased by the same amount, so
Finally, we observe that for any i ∈ S and i ′ ∈ N \S,
where the second inequality is because
Recall that δ -(S) ̸ = ∅ in G. We will now show that δ -(S) = ∅ in G ′ . Observe that for i ∈ S and i ′ ∈ N \S,
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
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 let X ′ = remove-incoming-edge(S, α, X). Then sw(X, µ) -sw(X ′ , µ) ≤ αn 2 .
proof. Observe that
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, i
proof. We first show that if an edge e / ∈ E, then e / ∈ |E ′ |. Suppose that i ∈ V (C), i ′ ∈ N , and edge
Now, suppose that i, i ′ / ∈ V (C) and edge (i, i ′ ) / ∈ E. Then
Finally, suppose that i ∈ V (C), i ′ ∈ N \V (C), and edge (i ′ , i) / ∈ E. Then
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)
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
Then by Equation (34),
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 let
This 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) and
Finally, suppose that i ∈ Q, i ′ ∈ N \Q, and (i ′ , i) / ∈ E. Then
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
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 let G ′ = create-slack-graph(µ, X ′ , 0) with edge set E ′ . Then
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 and (u, v) ̸ ∈ E ′ so we are done. Otherwise, there is a cycle in G r containing (u, v). As the overall set of allocations has not changed and ⟨X v , µ u ⟩ -⟨X u , µ u ⟩ > 0, we must have i ∈ V (C) s.t. ⟨X ′ i , µ u ⟩ -⟨X ′ u , µ u ⟩ < 0 < i ∈ V (C) s.t. ⟨X i , µ u ⟩ -⟨X u , µ u ⟩ < 0 .
Therefore, there exists some edge e = (u, i) for i ∈ V (C) such that e ∈ E but e / ∈ E ′ .
Applying the above once for each node, we obtain sw(X ℓ , µ)
≥ 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,
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,
Putting both equations together, we have
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 either 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.