Does Representation Guarantee Welfare?

Thank you for the review. We would be happy to add more discussion of related work, as you suggested.

How are the welfare of 2-representative panels compared with the 1-representative panels in empirical analysis? Would be good if the authors could show that.

Real data from citizens' assemblies does not contain information on alternative features or utilities. While working on the paper, we considered augmenting the real data with synthetic utility data, in order to measure the empirical difference in welfare estimation between 1- and 2-representative panels. However, we eventually decided against it since we felt the results would depend too strongly on the distribution over utilities to be meaningful.

Modeling assumptions are strong. For example, utilities are additive across features. ... Can the modeling assumptions be weakened?

Arguably, the only potentially restrictive assumption is the one on utilities. But we believe it is reasonable for the following reasons.

First, the assumption that the utility of an agent for an alternative is given by the product of their feature vectors is common in algorithmic game theory and computational social choice. See, for example, the following papers:

• Noothigattu et al. A Voting-Based System for Ethical Decision Making. AAAI 2018. (Section 5, Step II.)
• Balseiro et al. Contextual Standard Auctions with Budgets: Revenue Equivalence and Efficiency Guarantees. Management Science 2023. (Section 2, first paragraph.)
• Freedman et al. Adapting a Kidney Exchange Algorithm to Align with Human Values. Artificial Intelligence 2020. (Section 3.3.)

Second, we note that our model is in fact more expressive than it appears at first glance. Indeed, individuals could be represented through an arbitrarily rich feature embedding that captures nuanced attributes. Likewise, alternatives could also be represented in the same embedding space. The model where agent utilities are the dot product of an agent feature embedding and an alternative feature embedding is ubiquitous in AI; just to give one example, it underlies the two-tower model of recommendation. (We are prohibited from providing a URL but you can easily Google the term.) A caveat is that the more complex the feature space, the more demanding it is to produce a representative panel.

That said, a more general model would allow for non-linear utilities, e.g., the utility of an individual for an alternative could be a general concave function of the element-wise product of the individual's feature vector and the alternative's feature vector. We see this as an interesting direction for future work.

Thank you for the review. We will implement your suggestions, including expanding the related work introducing the moment problem in more detail.

In line 123, you state that that your definition of 1-representation is "essentially equivalent" to notions defined in the literature. Could you clarify what the differences are?

The definitions of 1-representation in prior work vary in how much 'tolerance' they allow, similar to our relaxation of $k$-representativeness in the empirical part. Specifically, previous papers assume that there is a lower and upper quota on the number of individuals with a certain feature value in the panel, with the corresponding proportion of people in the population with this feature value being within these quotas. See, for example:

Flanigan et al. Fair Sortition Made Transparent. NeurIPS 2022. (Section 2, second paragraph.)

In the theoretical part of the paper, you assume panels to be perfectly m-proportional. In the experimental section, this requirement is relaxed to proportionality rounded up or down. How would this relaxation affect the theoretical guarantees?

We believe that the qualitative results don't change when considering small errors with respect to the $m$-representativeness quotas, but a a precise theoretical analysis of this question seemed intractable when we considered it. A larger panel size comes with smaller error with respect to exact $m$-representation, which presents a way to alleviate this concern in practice.

What was the rationale behind the selection of the four specific citizen assemblies used in the experimental evaluation?

We chose these four citizens' assemblies in the paper because the data on the underlying populations — in particular, intersections between features — are publicly available and didn't require additional permission to be used. In the geographical areas where this underlying population data was available, we asked practitioners for the datasets on the individuals in the pool of candidates. We present all citizens' assemblies for which we obtained both candidate and population data in the paper.

Thank you for the review. We will correct the typos you pointed out in the final version of the paper.

Could you elaborate on epsilon‐accuracy - for example, why you focus on additive approximations rather than multiplicative ones?

We focus on additive rather than multiplicative approximation because this mirrors standard notions of accuracy in machine learning and statistics, so it is arguably the more natural choice. For example, in the PAC learning framework, accuracy is measured using an additive approximation: for an accuracy parameter $\epsilon$ and a confidence parameter $\delta$, the probability that that the difference between the true error and the empirical error of a hypothesis is at most $\epsilon$ is at least $1-\delta$.

That said, one can derive tight bounds for multiplicative $\epsilon$-accuracy from our proof technique by taking the ratio of the utility-maximum and utility-minimum instead of the difference in Lemma 15 and finishing the final proof steps accordingly. A matching lower bound can be proven with the techniques from the proof of the lower bound in Theorem 8.

It would also be helpful if you could discuss lower bounds on the worst‐case epsilon‐accuracy when $u_{min} > 0$.

For the rebuttal, we explored this helpful question and found that the upper bound in Theorem 9 on the accuracy of 2-representative panels is tight! One can prove this very similarly to the lower bound on the accuracy of 1-representative panels in Theorem 8. In fact, we believe that this proof technique can also be used for $k>2$, showing that the accuracy bounds for $k$-representation one can obtain with our upper bounding technique are tight. In the revised paper, we will include this matching lower bound and provide a proof in the appendix.

Additionally, could you expand on your utility assumption, namely that individuals’ utilities for alternatives derive from the attributes those alternatives possess?

This is a fair question; our answer is twofold.

First, the assumption that the utility of an agent for an alternative is given by the product of their feature vectors is common in algorithmic game theory and computational social choice. See, for example, the following papers:

• Noothigattu et al. A Voting-Based System for Ethical Decision Making. AAAI 2018. (Section 5, Step II.)
• Balseiro et al. Contextual Standard Auctions with Budgets: Revenue Equivalence and Efficiency Guarantees. Management Science 2023. (Section 2, first paragraph.)
• Freedman et al. Adapting a Kidney Exchange Algorithm to Align with Human Values. Artificial Intelligence 2020. (Section 3.3.)

Second, we note that our model is in fact more expressive than it appears at first glance. Indeed, individuals could be represented through an arbitrarily rich feature embedding that captures nuanced attributes. Likewise, alternatives could also be represented in the same embedding space. The model where agent utilities are the dot product of an agent feature embedding and an alternative feature embedding is ubiquitous in AI; just to give one example, it underlies the two-tower model of recommendation. (We are prohibited from providing a URL but you can easily Google the term.) A caveat is that the more complex the feature space, the more demanding it is to produce a representative panel.

Finally, in line 123 you state “This is essentially equivalent to the notion of representation considered in prior work on panel selection.” Could you clarify to what extent these two notions are equivalent, and where they might differ?

The definitions of 1-representation in prior work vary in how much 'tolerance' they allow, similar to our relaxation of $k$-representativeness in the empirical part. Specifically, previous papers assume that there is a lower and upper quota on the number of individuals with a certain feature value in the panel, with the corresponding proportion of people in the population with this feature value being within these quotas. See, for example:

Flanigan et al. Fair Sortition Made Transparent. NeurIPS 2022. (Section 2, second paragraph.)

Thank you for the review. We will increase the text size in the plots in the final version.

Why is there an assumption of the uniformity among voters? (That is, all individuals with the same values for the features used in the model (e.g., age and gender) are assumed to have the same utility for any given alternative.)

This is a fair question; our answer is twofold.

First, the assumption that the utility of an agent for an alternative is given by the product of their feature vectors is common in algorithmic game theory and computational social choice. See, for example, the following papers:

• Noothigattu et al. A Voting-Based System for Ethical Decision Making. AAAI 2018. (Section 5, Step II.)
• Balseiro et al. Contextual Standard Auctions with Budgets: Revenue Equivalence and Efficiency Guarantees. Management Science 2023. (Section 2, first paragraph.)
• Freedman et al. Adapting a Kidney Exchange Algorithm to Align with Human Values. Artificial Intelligence 2020. (Section 3.3.)

Second, we note that our model is in fact more expressive than it appears at first glance. Indeed, individuals could be represented through an arbitrarily rich feature embedding that captures nuanced attributes. Likewise, alternatives could also be represented in the same embedding space. The model where agent utilities are the dot product of an agent feature embedding and an alternative feature embedding is ubiquitous in AI; just to give one example, it underlies the two-tower model of recommendation. (We are prohibited from providing a URL but you can easily Google the term.) A caveat is that the more complex the feature space, the more demanding it is to produce a representative panel.

Thank you for the review. We will highlight the technical contributions and correct the typos you pointed out in the final version of the paper. Below we briefly respond to some of your comments.

Is the upper bound in Theorem 9 tight?

For the rebuttal, we explored this helpful question and found that the upper bound in Theorem 9 on the accuracy of 2-representative panels is tight! One can prove this very similarly to the lower bound on the accuracy of 1-representative panels in Theorem 8. In fact, we believe that this proof technique can also be used for $k>2$, showing that the accuracy bounds for $k$-representation one can obtain with our upper bounding technique are tight. In the revised paper, we will include this matching lower bound and provide a proof in the appendix.

... and is there any concrete evidence that the optimization program in Theorem 9 does not admit a closed-form solution?

We strongly believe that the optimization program in Theorem 9 doesn't admit a closed-form solution. The best evidence for this is the case $p=0$ (this optimization program can be found in Appendix A.3), where the variables appear both in the exponent and in the base of the first-order conditions. For a general $p$, the variables appear in the first-order conditions with high and non-integer powers in both the denominator and numerator, which is generally a good indicator that no closed-form solution exists.

The authors could consider exploring a weighted version of descriptive representation (where each person on the panel is assigned a nonnegative weight), which may help address the issue that is not an integer. The authors may want to look into characteristic functions, Fourier transforms, and their connections to low-degree moments. The reviewer wonders if the notions in the paper have any connections to proportional fairness (i.e., no subpopulation wants to leave and form a proportional smaller panel).

Thank you for the interesting suggestions. While idea of a weighted panel is theoretically interesting, we believe it would not be seen as legitimate in practice. Regarding notions of proportionality (such as proportionally fair clustering, justified representation, etc.), we have worked extensively on such notions and we do not believe they can be fruitfully connected to the paper under consideration.

The experimental setup is clearly described, but the paper could better justify the design choices. It feels a bit unnatural to use the maximum possible panel size as a measure of how easy it is to satisfy the representative constraints (i.e. it is harder to round the estimates to the true value when the true value is large). Would it make sense to study a multiplicative notion (e.g., the desired and actual number of people are within a factor of $1 \pm 0.1$)?

Thank you for the interesting suggestion. The definition of $k$-representativeness we used in the empirical part of this work comes from wanting to be as close to being perfectly $k$-representative as possible for a given panel size. In this setting, practitioners would generally want to choose a larger panel size to get more accurate $k$-representativeness, which may require a larger candidate pool size.

We re-ran our experiments to find (for different panel sizes and different $k$) the smallest possible $\varepsilon$ such that there exists a panel that is $(i)$ $k$-representative up to a multiplicative factor of $1\pm\varepsilon$, and $(ii)$ has the desired size, as you suggested. When the number of feature-value tuples considered is greater than the panel size, then $\varepsilon=1$, since for at least one feature-value tuple, no person will be in the panel, but the required quota is positive. If the panel size is greater than this lower bound, the achievable $\varepsilon$ decreases with the panel size (approximately) inversely linearly, as expected, up to the point where the pool is 'too skewed', roughly when for some feature-value tuple the quota is higher than the number of candidates in the pool with this feature-value tuple. This point is in all cases a bit before the maximum possible panel size of $k$-representative panels according to the notion used in the paper. After this 'maximum representative panel size,' $\varepsilon$ increases with the panel size, again as expected. To illustrate this, we list the results for the Aus2 dataset from the paper below:

We believe that this additional experiment is a valuable addition to our understanding of $k$-representative panels in practice. First, it confirms that increasing the panel size comes with more accurate $k$-representation up to some 'maximum panel size': up to the critical size $c$, the panel size is inversely proportional to $\varepsilon$. More importantly, it suggests that the maximum panel size we obtain from our additive approximation may be too high: there is a small gap between the critical size defined above, after which the pool is effectively too skewed, and the maximum possible size (in the additive sense). In this gap, the 'quality' of the $k$-representation already decreases with panel size, so the critical size can be interpreted as the largest reasonable panel size up to which adding people to the panel comes with increased representation. Fortunately, our new experiment shows that in the real instances we analyzed, the critical size for $2$- (or even $3$-) representative panels is frequently above the desired panel size and never drastically below.

In practice, a mix of the two approximations may do best: A downside of the multiplicative approximation is that if quotas for some feature-value tuples are small (say, 2.5 people of a certain type on the panel), even the 'closest' integer will induce a large epsilon (0.2 in this example), which will then in turn give feature-value tuples with larger quotas more wiggle room than necessary. An obvious downside of the additive approximation is that it doesn't 'incentivize', say, having 3 people of a certain feature-value tuple on the panel instead of 2 if the quota is 2.9. Furthermore, there is a tradeoff between tighter approximation guarantees and more equal selection probabilities for individuals in the pool. Which notion should be employed will depend on the goals of the practitioners.

We will add a discussion of these new insights and the additional experimental results in the revised paper.

And following this line of thought, does randomly sampling $O(k \log d/\epsilon^2)$ times from the population gives a $1 \pm \epsilon$ multiplicative tolerance for $k$-representativeness (which seems to follow from standard application of Chernoff bound and the union bound).

We considered selecting panels by randomly sampling from the population in the setting of welfare estimation but saw that the number of samples (=people on the panel) needed to get accuracy guarantees similar to those for (worst-case) 1- or 2-representative panels exceeds the size of real citizens' assemblies.