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: Truthfulness is an important issue in the field of indivisible resource allocation. However, it is widely known that fairness and efficiency are usually not compatible with truthfulness. In this work, the authors studied a relaxed notion of truthfulness, namely, non-obvious manipulability (NOM). Fortunately, under the relaxed notion, the negative results do not hold anymore. 

Originally, truthfulness means it is each agent’s dominant strategy to report the true values no matter what values will be reported by the others. The related notion NOM only requires that reporting the true values yields a (weakly) higher utility than lying in either the best and worst-case scenarios. 

The fairness notion concerned in this work is EF1 (envy-free up to one good), a popular relaxation of EF (envy-freeness). The efficiency notions concerned include utilitarian welfare maximization, egalitarian welfare maximization, and Nash welfare maximization. 

For fairness, under the new notion, the authors first show that the Round-Robin is actually NOM, which significantly separates truthfulness and NOM. Therefore, NOM and EF1 are compatible. Actually, using the algorithm by Aziz, WINE 2020, we can have a stronger result by achieving ex ante EF, ex post EF1 and NOM simultaneously. 

For efficiency, (a little bit unexpected to me since the requirement of NOM is weak to me), the authors proved that for any number of agents, both egalitarian and Nash welfare maximizations are not compatible with NOM. For utilitarian welfare maximization, however, although it is still not compatible with NOM with two agents, they are compatible with more than two agents. 

Finally, the authors investigated the compatibility among NOM, EF1, and Pareto efficiency. To answer this question, the authors provided a black box reduction from any algorithm that outputs (clean and non-wasteful) EF1 allocations to a new mechanism that not only ensures EF1 but is also NOM. Moreover, the reduction preserves the property of Pareto efficiency, which implies that NOM, EF1, and Pareto efficiency can be satisfied together, via existing results in the literature.

strengths_and_weaknesses: Strengths

I agree with the authors that NOM might be a better notion for non-manipulability since truthfulness is hard to achieve together with fairness and efficiency. Thus, I think this work may be a good initiating work. 

The authors also provide a relatively complete picture for NOM. 


Weaknesses
The requirement of NOM is still a bit weak to me (although it is still not compatible with some efficiency criteria). It will be better if the authors can justify why only the best and the worst cases are particularly interesting. 

The proofs are not technically hard.

The writing in general is good but can be further improved. 


Typos:

Line 130 M should be non-italic in \Pi_n(M).
Line 214 l does not dependent of her report
Line 273 argmin should be a function
Line 274 also report her
Line 275 she get
Line 277 I do not see why Nash social welfare maximization is the most popular objective. 
Line 329 each of these two subsets are 
Line 351 some useful notation
Line 417 establish Theorem 5
Line 418 that that
“with respect to” is sometimes abbreviated and sometimes not; better to be consistent

questions: For the reduction part, if all the valuations are strictly positive, the reduction actually does not need to do any change. I am not sure if this can be a good warm-up to show at the start of this section so that the readers can understand why we need to design the reduction like this.

The word “truthfulness” is used throughout the paper except related work, in which strategyproofness is sometimes used. I guess the authors want to be consistent with the referred papers, but I am not sure if the readers will get confused. 

Have you ever defined what “PO” is short for?

limitations: N.A.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the problem of non-monetary resource allocation when agents have additive valuation functions over indivisible goods. Since there exist strong impossibility results in this setting if one also imposes truthfulness, the authors consider the relaxed incentive guarantee known as non-obvious manipulability (NOM). The main result is that any algorithm that satisfies envy-freeness up to one good (EF1) can be transformed into a not-obviously manipulable and EF1 algorithm (subject to mild conditions). This main result is complemented by some other results regarding NOM in the domain of non-monetary resource allocation: the round robin and utilitarian social welfare-maximizing algorithms are NOM, but Nash and egalitarian social welfare-maximizing algorithms are not.
strengths_and_weaknesses: Strengths: The idea of the paper is novel and the idea is very interesting. Escaping and refining classic impossibilities in this space is an important problem, in my opinion. The results that are obtained, especially the main result (Theorem 5), are strong and surprising.

Weaknesses: I am not convinced that NOM is a good relaxation of truthfulness (for this problem, at least). See my question below.

Minor:

Line 99: "efficiency" -> "efficient"
Line 184: "an" -> "a"
Line 191: "agent" -> "agents"
Could lines 197-202 go to the appendix?

questions: 1) Lines 249-250 grabbed my attention, since my intuition is that manipulating the utilitarian SW-maximizing mechanism is (intuitively) "obvious" when valuations are not required to be normalized: I should report huge valuations for all goods. Is there intuition for why we shouldn't think of this as an "obvious" manipulation? It would also help me if you could lay out the formal relationship between NOM and obvious strategyproofness of Li17, if there exists one. Lines 38-40 hint at such a relationship but leave it ambiguous.

2) Can you write down the mechanism that is obtained from applying the reduction (Mechanism 1) to MNW? Even just for 3 agents and 4 items?
limitations: Adequately addressed.
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 work considers the tools available to a central designer needing to allocate goods fairly and efficiently to agents with additive valuation functions and no monetary transfers. There are no general envy-free and deterministic truthful mechanisms to do so. Recent other work in loosening truthfulness has explored what types of manipulations are likely to be taken advantage of. This work takes one such notion, “non-obvious manipulability” and asks what additional strength does relaxing truthfulness to NOM give to the central designer - notably, can she achieve a mechanism that  is deterministic and envy-free up to one item? More generally, how do her options change when she relaxes truthfulness to NOM?

The paper answers in the affirmative, and in fact gives a black box reduction from designing an EF1+NOM mechanism to that of designing an EF1 algorithm. 

This black box reduction hinges on handling the special cases where the demanded items are fully disjoint sets (1), fully disjoint except for the goods desired by one person (case 2), fully disjoint except the goods desired by two people (case 3), and if none of those apply, applying the algorithm directly (case 4).



strengths_and_weaknesses: The paper comprehensively addresses the impact that relaxing truthfulness to non-obviously manipulability gives to a designer. This makes for a helpful and interesting contribution to the literature surrounding relaxed notions of truthfulness.

The nature of the black box reduction - special cases for when two or fewer agents have overlapping demand sets raises a small question of whether or not there is a more fundamental core regarding three agents that can be embedded to simplify the reduction. 

questions: Can you comment on the jump from 2 to 3 agents in both Theorems 2&3 and in the core reduction and result? Does NOS retain relevance with three agents having overlapping preferences or is this a case where it is capturing 
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: This paper reconsiders the classic problem of allocating indivisible goods through the lens of non-obvious manipulability (NOM).  The results show that this can bypass known impossibility results for the stronger and more standard requirement of truthfulness.  In particular is possible to achieve deterministic+EF1+NOM and that this can be combined with (fractional) Pareto efficiency among other positive results.  Negative results show that Nash and egalitarian welfare maximization both fail to satisfy NOM.
strengths_and_weaknesses: On the positive side, the paper is clear and does a nice job revisiting a classic problem and gaining new insights about both classic mechanisms and new designs.  The black-box-reduction seems technically non-trivial and from a theoretical perspective the combination of properties it achieves is an improvement over prior work.

On the negative side, the arguments in Sections 3 and 4 largely seem straightforward, so the contribution here seems somewhat limited.  For Section 5, which has more of a technical contribution, it is unclear to me how important this is for practice.  Other than identifying that it has stronger theoretical properties, there isn’t any evidence presented that the results of the reduction are noticeably better than Round-Robin or PS-Lottery.  

questions: Can you make a case that the stronger theoretical properties yielded by the reduction lead to meaningfully better results in practice.
limitations: NOM is a relatively recent approach.  Given that the interest of the results hinges on the reasonableness of relaxing truthfulness to NOM, I was surprised there does not appear to be discussion of whether the guarantee provided by NOM and the incentives of them mechanisms that satisfy it are reasonable in this setting.
review_title: null

Meta-review: metareview: Reviewers agreed that this paper explored a natural and interesting strategic aspect of fair division (non-obvious manipulability). This helped escape classical impossibility results in fair division. Minor concerns were raised about the practical significance of NOM, but overall the sentiment was quite positive.
confidence: Certain
Decision: Accept