Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors study how representative are panels chosen via sortition, i.e., by selecting randomly individuals from a population. The authors measure representation as follows. First, they assume that there is some metric that measures similarity between members of the population and assume that each person would like to be represented by someone as similar as possible. Then, they say that the q-cost of a panel for a person is the distance of the q-th closest panel member from that person (according to the metric). The cost of a panel is the sum of the q-costs. Finally, representation is the worst-case ratio between the minimum panel cost and the expected one (we look at the expectation because panels are drawn by a randomized algorithm). The authors show that if q is greater than half of the size of the panel then good representation values are possible, and otherwise they are not. 
strengths_and_weaknesses: Strengths:
- theoretical results are nice and complete

Weaknesses
- The added value of the paper, as compared to previous publication, is nice but not as large as one might expect
- The value of the experiments is very unclear. I could not really tell what the point of the experiment is. The authors crunch some numbers and show plots, but I am missing actual high-level conclusions that go beyond analyzing the shapes of the plots
- Plots in Section 5 are missing any sort of standard deviation/variation information

Minor issues:
l. 99: "99 urban" --> "90 urban" ?
It might be useful to explain in lines 143-151 that correlations in the randomized selection process are allowed (assuming they are).
l. 221: "that that"
l. 222: "individuals" -> "individual"
questions: Why is it important to measure the distance between the candidates, instead of assuming that each agent can give a boolean value indicating if another person does or does not represent him/her?
limitations: I do not believe this question really applies to the theoretical part of the paper. For the experimental part, it is not clear to me what the actual point is, so I cannot really answer.
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 considers the fairness and representativeness of sortition, a randomized method of group selection. Typically sortition involves uniformly random selection of k participants. This work asks whether other methods of selection may lead to a more representative panel with minimal impact on fairness. Fairness here is the goal of selecting each participant with at least probability k/n while representation is the ability of selecting a panel such that each non-member is similar to a member. In particular, they make use of the "q-social cost" metric -- the sum of distances from each individual to their q-th closest panel member.

The paper shows that when q > k/2 uniform random selection provides optimal representation. For smaller q the paper shows that good representation is not possible with only a tiny loss in fairness but develops an algorithm that modifies a low social cost panel to improve representation. Experiments are performed showing the efficacy of the algorithms they have developed. For both Uniform Selection and RandomReplace, several examples are given demonstrating various q-social costs for different values of k and q.
strengths_and_weaknesses: I find the idea of the q-social cost, once I got some intuition for it, quite a fitting idea for measuring the quality of a panel formed via sortition. Focusing on metrics beyond just fairness is useful and relatively novel in sortition. The paper is generally quite well written although it would be nice to have a little bit more emphasis on giving natural, intuitive explanations of your definitions of representation (primarily) and fairness (fairly clear already). I found the proofs of the theorems in the main paper generally clear and they seem correct. 

Due to the simplicity/natural usage of the Uniform Selection algorithm adding to theoretical knowledge on the mechanism is a useful contribution.  The RandomReplace algorithm is interesting although it seems destined to remain theoretical; finding an optimal panel is obviously a very complex task in a real-world setting. Discussing the importance of the optimality of the panel would be a useful contribution -- e.g. I'm unclear on what properties you would expect if you applied RandomReplace to a uniformly selected panel.

I greatly appreciate the experiment section and some visualization of how q-social cost changes with k and q. Some parts of the experiements section could be clarified (see below).


Minor Issues

Line 127: Should it read "denotes the distance between i and j, and..."?
Line 209: Is P* only defined in Algorithm 1? Mentioning it in text here or in the Preliminaries would be ideal.
Line 218: "The algorithm reaches this line when *it* considers ..."
Line 224: This is the only place you say "agent"; consistency in terms is ideal.

Experiment section:
Is there a reason not to standardize the y-axis? It makes comparison between plots much simpler
What is opt_apx?
In general, more "prettified" legend terms would be better.
In Figure 1c is opt directly under opt_apx? This may be what you mean on lines 297-298 but it could be more clear.
questions: 1. Is it the case that RandomReplace is meant to provide a good balance of fairness and representation as compared with the optimal panel? Assuming so, is that evident in the experiments? I am unclear on what the experiments say about RandomReplace other than that it is (quite understandably) not as low-cost as the optimal panel.

2. Section 3 begins by alluding to multiple algorithms that are perfectly fair. Are there multiple such algorithms? Aren't they all necessarily equivalent to Uniform Selection?
limitations: The authors have provided only very little discussion of the potential societal impact of their work. However, the work relatively far removed from meaningful real-world impact; I do not feel such discussion is missing, only absent.
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: The paper addresses the problem of sortition, which is a democratic process consisting in randomly selecting a subset of citizens from a population. There are two important criteria in this selection process: *fairness*, meaning that citizens should have an equal chance to participate, and *representation*, meaning that the chosen panel should well represent the large population. The authors introduce a representation metric which is inspired by distortion-based analysis of voting over metric spaces, and which depends on a parameter $q$. Depending on the value of $q$, the paper provides results on whether a perfectly fair algorithm achieves good representation. In the regime where there is a necessary fairness-representation trade-off, an algorithm with guarantees on the two criteria is presented.
The results are illustrated with experiments on the Adult dataset, as well as the European social survey.

strengths_and_weaknesses: Strengths:
* The paper is clear, well-motivated and well-written.
* The idea of measuring representation based on the distance of an individual to the $q$-closest member is clever and intuitive.
* The theoretical results are not technically difficult, but they are intuitive, simple to understand and definitely interesting.
* The experimental evaluation is convincing enough. 
* I appreciated that the authors anticipated the need for a better understanding of the fairness-representation trade-off in the Appendix.

Weaknesses:
* Algorithm 1, Line 1: There is no explanation on how to compute the minimizer over all possible subsets of size $k$ among the set of size $N$. The minimization problem is likely intractable; therefore the authors should describe a computationally efficient method to solve this. I found no details in Section 4, neither in the experimental section, nor the Appendices. 

Minor comments:
* Topic: The paper is not related to machine learning: neither the techniques, nor the application problem. However, even if the paper falls outside NeurIPS usual topics, I do think sortition is an important problem.
* Additional references on representation constraints when selecting a panel of representatives from a set of candidates (if you think they are off-topic for your work, please explain why). In particular, [2,3] also use a representation metric in that context. 

[1] L. Elisa Celis, Lingxiao Huang, and Nisheeth K. Vishnoi. 2018. Multiwinner voting with fairness constraints. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI'18). AAAI Press, 144–151.

[2] Lang, J., & Skowron, P. (2016). Multi-Attribute Proportional Representation. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10024

[3] V. Do, J. Atif, J. Lang, N. Usunier. Online Selection of Diverse Committees. IJCAI 2021, Aug 2021, virtual, Canada.


questions: * Can you please respond to the concerns raised above? 
* Related to the main weakness I described, what are the approximate runtimes of the algorithms? What happens for larger values of $k,N$, e.g. $k=100$ as for citizens assemblies?



limitations: The social context of this work is well described.
review_title: null

Meta-review: metareview: Reviewers like the problem of fair sortition for its importance as well as its fitness to NeurIPS. Reviewers also liked the solid theoretical results. Minor concerns were raised about the technical depth and uninformative experiments, but the overall sentiment is quite positive.
confidence: Certain
Decision: Accept