Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper deals with a setting of participatory budgeting in which voters's preferences over projects are aggregated to fund a subset of the candidate projects with a limited budget. Based on justified representation in committee elections (a related setting without costs) a fairness concept is introduced as well as an aggregation rule (named Rule X) which is shown to satisfy the concept, while other commonly used rules fail to do so. Several variants, restrictions and extensions are discussed.
main_review: The topic of participatory budgeting and the suggested model are, as far as I know, in the scope of Neurips. The results and open questions significant and original as far as I can tell. The models and their theoretical analysis appear reasonable to me.

To my mind, related work should be elaborated on in the introduction. Some information is only provided later (see for example Section 3.1, middle and bottom of page 4), and should be mentioned early on. For instance, a reference for the concept justified respresentation is missing in the introduction (cf p. 1 and p. 3). "Many works" (l. 39) are referred to without literature pointers. The introductory example uses some general statements without reference such has "most cities" (l. 43), "many cities" (l. 55).

I like the readability of the problem setting and the main part of the paper. Especially, the intuition and formality, and the comparison to the state of the art in committee elections and a permanent review of where the results can be settled in comparison was quite helpful. At some points defensive statements like "our proofs are significantly different from..." and "This is yet another explanation why EJR is am important and well-justified axiom" seemed a little misplaced and too meta-explanatory to me.

Considering Example 1 (p. 7), I get the impression that the condition is too strong to hold for a single voter. Even if that player forms a T-cohesive subset, it might make sense to relax the EJR property to large enough groups. What happens to rules like PAV for such a variant? 

Proofs and additional details are often deferred to the appendix. From my point of view, the paper should be self-contained. Hence, it would be better to include at least sketches in the main paper and omit references to an appendix.
Similarly, Section 3.3 and the conclusion should be rewritten to present information differently.
Without the appendix many details are not comprehensible. For instance, I have not verified the proofs of Theorem 2 (Appendix D) and Theorem 3 (Appendix F). To my mind, the latter analysis of a new rule satisfying FJR is one of the main claims in the paper and should have more focus. Statements such as "in Appendix F we discuss other important properties as well as some drawbacks of GCR" (l.328) do not provide much valuable information in the main paper.

At the same time Figure 1 takes a lot of space for example details that are barely used. The picture is only referred to in one paragraph, and many variables are not even used.

The example of a "bike trail along Example River" (l. 66) additionally involves the issue of dependencies of projects which is not studied here. I wonder what can be said about such additional constraints.


Minor details:

l. 49: "so we can assume..." the following statement might work for the example but this is assumption cannot be implied (without reference from social sciences). It would be better to rephrase this less generalized.

l. 102: Please rephrase "that is"; what follows is only an implication.

l. 110: A Committee size |W| can also be less than k?

p.4: The notion mathcal{R}(E) is not defined before Definition 2, and can easily be added in the preliminaries.

p. 8: 3.3: Priceability is not defined at all.
      4.1: The tie breaking procedure is mentioned to be needed in the context of priceability, which is not studied in the main paper. For the sake of self-containment, perhaps the information "breaking ties in favor of smaller cost(T)" can be written in Footnote 6, if not left out completely
limitations_and_societal_impact: -
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the proportional participatory budgeting model, where the projects have arbitrary costs and the voters have additive utilities. In this classic model of PB, the paper studies fairness concept and explore whether existing rules satisfy certain fairness guarantee. Most of the results in this paper are based on approval-based committee elections and some concepts are slightly modified to fit the PB model.



main_review: The major contributions are:

1. The paper extends Rule X to proportional participatory budgeting and the axiom named Extended Justified Representation (EJR), which is well-known in committee elections. It is easy to follow since they define it step by step by using several `intermediate’ definitions. They also show that Rule X satisfies EJR up to one project, a mild relaxation of EJR, and give a counterexample to show the PAV rule does not satisfy EJR. In addition, they show that Rule X satisfies the alpha-core with asymptotically tight bounds with respect to alpha and other properties like exhaustiveness.

2. The paper proposes a strengthening concept of EJR, namely FJR, which guarantees representation to groups that are only partially cohesive. Although Rule X fails FJR, they also give a new rule named GCR, which satisfies FJR.

3. The paper also do experiments comparing different variants of Rule X, Phragmén’s rule, and PAV and explore more about GCR.

Here are some concerns about the paper.

1. It looks like EJR and EJR up to one project is different in the general PB model. The authors only show that Rule X satisfies EJR up to one project, and PAV fails EJR. Does PAV fail EJR up to one project in the general PB model? It would be better to compare two rules with the same axiom in the general PB model. Is there any brief thinking about Rule X and EJR? 

2.It would be better to give the definition consistently, like definition 7 uses |S|>cost(T)*n but definition 8 uses \sum_{c\in T}cost(c)\le |S|/n, both having the same meaning, but the former looks concise.

3. The authors also propose FJR. Are there any scenarios where the rules that satisfy EJR are not good, so we need to use rules that satisfy FJR?

The authors addressed my questions.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors introduce two axioms for participatory budgeting, EJR and FJR, which are related to proportionality/fairness of PB mechanisms. Their main result shows that a proposed PB mechanism, "Rule X" satisfies EJR, and PAV (an incumbent mechanism), and its variants, do not. They briefly describe a rule (Greedy Cohesive) that satisfies FJR. They describe some experiments with real PB data, which are not included in the main paper.

main_review: 
This paper presents some interesting and novel theoretical results in participatory budgeting. The exposition and notation is very clear, and authors take care to place their contributions within the existing literature. The introduction of EJR and FJR, and their adaptation of Rule X to a general PB setting, are both notable contributions.

The proof of their main theoretical results (Theorem 1 and Example 1) are easy to follow, and I appreciate that these are explicitly included included in the main paper. Some of the other theoretical contributions are less impactful, as they are left to the appendix (which I did not read). I am somewhat familiar with this literature -- and by no means an expert -- and these results look sound to me.

One negative point: there are several experiments with real PB data mentioned in the conclusion, which are not discussed or presented in the main paper. The extent of these experiments could almost constitute a separate paper, and they don't seem to add much to this paper since they are only mentioned in passing. As an applied researcher, I would have enjoyed reading about these experiments, and the implications of this theoretical work on real PB elections. However these experiments are not very important to the main (theoretical) contributions of this paper, so the overall paper is not diminished by their absence. 
limitations_and_societal_impact: There is very little discussion of the social impact of this work. The new proportionality axioms (EJR, FJR) are described in theoretical detail, though not from a practical perspective. (This seems to be the norm for most social choice and mechanism design literature.)

The authors certainly could have done more to discuss the practical pros and cons of their axioms and Rule X, perhaps with the discussion of some experiments using real data. Their one example of Circleville (Fig. 1) is nice, but only one example. In particular, it would be helpful if the authors expand on how the practical implications of EJR/FJR differ from those of the core (or other notions of fairness and efficiency in PB).
review_title: null

Meta-review: This is probably the strongest paper in my batch (as AC).  
Decision: Accept (Poster)