Robust Rent Division
Authors: Dominik Peters
Ariel D. Procaccia
David Zhu
Venue: NeurIPS 2022 Accept (2022)
Keywords: fair division
computational social choice
learning theory

Abstract: In fair rent division, the problem is to assign rooms to roommates and fairly split the rent based on roommates' reported valuations for the rooms. Envy-free rent division is the most popular application on the fair division website Spliddit. The standard model assumes that agents can correctly report their valuations for each room. In practice, agents may be unsure about their valuations, for example because they have had only limited time to inspect the rooms. Our goal is to find a robust rent division that remains fair even if agent valuations are slightly different from the reported ones. We introduce the lexislack solution, which selects a rent division that remains envy-free for valuations within as large a radius as possible of the reported valuations. We also consider robustness notions for valuations that come from a probability distribution, and use results from learning theory to show how we can find rent divisions that (almost) maximize the probability of being envy-free, or that minimize the expected envy. We show that an almost optimal allocation can be identified based on polynomially many samples from the valuation distribution. Finding the best allocation given these samples is NP-hard, but in practice such an allocation can be found using integer linear programming.

Robust Rent Division
Dominik Peters CNRS, Université Paris Dauphine-PSI. Cominik@lamsad..fff fr
Ariel D. Procaccia
Harvard University
arielpro@seas barvard.edu
David Zhu Harvard University david, wwwwgmaallaaaaeommamma com
Abstract
In fair rent division, the problem is assign rooms roommates and fairly split the rent based on roommates' reported valuations for the rooms. Envy-free rent division is the most popular application standard model assumes that agents can correctly report their valuations for each room. In practice, agents may be unsure about their valuations, for example because they have had only limited time to inspect the rooms. Our goal is to find robust rent division that remains fair even if agent valuations are slightly different from the reported ones. We introduce the lexislack solution, which selects rent division that remains envy-free for valuations within as large a radius as possible of the reported valuations. We also consider robustness notions for valuations that come from a probability distribution, and use results from learning theory to show how we can find rent divisions that (almost) maximize the probability of being envy-free, or that minimize the expected envy. We show that an almost optimal allocation can be identified based polynomially many samples from the valuation distribution. Finding the best allocation given these samples is NP-hard, but in practice such an allocation can be found using integer linear programming.
the fair division website Spliddit, The
Introduction
The literature fair division of resources has produced allocation mechanisms for many domains, such as course allocation, indivisible goods, chores, house assignment, and the selection of citizens' assemblies [Budish, 2011, Caragiannis et al., 2019, Moulin, 2019, Flanigan et al., 2021]. But arguably the most widely used example is rent division: this is the most popular application on the fair division website spliddit.org [Goldman and Procaccia, 2014], where it has been used more than 30,000 times since its launch in 2014.
Rent division deals with the common situation where group of n future roommates are planning to move into a house or apartment which has n rooms, one for each roommate. They will split the rent payments among themselves. The roommates may differ in how much they are willing to pay for different rooms. Given the room valuations of each roommate, our task to assign the rooms, and to decide how to split the rent. We wish to do this fairly, and envy-free: no roommate would strictly prefer to get another room, given the prices we have assigned to those rooms. Such an allocation is guaranteed to exist [Svensson, 1983].
will choose an allocation that is
Let us consider an example with n = 3 roommates, and let the total rent be $1000. Table shows the valuation that each agent assigns to each room. Given this information, the algorithm in use on Spliddit will assign Room to Alice, Room 2 to Bob, and Room 3 to Charlie, charging them $100, $500, and $400 respectively. This allocation is envy-free under the assumption (which we will make
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Room
Room
Room
Alice
300
400
300
Bob
300
700
0
Charlie
300
100
600
Spliddit
100
500
400
Lexislack
200
450
350
Table Example of valuations. In any envy-free allocation, Alice gets room Bob gets room 2, and Charlie gets room 3. The lower rows display the price vectors selected by Spliddit's rule (maximin) and by our lexislack rule.
Alice
Bob
Charlie
Alice
Bob
Charlie
Bie logai
ddlcusoo Inteedi
2041
2100
200
2010
2001
DOC
100
250
1100
250
Bouk Spiikal's rod: and Losilack may und thas lura gray
(a) Spliddit
(b) Lexislack
Figure 1: Illustration of the example in Table 1. For Spliddit's rule and for our lexislack rule, we show the quasilinear utility (value minus price) that each agent gets from each room. The bar corresponding to the room assigned to the agent is shaded in blue. Both rules are envy-free, and thus the blue bars at least high the gray bars. Subject to envy- freeness, Spliddit's 's rule maximizes the height of the shortest blue bar. Lexislack maximizes the differences height between the blue and the gray bars.
throughout) that agents have quasilinear utilities: their utility under allocation is the value of their room minus its price. For example, Alice has utility 300 100 = 200. She does not envy the others: Bob's room would give her only utility 400 500 200, and Charlie's room 300 400 < 200.
a typical instance, there are infinitely many allocations that are envy-free. Spliddit's algorithm chooses the one that maximizes the utility of the worst-off agent, subject to envy-freeness [Gal et al., 2017]. This is known as the maximin rule. In optimizing this objective, Spliddit might choose an outcome that only barely envy-free. In the example, Bob has utility 700 500 200, but he would gain the same utility from having Alice's 's room: 300 100. If, upon moving in, Bob discovers a defect in his room and now only values at 600, say, then he would envy Alice. Thus, the envy-freeness of Spliddit's 's allocation is not robust.
We study the rent division problem with the goal of finding allocations that are robustly envy-free, in the sense that they remain envy-free even if valuations change slightly. For this, we introduce the lexislack rule, which selects envy-free allocation where the minimum "slack" (the amount by which agent prefers her allocation agent j's) is maximized lexicographically. This produces an allocation that remains envy-free for all valuation profiles that are within a maximally large -radiis of the reported profile. In the example of Table 1, the lexislack rule assigns the rooms in the same way does Spliddit, but charges the roommates $200, $450, and $350. With these prices, each agent prefers their allocation to any other agent's by at least 150 (see Figure 1). This means that even after Bob's adjustment to 600, he does not envy Alice. We show that the lexislack rule always selects an essentially unique outcome, which can be found polynomial time by linear programming.
This notion of robustness may not always be appropriate. Consider two perturbations with equal (i-distance to the reported valuations: one changes agent i's valuations for all rooms by small amount, the other changes i's valuation for one room by a large amount. Lexislack places equal importance on them. But the former perturbation seems more likely: even if player uncertain about the value of a room, that value is more likely be close to their best estimate than further

---

away. Thus, arguably, different valuation profiles should be weighted differently: we do not want to sacrifice envy-freeness for a likely perturbation in order to obtain it for an unlikely perturbation.
To capture this idea, we propose to add noise -use--such as Gaussian noise - around the reported valuations. This way, we impute probability distribution 'D over valuations. In this setting, our interpretation of robustness is to look for allocations that are envy-free with maximum probability. However, it is not clear how one could efficiently find the most robust allocation given the noisy valuations. As part of our methodological contribution, we propose an approach based on synthetic sampling. Specifically, we sample number of valuation profiles from D, and then find an allocation that is optimal on this sample using integer linear programming (ILP). By calculating the VC dimension of the space of rent divisions, we give polynomial sample complexity bounds that show how many samples are sufficient so that this approach identifies an almost optimal allocation with high probability. Note that the samples are synthetic, but low sample complexity is crucial nevertheless: a small number of samples leads to a sufficiently small ILP that, as we show, can be optimally solved in practice (even though we prove that the problem is NP-complete).
We also show that one can use the sampling approach to find an allocation that minimizes the expected amount by which one agent envies another. In contrast maximizing the probability of envy-freeness, the minimum envy objective places more emphasis on avoiding bad violations of envy-freeness.
An advantage of our sampling-basee approach is that it is very general and does not place any restrictions on the distribution D. Our algorithms could also be used for rent division problems with uncertainty, where agents might explicitly report distributions over their valuations. For example, Spliddit-like user interface could let agents report their valuations as a range rather than a number.
We end with some experiments on data taken from Spliddit. They suggest that our three new rules significantly outperform the Spliddit maximin rule on robustness metrics. Interestingly, the lexislack solution does comparably well to the rules based on sampling. Given its conceptual simplicity and easy computation, this suggests lexislack as a good rule when robustness is desired."
Related Work
The rent division model is well-studied in the economics literature [Svensson, 1983, Alkan et al., 1991, Aragones, 1995, Su, 1999, Velez, 2018], often without assuming quasilinear utilities. That literature includes results on the structure of the envy-free set and about strategic aspects. Computer scientists have studied the computation of allocation rules [Gal et al., 2017, Procaccia et al., 2018]. Bei et al. [2021] study generalization of the rent division problem.
Robustness has been studied in several areas of computational social choice, such in voting [Shiryaev et al., 2013], in committee elections [Bredereck et al., 2021, Gawron and Faliszewski, 2019, Misra and Sonar, 2019], and in stable matching [Chen et al., 2019, Mai and Vazirani, 2018]. We are not aware of such work for fair division, though Menon and Larson [2020] study related problem of "stability" which requires that the allocation should not change much if valuations change slightly. For rent division, blog post by Critch [2015] argues in favor of aiming for robustness in the rent division problem. Critch [2015] implemented an algorithm for robust rent division that appears in experiments to maximize the slack, but it differs from the lexislack rule, and no theoretical analysis of this algorithm is available.
Our sampling-basse approach is conceptually related to work on data-driven algorithm design [Balcan, 2020J, which typically seeks to optimize the hyperparameters of an algorithm with respect to an underlying distribution over instances, based on samples. One thing that distinguishes our distributional setting that we are using the samples to optimize a single solution to our problem. Computational hardness results for problems similar to our sample-basee optimization problems have been obtained for stable matching and for Pareto-optimal assignment [Aziz et al., 2019, 2020].
2 Preliminaries: Rent Division
Let n E N and write [n] = (1....,n) n). Let N = n rooms. Without loss of generality, we let the total rent be 1. A (valuation) profile v = (Vrr)EeN.EER is a collection of values Vür E Q+, one for each agent i E N and each room E R.
[n]] be set of n agents, and let R = [n] be set of
A simple online tool to compare the lexislack and maximin rules is available at https://pref.ooolsreett
3

---

A room assignment is bijection o :N + R, so that agent is assigned room oii.. Given valuation profile v, we say that is optimal maximizes utilitarian social welfare Σien Vin(f)- An allocation (o. p) is room assignment a together with a payment vector p (PI,..., pn) IR" with ERER Pr = 1, where is the rent of room r. (The value p, is usually non-negative.)
We assume that agents have quasilinear utilities. This means that if a valuation profile and (a, p) is an allocation, then agent i's utility in this allocation is (io(1) - Pa(e), i.e., the valuation of for her room (i) minus the room's 's rent. An allocation (a, p) is envy-free if Via(i) Po((i) 3 U/r Pr for all i N and E R, so that each agent weakly prefers her allocation to receiving any other room.
solution a function that given a valuation profile, selects a set of allocations (usually a singleton, but ties may occur). A solution is essentially single-valued if when it selects more than allocation, then all agents are indifferent between them: every agent gets the same utility from all tied allocations.
The following facts are well-known [see, e.g., Velez, 2018], 8J. We include proofs in Appendix D.1.
Theorem 2.1. (a) For every optimal room assignment o, there are prices so that (o. is envy-free. (b) (a.p) is envy-free then optimal.
(c) Let 0i, 02 be optimal room assignments, and let (Ø), p) be an envy-free allocation. Then (a2, P) also an envy-free allocation, with all agents indifferent between the two: Vso1(() Pf)(f) (t))(1) Poz(i) for all E N.
Theorem 2.)(a) implics that an envy-free allocation exists for all valuation profiles. We can compute one in polynomial time: find an optimal room assignment using bipartite matching, then use linear programming to find prices p that make the allocation envy-free [Gal et al., 2017]. Theorem (c) implies that when selecting among envy-free allocations, we can restrict attention to any fixed and only vary the price vector p. By Theorem 2. (c), all utility vectors achievable in an envy-free allocation are achieved by allocations of this form.
3 The Lexislack Solution
We start by considering a common form of robustness: we look for allocations that remain fair for all valuations that are within some radius input valuations, for large radius as possible. Thus, unlike in later sections, we do not assume that valuations come from a probability distribution.
Let be valuation profile, fixed throughout. Let (a, p) be allocation. For i N and R, let
(o, (Vio()) Po(t) (vir Pr).
Then define the slack of this allocation as
slack(o, p) = minge min, Air (a,
Thus, an allocation has positive slack if every agent strictly prefers their allocation all other agents' allocations. An allocation (a,p) is envy-free if and only if slack(a. p) > 0.
Slack is measure of how robustly fair an allocation is, which formalize in the following result.
Proposition 3.1. Let (a, p) be an envy-free allocation with slack(o, p) > 0. If of is valuation profile that s-close to in the sense that
||u
oill2 EPER Mer 1/rll <
for all i E N, then (a, p) is also envy-free under v'.
Proof. Let i,j E N. Then Eren n loar 11/rl $ implies
(Vio()) - rlo())) + (wlous - Vio(i) <
(1)
Adding Pa(t) (z) to both sides and rearranging, we get
(V/r(1) (o()) (V(rG) Pot)) (Vir(1) Pa(i)) (Vir() PaGi) 0
where the last inequality by definition of slack. Thus, does not envy under v'. Since i and were arbitrary, it follows that (a.p) is envy-free under v'.
D

---

One can also prove variants of Proposition 3.1. For example, ||E; - 114y-ylle < s/2 also implies (1).
If we wish to ensure robustness in sense like in Proposition 3.1, this suggests the following rule:
maxislack(u) (v) = argima (a.p) slack(o,
This rule always selects an envy-free allocation: since envy-free allocations exist for every v, there exists an allocation with non-negative slack, and hence the maxislack solution also has non-negative slack. A maxislack solution can be found in polynomial time by computing an optimal assignment o and then solving the following LP:
max subject (Mar(() - Pa(t)) (Uior() - Pa()) > L Vi + and ErER Pr =
However, there are a few drawbacks to the maxislack rule. First, the rule is not essentially single- valued: there may be several maxislack allocations which induce different utilities. This is unlike Spliddit's 's maximin rule which is essentially single-valued [Alkan et al., 1991]. Second, there may be maxislack allocations that do not maximize robustness for all agents. To see this, suppose that two agents i and 12 agree on the valuation of every room. Then in any envy-free allocation, the utility they assign to the two bundles allocated to them is equal. Hence the maximum slack attainable is 0. and so every envy-free allocation is maxislack. However, there may be allocations for which the slack between other pairs of agents larger than O, and such allocations are more robustly fair.
In this spirit, to obtain robustness for a larger collection of agents (or of agent pairs), we can refine the maxislack solution using a leximin strategy. We call the resulting solution the levislack rule, The lexislack rule selects an allocation (a, p) that maximizes the smallest of the n² values (Air (ar, Ne) and subject to that maximizes the
of these values, and so on.
In contrast to maxislack, the lexislack rule is essentially single-valued. The proof is in Appendix D.2. Theorem 3.2. The lexislack rule is essentially single-valued.
In addition, this rule remains efficiently computable. Theorem 3.3. A lexislack allocation can be found in poly time by solving ( linear programs.
Proof sketch. This can be done using standard techniques [see Kurokawa et al., 2018, Section 5]. We give an overview of the algorithm. Start by computing an optimal a. We will decide on the best value of Air one-by-one. Let F + @ be the set of (i, r) pairs for which we have fixed their value. Use linear programming to find price vector such that (a, p) maximizes the smallest of the non-fixed values Air. subject to keeping the other A.r at their fixed value. Say the optimum is L. Now we need find a pair (i, r) & F such that necessarily A,, L in any lexislack allocation. This can again be done by linear programs that check whether it is possible that Air > L. One can show that at least one such pair (i,r) & I must exist; we then add F' and fix its value to L, and repeat.
4 Maximizing Probability of Envy-Freeness
In the previous section, we defined robustness using a measure of closeness based on the & fidiittacce. We now look at more flexible model where true valuations assumed to be noisy perturbations of the reported ones. A distribution D over valuations v, therefore, is obtained by asking agents for valuations, and then adding noise (e.g.. Gaussian or uniform) around those valuations. Our goal will be to find an allocation (a, p) that maximizes the probability of being envy-free with respect to D, ie.. one that maximizes
EFratep (a, p) = Pro-D[(a, p) is envy-free under o].
Our algorithmic approach for finding an allocation with high probability of cnvy-freeness is to obtain sample S of valuation profiles sampled from D, and to compute allocation that is envy-free on the most profiles in S, i.e., one that maximizes
EFrates(a, p) - (V S (a,p) is envy-free under r]|-
If the number m of samples is sufficiently high, we may hope that the best allocation on the sample S is also approximately the best the distribution D. In this section, we will give bound for the sample size m to be sufficient to ensure this property, and then we will discuss the computational problem of finding the best allocation for a given sample.
In future work, it may be interesting to study rules that explicitly maximize robustness defined with respect to distaacec rather than E
5

---

4.1 Sample Complexity
In this section, we will give an upper bound on the number of samples required guarantee that the allocation that maximizes EFrates also (almost) maximizes EFratep, with high probability.
Theorem 4.1. Let e, > 0. There is a value m E NN with
17 n² log n + log(1/8)
8
such that for every probability distribution 'D over valuation profiles, if is collection of at least m samples drawn i.i.d. from D, and (a",p" .p") is the allocation that maximizes EFrates, then with probability at least - 8,
EFratep (a", ,p''p"")) 3 max (a.p) EFratep(d,p)
We prove this theorem by adapting standard tools from learning theory. Let be any set, with an unknown ground truth labeling X {0. }. A hypothesis is function h X {0, 1}. Given sample 5 = (I1,.- Fm) of m elements
X (not necessarily distinct), write errs (h) 1
(x.))) # T(2;) H for the fraction of samples that h labeled incorrectly. For probability distribution DD over X, write err (h) = Pr (1(r) * ra=)] for the probability that incorrectly labels point
sampled from D.
hypothesis class H is set of hypotheses. Given a random sample drawn i.d. from D, and knowledge of the true labeling of those samples, our goal is find hypothesis h E H that approximately minimizes ( with high probability. Note that the ground truth т, interpreted hypothesis, need not be member of H. In learning theory, this setup corresponds to "agnostic PAC learning". where the "realizability assumption" " is not required to hold Shalev-Shwarte and Ben-David, 2014, Section 3.2].
We say that set S X shattered by H if for S C C, there exists E H with h(x) E S and h(x) = 0 if E C In other words, if we restrict the hypotheses in H to the set C, then all possible labelings of are part of H. The VC dimension VCdim (H) of H is the cardinality largest subset of X that is shattered by H. We are interested in VC dimension due to the following standard result, adapted from Shalev-Shwartz and Ben-Davis [2014, Theorem 6.8], which says that PAC learning possible hypothesis classes of finite VC dimension.
the
Theorem 4.2. Let e, 5 > 0. Let H be hypothesis class with VCdim(H) = d. Then there exists value m E N with
m = log(1/5) (/))
=0(1 m=0(
22
such that for every probability distribution 'D over X, S is a collection of at least samples drawn i..d. from D, and h² e the hypothesis that minimizes errs, then with probability at least
ehr)(h") < mingeu errp (h) +
For our application, we let X be the set of all valuation profiles The "correct" labeling is T(t)= 1 for all v. We identify allocations with hypotheses: For an allocation (ar, p). we define the hypothesis h(r,)) that for each
{1
if (a,p) is envy-free under (0 otherwise.
h Mapp) (v)
By these definitions, have that for all S and D.
EFrates p) err el( and
EFratep 1 (h(
We study the hypothesis class H. of all such hypotheses:
H (h(r,) allocations (a.p)).
To bound its VC dimension, the following result is useful:

---

Lemma 4.3 (Shalev-Shwand and Ben-Davin 2014, Exercise 6.11). Let Hi...., classes over X, with (H,) & for each 1,...,t. Then
,.....,,,,,... He be hypothesis
VCd .... U.. H4) < 4d + 2 log(())
We can now bound the VC dimension of H. Lemma 4.4. VCdim (P) = (n logn).
Proof. For each room assignment o, define the hypothesis class H. (h(,.p) p [R") correspond- ing to allocations whose room assignment is a. 'hen H = U~ Ha where the union ranges over all room assignments. We will show that VCdim(H,) & n² for each a. Since there are n! different room assignments and log n! (n log n), follows from Lemma 4.3 that VCdim(H) On log n), as
required.
Let be room assignment. Without loss of generality assume that o(t) i. Let d > n² + 1. Consider collection of d distinct valuation profiles v(()) 1.... u(d), We show that this collection cannot be shattered by Ho.
For i N, say y(k) uniquely restricting for (i,j) if
(9) for all l + k.
Thus, such profile uniquely maximizes the amount by which agent i prefers j's room to her own room, ignoring prices. Clearly, for any pair i E N, at most one profile can be uniquely restricting for it. Since there are n² many pairs (i.j) and d >> n²? there is at least one profile which is not uniquely restricting for any pair, say (1))
We now ask if there an allocation (a, p) that is envy-free under u v(d),
but not envy-free
under v(), We show that the answer is no, so H, fails to shatter this collection.
Assume for contradiction that (a,P) is such an allocation. Since it is not envy-free under (1)), there (1)
(I) - Pj Vs
a pair i,j j N with Uiy
Pt or equivalently
(1) (1)
0 U
> Pj Ps-
(2)
As (L)) is not uniquely restricting for (i,j), for some l + 1,
(1) (1) 1 a
(
(
(3)
Combining (2) and (3), follows that Vij U a contradiction.
(6)
> Pj Ps. Thus, (a.p) not envy-free under (())
Our main result in this section, Theorem 4.1, now follows immediately from Theorem 4.2.
4.2 Computational Complexity
To make use of Theorem 4.1, we need an algorithm that, given a collection S (v((1) ..... (m)) of valuation profiles sampled from D, finds an allocation that maximizes EFrates(o, p). This problem can be encoded as an integer linear program via standard encoding techniques, using binary variables Far encoding that agent i receives room r, continuous variables p. encoding the prices, and binary variable ye for each sample l E [m)) indicating whether the produced allocation will be envy-free under v(t) The full encoding appears in Appendix B.
Instead of an ILP approach,
hope for a polynomial time algorithm finding the best allocation? Let us formulate our optimization problem as decision problem as follows.
EF-RATE MAXIMIZATION
Input: Set N of agents, set R of rooms, list of m valuation profiles y ..... (m)) number B. Question: Does there exist an allocation that envy-free for least B of the m valuation profiles?
Unfortunately, this problem is computationally hard. We prove this by a reduction from CLIQUE, given in Appendix D.3.
7

---

Theorem 4.5, EF-RATE MAXIMIZATION is NP-compeete.
There are two sources of computational difficulty for solving EF-RATE MAXIMIZATION: we have to decide on one of the n! possible room assignments, and we have to decide on which subset of valuation profiles we are aiming to envy-free on. But in practice, there is a way to avoid the first source of hardness. Suppose the m valuation profiles are sampled from continuous distribution DD Then with probability 1, for each sampled profile y(() there is unique optimal room assignment (()), Any solution to the EF-rate maximization problem must use a room assignment that is optimal for least one of the given valuation profiles. Thus, most different room assignments candidates, and we can find an optimal solution using m calls to the following problem (one call for each candidate assignment a (())):
EA-RATE MAXIMIZATION WITH FIXED ASSIGNMENT
Input: A list of m valuation profiles v(1), ..... o(m), number B, room assignment a.
Question: there a price vector p such that (o, p) envy-free for least B of the m valuation profiles?
Unfortunately, this version of the problem is also hard, and this trick for continuous distributions does not help. We prove this by reduction from the feedback are set problem in Appendix D.4.
Theorem 4.6. EF- EF-RATE MAXIMIZATION WITH FIXED ASSIGNMENT NP-coeple
Nevertheless, as we show in Section 6, we can solve this problem in practice using integer linear programming (ILP). The reason this possible that the sample complexity is relatively low, leading to an ILP of practical size.
5 Minimizing Expected Envy
In Section 4, we defined robust envy-freeness as allocations that have a high probability of being envy-free when valuations come from given distribution D. In this section, we consider a different objective function that is more fine-grained. In measuring the probability of envy-freeness. we implicitly treat all failures of envy-freeness equally. We will now minimize expected envy, which treats cases where one agent envies another by a lot as more severe.
Given a valuation profile and an allocation (o,p), we define the allocation's 's (maximum) envy, envy, (a, to be
max 0, max [((a))) - Po()) (vio() - Po(i)] IJEN
This quantity, which is related to slack considered in Section 3, measures the biggest amount by which one agent prefers another's 's bundle. In principle one could allow negative values of envy, (a, p) for allocations that have positive slack, but chose to force these values be non-negative, since our focus is on avoiding envy. Note that an allocation is envy-free if and only if envy, p) = 0.
Our goal in this section is to find an allocation minimizing the expected envy with respect to D,
defined as
envyp(a,,) p) (e--peeny,,cr
Our approach will be similar to before: we obtain a sufficiently large sample S of m profiles from D and select the allocation that does best on the sample, i.e. it minimizes
envys(a, = 1 Eves envy,(ar,)).
5.1 Sample Complexity
For stating our sample complexity bound, assume that valuations normalized: let v; > 0 for all i E N and E R, and Ever Uir = for all E N. We are going to prove the following result:
Theorem 5.1. Let O, and let D be distribution. we draw m = O log à samples i. from and if (a*.p") minimizes envys then with probability at least 1 we have
envyplo" .p") min envyp +
8

---

Thus, if we draw sufficiently many samples, then with high probability the allocation minimizing expected envy on the sample will, up to E, be minimizing with respect D.
We prove this result by discretizing the space of allocations. We then use a concentration inequality show that w.h.p. the expected envy with respect to D is close to the expected envy with respect to the sample S. The proof of Theorem 5.1 appears in Appendix D.5.
Note that for this result we employed a direct approach. This technique and its discretization step would not have worked for the envy-free rate, because two very close rent divisions can in principle have very different EF rates. On the other hand, we expect that similar bounds for the minimum envy objective could be obtained by using extensions of VC dimension to real-valued functions (e.g..
5.2 Computational Complexity
Again, our sample complexity result needs an algorithm that finds the best allocation for given sample S. Like for EFrate, we can solve this problem using integer linear programming (see
Appendix B). For the formal complexity analysis, consider the following decision problem:
EXPECTED ENVY MINIMIZATION
Input: List S = (u((),,.. (()),, number B. Question: Is there (a,p) with en,ys(a,p) < BB?
This problem is again NP-complete. The proof is in Appendix D.6, by reduction from CLIQUE. Theorem 5.2. EXPECTED ENVY MINIMIZATION is NP-complete, even for binary valuation profiles.
Interestingly, this problem becomes easy once we fix room assignment a, because the best price vector can then be computed by linear programming (because the values of the integer variables in the ILP shown in Appendix B are decided by the fixed room assignment σ). Thus, the problem can be solved in time r!! poly(n,m) and hence is fixed-parameter tractable with respect to the number of agents n. This is good news: instances will often have a small number of agents, but we will will see
want to consider as large sample as feasible to ensure low maximum envy. In fact, momentarily, the NP-completeness of the problem is not an obstacle in real-world instances.
6 Experiments
We evaluated our rules on user data taken from Spliddit. 3 We studied distributions obtained by adding noise valuations. We started by selecting 1,000 instances random, speed up computations. The same selection is used for each experiment. For each instance, we normalize the rent to 1, and normalize valuations to sum to 1. We considered three noise models, each parameterized by choice of noise level e E {0, (0.0.01..... 0.09}.
1r Ur +1+ Uniform/=e, +=])
(Uniform)
"
(f) Uhr (1+N
(Normal)
Up
(6) Uir +1+r- e))
(Biased Normal)
In each of these noise models, valuations are increased decreased by random fraction. Here, N [u, o] is a normal distribution with mean z and standard deviation a. For the biased normal noise model, we put rooms in an arbitrary fixed order and label them with integers 0, 1,..., n 1. Rooms with a higher index have more noise.
For each noise model and choice of e, we produced sample S of size m = 100. We then computed allocations maximizing EFratey and minimizing envy We also computed the maximin and lexislack rules based on the input profile For each of the four allocations, we calculated their value of EFrates. and of en We then average over 1, 1,000 instances. The results are shown Figure for the Uniform noise model. Results for the other noise models and more details are given in Appendix As expected, on each of the two metrics, the rule optimizing it does best, but all three
This dataset kindly provided to us in anonymized form by the maintainer of Spliddit, Nisarg Shah.

---

Probability of Envy-Freeness (EFrates)
Expected Envy (envy
1.8
11.03
0.:01
knskeck
0.-
isacpoo rrbors
0.000
0.005
6.4
0.004
01002
Nota puratasee
Nossa pirzneur?
Figure Results experiments for the Uniform noise model.
rules aiming for robustness do similarly well. Spliddit's maximin rule does significantly worse on our metrics. Before the experiments, we expected that lexislack would do worse for the biased noise model, but this does not appear be the case.
In the appendix, we also evaluate the sampling-based rules on a freshly drawn sample different from the sample used to optimize the rules (Appendix A.2) as well on sample drawn from different probability distribution (Appendix A.3), to evaluate how sensitive these methods are to being optimized on a small sample and knowing the 'right' noise distribution. In both cases, find that the performance of the sampling-base baased methods worsens, while lexislack is still robust.
shows average computation time to compute allocations optimiz- ing EFrates and envys, using Gurobi 9.1.2 on four threads of an AMD Ryzen 2990WX (128 GB RAM) with the ILP formulations from Appendix B. The re- sults were obtained for random lection of 300 Spliddit instances with with the Uniform noise model for = 0.05, and sample sizes m vary- ing from to 125. Minimizing envy much faster due fewer integral variables. In Appendix A.4, we report some additional computation times as function of the noise parameter s.
Figure 3
7.0
6.%%
5.06
Max. Prob. EF
4.0
30ss
Min. Exp. Envy
75
100
125
Figure 3: Computation time depending on sample size
7 Future Directions
Our approach should be applicable to many settings beyond rent division, such as homogeneous divisible goods, cake cutting, or even indivisible goods. For example, the lexislack rule can be adapted these settings, and similar results as in our distribution-bl based approach might be achievable.
We have shown that the lexislack rule shares some key properties with the maximin rule, such as es- sential pongle-valuednes, and polynomial-time computability. It would be interesting axiomatically contrast the two solutions, for example with respect to strategic properties like manipulability.
For our distribution-basee approach, we assumed that we have access to D only via sampling. Often we may know D more explicilly, for example we are just adding noise to reported valuations. For such well-behaved D, can we design direct algorithms for finding optimal allocations with respect to our two objectives, without needing samples?
Acknowledgments and Disclosure of Funding
This work was partially supported by the National Science Foundation under grants IIS-2147187, CCF-2007080, IIS-2024287, and CCF-1733556; and by the Office of Naval Research under grant 200014-20-1-2488
10

---

References
A. Alkan, G. Demange, and D. Gale. Fair allocation of indivisible goods and criteria of justice. Econometrica, 5924):023-11039 1991.
E. Aragones. derivation of the money Rawlsian solution. Social Choice and Welfare, 12:267-276, 1995.
H. Aziz, P. Biró, R. de Haan, and B. Rastegari. Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity. Artificial Intelligence, 276:57-78, 2019.
H. Aziz, P. Biró, S. Gaspers. R. de Haan, N. Mattei, and B. Rastegari. Stable matching with uncertain linear preferences. Algorithmica, 82(5):1410-1453 2020.
M.-F. Balcan. Data-driven algorithm design. In T. Roughgarden, editor, Beyond the Worst-Cast Analysis of Algorithms, chapter 29. Cambridge University Press, 2020.
X. Bei, Z. Li, J. Liu, S. Liu, and X. Lu. Fair division of mixed divisible and indivisible goods. Artificial Intelligence, 293:103436 2021.
R. Bredereck, P. Faliszewski, A. Kaczmarczyk, Niedermeier, Skowron, and N. Talmon. Robust- ness among multiwinner voting rules. Artificial Intelligence, 290:Article 103403, 2021.
E. Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 11966):061--1103 2011.
I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang. The unreasonable fairness maximum Nash welfare. ACM Transactions on Economics and Computation (TEAC), 7 (3):1-32, 2019.
Chen, Skowron, and Sorge. Matchings under preferences: Strength of stability and trade-offs. In Proceedings of the 20/9 ACM Conference on Economics and Computation (EC), pages 41-59, 2019.
A. Critch. Robust rental harmony. http::/pprma.ccQQMMMDHHHAYY
https://erritch.com/eee 2015.
Archived at
B. Flanigan, P. Gölz, A. Gupta, B. Hennig, and A. D. Procaccia. Fair algorithms for selecting citizens' assemblies. Nature, 996:548-552, 2021.
Y. Gal, M. Mash, A. Procaccia, and Y. Zick. Which the fairest (rent division) of them all? Journal of the ACM, Articce 39, 2017.
G. Gawron and P. Faliszewski. Robustness of approval-based multiwinner voting rules. In Proceedings of the 6th International Conference on Algorithmic Decision Theory (ADT), pages 17-31, 2019.
J. Goldman and A. D. Procaccia. Spliddit: Unleashing fair division algorithms. SIGecom Exchanges, 13(2):41-46, 2014.
D. Kurokawa, A. D. Procaccia, and N. Shah. Leximin allocations in the real world. ACM Transactions on Economics and Computation, Articee 11, 2018
Mai and V. V. Vazirani, Finding stable matchings that are robust to errors in the input. In Proceedings of the 26th Annual European Symposium Algorithms (ESA), page Article No. 60, 2018.
V. Menon and K. Larson. Algorithmic stability in fair allocation of indivisible goods among two agents. arXiv:2007.152000 2020.
N. Mísra and C. Sonar. Robustness radius for Chamberlin-Couran on restricted domains. In Proceedings of the 45th International Conference Current Trends in Theory and Practice of Informatics (SOFSEM), pages 341-353, 2019.
H. Moulin. Fair division in the internet age. Annual Review of Economics. 11:407-441,
11

---

A. D. Procaccia, R. A. Velez, and D. Yu. Fair rent division on budget. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), pages 1177-1184, 2018.
S. Shalev-Shwartz and S. Ben-David. Understanding Machine Leurning: From Theory to Algorithms. Cambridge University Press, 2014.
D. Shiryaev, L. Yu, and E. Elkind. On elections with robust winners. In Proceedings of the 12th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 415- 422, 2013.
E. Su. Rental harmony: Sperner's lemma in fair division. American Mathematical Monthly, 106 (10):930-942, 1999.
L.-G. Svensson. Large indivisibles: An analysis with respect to price equilibrium and fairness. Econometrica, 51(4):939-954 1983.
R. A. Velez. Equitable rent division. ACM Transactions on Economics and Computation (TEAC), 6 (2):Article 9, 2018.
L. A. Wolsey, Integer Programming. John Wiley & Sons, 1998.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We mention open problem in the
section on future directions, well throughout the paper.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Due to space con- straints, many proofs appear in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material as URL)? [Yes] In the supplemental material, but not including the data.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running exper- iments multiple times)? [Yes] We report standard errors, with respect to the 1,000 instances.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Figure 3 and the hardware details at the end of Section 6.
4. If you using existing assets (e.g., code, data, models) curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We use proprictary dataset from Spliddit.org, whose creators we cite [Goldman and Procaccia, 2014].
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're
using/curating? [No]
12

---

(c) Did you discuss whether the data you are using/curating contains personally identi- fiable information or offensive content? [No] The data we received was completely anonymous.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "se_1oUXSXEE", "reviewer": "Reviewer_NxEV", "summary": "The paper studies the problem of robust envy-free rent division.  In the conventional problem variant, given n individuals and their evaluations for n rooms, the goal is to find a rule to allocate the rooms and fairly split the rent such that everyone is satisfied with the room and the split payment (i.e., allocation is envy-free).  Prior literature assumes that the individuals' valuations are accurate. This paper proposes robust allocation rules such that the allocation remains envy-free (or maximizes the probability of being envy-free, or minimizes expected envy) even if the reported evaluations deviate from the true ones.", "questions": "My main question is whether the authors gave any thought to the implications of their approaches to robust fair rent devision on incentives to misreport values (i.e., are these stronger in this context, and how do the different models of \"robustness\" impact incentives).", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n1. The paper is very well-written, and the organization of the results make it easy to follow. The paper studies several notions of robustness against different uncertainty around the true evaluations.  The l1 notion seems quite natural, and yields a polynomial-time algorithm.  It seems that l_inf robustness would do similarly, although the paper doesn't state that explicitly (just that Prop 3.1 essentially goes through for l_inf robustness).  Distributional variations are interesting as well; although they yield NP-hard optimization problems (but poly sample complexity), the associated ILPs seem fast enough in practice.\n\n2. There is a particularly interesting sample complexity result for the distributional variant of this problem in which the authors derive VC dimension of the allocation \"hypothesis space\" (which is polynomial).  This nicely combines with relatively standard arguments to get polynomial sample complexity.\n\nWeakness: \n1. I found the l_1 and l_inf models of robustness considerably more convincing than the distributional models, for a few reasons.  First, l_inf seems to address the main limitation of l_1 that the authors highlight in the introduction.  Second, l_p models capture a nice intuition related to incentive compatibility: that while people may misreport valuations, they will typically stick relatively close to true valuations (although admittedly here the Gaussian model also makes good sense).  This is not to say that the distributional models are bad; it's simply that they seem somewhat forced here, in the sense that added value seems low, and increased complexity therefore too weakly motivated.\n\n2. There isn't any discussion of incentive compatibility.  This is natural here, since it conflicts with envy-freeness (if I recall correctly), but it would still be useful to understand how the notions of robustness impact manipulability, at least one compared to the other.\n\n3. It would also be useful to include computational results for Lexislack, perhaps as a part of Fig 2 (if it makes sense visually), or separately.", "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": "Yosb-wTsT9Z", "reviewer": "Reviewer_4a6w", "summary": "This paper provides new algorithmic and complexity results for the problem of computing envy-free solutions to the fair division problem. Here, n agents must each be matched to one of n rooms given their valuations for the rooms and split the total rent for the n rooms among them, and the agents have quasilinear utilities, i.e., their utility for receiving a room is its value minus their payment which is their share of the rent. Previous work proves that an envy-free solution to the rent division problem with quasilinear utilities always exists and can be computed in polynomial time using a linear program to compute the prices that result in envy-freeness. However, existing approaches to compute such envy-free allocations are not robust to perturbations to agent's utilities (such as the Spliddit algorithm which is focused on maximizing the utility of the agent with lowest utility).\n\nThe main conceptual contribution of this paper is a new objective: maximizing robustness to perturbations in agent utilities under the envy-freeness constraint. Two such objectives are considered under a Gaussian noise model, i.e., when agent's true valuations are assumed to be \"drawn\" from a distribution obtained by adding Gaussian noise to their reported valuations:\n- Maximizing the probability that the allocation is envy-free w.r.t. this distribution\n- Minimizing the expected envy, i.e., the sum total of envy experienced between every possible pair of agents, w.r.t. the distribution\n\nGiven a set of samples from this distribution, there are polynomial time algorithms that compute the optimal solution w.r.t. either of these objectives and the set of samples. \n\nThe main technical contributions are:\n- Sample complexity results for the number of samples needed to provide a guarantee that the solution computed by a polynomial time algorithm is at least within some tolerance parameter of the optimal solution with high probability for either of the above objectives.\n- Computational hardness results for computing the optimal solutions w.r.t. the distribution of valuation profiles", "questions": "None", "limitations": "I believe the authors have adequately addressed the limitations of this work and proposed meaningful avenues for future work.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- [Relevance] The paper uses several tools from learning theory to arrive at significant technical results.\n- [Novelty] The proposed objectives of maximizing robustness are novel to the best of my knowledge.\n- [Significance] The paper makes several important and interesting conceptual and technical contributions which I believe will be of interest to the large computation social choice community. The future directions pointed out are well chosen and I agree that they are interesting questions for future work (e.g. how to elicit uncertain valuations from users on platforms like Spliddit and their implications on computing robust solutions)\n- [Writing] The paper is well written and organized and I agree with the authors' choice of which proofs are included in the main paper or left to the appendix. The discussions of the motivation and related work are sufficient given the space constraints.\n- [Soundness] I was able to verify the main results and they seem sound. However, I was unable to check all of the results (e.g. the computational hardness results) thoroughly due to a lack of time.\n\nWeaknesses:\n- No significant weaknesses that must be addressed in a conference publication.\n- It would have been interesting to see at least experimental results with more noise models. However, this is a minor nitpick given the space constraints.", "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": "XQPYoUJHRkh", "reviewer": "Reviewer_Vr2D", "summary": "This paper focuses on the problem of fair rent division: how does one split a total cost among agents in a way that respects the individual agents' valuations and returns an allocation and a cost split that is envy free? This paper focuses on the case where there is uncertainty in the valuations reported by the agents. The paper therefore introduces what they call the lexi-slack solution which remains envy free with as large a radius as possible from the agent valuation reports. They also look at the case where we get samples from a valuation distribution and we want to maximize the probability of selecting an EF allocation with a small number of samples. ", "questions": "* A major major issue I have with the paper as it currently exists is around the use of data. No discussion of IRB process, informed consent etc. is given for the data from Spliddit. To my knowledge this data is not open source and it is not clear that the use of this data was cleared with users from the website. I hope the authors addressed this in a responsible way, otherwise I do not feel the results can or should be published, ethically. I have flagged this paper for this reason and hope the authors have these issues handled and just didn't include details in this writeup.\n\n* See question above about practical applications of the sampling results.\n\n* See question about other heuristics for refining the solution space of maximin that could be used/evaluated in a more fair manner than the \"better\" claim made in the paper.", "limitations": "One question / limitation that isn't discussed but might be interesting for future work is any notion of the mechanism being adversarial. The writing currently points to the fact that maximin can cause envy for small changes in valuations but what if the center is choosing these in a way to benefit one agent or another. This isn't a hard limitation but the discussion is a bit taught in part 7 so a bit more would be nice.\n\nBuilding on this, there is a discussion of the limitations of the L_1 distance metric, were other metrics used? Why L_1 and not others given that even the authors say that L_1 can over optimize for one agent... a bit more discussion would be nice.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "++ The paper is extremely well written, it is easy to follow, and all problems and notation are clear. The discursive style is very nice and overall it was a very fun and interesting paper to read.\n\n++ The proofs and results seem correct to me and are written very clearly. While I did not check the proofs in detail I was able to follow most of the arguments and they seemed reasonable.\n\n++ I really enjoyed the sample / learning portion of the paper and found that interesting. One question/limitation I would have liked to see discussed is how this sampling would happen in the real world? Would one agent report their valuations multiple times??? I don't see how this would be practically applicable.\n\n-- I find the claim: \"We end with some experiments on data taken from Spliddit. They suggest that our three new rules\n83 significantly outperform the Spliddit maximin rule on robustness metrics.\" a little disingenuous. Of course the method that returns an EF allocation that has as a secondary constraint these other robustness metrics is better, this is not surprising. What would greatly strengthen the claim is comparing to some other heuristically optimized robustness metric. While this is really not that necessary since lexislack is basically this (since it doesn't minimize expected envy which is NP-hard) but this claim could be written in a more even handed way and/or evaluated against other poly-time heuristics that get stacked on the maximin rule.\n\n-- None of the experiments contain error bars or confidence intervals for especially Figure 1. So it's basically impossible to tell what the difference are and whether or not they are significantly different. The empirical claims would be much improved with some error bars or empirical confidence intervals.", "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": ["Privacy and Security (e.g., consent)"]}, "extra_text": {}}, {"review_id": "Bab6cRLEeeM", "reviewer": "Reviewer_5Apq", "summary": "This paper proposes three robust approaches for the envy-free rent division problem: the lexislack approach that looks for allocations that remain envy-free for a range of valuations around the input one, an approach that maximizes the probability of envy-freeness, and one that takes the magnitude of envy into consideration by minimizing it. The authors provide time complexities for obtaining solutions for all these approaches, as well as the probabilistic bounds that guarantee the quality of the solutions of the latter two approaches. The robustness and the computation times of the proposed approaches are demonstrated on user data collected from Spliddit.", "questions": "\nBelow are some detailed suggestions and questions for the paper.\n\n$\\bullet$ Line $116$, Page $3$ (Section $2$): what does \"weakly prefers\" mean?\n\n$\\bullet$ Lines $129$ to $130$, Page $3$ (Section $2$): \"we can restrict... of the form $(\\sigma,p)$\" is a little bit confusing to me: isn't an allocation always of the form $(\\sigma,p)$?\n\n$\\bullet$ Formula $(1)$, Page $4$ (Section $3$): it seems to me that it should be $(v_{i\\sigma(i)}-v'_{i\\sigma(i)})+(v'_{i\\sigma(j)}-v_{i\\sigma(j)})\\leq s$.\n\n$\\bullet$ Line $146$, Page $4$ (Section $3$): at the end of the proof, it is better to recall that the conclusion holds since $i,j\\in N$ are arbitrary. \n\n$\\bullet$ Theorem $4.1$, Page $5$ (Section $4$): I would suggest providing a brief description of the spirit of Theorem $4.1$ in the main text.\n\n$\\bullet$ Lines $199$ to $200$, Page $5$ (Section $4$): I would suggest providing references for the sentence \"In learning theory...need not hold.\"\n\n$\\bullet$ Line $200$, Page $5$ (Section $4$): I guess the \"realizability assumption\" corresponds to the setting \"the ground truth $\\tau$ need not be a member of $\\mathcal{H}$\". Please elaborate these two more clearly.\n\n$\\bullet$ Line $207$, Page $5$ (Section $4$): \"...with ${\\rm VCdim}(\\mathcal{H})=d$\" should be \"...with ${\\rm VCdim}(\\mathcal{H})=d$ over $X$\"?\n\n$\\bullet$ Line $258$, Page $7$ (Section $4$): could the authors explain why \"Then with probability $1$...assignment $\\sigma^{(\\ell)}$\" is a direct result of the continuous distribution assumption?\n\n$\\bullet$ Line~$261$, Page $7$ (Section $4$): the correspondence between the i$th$ call ($i\\in[m]$) and the $\\sigma$ (that is optimal for $v^{(i)}$) should be stated clearly.\n\n$\\bullet$ Lines $296$ to $298$, Page $8$ (Section $5$): it might be better to move \"On the other hand...pseudo-dimension).\" to the last section.\n\n$\\bullet$ Line $307$, Page $8$ (Section $5$): could the authors provide more detail about this linear program? \n\n$\\bullet$ Line $307$, Page $8$ (Section $5$): I think \"this means that\" is incorrect here: \"computed by linear programming\" does not \"means\" that the problem can be solved with certain time complexity.\n\n$\\bullet$ Lines $317$ to $318$, Page $8$ (Section $6$): what do the superscripts $(\\ell)$'s mean?\n\n$\\bullet$ Lines $324$ to $326$, Page $9$ (Sectio $6$): the authors should point out clearly that \"For each of... over all $1000$ instances\" is the testing phase.\n\n$\\bullet$ Lines~$329$ to $330$, Page~$9$ (Section~$6$): the sentence \"Before the...to be the case.\" is unnecessary.\n\n$\\bullet$ Figure~$2$, Page~$9$ (Section~$6$): I suggest the authors report the computation time with more values of $n$.", "limitations": "Line $108$, Page $3$ (Section $2$): \"...each agent $i\\in N$ and each room $r\\in R$\" should be \"..each $(i,r)\\in N\\times R$\"?\n\nLines $137$ to $138$, Page $4$ (Section $3$): in the formulation of \"${\\rm slack}$\", \"$\\Delta_{ir}$\" should be \"$\\Delta_{ir}(\\sigma, p)$\"?\n\nLine $164$, Page $4$ (Section $3$): \"$n^2$ values in $\\Delta(\\sigma,p)$\" should be \"$\\{\\Delta(\\sigma,p)\\}_{(\\sigma,p)\\in N^2}$\".\n\nLine~$231$, Page $6$ (Section $4$): \"pair $i,j\\in N$\" better to say \"pair $(i,j)\\in N \\times N$\"?\n\nThere are several other typos or grammatical errors. I would suggest proofreading the paper carefully.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe models proposed in this paper are very practical. My favourite part is the establishment of Theorem $4.1$, wherein the authors intelligently parallel a standard result in PAC learning to their framework and derive the probabilistic bound for their solution. \n\nWeaknesses:\nSome places can be better elaborated and several typos should be corrected.", "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