Venue: NeurIPS 2022 Conference

Reviews:

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: This paper considers several approximate fairness allocation problems among n players (envy-free, perfect, and equitable), and considers query complexity in the Robertson-Webb model (RW). The authors show lower bounds and upper bounds for approximate envy-free allocation (no player prefers another player's piece to her own) for any number of players. For approximate perfect and equitable allocations, improvements were made to the case n=2 players. To achieve their upper bounds, the authors formalize "moving-knife protocols" (MKPs) within the RW model.
strengths_and_weaknesses: S1. Novel theoretical upper and lower bounds obtained for approximate allocation.

S2. For epsilon-envy-free allocation, algorithms are efficient, i.e. O( log 1/epsilon ) for 3 players, O( n / epsilon ) for n players. Also, the upper bound in 3-player case matches the lower bound proven.

S3. It was unknown if MKPs could be formalized within the RW model. The fact that they can is quite interesting, in my opinion. This unifies two seemingly disjoint techniques.

W1. With the exception of approximate envy-free allocation, the method of authors did not improve existing upper or lower bounds for n >= 3 players, only for n = 2.

W2. Lower bound for approximate envy-free allocation is not tight for n >= 4 players.
questions: 
No questions.
limitations: 
Yes.
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 various problems in the fair cake cutting area, and advances theoretical state of the art by providing improved lower and upper bounds.

In particular, three notions of fairness are considered: envy-freeness, proportionality, and equitability (plus the combinations of the three, called "perfect"). Because of strong impossibility results, the authors focus on the approximate variants of these fairness concepts.

They establish a lower bound of $O(\log 1/\epsilon)$ for the query complexity of three problems: connected $\epsilon$-envy-free (for three players), connected $\epsilon$-equitable and $\epsilon$-perfect allocation with two cuts (for two players). They also present almost tight upper bounds for the 1st & 3rd problems (the other ones already had an upper bound matching the new lower bound).

While essentially nothing was known for $\epsilon$-envy-free, the other two notions already had _similar_ upper bounds for 3 (as opposed to 2) players, with upper bounds that still are pretty loose.

They show how a large class of cake-cutting methods can be simulated using Robertson-Webb query model (where an outsider asks players about their preferences until a solution can be proposed).
strengths_and_weaknesses: Strengths:
- Advances state of the art and closes the gap for certain settings.

Weaknesses:
- The results and methods seem incremental.
- Relevance to the community is unclear.
- No real application discussed, hence no experiments.
questions: none
limitations: n/a
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper does a nice job expositing and motivating the question of query complexity of \eps-EF cake cutting. Unfortunately, it seems quite outdated, missing important references from the past ~5 years. (I usually wouldn't be too worried about missing references, but the technical contributions in the paper are not so impressive so I view the main contribution as motivating the questions, but then the context is more important.)

I’m also not sure that this is a good fit for NeurIPS, even interpreting the scope quiet liberally.

UPDATE: Given the authors' responses I went back and re-read the paper. 
I think it's nicer than I had originally assessed and will increase the score. 
However, I'm still skeptical about whether this is a great fit for NeurIPS. 

As a minor note, I also realized that the $\Omega(\log(1/\epsilon))$ lower bound only holds against deterministic protocols. 

strengths_and_weaknesses: See summary above. 
questions: UPDATE: These questions have been answered by reviewers.

How does your submission relate to a paper by Brânzei and Nisan (EC’19) on communication complexity of cake cutting?


How does your protocol for 3 agents compare to the protocol by Deng et al for monotone valuations?

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: 
The paper is in two parts
I) The authors prove new upper and lower bounds in the RW model of cake cutting, which is a model for
discrete protocols. The main operations are CUT and QUERY. In all problems each player has a valuation
function on pieces of cake that may differ quite a lot from the other players. The authors consider
three types of cake cutting. In all of them assume that there are n people A1,...,An and that at the
end Ai gets Pi. They consider three types of outcomes

a) epsilon-envy free. For all i, Ai thinks that Pi is \ge Aj +\epsilon AND Pi is connected. They show

--- for n=3 there is an upper bound of O(log (1/epsilon) queries and a matching lower bound of
Omega(1/epsilon) queries.

--- for n\ge 4 an upper bound of O(n/epsilon) queries and a lower bound of Omega(1/epsilon) queries

b) epsilon-perfect. For all i,j Ai thinks Pj is size 1/n PM epsilon. Assume 2 players only.

-- if the min number of cuts is used then this can be done with O(1/epsilon) queries

-- if 2 cuts are used then this requires Omega(1/epsilon).

c) epsilon-equitable if there is some c such that, for all i, Ai thinks Pi is c PM epsilon.
For 3 players AND the pieces are connected, this requires Omega(\log 1/epsilon).

2) There is another cake cutting paradigm: Moving Knife. This paper introduces a model
for MK protocols that captures all current MK protocols. They show that all moving knife
protocols can be simulated by O(log(1/epsilon) queries in the RW model. This allows one to easily get
lower bounds on moving knife protocols. These lower bounds match the upper bounds.


strengths_and_weaknesses: 1) The envy-free protocols have always had the problem of the pieces being very disconnected.
This paper addresses that by looking at epsilon-envy free for which they have protocol
and lower bounds. For n=3 the upper and lower bounds match.

2) The moving knife protocols have not had a good model or any lower bounds. This paper
provides both.

These results are original, significant, and clear.

Weaknesses:
1) There seem to be two parameters: number of queries and number of cuts. The paper does
not mention the number-of-cuts for many of their algorithms, making me wonder if they are
galactic.

This is unclear.


questions: 
1) What does your model of Moving Knife protocols say about the
non-approximate moving knife protocols. The  epsilon=0 case.

2) The proofs look correct but I could not tell what the new ideas were. 



limitations: 
This paper has no societal impact.
It is about a very interesting math problem.
review_title: null

Meta-review: metareview: This paper considers the well-studied cake-cutting problem that captures the fair division of a resource (e.g., time, mineral deposits, fossil fuels, and many others) among n parties with equal rights but different interests over the resource. This is also a natural problem in algorithmic game theory. Various such settings are considered where the i'th party gets part P(i) at the end of the protocol. Approximation (various notions of, parametrized by some error epsilon > 0) are essential to the results in the paper. 

In the first part of the paper, new upper and lower bounds are developed in the Robertson-Webb model of discrete protocols. For instance, "epsilon-envy-free" protocols are considered (for all (i,j), player i thinks---according to their valuation function---that P(i) is at least P(j) - epsilon AND P(i) is connected) and it is shown, e.g., that: (a) for n=3, Theta(log (1/epsilon)) queries are necessary and sufficient; and (b) for n >= 4, an upper bound of O(n/epsilon) queries and a lower bound of Omega(1/epsilon) queries. This is just a sample. In the second part of the paper, another cake-cutting approach---Moving Knife (MK)---is considered: the paper introduces a model for MK protocols that captures all current MK protocols and shows new results.

This is a comprehensive paper on a natural mathematical model for fair division. 
confidence: Certain
Decision: Accept