Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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).

The 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:
- Maximizing the probability that the allocation is envy-free w.r.t. this distribution
- Minimizing the expected envy, i.e., the sum total of envy experienced between every possible pair of agents, w.r.t. the distribution

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

The main technical contributions are:
- 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.
- Computational hardness results for computing the optimal solutions w.r.t. the distribution of valuation profiles
strengths_and_weaknesses: Strengths:
- [Relevance] The paper uses several tools from learning theory to arrive at significant technical results.
- [Novelty] The proposed objectives of maximizing robustness are novel to the best of my knowledge.
- [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)
- [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.
- [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.

Weaknesses:
- No significant weaknesses that must be addressed in a conference publication.
- 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.
questions: None
limitations: I believe the authors have adequately addressed the limitations of this work and proposed meaningful avenues for future work.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
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.

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

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

-- I find the claim: "We end with some experiments on data taken from Spliddit. They suggest that our three new rules
83 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.

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

* See question above about practical applications of the sampling results.

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

Building 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths: 

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

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

Weakness: 
1. 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.

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

3. 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.
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
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
The 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. 

Weaknesses:
Some places can be better elaborated and several typos should be corrected.
questions: 
Below are some detailed suggestions and questions for the paper.

$\bullet$ Line $116$, Page $3$ (Section $2$): what does "weakly prefers" mean?

$\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)$?

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

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

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

$\bullet$ Lines $199$ to $200$, Page $5$ (Section $4$): I would suggest providing references for the sentence "In learning theory...need not hold."

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

$\bullet$ Line $207$, Page $5$ (Section $4$): "...with ${\rm VCdim}(\mathcal{H})=d$" should be "...with ${\rm VCdim}(\mathcal{H})=d$ over $X$"?

$\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?

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

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

$\bullet$ Line $307$, Page $8$ (Section $5$): could the authors provide more detail about this linear program? 

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

$\bullet$ Lines $317$ to $318$, Page $8$ (Section $6$): what do the superscripts $(\ell)$'s mean?

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

$\bullet$ Lines~$329$ to $330$, Page~$9$ (Section~$6$): the sentence "Before the...to be the case." is unnecessary.

$\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$"?

Lines $137$ to $138$, Page $4$ (Section $3$): in the formulation of "${\rm slack}$", "$\Delta_{ir}$" should be "$\Delta_{ir}(\sigma, p)$"?

Line $164$, Page $4$ (Section $3$): "$n^2$ values in $\Delta(\sigma,p)$" should be "$\{\Delta(\sigma,p)\}_{(\sigma,p)\in N^2}$".

Line~$231$, Page $6$ (Section $4$): "pair $i,j\in N$" better to say "pair $(i,j)\in N \times N$"?

There are several other typos or grammatical errors. I would suggest proofreading the paper carefully.
review_title: null

Meta-review: metareview: Reviewers are all positive and excited about the paper: interesting and natural model, novel and robust mechanism with theoretical guarantees, nice sample complexity analysis, experiments on real-world data.
confidence: Certain
Decision: Accept