Dynamic Fair Division with Partial Information
Authors: Gerdus Benade
Daniel Halpern
Alexandros Psomas
Venue: NeurIPS 2022 Accept (2022)
Keywords: dynamic fair division
partial information
distrortion

Abstract: We consider the fundamental problem of fairly and efficiently allocating $T$ indivisible items among $n$ agents with additive preferences. The items become available over a sequence of rounds, and every item must be allocated immediately and irrevocably before the next one arrives. Previous work shows that when the agents' valuations for the items are drawn from known distributions, it is possible (under mild technical assumptions) to find allocations that are envy-free with high probability and Pareto efficient ex-post. 

We study a \emph{partial-information} setting, where it is possible to elicit ordinal but not cardinal information. When a new item arrives, the algorithm can query each agent for the relative rank of this item with respect to a subset of the past items. 
When  values are drawn from i.i.d.\ distributions, we give an algorithm that is envy-free and $(1-\epsilon)$-welfare-maximizing with high probability. We provide similar guarantees (envy-freeness and a constant approximation to welfare with high probability) even with minimally expressive queries that ask for a comparison to a single previous item. For independent but non-identical agents, we obtain envy-freeness and a constant approximation to Pareto efficiency with high probability. We prove that all our results are asymptotically tight. 

Dynamic Fair Division with Partial Information
Gerdus Benadè Boston University benade@bu. edu
Daniel Halpern Harvard University dhalpernøg harvard.edu
Alexandros Psomas
Purdue University apsomas@cs. peppomaasss.peedee.ee.e edd
Abstract
We consider the fundamental problem of fairly and efficiently allocating indi- visible items among agents with additive preferences. The items become avail- able over a sequence of rounds, and every item must be allocated immediately and irrevocably before the next one arrives. Previous work shows that when the agents' valuations for the items are drawn from known distributions, is possible (under mild technical assumptions) to find allocations that are envy-free with high probability and Pareto efficient ex ex-post.
We study a partial-informatie cardinal information. When a new item arrives, the algorithm can query each agent for the relative rank of this item with respect to a subset of the past items. When values are drawn from i.i.d. distributions, we give algorithm that envy-free and (1 weelare welfare-maxiiiizng with high probability. We provide similar guaran- tees (envy- freenesss and constant approximation welfare with high probability) even with minimally expressive queries that ask for comparison to single previ- ous item. For independent but non-identical agents, we obtain envy-freeness and a constant approximation to Pareto efficiency with high probability. We prove that all our results are asymptotically tight.
setting, where it is possible to elicit ordinal but not
Introduction
We consider the following fundamental problem in fair division. A set of 7'' indivisible items, arriv- ing one at a time, must allocated among a set of n agents with additive preferences. The value vs, that agent has for the item in round is realized once the item arrives. Each item must be allocated immediately and irrevocably upon arrival, and we ask that the overall allocation is fair and efficient.
Previous work on this problem shows that, despite the uncertainty about future valuations, one can achieve simultaneous fairness and efficiency when agents' values are stochastic. Specifically, when each Vi.e is drawn i.i.d. from distribution D, the simple algorithm that maximizes welfare each item is allocated to the agent with the highest value - envy-free with high probability and (obviously) ex-post Pareto efficient [DGK* 14, KPW16]. The same guarantee holds for independent and non-identical agents (Vi,, drawn from an agent-specific distribution D.) for the algorithm that maximizes weighted welfare [BG22]. Even when agents' valuations for an item are correlated (but items are independent), Pareto efficiency ex-post compatible with strong faimess guarantees ("envy-freennes with high probability envy-freeness up-to-one item ex ex-post") [ZP20].
Despite the computational simplicity of (most of) the aforementioned algorithms, an unappeal- ing aspect, especially from a practical perspective, is the requirement that agents report an ex- numerical value for each item. Eliciting expressive additive valuations can be impractical, e.g., due to agents' cognitive limitations. Motivated by such considerations, growing body of work in AI studies what can be achieved by algorithms that only elicit ordinal information. This idea originates from [PR06]. who defined the notion of distortion to measure the worst-case de- terioration of an aggregate cardinal objective (e.g., utilitarian social welfare) due to only hav- ing access to preferences of limited expressiveness, particularly ordinal rankings. Recent works
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

prove bounds on the distortion in the context of many problems in social choice, e.g. vot- ing [CNPS17, GKM17, MSW20, MW19, Kem20a, Kem20b, GHS20J, matching [FRFZ.14) and participatory budgeting [BNPS21]; see [AFRSV21] for a recent survey.
In this paper, we study the power and limits of eliciting ordinal information in dynamic fair division. The value Ui of agent for item is drawn from unknown distribution upon arrival, and the algorithm is provided, from each agent, partial ordinal information about this item, e.g., its rank relative to the past items allocated to this agent, or even just single past item allocated to this agent. Under what distributional assumptions and elicitation constraints, can we simultaneously achieve qualitative fairness and efficiency? We answer these questions.
1.1 Our Contribution
We start by establishing a separation between the cardinal setting and our ordinal onc. Pareto effi- ciency alone is trivial (allocate all goods to the same agent) and, in the cardinal setting, is known that Pareto efficiency ex-post is compatible with envy-freeness with high probability (as long as agents are independent). We prove (Theorem 4) that in our setting, even for the case of two i..dd agents and any known distribution, envy- sevy-freeness with high probability is incompatible with even a very mild notion of (exact) Pareto efficiency, one-swap- Pareto efficiency, which requires that there is no beneficial one-to-one trade of items between agents (but allows for improvements via many- to-many trades of items).
We proceed to give an essentially matching positive result. For any number of i.i.d. agents and an unknown distribution D, there exists algorithm (Algorithm 1) that is envy-free with high probability and guarantees a (1 ---approxiimtioonn to the optimal utilitarian social welfare (the sum of utilities), for all E > 0, with high probability (Theorem 5). When item arrives, the algorithm learns for each agent i its relative rank compared to a subset of prior items allocated to agent i (but otherwise knows nothing about the underlying numerical valuation). Our algorithm works in epochs. Each epoch has an apploration/aamliinn phase, where each agent gets a pre-determined number of items, followed by an exploitation/ranking phase, where each fresh item is given an agent whose empirical quantile is largest. The goal is to make a sublinear number of errors compared to the "ideal" algorithm that allocates each item to the agent with the highest true quantile. The algorithm has to balance the need for sampling, which leads to more accurate empirical quantiles, against the number of inefficient allocations made while sampling. A significant technical barrier that we cannot fix a target accuracy because the underlying distribution is unknown. That is, for every fixed accuracy for the empirical quantiles, there exists a distribution for which this accuracy is not good enough for even a constant approximation to the optimal welfare. Instead, we need to make our epochs progressively longer, thereby guaranteeing progressively better bounds.
Given this strong positive result, we explore the limits of what we can achieve when further re- stricting the amount of information available. What if each agent can remember only single item previously allocated to them, and the fresh item is compared to just this one item?" Surprisingly, the aforementioned positive result can almost be recovered even in this very restrictive setting. We prove that there exists an algorithm (Algorithm 2) that is envy-free with high probability and guar- antees a (1 1/e)² E approximation to the optimal welfare with high probability, for all E > (Theorem 9). Our algorithm again proceeds in epochs with gradually increasing exploration and exploitation phases; this time the goal is a sublinear number of differences compared allocating each item to a uniformly random agent with quantile at least 1 - 1/n, which we prove is envy-free and approximately efficient (Lemmas 2 and 1). When exploring, the algorithm puts a new item in memory, estimates its quantile, and rejects it if not sufficiently close to 1 - 1/n. We need to sample enough to ensure high confidence in the estimated quantile, but also account for the additional sam- pling since an item 's quantile value might be far from 1 1-1/m 1/n to begin with; several technical details need to be accounted for. We give a mear-iathhnn lower bound: no algorithm with a memory of one item can achieve 1999-approximatioo to the social welfare with high probability; therefore a constant approximation (which Algorithm provides) is all we can hope for.
Finally, we relax the i.i.d. condition and study agents that are independent but not identical; each agent i's values are drawn from an unknown distribution D,. Even with unbounded memory, we
So, the algorithm only learns if the new item is better or worse than the item in memory and may. at that time, choose to replace the item in memory.
2

---

Table
Main Results
Setting
Possibility
Impossibility
Unbounded Memory, i.i.d.
EF (1 e)-welfare (Theorem 5)
EF + PO (Theorem 4) .999-welfare (Theorem 8)
Limited Memory, i..d. Unbounded Memory, non-i..d.
EF 1.99.399wwlllf (Theorem 9)
EF+ -367-PO (Theorem 13)
EF +809-PP (Theorem 12)
show that is impossible to get a L+v2s ~ .809 approximation to Pareto efficiency with probability more than 2/3, even for two agents (Theorem 12). At the same time, we prove that Algorithms and 2 are envy-free and 1/ee approximately Pareto efficient with high probability! Note that, though both algorithms give the same formal guarantees and Algorithm 2 elicits strictly less information, one might still prefer to use Algorithm since has significantly shorter exploration phases. A summary of our results can be found in Table
We leave the study of correlated agents as an interesting open problem. Finally, we note that beyond stochastic valuations, [BKPP18] show that it is possible to achieve sublinear envy by randomly allo- cating every item when agents' valuations are adversarially generated (and this optimal); however, sublinear envy is incompatible with non-trivial efficiency even in the cardinal setting [ZP20].
1.2 Related Work
number of works study fair division under ordinal preferences, e.g., [AGMW15, BELIO, BB, NNR17), NNRI17, but often these models do not assume an underlying cardinal model and work directly on the ordinal preferences. [ABM16] assume underlying cardinal information and, among other results, bound the approximation ratio of truthful mechanisms that elicit rankings. Closer to our work, [HS21] study rules that have access to the ranking of the top-k items of each agent and bound the ratio of the social welfare of the allocation returned by rule in the worst case. They also characterize the value of i needed to achieve prominent notions of fairness, namely envy-freeness up to item (EFI) and approximate maximin share guarantee (MMS), well bound the loss in efficiency incurred due to fairness constraints in this setting.
Our work contributes to the growing literature in dynamic fair division [KPS14, AAGW15, FPV15, FPV17, BKPP18, LLL18, HPPZ19, ZP20, GPT21, BKM22, GBI21, VPF21, BGGJ22, BMS22, KS22] (and we note that the celffre-maximiine the dynamic setting, even though the their settings are not explicitly dynamic). To the best of our knowledge, we are the first to study imperfect expressivity in dynamic setting in fair division.
algorithms of [DGK 14, KPW16, BG22] work in
2 Preliminaries
A set 'f indivisible items/goods, labeled by G = f1, ,T,, needs to be allocated to set of n agents, labeled by V = (1....,n) .n.. Agent E A assigns a value Us,t [0. 1] to item E G. We assume agents have additive valuation functions, so u; (S) = Eies Vi.t for S C G. An allocation is a partition of the items into bundles Ay..... An, where A, is the of items assigned agent i E A. Each allocation has associated utility profile v(A)
(A.),...., (A.)).
Items arrive online, one per round. The agents' valuations for the item in round /. (the I-th item) realized when the item arrives. Every item is allocated immediately and irrevocably before moving .t) for the set of items that arrived in the first
on to the next round. We write g" {1, rounds, and A for the allocation of agent after the t-th item was allocated. We consider two different models which specify how values are generated. In the i.i.d. model, the value of agent i for item is independently drawn from an unknown distribution D with CDF F, i.e., Vi,t ~ D for all E N and E G. the non-i.i.d model, the value of item for agent i is independently drawn from an unknown, agent-depended
distribution D, with CDF F, i.e., Ug D, for all i e N and I E G. We write X; for the random variable for i's valuation, and X,, for the random variable for i's valuation for item I. It is often convenient to work directly with the quantile of an agent's value rather than the value itself; let Q, = Fx(X;) and Q F.(X,,) respectively be the random variable denoting the quantile of agent the associated item. Note that all Q2 and Q are i.i.d. and
3

---

follow Unif(0, 1] distribution. Unless explicitly stated otherwise, we assume all distributions continuous (i.e., do not have point masses).
Ordinal information. We assume the realizations Vi, are not available. Instead, our algorithms have access to ordinal information. Specifically, given current item t, the algorithm can access each agent's ranking for S {(} U M, M S G The size of M, which we will informally refer to as the memory size, determines the complexity of eliciting information from each agent. In extreme, agent compares a new item to single item they had previously received, i.e., M C A [M] S 1. In the other extreme, t. is compared to all previous items she received, so M A We write (S) for the ranking of agent for subset S of the items, and o, " for the position of item E S with respect to subset S according to agent i. The highest value item is in position 1 and the lowest in position |S]. For example, if S {1, (1,4), 11 = I and Vi,4 0.1,
(.(S) (1 > 4), o; (S, = 1 and 0; (S, 4) = 2.
Algorithms. An algorithm A, in each step i, queries each agent for ordinal information with re- spect to some subset M and then makes (possibly randomized) allocation decision based on this ordinal information and the history so far. An instance of our problem is parameterized by the num- ber of agents and the (unknown) value distributions D...... D,,. Let Ep(( be the event that some algorithm satisfies property P (e.g., envy-freeness or PO or e- e-welfare) at time We are interested in the probability that an algorithm satisfies certain properties in the limit, as the number of rounds tends to infinity, where the randomness is over the random choices of the algorithm as well as the randomness in the valuations.
Definition 1. An algorithm satisfies P with high probability if lim Pr[Ep(t)] =1.
Note that this definition of high probability allows for dependency on n and the underlying distribu- tions (i.e., they are treated as constants).
Efficiency notions. An allocation A Pareto dominates an allocation A', denoted A A', when ((())) 2 0s (A{) for all E N and there exists j E N with (Ag) > (y(4)) An allocation A is Pareto efficiens or Pareto optimal (PO) if there is no feasible (integral) allocation that Pareto dominates it. An allocation A' is in the (one) swap-neighborhood of A when it can be created from A with single exchange of items between one pair of agents. Formally, there exist i, / and items Zj E Aj and x; E A; so that A; (A, \ (z,)) A; (A, \ {zj U [2 and A A for all other agents A j. An allocation A is one-swap Pareto optimal (SPO) it is undominated by any allocation in its swap-neighbel wwap-neighborhoo.. We use notion of approximate efficiency defined a-Pareto efficient when v(A/aa is undominated.
by [RF90] according to which an allocation
The social welfare of an allocation A is sw(A) = EieN' (AA)).. Let allocation A denote a (social) welfare optimal allocation for which (w(A")= 2 Sw(A) for all feasible allocations A. An allocation provides an a-approximation to welfare if sw(A) 2 a sw(A").
Fairness notions. We focus on prominent notion of fairness called envy-freeness. An allocation AT = (AT.... ..... A.....A))) of T items is envy-free (EF) when v,(A 2 (A{4 ) for all i,j E N, and c-strongly-envy-fie (esstron-EFF) when (A.)) 2 uy (A,)) + cf'
3 Ideal Quantile-based Algorithms.
For our analysis, it will be useful to compare our algorithms with ideal algorithms that know exact quantile values for every item (and, in fact, several of our lower bounds apply to these stronger algorithms too). Two ideal algorithms of interest are (1) quantile maximization, which allocates each item to the agent with the highest quantile value for it, and (2) "g-threshold," which allocates each item uniformly random among agents whose quantile is at least (and uniformly random over all agents, if all quantile values are less than 9).
In the i.i.d. model, quantile maximization is the same as value maximization, and thus envy-free with high probability and ex-post welfare optimal. The property we will use e-strong envy-freeness, for some distributtion
constant c, which we state as Lemma 1. This was essentially proved by [DGK+ + 14]; we provide an alternate proof that also works, essentially unchanged, for the a-1. threshold algorithm; it can be found in Appendix A.I. The main idea is that an agent's 's value for

---

an item conditioned on them receiving it is strictly larger than their value for item received by another agent. Combined with the fact that the probability of receiving an item is equal for all agents, standard concentration results ensure each agent strictly prefers their own bundle with high probability.
Lemma 1. /Essentially [DGK+14JJ 14J.] In the i.i.d and non-ii.d models, the quantile maximization algorithu and the thressolllll algorithm are c-stronglyeemy-fiee,, with high probability, where the constant c = minigx(E|X,, Qi 2 1/2] - [E(x))) (4n).
Note that is strictly positive since our distributions are continuous. In the ii.d. model, we show that the 2-1 thresholl algorithm gives a (1 - 2) approximation to welfare (Lemma 2) with high probability.
Next, we prove that the -hh-threshold algorithm guarnatees a constant approximation to welfare. T2 The main idea for this proof is that, with constant probability, some agent has a quantile of at least n-1 for each item. Additionally, giving an item an agent with quantile least 2-1 generates a
n. within a constant factor amount of welfare as giving it to the agent with the highest welfare.
((1 ((1- 2)
Lemma 2. In the i..dd model, the " threshollll algorithm guarantees approximation to welfare, with high probability, for all >
Proof. Let F be the CDF of an arbitrary continuous distribution. The expected contribution of an item to the welfare of the threshold algorithm is at least
1
E
P-1(Q) 12 n
Pr U~Uni100
Qi
2
Q~-Uni(o,1]
iEN
11
For the first term we have
E
(Q) Q2 n
E
[2)
U-.11f(0.1]
Q~Unift -=1
(g) Sumi -_1 (1)) dq
F F-1(g) nn da
(fL
(nanto (0)) 2)
(g) fneat p. 1] dg
p-1
F (() n
n
E Q~Bea|n,1]
Pr Q Betalt [11]
Q 2
E [e
(Q)
Pr QeeBeta(n.1]
n 1
E @~U
F (max Q.) VEN
Pr 1)
max Qi
where we used the fact that the maximum of draws from U(0, 1] follows a Beta(n, 1). The expected contribution to the welfare is thus at least
(max 2.)] (1- (1- EE
2
R 1 11-
F F- (max Q.) TEN
IE
F
EE @-Uni((.1]
@-UUni((o.1]
Finally, for any fixed & > 0, standard Chernoff bounds tell us that with high probability, the optimal welfare of I' items is at most T' (1++/2) ( Eq
[P- (maxIeN Q:)] while the welfare of
the threshold algorithm is at least T-(1 - e/2) (1 2) [E [ [F- "maxeE Q.))- Indeed, the expected optimal welfare is equal T 13 [ (maxieN Q.)]. the sum of T i.i.d. random variables with expectation B3-- "maxIeN Q.).. The standard multiplicative
5

---

Chernoff hound says that the of i.i.d. variables exceeds (1 + c/2) times its expectation j is most exp(-ue /12). Plugging in μ = T _0-omuoo,1]- (maxieN Q:)]. we get the desired
statement. The statement about the welfare of the threshold algorithm follows similarly. Thus, the algorithm is a
(1-2) (1-2)- -1- ( (11e/22((1+/2)2 (1- (1 (1-8)2 1 (1-2) e
2
approximation to welfare, with high probability.
Finally, we prove that both ideal algorithms are approximately efficient. Let P be the following property of an allocation: all items such that exactly one agent has quantile values at least 1 1/n are in the bundle of this agent. Both ideal algorithms (quantile maximization and 1 1 1-1/n-threshold satisfy P We prove that, in the non-i.i.. model, "' implies an almost 1/ce approximation to efficiency. Our proof uses the fact that there is a (roughly) 1/e probability that exactly one agent has the high quantile, the value of an agent's bundle in an algorithm that satisfies P is, with high probability, 1/fe approximation to their value for their T' T/n most valuable items. Therefore, when considering alternate allocation A', the agent in A' that gets at most /nn items cannot be improved upon by more than a 1/e factor. The proof can be found Appendix A.2.
Lemma 3. In the non-i.id. model, every algorithm whose allocations satisfy P is (1/e-e)-Pareee optimal, with high probability, for all & > O.
4 Unbounded Memory in the LLD. Model
We explore some fundamental limits of our setting. Efficiency by itself is easy: allocate all items to the same agent. However, in contrast to the cardinal setting, find one-swap Pareto efficiency is incompatible with envy-freeness with high probability, even for two i..dd agents, and even when the underlying distribution is known.
Theorem 4. In the ii.d. model, even for n = agents, there does not exist an algorithm A which is one-swap Pareto efficient and envy-free with high probability, according to D. for any continuous, bounded and known value distribution D.
when values are sampled
The proof can be found in Appendix B.I. The main idea is the following, As the agents are priori identical, we can assume without loss of generality that A gives the first item to agent The proof shows that, with positive probability, this decision becomes an irrevocable "mistake," in the sense that agent 2 really liked the item and agent did not. This mistake will make envy-freeness and me-swaa-PPareto efficiency incompatible.
Theorem 4 implies that when we have access only ordinal information, we need settle for some approximation to envy-freeness and efficiency. Our main positive result for this section is an algorithm that essentially matches the aforementioned lower bound.
Theorem 5. In the i..dd. model, Algorithm achieves envy-freeness and (1 - E) approximation to welfare, with high probability, for all 0.
Algorithm works in epochs: each epoch k has an exploration/sampling phase, where each agent receives pre-determined set of items, denoted G irrespective of their valuation. This is followed by an exploitation/ranking phase, where each item is given the agent with the highest empirical quantile (with respect to items received in the preceding exploration phase, i.e. G.)). The key idea for the proof is that the exploration phases will ensure nearly all of the items will go to the agent that truly has the highest quantile. Using this, the good properties of the ideal quantile maximization algorithm will carry over to Algorithm
We start with a technical lemma, which gives us a bound on the length of the exploration period we need in each epoch. The following definition will be useful.
Definition 2. A sample of n m items (where each agent is allocated exactly m items) is e-accurate if, with probability at least highest for the agent with highest quantile value.
the relative rank of fresh item (with respect to the sample) is
Lemma 6. Ife, E 1), and m E + are such that e > 2
(2(2n/))
then giving m samples to 2m
each agent is E-accurate with probability at least 1 - 8.

---

Algorithm 1: EF (1 - c)- Wellfaee
for epoch ks = 1... do
Sampling Phase: (n k items)
Give the j-th item in this phase to agent jmmo n).
Ranking Phase: (k* items)
for each item g in this phase do
Elicit of (Gt U {g}.9) g) for all i E.N
Allocate g to an agent j E arg min (G) U (9).9).
Proof. We will use the D (DKW) inequality [DKW566, Mas90] to show the empirical CDF of sampled quantiles is reasonably close a uniform distribution with probability
1 1. We then show this is sufficient guarantee E-accuracy for the chosen E. Let F; be the empirical CDF of the sampled quantiles for agent i.e., (g) for q E [0, 1] is random variable that describes the proportion of sampled items with quantile at most q. Note that F; exactly captures agent i's ranking for new item: if a fresh item has quantile qi for agent i and qj for agent j, then i ranks it higher than j exactly when (4:) (g))
Noting that the CDF for the actual quantile distribution (i.e., the uniform distribution) is the identity on [0, 1]. the DKW inequality states that for all y > 0, Pr supspuee (F((() gl > > I 2e 2mm²
We want this condition to hold for all agents, simuitaneously, with probability least 1 - 8, so
we pick 7 such that 2e -2my² S 6/n and apply a union bound: suffices to choose 7
In ln(2n/8) 2m
We now show that the DKW condition (sup,ejo.1) i] [g) gl S ?) being satisfied for all agents i is sufficient to guarantee e-accuracy. Consider sampling quantiles QI,..., Qn for fresh item. Let jmax E argmax,ex Q, be a quantile-maximizing agent (technically a random variable). Our goal is to show that with probability at least 1 (with respect to the samples of Q1..... Qn) Femax (Qimax) > Fy (Q₂) for all j * ımax, This ensures that jmax has the highest empirical rank, and hence receives the item. Let (()):..,, Q()) be the respective order statistics. A key observation is that ((n) Q(x-1) ~ [eta[[1 n|] [Gen19]. The PDF of a Beta[1, n) distribution is f(x) = nx=
for x E [0, 1]. Since f(x)= s n, Pr[Q(n) ((n-l) < p] < np for all p > 0. Plugging in P = 2y, have Pr[Q(()) Q (1- 27 2ny We will show that long E > 2my, e-accuracy holds. First, we have Pr (m) ((n-1) > 27| > 1 1- E. Conditioned on Q(n) - Q (nnn)) > 2%, the item is given to i max To see why, observe Q.aax = Q(m) and Qj I Q (n-1) for all # fmax by definition.
Using the DKW inequality condition, follows that Fimax ( (Qimae) Q mma - > 2 2 (Q,))
We conclude that for = > 2m/
(2(2//8) 2m
E-accuracy is satisfied with probability at least 1 - 5. O
Using Lemma can get, for each epoch, bound on the number of decisions where Algorithm differs from the quantile maximization algorithm.
Lemma 7. The allocation of Algorithm I differs from that of the quantile maximization algorithm after T steps by at most fT) items with high probability, where f(T) O(poly(n) -T15/16).
Proof. We start by bounding the accuracy of Algorithm 1 in each epoch k. In epoch k. each agent receives 4 items during the sampling phase. We claim that the sample in epoch & for k > 3n is Eg-accurate for & := 3n/1/3/2 with probability least 1 òg, for 5g := 2 Indeed, first note that by the choice of ks we have that εx, & E (0, 1). Hence, we just need to show that these values satisfy the inequality of Lemma 6. We have that
3n
2n
I K3
In(e2k) 2k
In 1n(2n/6s)
EK
2n
2n
2ml
13/2
13/2
2k-1
Next, fix a time T. Slightly abusing notation, let k(t) min(K E NI EK_ nk* + R. 2 t) be the M(T))
function that given an item t returns the epoch item is in. Notice that T > k== n h >
7

---

(k(T) 1)e, and therefore k(T) S 271/8. In any of the algorithm, we can classify every item t S 7 into one of four categories.
1. Item & was allocated in one of the first 3n - epochs, that is, k(t) < 3n.
2. Item f was allocated in the sampling phase of epoch k(t) 2 3n.
3. Item & was allocated in the ranking phase of epoch k(t) 2 3n; the epoch was aucuuraceurate.
4. Item & was allocated in the ranking phase of epoch k<t) > 3n; the epoch was not (k(t)) acccraat..
mistake if it was given an agent with non-maximum quantile for it. We show that the number of mistakes in each category are bounded by n 2n/5//5 1n and 158m (T) respectively, with high probability. This implies that the total number of mistakes is at most the sum of these quantities, which is O(poly(n) T116166, with high probability, via a union bound.
We say an item
The number of items the first category is at most
Σ k'n k S Σ (3n) "n (3n)² < (3n) (3n)² S nn
Hence, the number of mistakes in the first category is also at most n2
For the second category, since k(T) < 271/5, we have that the total number of items in the sampling phase (with probability 1) upper bounded by
k(7)
nk S nk(T)) < 2n/5/8
Each item in the third category has probability Ex(() of being mistake. The expected number of mistakes is therefore most 2k=3n E > 3n/2 < 3nk(T))5/2 15/16 Using Hoeffding's 's inequality we get that with high probability the number of mistakes at most 9n.11 since deviation of 15/16 occurs with probability most exp(-2n 2715// /T) exp( 2xp(-2n277//)
k(T) For the fourth category, the expected number of items is most A(T) ōgk5 2n Σ
k=3n S
2n
0c k=1 AIz < 158n. Using Markov's inequality we have that the number of mistakes is at most 158n (T) with probability at least 1 - In(T), i.e., with high probability.
Finally, we can prove Theorem 5 as a relatively straightforward consequence of I Lemma 7, since the ideal quantile maximization algorithm satisfies nice properties (e.g., Lemma 1). The full proof can be found in Appendix B.2.
Bounded Memory in the LLD.. Model
In this section, with even more limited partial information: each agent allowed to "remember" only a single item. We first show that, in this case, need to settle for constant approximations of welfare. The main idea the proof a difficult value distribution. Agents have essentially one of three values, low, medium, high. The key idea is that matter what quantile thresholds an algorithm has, it will either be the case that with reasonable probability, the highest value agent has medium value but is indistinguishable from all low value agents, the highest value agent has high value, but is indistinguishable from all medium or low value agents. In either case, the algorithm will make a mistake with constant probability, and hence cannot guarantee close optimal welfare. The full proof can be found in Appendix C.I.
interested in the more ambitious problem of designing dynamic algorithms
Theorem 8. In the i..dd model, given memory of one item per agent, there is no algorithmm that is 999-welfare maximizing with high probability for all continuous and bounded value distributions.
8

---

Algorithm 2: Bounded Memory
for Epoch k 1... do
Sampling Phase: (k-9 items)
NOTWITHINERROF < for trial = 1, =1...., 1. do
for i E NOTWTHHNERROR do
Allocate the next item to agent i, and update her memory number of items (for each agent)
Test k -N for i E NOTWITHINERRON do
if Proportion of test items for agent is within +11 /1/22 of (n - 1)/n then NOTWITHINERRON
NOTWITHINERROR (i)
Ranking Phase: 1k items)
for each item g in this phase do
if Some agent has high signal then
Give g to (uniformly) random such agent
else
Give g to agent uniformly at random
Our positive result matches this lower bound to a constant.
Theorem 9. In the i..dd model, given a memory of one item per agent, Algorithm 2 achieves envy- freeness and a (1 - 1/e)² - approximation to welfare, with high probability, for all >> O.
Algorithm 2 works in epochs, similar to Algorithm 1. In each epoch's exploration/sampling phase, tries to find an item whose quantile is close to the p-1 p-1- threshledooldd algorithm. Epoch & makes k3 such attempts, and each candidate item is tested against y fresh items to get an estimated quantile. If everything is within the error we can tolerate, the algorithm remembers this item for this epoch; oth- erwise, the agent has an arbitrary item in memory during this epoch. During the exploitation/ranking phase, Algorithm 2 tries to mimic the n-1 thressool algorithm (instead of the quantile maximization algorithm as Algorithm did), and, in fact, inherits its approximation factor (Lemma 2) exactly.
Our first technical lemma, Lemma 10, gives necessary bounds the various variables of Algo- rithm 2 for a sample to be 6-accurate with respect to the ideal threshold algorithm; see Definition 3. Its proof be found in Appendix C.2.
Definition 3. A of items in memory, one for each agent, is s-accurate with respect q² if with probability at least exactly those that value the fresh item more than their item in memory.
when a fresh item is sampled, the agents with true quantile above gº' are
Lemma 10. For all 8 1). (1) at least trials are done with In(2n/6) and (2) least e/(3n)
test items are used per trial for & 2 18n² In (47)), and (3) the tolerance for accepting an item / e(n3), then the items in memory are s-accurate (for all agents, simultaneously) with respect to
q² n with probability at least 8.
Though Lemmas 6 and 10 resemble each other (and are used analogous ways), the proofs require different techniques, the sampling processes are very different. Next, we prove analogue to Lemma 7: the number of disagreements between Algorithm and the ideal threshold algorithm sublinear." The proofs of Lemmas 7 and 11 are similar, precisely because Lemma 6 matches Lemma 10. Theorem 9 follows from Lemma 11 as in the i.i.d. case. The proofs of Lemma 11 and Theorem can be found in Appendices C.3 and C.4 respectively.
n- n=I-threshold algorithu after T Lemma 11. The allocation of Algorithm 2 differs from that of the x steps by at most (TT items with high probability, where ((T) E Oppoly(n) T11/188.
Note these are randomized algorithms, so by "differ on item" here we mean that the distributions over agents receiving the item differ.

---

6 The Non-I.I.D. Model
In this section, we study the non-i.id. model. We first establish a strong lower bound for the non-i.i.d. model. The following negative result holds even for algorithms that know the associated quantile for every fresh item.
Theorem 12. Even for non-identical agents, there no algorithm that EF and c-PO with prob- ability for e > 1t/5 R .809 and > 2/3, for all continuous and bounded value distributions.
4
Here provide proof sketch of Theorem 12. The full proof can be found in Appendix D.1.
Proof Sketch. The main idea is that an algorithm, even if it can see the exact quantiles of all items, cannot distinguish between agents having potentially different kinds of distributions. At one extreme end, agents may have nearly identical values for all items. On the other extreme, agents may only care (i.e., have high value) for, say, their top third of items.
Consider the case of two agents. Notice that if both agents have nearly identical values for all items, to be EF, the bundle sizes of both agents must be approximately the same. We then show that, no matter how an algorithm does this, it must be the case that one agent, say agent 1, receives a significant number of items with quantile outside of their top third does not receive significant number of items with quantile in their top third.
However, suppose instead the value distributions were such that agent 2 still has nearly identical values for all items, but agent only has high value for their top-third items. In the setting described above, agent 1 would be willing trade many of their bottom two-third quantile items for the items agent 2 received in their top third. By setting up this trade correctly, both agents total utilities go up by significant amount. The existence of such trade violates constant approximations to PO. N
Algorithms 1 and are envy-free with high probability, even in the non-i.i.d. model, since envy- freeness is not an "inter-agent" property. Our last result shows that they also give constant approx- imation to Pareto efficiency, by combining Lemma 3 with Lemmas 7 and 11. Its proof can be found in Appendix D.2.
Theorem 13. In the non-i.id. model, both Algorithm I (unbounded memory) and Algorithm 2 (one- item memory) are EF and (1/e-e)-PO with high probability, for all & > 0.
Interestingly, the guarantees for Algorithm 2 in the non-i.i.d. model are only marginally worse com- pared to the i.idd. model; the approximation ratio decreases from (1 - 1/e)² x 0.4 to 1/e z 0.37. Finally, note that, even though the formal guarantees in Theorem 13 are the same for the two algorithms, and even though Algorithm uses memory size of one, Algorithm has the benefit of much shorter epoch lengths (in addition to better guarantees under the i.i.d. model).
7 Conclusion
To conclude, we have analyzed the online fair division problem when agents only reveal partial information. In multiple settings, we have proved tight bounds on what properties are attainable. As for future work, one direction would be to move past the assumption that agent values are drawn independently, as we may not expect this hold in practice. Additionally, there are many other forms of partial information that could potentially achieve different properties. For example, if agents can compare not just single items but small subsets of items, then it may be possible to achieve stronger results such as arbitrarily good approximations to PO even in the non-i.i.d. setting.
Acknovledgements
Alexandros Psomas is supported in part by an NSF CAREER award CCF-2144208, Google Re- pa search Scholar Award, and by the Algorand Centres of Excellence program managed by Algorand Foundation. Any opinions, findings, and conclusions or recommendations expressed in this ma- terial are those of the author(s) and do not necessarily reflect the views of Algorand Foundation. This material is based upon work supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE1745303.
10

---

References
[AAGW15] Martin Damyanov Aleksandrov, Haris Aziz, Serge Gaspers, and Toby Walsh. Online fair division: Analysing a food bank problem. In Proceedings of the 24th International Joint Conference Artificial Intelligence (ICAI), pages 2540 2546, 2015.
[ABM16] Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis. On truthful mech- anisms for maximin share allocations. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), pages 31-37, 2016.
[AFRSV21] Elliot Anshelevich, Aris Filos-Ratsikas, Nisarg Shah, and Alexandros A Voudouris. Distortion in social choice problems: the first 15 years and beyond. In Proceedings of the 30th International Joint Conference Artificial Intelligence (IJCAI), pages 4294-4301, 2021.
[AGMW15] Haris Aziz, Serge Gaspers, Simon Mackenzie, and Toby Walsh. Fair assignment of indivisible objects under ordinal preferences. Artificial Intelligence, 227:71-92, 2015.
[BBL+17] Dorothea Baumeister, Sylvain Bouveret, Jérôme Lang, Nhan-Tam Nguyen, Trung Thanh Nguyen, Jörg Rothe, and Abdallah Saffidine. Positional scoring- based allocation of indivisible goods. Autonomous Agents and Multi-Agent Systems, 31(3):628-655, 2017.
[BEL10] Sylvain Bouveret, Ulle Endriss, and Jérôme Lang. Fair division under ordinal pref- erences: Computing envy-free allocations of indivisible goods. In Proceedings of the 19th European Conference on Artificial Intelligence (ECA!), pages 387-392, 2010.
[BG22] Yushi Bai and Paul Gölz. Envy-free and pareto-optimal allocations for agents with asymmetric random valuations. In Proceedings of the 32nd International Joint Con- ference on Artificial Intelligence (IJCAI), 2022. Forthcoming.
[BGGJ22] Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin. Online nash social welfare maximization with predictions. In I Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1-19, 2022.
[BKM22] Siddharth Barman, Arindam Khan, and Arna Maiti. Universal and tight online algo- rithms for generalized-men mean welfare. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), 2022. forthcoming.
[ВKPP18] Gerdus Benade, Aleksandr M Kazachkov, Ariel D Procaccia, and Christos-Alexandros Psomas. How make envy vanish over time. Proceedings of the 10th ACM Con- ference on Economics and Computation (EC), pages 593-610) 2018.
[BMS22] Anna Bogomolnaia, Hervé Moulin, and Fedor Sandomirskiy. On the fair division of 2022.
random object. Management Science, 68(2):
[BNPS21] Gerdus Benade, Swaprava Nath, Ariel D Procaccia, and Nisarg Shah. Preference elicitation for participatory budgeting. Management Science, 67(5):2813 12-222277 2021.
[CNPS17] loannis Caragiannis, Swaprava Nath, Ariel D Procaccia, and Nisarg Shah. Subset selection via implicit utilitarian voting. Journal of Artificial Intelligence Research, 18:123-152, 2017.
[DGK*14] 14] John P. Dickerson, Jonathan Goldman, Jeremy Karp, Ariel D Procaccia, and Tuomas Sandholm. The computational rise and fall of fairness. Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI), pages 1405-1411, 2014.
[DKW56] Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pages 642-669, 1956.

---

[FPV15] Eric Friedman, Christos-Alexandros Psomas, and Shai Vardi. Dynamic fair division with minimal disruptions. In Proceedings of the 16th ACM Conference on Economics and Computation (EC), pages 697-713, 2015.
[FPV17] Eric Friedman, Christos-Alexandros Psomas, and Shai Vardi. Controlled dynamic fair division. Proceedings of the 18th ACM Conference on Economics and Computation (EC), pages 461-478, 2017.
[FREZ14] Aris Fatsska, Søren Kristoffer Stiil Frederiksen, and Jie Zhang. Social wel- fare in one-sided matchings: Random priority and beyond. In Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT), pages 1-12, 2014.
[GBI21] Artur Gorokh, Siddhartha Banerjee, and Krishnamurthy Iyer. From monetary to non- monetary mechanism design via artificial currencies. Mathematics of Operations Re- search, 2021.
[Gen19] James E Gentle. Computational statistics. Springer, 2019.
[GHS20] Vasilis Gkatzelis, Daniel Halpern, and Nisarg Shah. Resolving the optimal metric dis- tortion conjecture. In Proceedings of the 61 Symposium Foundations of Commputrr Science (FOCS), pages 1427-1438, 2020.
[GKM17] Ashish Goel, Anilesh K Krishnaswamy, and Kamesh Munagala. Metric distortion of social choice rules: Lower bounds and fairness properties. In Proceedings of the 18th ACM Conference on Economics and Computation (EC), pages 287-304, 2017.
[GPT21] Vasilis Gkatzelis, Alexandros Psomas, and Xizhi Tan. Fair and efficient online allo- cations with normalized valuations. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pages 5440-5447, 2021.
[HPPZ19] Jiafan He, Ariel D Procaccia, Alexandros Psomas, and David Zeng. Achieving a fairer future by changing the past. Proceedings of the 28th International Joint Conference Artificial Intelligence (IJCAI), pages 343-349, 2019.
[HS21] Daniel Halpern and Nisarg Shah. Fair and efficient resource allocation with partial information. In Proceedings of the 30th International Joint Conference Artificial Intelligence (IJCAI), pages 5456-5463, 2021.
[Kem20a] David Kempe. An analysis framework for metric voting based on Ip duality. In Pro- ceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 2079- 2086, 2020.
[Kem20b] David Kempe. Communication, distortion, and randomness in metric voting. In Pro- ceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 2087- 2094, 2020.
[KPS14] Ian Kash, Ariel D Procaccia, and Nisarg Shah. No agent left behind: Dynamic fair division of multiple resources. Journal of Artificial Intelligence Research, 51:579- 603, 2014.
[KPW16] David Kurokawa, Ariel D Procaccia, and Junxing Wang. When can the maximin share guarantee be guaranteed? In Proceedings of the 30th AAAI Conference Artificial Intelligence (AAAI), pages 523-529, 2016.
[KS22] Yasushi Kawase and Hanna Sumita. Online max-min fair allocation. In Proceedings of the 15th International Symposium on Algorithmic Game Theory (SAGT), pages 526 543, 2022.
[LLL18] Bo Li, Wenyang Li, and Yingkai Li. Dynamic fair division problem with general valuations. Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pages 375-381, 2018.
12

---

[Mas90] Pascal Massart. The tight constant in the Dxortazky-Kiffeeewolfooiiiiziii inequality. The annals of Probability, pages 1269-1283, 1990.
[MSW20] Debmalya Mandal, Nisarg Shah, and David P Woodruff. Optimal communication- distortion tradeoff in voting. In Proceedings of the 21 ACM Conference on Eco- nomics and Computation (EC), pages 795-813 2020.
[MW19] Kamesh Munagala and Kangning Wang. Improved metric distortion for deterministic social choice rules. In Proceedings of the 20th ACM Conference Economics and Computation (EC), pages 245-262, 2019.
[NNR17] Nhan-Taae Tam Nguyen, Trung Thanh Nguyen, and Jörg Rothe. Approximate solutions to max-min fair and proportionally fair allocations of indivisible goods. In Proceedings of the 16th International Conference Autonomous Agents and Multi-Agent Systems (AAMAS), pages 262-271, 2017.
[PR06] Ariel D. Procaccia and Jeffrey S. Rosenschein. The distortion of cardinal preferences in voting. Proceedings of the 10th International Workshop on Cooperative Infor- mation Agents (CIA), pages 317-331, 2006.
[RF90] Günther Ruhe and Bernd Fruhwirth. e-optimality for bicriteria programs and its appli- cation to minimum cost flows. Computing, 44(1):21-34, 1990.
[VPF21] Shai Vardi, Alexandros Psomas, and Eric Friedman. Dynamic fair resource division. Mathematics of Operations Research, 2021.
[ZP20] David Zeng and Alexandros Psomas. Paimess--fficiency tradeoffs in dynamic fair division. In Proceedings of the s ACM Conference on Economics and Computation (EC), pages 911-912, 2020.
13


Reviews:
[{"review_id": "RH1mgpZTJa_", "reviewer": "Reviewer_rhEt", "summary": "The paper considers notions of fairness in an online (dynamic) input setting, wherein items arrive one at a time and must be irrevocably allocated to one of the $n$ agents of the system. Specifically, the authors focus on the \"partial information\" setting where the algorithm has access to ordinal, rather than cardinal information. This is an interesting problem context that, in spite of its increased complexity, is shown to allow for strong fairness guarantees. The paper presents asymptotically tight results for envy-freeness and approximation social welfare maximization under different partial information assumptions (with high probability arguments).", "questions": "Have the authors considered other input models (such as adversarial or random order)? Is the iid problem setting the only one in which such strong (and asymptotically tight) results be achieved?\n\n", "limitations": "The authors mention the correlated input model as a future direction (that is not considered in the submission). I think the above mentioned input models should also be considered limitations of the present work as the iid input is necessarily the strongest assumption.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The writing is very clear and easy to follow throughout the paper. Discussion of the results and presentation of their proofs is also nicely presented.\n\n2. The problem context is very interesting and seems to have only been considered in a handful of papers. Additionally, all presented results are asymptotically tight (proofs seem correct) which nicely opens and closes certain questions.\n\nWeaknesses:\n1. The authors appear to be missing some important citations that discuss related work. In particular, \"Dynamic Fair Division with General Valuations\" (Li el al 2018) seems to be a notable omission. Other papers of interest that are not cited: \"A simple online fair division problem\" (Bogomolnaia et al. 2019) and \"Online Nash Social Welfare Maximization with Predictions\" (Banerjee et al 2022). \n\n2. While the problem context is well-defined, it does feel that the motivation for it is somewhat lacking. A more extensive discussion of the related work and how the present work fits into that context + some discussion and concluding remarks would be beneficial in this regard for the uninitiated reader.\n\n3. Though most of the writing and proofs are clear, it might be beneficial to defer more of the highly analytic steps to the appendix in favor of a more intuitive discussion of the result (which could in turn save some space to include the above).\n\n4. The iid input assumption seems a bit weak. Do any results exist in the partial information model for the adversarial or random order input models?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "R51oSWk8W_q", "reviewer": "Reviewer_c1uw", "summary": "The paper studies a standard sequential item allocation problem where items need to be irrevocably allocated to agents upon arrival. The goal is to achieve some notion of fairness (e.g. envyfreeness) and efficiency (e.g. Pareto efficiency).  This paper extends the previous works by focusing on achieving these properties only through partial information (e.g. ordinal relative ranking of items). The authors focus on two main models\n\n1)\tUnbounded memory model where an algorithm learns the relative ranking of the item compared to prior items, and\n2)\tBounded memory model where each agent only “remembers” a single prior item and the algorithm can only compare against that item.\n\nThe paper studies agents with i.i.d (known or unknown) distributions as well as non-i.i.d  distributions. In both cases, the authors devise careful sampling algorithms to achieve envyfreeness and some approximation to welfare with high probability.\n", "questions": "Phase transitions: The paper only focuses on achieving envy-freeness at the end in contrast to satisfying some notion of fairness at each step. If we consider fairness at each step (or even epoch), what type of EF guarantees can we expect? Is there going to be a phase transition at some step similar to the phase transition shown by Dickerson et al.? If yes, when would the phase transition occur?\n\n\nIn the model that takes ordinal information as rankings, the preliminaries section does not properly explain how to deal with weak preferences or ties. How does the algorithm deal with ties when eliciting ranks of the fresh item? Can you elaborate on this?\n\nUpdating memory: in Algorithm 2, at each epoch an agent’s memory is updated with comparison with (prior) k^6 items. What is the reason behind such updating mechanism? If an agent’s error is not within the tolerance, an arbitrary item is chosen to be remembered. This seems a bit arbitrary (no pun intended). Is the reason mainly due to assumptions on distributions? \nWouldn’t it be more beneficial to remember a certain item (say the one with the average highest ranking)? \n\nAlgorithm 1 uses more memory compared to Algorithm 2 but they both achieve the same guarantee on the non-iid model. However, Algorithm 1 offers shorter epochs. Could Algorithm 1’s bound improve with longer epochs? In other words, is the bound tight both for iid and non-iid models?\n\nThe crux of the paper is assuming envyfreeness and devising exploration techniques to achieve reasonable welfare approximations. I wonder whether it is possible to improve on efficiency (or its approximations) by relaxing the fairness notion to EF1, proportionality, etc.?\nThe first question is whether the impossibility results in Theorem 4 or 12 still hold.  \n\nIn general, simultaneously achieving fairness and strategyproofness is a challenging task; and it is often impossible in fair division. I wonder if there is a way to achieve strategyproofness under the settings of this paper (e.g i.i.d bounded or unbounded models)?  \nLet me elaborate: in fair division models, strategyproofness is quite challenging to achieve in general (there are several incompatibility results even with relaxations to fairness). However, there may be some hope in the models with i.i.d distributions, or models that limit elicitation process (such as this paper), and/or when randomization can help alleviate the incompatibilities. \n\n\nProof of theorem 4 constructs an instance with two agents where an arbitrary agent receives an item that is not liked so much by it, but it is liked by the other agent. Although constructing such examples/events is easy, the argument is quite neat and shows the limitations of satisfying EF and a weak efficiency notion with high probability even in the i.i.d model. \n", "limitations": "No. The authors do not explicitly discuss any limitations to their results. In fact, I encourage the authors to include a concluding remarks section and discuss not only the limitations (or boundaries) of their results but also some potential future directions.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n-\tFair division is a fundamental research direction within AI and computational social choice; the dynamic aspects of fair division, whether it is with respect to dynamic item allocation or elicitations are all intriguing directions with practical value. The current paper makes progress in three different dimensions: achieving fairness and efficiency, dynamic resource allocation, and elicitation frameworks and information loss (due to ordinal vs. cardinal elicitation formats). \n\n-\tIt is well known that when there are more items than agents (larger than a logarithmic factor), envyfree allocations exist with high probability (Dickerson et al. 2014). While achieving envyfreeness or efficiency separately are trivial under distributional assumptions, simultaneously achieving both is a challenge. Thus, the current paper focuses on sampling/exploration frameworks to improve efficiency bounds (while EF is easy) with unbounded memory (and thus, comparisons). The most surprising result is that the authors show that you can achieve these bounds for efficiency with high probability even if agents are forgetful, i.e., they can only compare a new item with a single prior item.\n\n-\tThe results in the paper including incompatibility results (Theorems 4 and 12) and the proof of the two algorithms involve challenging (and non-trivial) arguments and seem to be sound--although the write up of the proofs can be improved (see my next comments).\n\nWeaknesses:\n\n-\tThe write up of the paper can become quite challenging at various points. There is a general assumption that a reader should be more or less familiar with the techniques, reasons they work, etc. which can make the paper inaccessible to a general NeurIPS audience. On the other hand, even for a researcher in computational social choice and fair division, some sections and explanations lack sufficient intuition, which could make the paper hard to follow.\n\n-\tThe proofs are written mainly formally, which is a plus. However, I was not able to fully follow some of the proof arguments, perhaps due to missing steps. It could be nice to include full proofs and provide intuition on the most challenging aspects of the proof (some steps are easy to see).\n\n-\tIt is a bit awkward to end a paper with no conclusions or mention of future directions. The ending of the paper seems a bit abrupt.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "K7a4YFuUjSr", "reviewer": "Reviewer_qJFx", "summary": "Fair division of indivisible goods is a flouring research area in computation social choice. There are some works that study the dynamic setting when the items arrive one by one, and the algorithm needs to make immediate and irrevocable decisions at the time when a new item arrives. The existing works already show that when the values are independently drawn from an identical distribution, we can achieve envy-free with high probability and PO simply by allocating each item to the agent who has the highest value. This result can be extended to the cases of agent-specific distributions and correlated agents. All these results require the knowledge of distributions and the realized values, which motivates the current work to study the partial information setting when the algorithm only has ordinal (relative) rankings. \n\nThe current work assumes that at the time a new item arrives, the relative rankings of the item in each agent’s bundle are revealed to the algorithm, based on which the algorithm needs to allocate whom to allocate it. Different from the cardinal setting, the authors first showed that envy-freeness with high probability is incompatible with (exact) Pareto optimality, but compatible with approximate PO and utilitarian optimal welfare. The algorithm, consisting of exploration/sampling phase and exploitation/ranking phase, is natural, where the first phase is used to store samples that can be used to calculate the empirical quantiles. The authors (approximately) optimized the length of the sampling length where longer means more accurate empirical quantiles but more inefficient allocations. \n\nSecondly, the authors also studied a more demanding setting where the relative ranking is restricted to a fixed number of items, representing the limited memory situation. Fortunately, the previous results can almost be recovered. \n\nFinally, the authors also explored the extent to which fairness and efficiency are compatible for non-iid models. \n\nQuestions:\n\nWhat if the distributions are not bounded or continuous? How will they change the current results?\n\nTypos:\nThe paper is well written, as far as I check. I did not find many typos, but \\ldots and \\cdots should be consistent. ", "questions": "What if the distributions are not bounded or continuous? How will they change the current results?", "limitations": "N.A.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\nThe partial-information model is very interesting to me. The results are natural and complete. The paper is well-written and easy to follow. \n\nWeaknesses: \n\nI worry about the technical contribution. The algorithms are very standard by using the first phase to record the samples which provide empirical quantile estimations for items in the second phase. Of course, the results are not straightforward, but I did not find many technical novelties. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FY3kxSr4YD", "reviewer": "Reviewer_8ye5", "summary": "This paper studies a fair allocation problem in a dynamic setting, where items arrive one by one. Agents have additive valuations and a valuation of an items follows an unknown distribution (i.i.d/non-i.i.d.). In this paper, it is assumed that an algorithm cannot know the cardinal information of the valuation, but can obtain the ordinal information. For the i.i.d. case when agents can compare a new item with any subsets of previously allocated items, the authors give an algorithm whose output is EF and also $(1-\\epsilon)$-approximation to optimal utility with high probability. When agents can compare a new item with one of previously allocated items, the authors give an algorithm whose output is EF and also $((1-1/e)^2-\\epsilon)$-approximation to optimal utility with high probability. Finally, for the non-i.i.d. case, the authors show that the aforementioned two algorithms output an allocation that is EF and 1/e-approximately Pareto optimal with high probability.", "questions": "Is there any relationship between the problem of this paper and the secretary problem? The idea of deciding a threshold by estimation also appears in papers related to the secretary problem.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Originality: The problem setting where an algorithm has access only to the ordinal information is novel in the line of dynamic settings. The idea of proposed algorithms is to estimate the distribution by sampling, and this is done by combining existing ideas carefully.\n- Quality: The results seem correct as far as I have checked. It is better to mention some application if the authors have some in mind. The framework of the proposed algorithms looks like the $\\epsilon$-greedy algorithm of the stochastic bandit problem. It may be possible to improve the performance by incorporating ideas of bandit algorithms.\n- Clarity: I feel that this paper is mostly well-written. I recommend the authors to place a table that summarizes the contributions (about possibilities and impossibilities) so that the reader can grasp the main results at a glance.\n- Significance: I do not think that the fair allocation attracts much attension in the NeurIPS community. Nevertheless, the proposed algorithms is built by a kind of learning technique, and seem closely related to the bandit algorithms, so I guess that this paper is related to this conference.\n- Minor comments:\n    - The term $\\alpha$-Pareto efficient can be changed to $\\alpha$-Pareto Optimal for consistency of terms. In Theorem 13, the authors use “$(1/e-\\epsilon)$-Pareto optimal.”\n    - line 169: $v_i(V_j)$ → $v_i(A_j)$\n    - If $c$-strongly-EF was introduced before, it is better to add a reference in the definition.\n    - For the non-i.i.d. model, the criteria of efficiency is moved on to the Pareto optimality from the utilitarian welfare. I guess that this is because it is hard to approximate the utilitarian welfare in the non-i.i.d. case. It may be helpful if the authors mention about this in the introduction of Section 6.\n    - There are some other recent papers related to the online fair allocation, say,\n        - Banerjee, Gkatzelis, Gorokh, and Jin. Online Nash Social Welfare Maximization with Predictions, SODA 2022\n        - Kawase and Sumita. Online Max-min Fair Allocation, SAGT 2022\n        \n        If the authors find some relationship, please refer these papers.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept