Venue: NeurIPS 2022 Conference

Reviews:

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: In this paper, the author proposes a new concept called Strong Proportionality as a new fairness measurement. The author shows that Strong Proportionality is not achievable using deterministic and strategyproof mechanisms and proposes a randomized mechanism called Random Rank which can achieve not only Strong Proportionality but also other efficiency concepts like universal truthfulness etc. 
strengths_and_weaknesses: Overall, the paper contributes useful concepts, and the definitions and mathematical arguments are clearly written. The impossibility results show us the limitation of deterministic mechanisms and thus the randomized mechanisms are naturally motivated. The paper gaps between the economic and machine learning literature and is a valuable contribution to the community.




questions: I have a few questions:

- In the actual deployment, will the decision-maker picks and fix a deterministic mechanism (choose from the randomized mechanisms?) If that's the case, the theoretical guarantee holds only in expectation over the choice of the deterministic mechanism, which does not hold for every single mechanism. The paper could be stronger if the author could say something like "w.h.p. over the choice of the mechanisms, the deployed mechanism also satisfies strong proportionality" etc.

- Can the authors comment on how the mechanism scales up to a higher dimensional setting? Will there be any curse of dimensionality problem?
limitations: NA
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: This paper proposes a new concept Strong Proportionality, which means in the case that there are only two groups of agents at two locations, then both groups incur the same total cost. This is a stronger version of the Proportionality property in the participatory budgeting literature. The authors show that there is no deterministic strategyproof mechanism satisfying this property, and designed an algorithm, Random Rank, that satisfies Strong Proportionality in expectation. They also show that Random Rank is the only randomized mechanism that achieves universal truthfulness, universal anonymity, and Strong Proportionality in expectation. Finally, they show that if universal truthfulness could be weakened to truthfulness in expectation, then there is a mechanism that could have a fairer ex-post fairness guarantee.

strengths_and_weaknesses: * Originality: This paper is closely related to research on facility location and fairness in collective decision making, especially the Proportionality concept in participatory budgeting. The Strong Proportionality concept is naturally motivated. The proofs are nicely built on previous results about the Phantom mechanism. Related work is properly cited.
* Quality: The notations are well defined. The theorems / lemmas are cleanly presented and proved.
* Clarity: This paper is well written and organized. A minor comment: Figure 1 and Table 1 are not referred to in the main paper. 
* Significance: The authors have a nice summary of randomized social choice and facility location mechanisms in Table 1, and show how Random Rank is the only algorithm that satisfies all the properties listed. This result is interesting and could inspire new research directions in this area. However, I feel the setting that there are only two groups of agents at two locations is limited. 

questions: Have you considered generalizing the setting to multiple groups in 1 dimension? What makes it much more difficult than the two groups case?
limitations: The authors mentioned that one future direction would be to extend the problem to multiple dimensions, but even in the one dimension case, it would be nice to have a more general case than only two groups of agents.
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 work considers the classical facility location problem with a new fairness constraint, "strong proportionality." The authors show that no deterministic strategy can be both strategyproof and fair, and further leverage known characterizations of strategyproof mechanisms in this setting to identify ``Random Rank" as the unique (randomized) mechanism that is both strategyproof and fair.
strengths_and_weaknesses: Strengths: This paper succeeds in providing a complete characterization of strategyproof mechanisms that satisfy their notion of strong proportionality. The paper is quite well-written and respectful to the reader.

Weaknesses: My overall impression is that the results and techniques in this work may be somewhat limited in scope; a more thorough investigation of the ramifications of strong proportionality would make for a very strong paper.
questions: ---Again, I would like the thank the authors for the clear and respectful exposition.

---To elaborate on the ``weaknesses" above, how surprising is the main result? While I am not an expert on this literature, the strong characterization of strategyproof mechanisms seems to make the result somewhat unsurprising, at least naively. This rigidity further manifests in the limited setting of the problem to $[0,1]$ or $\mathbb{R}$.
    
---One could even argue that the main takeaway of the main result is that it shows that strong proportionality is itself not a sufficiently interesting fairness notion, especially given that it seems to have been first introduced in the present paper.
    
---That said, I do wish to emphasize that the arguments in this work are quite nice in their own right. However, it seems to me that the results in the present paper would be a great complement to a more thorough investigation of strong proportionality or other related fairness notions, as seems to have been done for proportionality in Aziz, et al (2021).
    
---The definition of randomized mechanism (Footnote 3) seems slightly ambiguous; it seems like the probability distribution over deterministic algorithms should itself be a function of the input to accommodate the example in the footnote, but this isn't clear in the definition.
limitations: There do not appear to be obvious negative societal impacts. The authors do discuss several possible avenues for improving the current results.
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 mechanisms for facility location games that are both truthful and fair.  In particular, the authors consider a fairness notion called Strong Proportionality, which roughly says when there are two groups of agents where each group are located at the same location, the total costs of the two groups should be the same in expectation.  The main result is that the only mechanism that is anonymous (meaning symmetric across agents), truthful, and strongly proportional is Random  Rank, which picks an integer k uniformly at random between 1 and n and outputs the k-th largest location.
strengths_and_weaknesses: Strengths

The paper is well written and polished.  Fairness in facility location games is a meaningful problem.  The main result of the paper is clean and nice, and the proof is cute and nontrivial.  Conceptually, I mostly view the result as a negative message saying proportionality is hard to achieve in facilitty location games, which is of course a meaningful message.


Weaknesses

My biggest concern is regarding the proportionality axiom itself.  While the axiom definitely makes sense, it's not clear to me it is the only reasonable notion of fairness in the context of facility location games.  To this end, I'd appreciate more discussion on other notions of fairness (if they exist) and why they are not as suitable for the purposes of this paper.  A less important thing is I'm curious about the possibility of a characterization for truthful-in-expectation mechanisms.  There presumably one would need some new techniques, since the characterization by Massó and Moreno De Barreda no longer applies.
questions: (Also putting some detailed comments here.)

Line 70, "k-facility: the "-" looks like a minus sign.

"AverageOrRandomRank-p": again the "-" looks like a minus sign.

Sec 6: I'm a bit confused by the logical flow here.  Random Rank is only fair in expectation, and the fix is another mechanism that is also only fair in expectation?  Is the idea that the new mechanism is "more fair" (although still not "exactly fair") in the ex-post sense?
limitations: Overall I'm satisfied (see detailed comments above for some minor suggestions).
review_title: null

Meta-review: metareview: Executive summary:

This paper considers the facility location problem. The authors define and explore a natural new fairness notion called "strong proportionality" (Definition 5). They show that no mechanism can be universally truthful and universally strongly proportional; at the same time they show that the randomized RandomRank mechanism they devise is the unique mechanism satisfying universal anonymity, universal truthfulness, and strong proportionality in expectation.

Discussion:

There is considerable support for this paper (one accepts, two weak accepts, and only one borderline reject). All reviewers appreciate the model and the new fairness notion, and that it uniquely characterizes (a natural) randomized mechanism.

The only slightly negative reviewer still liked the paper, but was worried the fairness notion may be limited to the specific problem and wasn't explored more generally.

Accept.
confidence: Certain
Decision: Accept