Does Representation Guarantee Welfare?
Authors: Jakob de Raaij
Ariel D. Procaccia
Alexandros Psomas
Venue: NeurIPS 2025 poster ()
Keywords: sortition
citizens’ assemblies
governance
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: A panel satisfies *descriptive representation* when its composition reflects the population. We examine the role of descriptive representation in collective decision making through an optimization lens, asking whether representative panels make decisions that maximize social welfare for the underlying population. Our main results suggest that, in general, representation with respect to *intersections* of two or more features guarantees higher social welfare than that achieved by the status quo of proportionally representing individual features. Moreover, an analysis of real data suggests that representation with respect to pairs of features is feasible in practice. These results have significant implications for the design of *citizens' assemblies*, which are gaining prominence in AI governance.

Does Representation Guarantee Welfare?
Jakob de Raaij Harvard University
Ariel D. Procaccia Harvard University arie arielpro@seas. harvard.edu
jderaai j@fas harvard.edd edu
Alexandros Psomas Purdue University apsomasêca purdue edu
Abstract
A panel satisfies descriptive representation when composition reflects the pop- ulation. We examine the role of descriptive representation in collective decision making through an optimization lens, asking whether representative panels make decisions that maximize social welfare for the underlying population. Our main results suggest that, in general, representation with respect to intersections of two more features guarantees higher social welfare than that achieved by the status quo of proportionally representing individual features. Moreover, an analysis real data suggests that representation with respect pairs of features is feasible in practice. These results have significant implications for the design of citizens' assemblies, which are gaining prominence in Al governance.
1 Introduction
A citizens' assembly is group of everyday people who come together to discuss policy issue, with the goal of informing decision makers [23, 25, 18]. This paradigm has been on the rise around the world, with some of the most prominent assemblies convened by European governments to tackle constitutional questions and climate change. The success of citizens' assemblies driven, at least in part, by several characteristics.
Deliberation: Assembly members engage in a deliberative process over a period of weeks or months.
Random selection: The assembly is selected through a lottery.
Descriptive representation: The lottery is designed ensure that the assembly proportionally reflects the population according to multiple features, such as age, gender, ethnicity, level of education, geography, and viewpoint.
In this paper, are interested in better understanding the role of descriptive representation. Political theorists have long argued that descriptive representation contributes to the legitimacy citizens' assemblies and promotes public trust in their recommendations. This thesis is largely supported by experimental evidence [15], but it is disputed by some studies [16].
We steer clear of this (partly normative) debate as we examine descriptive representation through novel, quantitative lens. Our key research question this:
If panel satisfies descriptive representation, does make dectsions that optimize social welfare for the underlying population?
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

If the answer were a clear "yes," it would provide a new, objective way to justify the importance of descriptive representation. And if the answer were more nuanced (spoiler alert: it is). would inform the design of future citizens" assemblies that make better decisions or recommendations.
Our approach and results. There are several things to unpack in our informal research question; we start with social welfare. We assume that each individual is identified by their feature values (e.g., state = Massachusetts), and that each alternative is associated with benefits for each feature value (e.g., resident of Massachusetts would derive benefit 0.2). The utilitty of an individual for an alternative is simply these benefits summed over the individual's 's feature values. A social welfare function maps these individual utilities to an aggregate measure of welfare; for example, utilitarian social welfare returns the sum of individual utilities. We focus on the well-established class of power mean functions [6, 20], which is parameterized by p E [-00, 1]. The class includes utilitarian social welfare (p = 1), as well as other prominent social welfare functions such as egalitarian and Nash.
The more subtle definition is that of descriptive representation. Ideally, one would want every inter- section of features to be proportionally represented on the panel. In practice, citizens' assemblies ask for what we call I-representation: The proportion of each feature value the panel (approximately) matches the population. One of our main insights is to extend this requirement to m-represennatton, which requires that each intersection of up to features be proportionally represented on the panel.
With this terminology hand, we can refine our research question:
How well does the p-mean welfare of a m-representaaive panel estimate the p-mean welfare of the underlying population, for different values of p and m.?
The reader may have noticed ostensible gap between the earlier goal of making good decisions and the current goal of accurately estimating welfare; as we show, the latter goal implies the former in our model. But if our goal is simply to estimate welfare, why do we even need deliberative process serees--ann can we not just poll the population? The answer is that we view the utilities of individuals in the population the utilities they would have under the same conditions as a citizens' assembly, after being informed about the topic and engaging in a deliberative process. These utilities are unknowable, of course, and indeed our guarantees do not require access to them.
In Section 3, we investigate the relation between the status quo of 1 1-representation and social welfare. Our first technical observation is that for utilitarian social welfare (p 1). if panel is I-representative, its (mean) social welfare for any alternative is equal to the (mean of the) population's 's social welfare for the same alternative. Therefore, 1-representative panel that seeks maximize utilitarian social welfare will select an alternative that is optimal for the population (by the same measure). However, for p < alternatives such that no 1-representative panel chooses the alternative that maximizes the p-mean welfare of the population. In Theorem we determine the worst-case accuracy that is, the worst- case difference between the p-mean welfare of the panel estimate and the p-mean welfare of the underlying population of 1-representative panels.
prove that this is not the case: there populations and sets of
In Section 4 we proceed to study 2- 2-representative panels. In Theorem 9, we prove that 2-representation allows for significantly better worst-case guarantees for accuracy, compared to 1 I-representation. Our proof crucially relies on the fact that finding the minimum/maximun welfare a m-representative panel can have for alternative (the difference between this maximum and minimum is the object we want to bound) boils down to solving a momeni problem [22]. To get explicit bounds, we leverage the fact that extreme points of our moment problem are probability measures (corresponding to populations) supported on a discrete set of size at most 3 [17], for the case of 2-representative panels.
Finally, in Section 5 experimentally show that it is possible to select 2-representative panels in real-world instances. We analyze data from four different citizens' assemblies: one from a Western European country and three from Australian states. Our experiments show that (approximate) 2- representative panels exist with the current panel sizes for two of the datasets, and would exist by picking slightly smaller panel for third dataset. In the final dataset, (approximate) 2-representation is infeasible; we attribute this fact to the very small and skewed pool of volunteers.
Combined, our theoretical and experimental results provide clear, prescriptive message: It is practical to select panels that are 2-representative and, by doing so, the quality of the decision the panel makes (as measured by its p-mean welfare for the entire population) significantly increases.

---

Related work. There is fast- -rrwiigoingg body of work on algorithms for selecting and facilitating citizens' assemblies. The majority of papers develop and analyze algorithms for computing lotteries over assemblies [9, 10, 11, 12, 2, 14], while others focus on supporting deliberation [3, 4]. Our work is closer spirit to papers that consider the connections and tradeoffs between representation and fairness [3, 7]: by contrast, we investigate the relation between representation and welfare (and discuss the addition of fairness in Section 6).
In terms of impact on AI, some of the most prominent technology companies have been experimenting with citizens' assemblies as a tool for Al governance. In particular, Meta has organized a sarge-scale deliberation on Al policy [5]. Google DeepMind has explored related ideas and their researchers have published prominent work on the use of large language models for mediating deliberation in citizens' assemblies [24].
2
Preliminaries
We consider the problem of a population of individuals selecting a representative panel to make decision on its behalf. Every individual is represented using a set F of features (e.g., gender, age, geographical region, and so on), where each feature f E F can take d different values; denote by Vy. Vi5l = dy. the set of values that feature f E F can take. Every individual is represented by a rype y. assignment of values the features in F. For any f E F, let y(ʃ; , v) be the indicator function for having value v for feature f. That is, y(f, v) = if and only if the type y has value u for feature distinct if there exists least feature f for which
f. else y(f, v) = O. We say that two types they have a different value. We write y = (y(S, v)) E {], where d = E)Er to represent the vector containing v(f, v) for all e E Vy f
13
A population P {1)1)1),,..... ....
(UT, } is set of T distinct types of individuals I = {UI,.... yr where individuals of type y; make up a fraction qi E (0, 1] of the population. We call qi the population share of type y;- It holds that D 4i = 1. We denote by n the total number of individuals in the population. Thus, q; n E N for all i [2].
Example 1. Consider a situation where F = fage, gender). with Vage = {15-29, (0+) and "gender {Male, Female, Non- Non-binary). Therefore, dage 2 and dgender 3. Consider an indi- vidual who is 30+ and Male. Their type. V1. is such that, for example, y/1 (age, 30+) = and y1 (gender, Non-binary) value for the first feature and the first value for the second feature. Finally, consider a population P {yn 0.4), (12, 0.4), (ys, 0.2)}, meaning that 40% of the population has type y1, 40% has type 12. and 20% has type y/-
O. The corresponding vector is yı (0, 1; 1,110.0.. 0, 0): they have the second
Panels and representation. A panel C - ((,,rr), (UT, rT]} in population P specifies, for each type Vi E I, its fraction r; E [0, 1] in the panel. It holds that Σ Dim1 T; = 1. We denote by k the total number of individuals in panel (thus, r; k E N for all i). We assume that the panel is a subset of the population P, and therefore ri k S qi n for all i [T].
We are interested in panels that are representative of the population. A panel C in a population P 1-representative if for every feature f E F, and every value v E V/, the fraction of individuals in C with value v is equal to the fraction in P. That is, for all f E and v e Vy
Σ En
Σ rin(ffv). N.
Σ Ey.ez r.yi. This is essentially equivalent, up to weakening the equality constraint allow for small deviations, to the notion of representation considered in prior work on panel selection.
or, more concisely, E EZ d:yi
More generally, define m-representative panel follows:
Definition 2. For any m E (1,... {F)), we say that panel a population m-representattiv if for every set of l < m features F C F, |F = l and every possible é-tuple of values (uy)seF X5FF Vy, the fraction of individuals in C with values y is equal to the fraction in P. That is, for all such F and (Vy)SEF,
Σ a II EE
(lf.vv))= = Σ II v((.vy).
JEF
V'EI
FEF
3

---

Note that EEF (y( = 1 if and only if type has value by for all f E F.
Alternatives and utility. Panels are asked to decide on an alternative, from a given set of alternatives
A. For alternative a E A and feature F, let a(f, R2o be the benefit that an individual with value for feature f gets from a. We define a = (a(f, u) v)V,,, analogously to y.
We assume that the utility of an individual for an alternative is the sum of all these feature benefits, ie., the utility of an individual of type Ye E I for alternative a is
(aaa) y
Σ Σ SEFUEV,
Without loss of generality, assume throughout the paper that utilities non-negative and that the utility of every individual for every alternative is at most 1. For a given set of alternatives A and population P. we define Umin miny, ET minae A ua(a) to be the minimum utility of any individual in the population for any alternative in A. We have that Umin E [0,
Example (Example continued). Consider a set of alternatives A {ai,a2), where 0.5, (gender, Male)
0.3. an (gender, Female) = 0.5, a Igender, Non-binary) = O, a2 az(age, 15-29) = 0.7, 02(age,,00) 30.00+ = 0.3, az(gender, Male) =
a (age, 15-29) 0, (age,30+)
02 ggender, Female) = 0, and ag(gender, Non-binary) = 0.3. In short, a1 = (0, 0.5; 0.3, 0.5, 0) and ag = (0.7, 0.3, 0, 0, 0.3).
Then, since y1 has values 30+ and Male, we have that
u1 (01) Y1 a1 = 01 (age, + a1 (gender,, Male) 0.5 + 0.3 0.8, while un (a2) = 0.3 0 = 0.3. Assume that y2, Va are such that also u2(a1). uz uz(2)), ua ua(a)), ug(a2) 2 0.3; therefore, Umin = 0.3.
Panel and population welfare. We assume that the welfare of a population P for an alternative a is
the p-mean of individuals' utilities, for some p E I., S 1. That is, up, = EE yi EI ( For p 1 this is the standard arithmetic mean (up,1 utilitarian social welfare, for p it becomes the geometric mean (up,o(a) = II ()( (), cor- responding to Nash social welfare, and as p approaches oo it becomes the minimum (up,-on (a) ming.ez 44 (a)). corresponding to egalitarian social welfare. Analogously, we define the utility of a panel C for an alternative a, uCC.p. be the p-mean of the utilities of the individuals in the panel.
Enez (a,;(a)). corresponding to
Objectives. There are several natural ways to measure whether panel makes good decisions, in the sense of representing the opinion of the population well. A natural choice, for example, would be to ask that the social welfare of the panel is an accurate estimate of the social welfare of the population, for every alternative; then, naturally, optimizing for the panel approximately optimizes for the population. Another choice would be to ask that the panel orders alternatives in a similar way as the population would, i.e., the panel prefers an alternative over an alternative a', the population cannot have high welfare for a' and a low welfare for a.
Formally, given e O, we can define the two notions follows.
Welfare based: We say that panel C is e-accurate with respect p for welfare estimation if (a) up (a)) & e for all a A.
Pairwise comparisons: We say C is e-accurate with respect to p for pairwise comparisons (a) > (c') implies that (p) 2 (a') E for all a' e A.
These two metrics are closely related: the former implies the latter.
Theorem 4. Let A be set of alternatives, and let C be panel in population P. Then, for all E 2 and p < 1, we have that if C is s-accurate with respect to p for welfare estimation, it is 28-accurate with respect to p for pairwise comparisons.
The other direction approximately holds as well. If panel is not e-representative for welfare estimation for set of alternatives A, then not e-representative for pairwise comparisons on A U {a} for additional alternative a.

---

Theorem 5. Let A be set of alternatives, and let C be a panel in population P. Then, for all E 2 0 and p S 1, we have that if C is not E-accurate with respect to p and A welfare estimation, there exists an alternative o' such that C is not e-accurate with respect to and A U {al) for pairwise comparisons. Furthermore, adding a' to does not change Umin-
In light of the tight connection between the two notions implied by Theorems 4 and 5 (whose proofs are deferred to Appendix A.I), in the remainder of the paper, we focus on accuracy with respect to welfare estimation. We therefore refer to panel that is e-accurate for welfare estimation simply as e-accurate.
Representation to Single Features
In this section, prove tight upper and lower bounds the worst-case accuracy of 1-representative panels, for different values of p.
We start by proving that, for 1, a 1-representative panel always has the same utility as the population for every alternative (i.e., it is s-aceurate for =0).
Theorem 6. Let A be set of alternatives, P be population and C be a 1-representative panel in P. Then, for all a E A, uc,1 up, (a). That is, is O-accurate with respect to -.
Proof. For p 1, the welfare of the panel and population is a weighted sum of the utilities of the corresponding individuals. And, an individual's utility is the sum of the alternative's benefit a af,, v) for their feature values E Vy, f E F. By switching the order of summation, we have
ne,1 (a) =E (ru((a)= Σ ri(a y:)
Σ r.y 2:
Σ P.Y
Mi NE
where the last equality follows from the fact that the panel is 1-representative. Continuing our derivation,
(a) - Σ
9:91 Σ
qqu((a) (p))
BIEZ
BIEI
and the theorem follows.
Unfortunately, Theorem 6 does not hold for < 1. When p < 1, the population and panel welfare functions become non-linear in a, and therefore we cannot factor out a like we did in the proof of Theorem 6. In fact, as we show next, for any p < 1, it is possible that, in the worst case, all 1-representative panels (other than the entire population) perform poorly at welfare estimation for some alternative, and choose alternatives that are suboptimal for the population.
Example 7. In this example we will show that for all umin E [0, 1). there exists population P and set of alternatives A, such that ming,ez min (a) Umin and such that for p 1, no 1-representative panel chooses the alternative that maximizes the p-mean welfare P.
Assume that there are two features, fo and fwr that take values U1, U2 and W1, wy respec- tively. Thus, there are four possible types of individuals, represented in the left part of Ta- ble 1. Let P be the population where each type is present in exactly one individual. There- fore, the only two 1-representative panels are C1 = ((11,0;1,0), 1/2), ((0, 1;0, 1), 1/23 and C2 {((0, 1,0), 1/2), ((1, 0; 1), 1/2)).
Consider the following set of 3 alternatives: A= {ai, a2, az}, where aj (umtn /2, 1/2, 1/2, Smmn a2 (Monin/2. /2, 1/2, 2min/2, /2, 1/2), and ag (L+3umm))/s. 4m-mm,, (1+3umm)) 1/s, (1+3emin)/)) The util- ity of each type for each alternative are shown in Table 1.
For any p < 1. we can see that the first panel, C1, gets the highest utility from 01, while the second panel, C2. gets the highest utility from ag since the p-mean of x and (1 umunn - x for p is = (1+Wma)/2. However, overall, the population
uniquely maximized when = (1 + umin) gets the highest utility from alternative 0z. This fact is algebraically tedious to verify; we defer the calculations to Appendix A.2.
The main point of Example that any 1-representative panel in P, C1 or C2, overestimates the welfare of some alternative, a₁ 02, respectively, quite badly. For example, for umin = 0 and any
5

---

Table 1: The population and alternatives in Example
types
alternatives & utilities
panels
values
y
a1
a2
ag
Vi, Wi
(1,0;1,0)
(1+Mimin)) 1/2
Umin 1
33mmn (3+ 3+mam))
V2, W2
(0,1:0,1)
(1+Mmm 1/2
C2
U1, W2
(1,0;0,1)
Umin
(1+umio)/2 (1+0min)
(1 (433mii// 1/4
222 W1
(0,1;1,0)
(3+
S O, both and 02 have welfare of 0 with respect to P. but a welfare of 1/2 for the panel that chooses them. However, alternative 03 gives the highest welfare to the population (for umin 0 and p S the population's utility number between 1/4 and /3/4 4 0.43).
We now state the main theorem of this section, giving tight bound on the worst-case e-accuracy of a 1 1-representative panel.
Theorem Let A be a set of alternatives, P be any population, and be any L-representative panel 1). Then, for all p 1. C is E-accurate with respect to p. where
in P, so that Umin
P
p.
1-umin
uminn
Mmiin "Mmin" 1-mmm
for p OV (p < A Umin 0)
1
In (1/Mmin)
-mmin
In
[n (1/Maaa))))
1- Mmnin
-1)
for = 0.A Umin >
for p S 0A Umin
Furthermore, for all p < and Umin E [0, 1), for any ex < there exists a 1-representative panel such that C is not e' -accurate with respect p.
The proof of Theorem is deferred Appendices A.3.3 and A.4.1. The first part of the theorem (the upper bounds on E) follows as special case of the analysis of the m-representativv case in Appendix A.3 that also gives the main results of the following section for 2-representative panels.
4 Representation to Tuples of Features
In this section, we prove bounds on the accuracy of m-reppresentative panels. We start by showing that 2-representation enables significantly better worst-case e-accuracy compared to 1-representation. Theorem Let be a set of alternatives, be any population, and be any 2-representative panel in P, so that umin E [0, 1). Then, for all < 1, C is E-accurate with respect to p. where
8 maxx1.82
K2- No 21 22-2x++I
(1-R1)²
Ni T-Ki
(rg - M )2
Kg Umints1 Ri umin
K2 24min 6i t Uminn Umin"
Kg 24min Ki + amin?
s.l. Umin
< x27 < R2
and
82 ummnn Memii
< Ki 1,
for > OV (p < 0 Umiin 0),
(1=11 15--1177
E max
Ki Ki-Ki I-Ñ1
12 2umin Momtn
(Umin)
2smin
Munin
Ri - Hemin
s.t. Umin
K2 < K2
and
Ki <1
14
for p = 0/A Umin > 0, and
E = 1 S 0 Umin Furthermore, for p < and Unin E [0, 1), for any e' < e, there exists a 2-representative panel such that C is not e' -accurate with respect p.

---

The optimization program in Theorem 9 has two variables, K1 and Kg. We call those the moments:
Definition 10. For i O.... [FI, the i-th moment of population P for an alternative a is K₁ Eneer 90" (uy(a))) The i-th moment of a panel C for an alternative a is K; = Ew, Ex, ry (uz(a))
Our proof of e-aceuracy has the following high-level steps. First, we prove that the first m moments of m-representative panel C in P are the same the moments of P for any alternative. That is, for all a E A and any integer S L < m. Ey.er 9:- (u;(a))( Ey.ez Ti (uz(a))
Second, given this fact, we can write mathematical program for the minimum and maximum utility a panel or population with fixed first m moments Ki....r Km (note that always Ko = 1) can have. Concretely, by having a variable 2, for the utility of a type yJ E I. given m moments, we can ensure feasibility by asking that Eg, Qj (xz)) Kig, for all i {0, 1, .., m] (and xy E [Mminn 11, 4 2 0). Then, by maximizing and minimizing (En 43 (xr) //pp/ we get bounds on the welfare of a panel or population with moments Ho,,-... Kin-
Third, the relaxation of this program to also allow I of infinite size is known as a moment problem [22, 21J. hence our choice of terminology in Definition 10. In particular, the population is characterized as a probability measure (distribution) μ on [umin; 1] where μ((x)) corresponds to the share of individuals with utility z. The feasibility constraints become St p(z)- x² dr = N; for all i E {0, I,..., m].
determining the first m moments of μr, and we maximize and minimize (f x² =²du((x))//p
is known that the extreme points of moment problems are probability measures supported on a discrete set of size at most + [17]. This additional structure allows for explicit bounds the maximum and minimum utility of a panel/population as a function of f1 ki,..., ; Kim. which we obtain for = 2. The difference of these quantities is our bound on the e-accuracy of 2-representative panel. We obtain worst-case bounds on 6, as we prove, by maximizing this difference over the set of all K2 and K2 that can be the first two moments of a population P for an alternative a A.
We defer the details of the e-aceuracy proof to Appendix A.3. In Appendix A.4.2, we then prove the second part of Theorem 9: The bounds obtained with the proof technique described above are tight.
For greater m, solving the relaxed optimization program analytically to obtain explicit bounds on the maximum and minimum utiliity of panel/population as a function of Ki,..., Kim becomes increasingly difficult. And, even if such bounds were obtained for m > 2, the overall bound on e in the style of Theorem 9 would be an even less tractable optimization program in m variables; it is unclear if its value could even be numerically calculated.
In fact, we believe that already the solution to the optimization program in Theorem 9 does not admit closed-form solution in terms of p and umin- However, for a fixed p and Umin we can numerically solve this optimization program. We plot these results in Figure 1. In particular, Figure la shows the tight worst-case e-accuracy of 1-representative panels as dashed lines and the upper bound on worst-case E-accuracy of 2- 2-representative panels as solid lines, for 4 different values of Umin. with varying along the horizontal axis. We find that 2-representative panels are a-accurate in the worst case for significantly smaller e. For example, for Umin 1/5 and Nash welfare (p 0), 2-representation gives 0.039 accuracy, while 1-representation only gives 0.155 accuracy. Figure 1b shows the ratio of these bounds: the worst-case for 1 1-representative panels divided by the bound on the worst-case e for 2-representative panels, for different values of p. with umin varying along the horizontal axis. We can see that the relative accuracy increases quite drastically, especially when p is not far into the negatives and Umin is far enough away from O. utilities are generally high, this ratio is the largest: for Umin 4/5 (corresponding, after scaling, to utilities in [8, 10) and Nash welfare, accuracy increases by 2700% for 2- 2-representative panels over 1-representative panels.
Given the positive result in Theorem 9, we turn our attention to the only case in which 2-representative panels don't improve on 1-representative panels: the case p S and umin = O, we proved that and 2-representative panels are no better than 1-accurate in the worst case. It is natural to ask if we can do better with m-representattvv panels for larger m.
The answer is negative. One could imagine a very popular alternative with utility close to 1 for everyone but single person y², who has utility 0. The population's utility (for p S 0) for this alternative is 0, but any panel that does not include y² has utility close to for this alternative (and therefore chooses it). We formalize this idea in Theorem 11.
7

---

10
Maat
relatite improveeent
e-acearscy bound
Drate
06
02
0.
Mamin
(a) Worst-case a-ccuurayy of me-representative panels for m E {1, Figure I: Numerical comparisons of e-accuracy bounds for E {1,
(b) Relative improvement of e-accuracy from to m i.e. (e-ac. at m ()/(s-ac. 2).
Theorem 11. For any positive integer m and number of features |F], there exists a population P and a set of alternatives A, such that ming.ez minae Uz(a) = Mmnin 0, and m-representative panel in P, such that C is not E-accurate with respect to any p S 0 for any 1-
FF
As | becomes large, this lower bound goes to 1, for any fixed m. Since uc.p(a). ( E [0 for all A, is also trivial upper bound. We prove Theorem 11 in Appendix A.5.
5 Empirical Analysis
We have shown that 2-representative panels give significantly better worst-case guarantees than 1 1-representative panels. However, this result only has practical impact if it is possible select 2-representative panels in real-world instances. Our next goal is to show that this is indeed the case.
Selecting panel. Selecting citizens' assembly in practice commonly has three stages. First, large number of individuals receive an invitation to participate in the panel. Second, some fraction of these individuals indicate their willingness to participate. We call this group the pool of volunteers. Finally, a panel of the desired size is chosen from the pool volunteers.
It is common occurrence in practice that individuals with certain features more likely to accept the invitation to participate than others. Therefore, the composition of the pool of volunteers often is fairly different from the underlying population. If the size of the pool is too small, it may not be possible to select a panel desired size that 2- 2-representative (or even 1-representative).
Data. We analyze data from four citizens' assemblies: nationwide panel from a Western European country (which we denote 1UR and three state-wide panels from Australian states (which we denote AUS1, Aus2, and AUs3). Detailed information about the datasets can be found in Appendix A.6. All actual panels were chosen to be approximately 1-representative of the underlying population.
For all four panels, we obtained data the intersections between feature-values of the underlying population. For EUR1, we used the European Social Survey [19], which collected data on wide variety of features and their intersections, including those used in EUR1. Responses are re-weighted the data to account for sampling bias. For AUSI, Aus2, and AUS3, we used data from the 2021 Australian Census [1]. Through their online data tools, we obtained data on the intersections of individuals" features. We excluded feature capturing the level of climate concern from EUR since the number of volunteers with no concern at all was too low to even form a 1-representative panel of the desired size. In AUSI and AUS2, we had to exclude a feature capturing an individual's ownership weren 't
of their residence since these statistics are stored in separate dataset dwellings, able to obtain this feature's 's intersection with other features. For more details on the datasets and data cleaning, again refer to Appendix A.6.
m-representation in practice. Exact 1-representation or m-rrepresentation for any m (essentially) never attainable for a fixed desired panel size k. the desired number of individuals with a certain

---

EUR
AuS1
maximum panel size k
pool size: 1715
maximum panel size k
pool size: 1070
1350
150
300
desired panel
200
250
size: 110
desired panel size: 50
representation level m
representation level m
AUS2
AUs3
maximum panel size k
pool size: 1145
pool size: 509
maximum panel size
170
100
830
630
desired panel
desired panel size: 328
size: 45
40
representation level m
representation level m
Figure 2: The maximum size of m-representative panels up to rounding for [IFI], shown in teal. The dashed lines show the size of the pool of volunteers and the panel size used in practice.
tuple of feature-values, in the panel will almost never be an integer. We consider two weakenings of m-representation for practice: panel is m-representatiin up to rounding if for any f-tuple of feature-values, f E [m.) the number of people with these feature-values on the panel is equal to the (rational) desired number, up to rounding it up or down. A panel e-approximately m-representative if for any Êttulee of feature-values, E [m]] the number of people with these feature-values on the panel within a multiplicative factor of (1 + 8) of the desired number. Since the quotas from the underlying populations are only ever estimates with some error, these small "wiggle rooms" around quotas are justified.
Experiments. For each m between 1 and the number of features considered in the panel, [F), we found the largest size of an m-representattiv panel up to rounding using individuals from the pool of volunteers. Furthermore, we found for each m between 1 and [J] and panel size & between and pool size the smallest for which an e-approximately m-representative panel exists. For given and desired panel size k we checked for the existence of an m mrrrprresentatie panel of size using an integer linear program. Each person in the pool of volunteers corresponds to one binary variable, encoding whether this person in the panel or not. The constraints on the variables are the size of the panel, k. and having be m-representattiv (up rounding e-approximately) to the underlying population data. We used Gurobi, run on a 14-inch MacBook Pro (2023) with Apple M3 Pro chip, to check whether the program is feasible, i.e., whether m-representatiie panel exists.
Results. Our results for merrppresentation up rounding shown in Section 5. The main takeaway that 2-representation up to rounding generally feasible in practice.
In the EUR1 and Aus1 datasets, the bottom dashed lines tines-showig showing the maximum size of an m- representative panel- lie above the "desired panel size" used in practice. For AUS2, the largest 2-representative panel is of size 278 slightly below the desired panel size of 328. Since the number 328 does not have special significance,' our results suggest that slightly contracting the panel in order to boost its degree of representation would be good tradeoff. By contrast, in AUs3, the
It likely started out "round" number and decreased when selected panelists dropped out.

---

EURI
AusI
minmmm approx error E
1.0
desired panel size
10
desired panel size
minimum approx. error
04
64
02
panel size k
panel size k
Figure 3: The smallest e for which e-approximate m m--rppresentative panels exist as a function of the panel size k for selected m E [[F]]. The dashed lines show the desired panel sizes.
largest 2-representative panel is of size 31, which is 69% of the desired panel size of 45, The pool of volunteers for AUS3 only contains 509 individuals- sestualll-sghnnee -ignificantly fewer than the other assemblies, which all have more than 1000 volunteers. We conclude that an investment in the recruitment of volunteers may make greater degree of representation possible.
Our results for e-approximate m-representation give more nuanced insights on the tradeoff between accurate representation and panel size. The results for EUR I and AUS I are shown in Figure 3; the plots for the other instances can be found in Appendix A.6.4. First, we note that s-approximate is not possible if the total number of possible m-tuples of feature-values
m-representation for in the population is greater than k, or feature-value m-tuple exists in the population but does not exist in the pool of volunteers, since in either case for some feature-value m-tuple the number of individuals on the panel is 0 while the quota is greater than O. This is the case for m 2 2 in EURI and Aus3. In all other instances, we find that the best achievable decreases with the panel size (approximately inversely linearly) for panel sizes less than a critical size k"; this is the panel size which the pool is "too skewed" since for some feature-value m-tuple the quota is higher than the number of candidates in the pool with this feature-value m-tuple. For panels larger than this size k", e increases with the panel size (approximately proportional to 1 -- This critical size is the largest panel size up to which adding people to the panel comes with improved E-approximate m-representation guarantees, and is slightly below the maximum size of an m-rrepessentative panel up to rounding in all instances where e < 1 is possible. We conjecture that aiming for mix of the two definitions of approximate m-representation will do best in practice.
6 Discussion
We conclude by discussing two points that may contribute to a fuller understanding of our approach
and its limitations.
Throwing fairness into the mix. As mentioned in Section 1, citizens' assemblies are randomly selected. In practice, this is done by computing a lottery such that each panel in its support is I-representative. A commonly used algorithm optimizes the lottery to maximize a fairness objective: the minimum probability of selecting any volunteer [10]. The same algorithm can be directly applied when the underlying notion of representation is m-representation for m > instead of m = 1. However, this may come at a cost to the fairness objective, because the feasible set shrinks as the constraints become stronger. While we focused on the relation between representation and welfare, future work could explore the tradeoff's between representation, welfare and fairness.
Empirically estimating welfare gains? The reader may have noticed that, despite access to real data from citizens' assemblies, our empirical analysis does not evaluate our main theoretical claim: greater degree of representation contributes to social welfare. The reason is that we do not have access to real utilities, and synthetic methods for generating them may seem contrived. Let us reiterate, however, that the lack of access to utilities is not a barrier to applying our results, as we argue for a greater degree of representation with respect known features, which leads to improved social welfare with respect unknown utilities.
10

---

Acknowledgments
We would like to express our gratitude to Bailey Flanigan for her invaluable assistance in obtaining the datasets on the pools of volunteers in the four citizens' assemblies we analyze, by suggesting for which citizens' assemblies sufficient data on the underlying population is available, contacting the organizers of the citizens' assemblies for permission to use their data, and sharing the datasets with us. We also thank her for providing the dataset on the underlying population data for the European citizens' assembly. We furthermore thank the organizers of the citizens' assemblies for granting us permission to use their data.
Alexandros Psomas is supported in part by an NSF CAREER award CCF-2144208, and a research award from the Herbert Simon Family Foundation.
References
[1] Australian Bureau of Statistics. 2021 census -actural diversity, 2021.
[2] C. Baharav and B. Flanigan. Fair, manipulation-robus. and transparent sortition. In Proceedings of the 25th ACM Conference Economics and Computation (EC), pages 756-775, 2024.
[3] J. Barrett, Y. Gal, P. Gölz, R. Hong, and A. D. Procaccia. Now we're re talking: Better deliberation groups through submodular optimization. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pages 5490-5498, 2023.
[4] J. Barrett, P. C. Verpoort, and K. Gal. A new heuristic algorithm for balanced deliberation groups. arXiv:241022145) 2024.
[5] N. Clegg. Bringing people together to inform mecision-making on generative Al. Blog post, 2023, URL /ttt:p:://bbuute fb. cww wwwmm//ww///22/////mmm http:///////geeaatiieeeeeeeeeeee cemprrttivee----commutt-tt-oooo communtyy-ootourrmnrnm
[6] C. Cousins. An axiomatic theory of provably-fair welfare-centric machine learning. In Pro- ceedings of the 35th Annual Conference on Neural Information Processing Systems (NeurIPS), pages 16610-16621, 2021.
[7] S. Ebadian and E. Micha. Boosting sortition via proportional representation. arXiv:2406.00913, 2024.
[8] Fishkin. Democrucy When the People Are Thinking: Revitalizing Our Politics Through Public Deliberation. Oxford University Press, 2018.
[9] B. Flanigan, P. Gölz, A. Gupta, and A. D. Procaccia. Neutralizing self-selection bias in sampling for sortition. In Proceedings of the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
[10] B. Flanigan, P. Gölz, A. Gupta, B. Hennig, and A. D. Procaccia. Fair algorithms for selecting citizens' assemblies. Nature, 596:548-552, 2021.
[11] B. Flanigan, G. Kehne, and A. D. Procaccia. Fair sortition made transparent. In Proceedings of the 35th Annual Conference on Neural Information Processing Systems (NeurIPS), pages 25720-25731, 2021.
[12] B. Flanigan, J. Liang, A. D. Procaccia, and S. Wang. Manipulation-robus.. selection of citizens' assemblies. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 9696-9700 9096-9703,2000 2024.
[13] D. Grinberg. Notes on the combinatorial fundamentals of algebra, 2022.
[14] D. Halper, A. D. Procaccia, E. Shapiro, and Talmon. Federated assemblies. Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), pages 13897-13904, 2025.
[15) M. Hayes and M. V. Hibbing. The symbolic benefits of descriptive and substantive representation. Political Behavior, 39:31-50, 2017.
[16] D. Jacobs and W. Kauffman. The right kind of participation? The effect of a deliberative mini-public on the perceived legitimacy of public decision-making. Public Management Review, 23:91-111, 2021.
[17] A. Karr. Extreme points of certain sets of probability measures, with applications. Mathemat- ics of Operations Research, 8(1::74-85, 1983.

---

[18] H. Landemore. Open Democracy: Reinventing Popular Rule for the Twenty- Fiist Century. Princeton University Press, 2020.
[19] Norwegian Agency for Shared Services in Education and Research. European Social Survey round data, 2016.
[20] K. S. Pardeshi, I. Shapira, A. D. Procaccia, and A. Singh. Learning social welfare functions. In Proceedings of the 38th Annual Conference Neural Information Processing Systems (NeurIPS), 2024.
[21] K. Schmüdgen. The Moment Problem. Springer, 2017.
[22] T.-J Stieltjes. Recherches les fractions continues. Annales de la Faculté des Sciences de Toulouse pour les Sciences Mathmmtiques et les Sciences Physiques, Série 1, 8(4):J1-J122 1894.
[23] P. Stone. The Luck of the Draw: The Role of Lotteries in Deciston Making. Oxford University Press, 2011.
[24] M. H. Tessler, M. A. Bakker, D. Jarrett, H. Shehan, M. J. Chadwick, R. Koster, G. Evans, I.. Campbell-Gillingann, T. Collins, D. C. Parkes, M. Botvinick, and C. Summerfield, Al can help humans find common ground in democratic deliberation. Science, 386(6719), 2024.
[25] D. Van Reybrouck. Against Elections: The Case for Democracy. Random House, 2016.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The technical sections of the paper (and supplementary material) include all the proofs and code for all claims and statements made in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have proved our theorems only for the model described in Section 2, under the specific conditions their statements. The experiments were conducted described in Section and corresponding appendices (e.g., we ran experiments only on the four datasets we cite).
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
13

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Section contains our model, and the statements of all our theorems/lemmas include exactly the conditions needed.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The code used to obtain our experimental results is straightforward and described in Section 5, in the paragraph titled Experiments. Anyone with access to a dataset citizens' assembly and the aggregate underlying population data (which is publicly available for the datasets we use) can reproduce our experimental results.
Justification:
of the pool of candidates
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
14

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: We do not release the datasets of the pool of candidates, containing individual- level data, for the four assemblies we analyze because we do not have permission do so from the data owners (however, we did, of course, obtain permission to use the data for our experiments). We do release our code since it very straightforward, cleaning data as described in Appendix A.6 and solving linear program using external software as described in Section 5. The datasets for the underlying population that we used are publicly available, see [19, 1].
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.o
cwmmiisssssooiyyyoooooooo for more details. public/ gewidee/ooeeeuuiieeeeeeeeeeeeeee
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cc/ wwtppcccccc///cccccccccccc.cclll httpa//ggiiieee/eeeuuubiiieeeeee //o///oooeeSeeeeeeeeeeeeeee wwriissssiiniiyynyo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
All relevant details of our experimental setup described in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
15

---

Answer: [NA]
Justification: In our experiments, we analyze four past instances of citizens' assemblies. While our positive results on the existence of 2-representative panels are a signal that such panels may exist in other real-world instances, no statistical claim of generalization can be made (nor is made).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: In Section 5, in the paragraph titled Experiments, we describe the computer used to rum our experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http///eurrpp..peee cct.cccc///// cc/ppblic////eceeccecccccccccllt httpppulllttiieeeeeeeeeepee cscuieeeeleleeeeeee
Answer: [Yes]
Justification:
We have reviewed the guidelines and our work follows them.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
16

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes].
Justification: We discuss the potential for positive societal impact in Section and Section 6. Negative societal impacts are implausible.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Our experiments do not pose such threats, since they only involve (simple) calculations.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
17

---

Answer: [Yes]
Justification:
The datasets for the underlying population that we used can be found here:
[19, lJ.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
18

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The paper does not involve LLMs as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non non-standard components.
Please refer to our LLM policy fnttps:// http///eesppp.eeeeee cc/Confferences/2225 for what should or should not be described.
19

---

A Technical Appendices and Supplementary Material
A.1 Proofs missing from Section 2
Proof of Theorem 4. Let a, d' E A be any two alternatives such that uc.p(a) > uc,((a)). Since the panel is e-accurate for welfare estimation, we have that
(P 2 (C.p(a)
ue.p(a') - E 2 up,p(d') 28,
which implies that C is 2e-accurate for pairwise comparisons.
Proof of Theorem 5. Since C' is not e-accurate, with respect to p and A, for welfare estimation, there exists an alternative a E A such that (uc.p(a) p()) > Let 8 > 0 be any real number such that 8 < |uc,p(a) up,r(a)] -E.
If (c. > (a), consider an alternative a' such that v) = (ap + E + 8) for all f E F. Vy. Then, uy(a') (P + E + 8 for all y E I. and therefore also (P'p(aa) = uc,p(a')
p(a) + + ô (where we used the fact that, if all individuals have the same utility x for an alternative, the p-mean of their utilities is also I). We have that (c, > (a) + E 0 = (a') but (p,) < up + 8 = (p')
E, which contradicts the fact that C is s-accurate for pairwise comparisons. Similarly, u..p(a) < (u),p(a), consider an alternative d' such that a' d'(f. v) = (up.p(a) E 6)/(F1 for all f F. V,- Then, "yyaa) = up x (a)) - E - 8 for all y E I, and therefore (a') = (c,) = (() - - 8. We have that (a) (a) E 5 uc.p(a') but up,, - (p)
8 = up (a)),)))
contradiction to being eaaccurate for pairwise comparisons.
Lastly, we note that the alternatives a' defined above don't make any individual's 's utility be more than 1 or less then Umin- We know that (a.,(a),, (p) E [umin: 1). so since min (uc., (a)) up up (a)) S
Uy (a') < max(uc., (a), up (a)), we also have uy E [umins for all y E I.
A.2 Calculations for Example 7
We first prove a short technical lemma to simplify the calculations.
Lemma 12. Let < 1 and c1, C2, x E R so that 02 > 2 20ip E (0, and 02 > >0>220
i < 0. Then for p + 0,
d
(c2 + (2((0)- x)² + (c1+)pp ( x
(x)
x)))
1/8
00,
da
and equality holds only if x = 0. Furthermore, d (((e (21(c + x)
z) + +2)) s
dx
and again equality holds only if =0. O.
Proof. We'll first denote f(x) = ((c) - x)p + (cI + +x) + (02 - x)p + (c2 + x))) and consider
the case p # O. We can see that
d da =
((()
7 20((s + xz)=-1 - (c1 - -))--1 + (o2 + x) (c2 2
p
The two p's cancel. Since all of the summand in f(x) are non-negative (positive if < 0) and (c2 + x) is positive,we we have that fxx) > 0, so (f(z)) 1/p-1 > 0. It follows that the sign of _ (f())) // is the same as the sign of (c1 + x)p-1 (a - x)p-1 + (c2 + 2)p-1 - (e2 - x)p-1, Since p < 1, we
know that the function g(x) = -=11 is strictly decreasing in x. (cr + x:)= < (cz - => and
(o2 + x)p-1 < (02 z=)=' with equality only if = 0. The first part of the lemma follows.
For the second part of the lemma, we denote
f(x) = (ci - (c + x)(22 - (c2 + z)) = (c² - -+) --=xx x²)
and get that
dx 11 = 1
(f(z)) (403 -2x + &G))
20

---

All the terms in the fourth root are positive, so we have that f(x) > 0 and thus (f(z))
([(r)))///-]- 1/4-1 > 0. It
follows that the sign of dz (f))) 1/4 is the same as the sign of (4r 2x(cf c2)) If we
are done. Else, since 02 2 C1 > x > O, we have that 4x 2r(ef + +(3) < 4x 2x(x² + x²) The second part of the lemma follows.
To show that the population indeed gets the strictly highest utility from ag for any umin E [0, 1) as claimed in Example 7, we let
Mxx) ( (3((e1 - z) + (c1 + x)" + (e2 - r)P + (02 + x)))) 21(60 ((1-2) x)(c1 x)(c2 2) + =))
p 0
if p=
where 61
Ummii Note that we express the welfare of the population for the alternatives in A using
1+3umin and c
up (01) = p(2)) = h Umin
(p,)(as) = h(0).
4
By Lemma 12, we know that h is strictly decreasing on [0, ()) for S and on [0, ci] for p E (0. 1). For E (0, 1) and any Umin E [0, 1) we have that C1 2 --mmi and for S and Umin E (0, 1) we have that C₁ > 1 Vimin so we get that h00) h( ((=_"mn)) ). Thus. up (pp)) > up (p,,p up, ((2))
There remains the case umin and p S 0 that we already treat in Example 7 but repeat here for the sake of completeness. In that case, both a₁ and a2 have a welfare of for P since one individual in PP has utility 0. Alternative ag has welfare of at least 1 > 0 for P (using that the p-mean of list of numbers at least as big as the smallest number).
A.3 Upper-bounding the e-aceuracy of m-representative panels
In order prove the upper bounds in Theorems 8 and 9, first establish our general framework for bounding the E-accuracy of m-representative panels in Appendix A.3.1. We then turn to the cases m 1 and in Appendices A.3.3 and A.3.4, respectively, where analytically solve the optimization problems bounding the e-accuracy from the general framework for m-representative panel.
A.3.1 Properties of m-representative panels
We start by proving Lemma 13, a property of m-representative panels that is crucial for the proof's of Theorems 8 and? 9.
Lemma 13. Let A be a set of alternatives, be a population, and C an m-representative panel in P. Then, for any A, the first moments of C and P for are the same. That is, for any integer 1 < l m,
Σ (au((a))² =E rr(u(())) WEE
MEZ
Proof of Lemma 13. First, note that by definition a panel that is m-representative is also representative, for I m. Thus, it suffices to show that the equation in Lemma 13 holds for f. m.
The key insight is that Σn,ez 9, (a)) is polynomial in {v.(f. u) SeF, vev, of degree m. This allows use the definition of being m-representaatvv to "switch" the Øj in any term of the
21

---

polynomial to rj. Formally, we get that
ΣΣ fEF
E -
als a(f.v)u;(f:o)
di
m2 Il
Σ 4j Σ
Σ
alfe (sss
My EZ
(hwuufm) Ex
Um EVy, X...xVmm
{>> Σ
Σ (l)....em) EViL X..XV
IIIIII (f. im1
(m...f))) Ex
and analogously for the panel
m [I(fiie))
Σ Ty m MGEI
E
E
Σ
II,III,,
(ns (1)
VG
(fr.nef))) Ex
(ur...PPm) X...XVI fm
EVi,
We conclude the proof by arguing that for any fm) E fm and U1, um Vs, x ... X Vim. it holds that
ΣΦ Φ If = r I1 II (f). EI i=1
MEEI E=1
Let's first assume there exist two indices i # i' such that ft = fir but is * uy. In this case, we know both sides of Equation (I) are zero since no type Yj E I can have yj (f. n.) (f(f =1 for Us A ny (i.e., each feature takes exactly one value per type), where f = fi fi.
The case where whenever fi fp. also e; = Uy remains. We know that y; (fi, 0;) = yj (fv. Uz) E (0, 1) for all y/ E I, and thus (fi, 0;) = yo (fa, (fy, vw). Let Z = (f (f1, fm) be the
set of the unique features in (fi...., fm.) Z S We get that for any (ty)sEZ E X sez Vj, holds that
Σ I (f ET
v II (,((vf) = Σ r II
II vf(ffo))
Σ r I (f, vs),
BE
Jez
MET
JeZ
ME
=
where the second equality follows from the definition of m-representation (see Definition 2), and the fact that |Z| < m.
From Lemma 13, we have that the first m moments of an m-representativv panel C in P are the same the moments of P. Also note that the 0-th moment is always identical, Kög Σ (j 1. We'll now use moments to bound the utility an m-representative panel can have.
Lemma 14. Let Umin E [0, 1] and p < 1. Let P be a population (resp., let be a panel) with moments Ko 1, K1, ..., Kem Then for any alternative such that uz(a) E [Mmins foror all y E I, holds that
UMIN(K1, K1, .... Kmni Umin) (p)) (a) S UMAX(K1, Kmi P, Umia).
22

---

where"
UMI Smn:P P, umin)
and
UMAX(N1 .... Nim's Muuin)
are, respectively,
m
min
Σ qaas
max
Σ qiet
1=
m
m
s.1.
qerg = Kjj for all E (O...,,
8.1.
Σ qarl = Kj for all E (0,..,,))
q: 0 for all E {0, ..., mm,
9:
for all i {O, m}
32 E [umin 1] for all i E (0,..., m..
2, E [umin 1. for all { m}.
Proof. We'll prove the theorem for any population P. The proof for panel C is identical.
We know that for any population P with moments Ko, Mi,, -.: Km holds that the utility up.p(a) upper and lower bounded by maximizing and minimizing, respectively, the following optimization problem
Σの. (uy)p
max / min
Σ 9i (uj)* = K, for all i E {0, 1..,, m}
s.t.
ByEΣ
Uy [Mmin
for all y EI
since the feasible region is exactly the region of all populations with moments as given, and the utilities are allowed to take any value within [Mmin 1).
Since Ey, qj (this is enforced above by the moment constraint for i 0), we can interpret the q, and Uy in the above program as a probability measure over [umins 1), placing probability mass qj on uj. We can this observation relax the constraints of the above program by replacing the and u, with any probability measure on [umin 1]. Note that this is essentially equivalent to allowing ni the individuals in the population, go to infinity. Thus, get that up (a) is upper and lower bounded by maximizing and minimizing, respectively, the following optimization problem
(L Amin
((ddula)) du((()
max / min
[ x du(x)) Kr. for all i {0, I,.., m}
s.t.
Manin
p(x) 2
for all e [Umin 1].
Let M be the feasible region the optimization program(s) above (noting that continuous, discrete, and mixed probability measures are all in M). If we take the corresponding to some population, we see that the moments the population are identical to the moments the probability distribution M.
Problems of the above type, where a space of probability measures over bounded interval is defined by their moments, are called moment problems [22]. It is known that the space of such probability measures is convex, with the extreme points being distributions supported on a discrete set of size at most m + 1, where is the number of moments [17, Theorem 2.1 for general Umin Proposition 3.2 for umin 0].
It remains to show that the objective function of the above program takes its extreme values at the extreme points of the constraint set. To see this, let μ1, #2 E M be any two distributions, and for
"To keep the notation concise, we'll write the following proofs for a general p p-mean and don't 't explicitly state the special case 0 whenever the corresponding mathematical statements can immediately be obtained from replacing the mema with the geometric mean.
23

---

some & E [0, 11, let = tu1 + +1 t)pe E M be convex combination of Ml, /2. Then, the objective
function (i.e. p-mean) of μ
Ge Monin
(f emm
+ 11--0 [
#
zdduu)
xddu
x 112
(T Montn
$2 + (1-
xf xddp1
x²
u2
In particular, the objective function for j is the p-mean of the objective functions for joi and p2, weighted with / and respectively, and as such, always between the two.
Thus, we conclude that the above optimization program takes its maximum and minimum values at extreme points of the constraint set, which is discrete distributions with support size at most m 1. Applying this yields the optimization programs in the theorem statement.
Lemma 14 gives us upper and lower bound on the utility of a population or panel with given first m-moments. We can use Lemma 14 to prove the following lemma.
Lemma 15. Let Umin [0, 1] and 1. Let P be population and let C be m-representative panel in P. Let a be any alternative such that uy (a) E [Uminn for all yj E I. Then C is E-accurate with
E max UMAX(K1; ... Romis P, Uminn UMIN(N11 .... Kmi P. Umin)
s.t.
[K(+))1y20 1m/2 [(1 + Umin (+6+5+1 Ki-5+2 Umin Ks+sle.j=0
11/2-11
2 0
if = 0 mod 2
[K4+*+1 Umin 11 1)/2 [KSS4 Kits+1ll,
(m-1)/2 1)/2
20
if = 1 mod 2
where 11 is a d d matrix with entry Mi, at position (i.5) and M > 0 means that M is positive-senie seniiie--emidefiiitt..
Proof. Lemma 14 implies that for given sequence of moments Ki,.., Km it holds that
(c)) uP (a)) I UMAX (K1, ... Kmi P, Umin) UMIN(K1, (K1, ... Kmmi P. Umin).
Thus, C is guaranteed to be s-accurate with
UMAX(K1, Kmi P, Umin) UMIN(K1, ..., Km. P, Umin)
S.t. Ki,..., Ni are the moments of a population (or panel) and alternative, given umin We can relax the constraints on Ki, Km, similarly to the proof of Lemma 14, by only requiring 61, .., Ky to be the moments of probability measure μ on [Main 1]. Determining whether such probability measure j exists given moments and a bounded interval is known as the one-dimensional truncated moment problem on bounded interval; refer to [21] for concise and contemporary proof that the constraints in the lemma statement are necessary and sufficient for K1, Ky, to be the moments of probability measure y [Mmiu 1).
L
A.3.2 Solving for UMIN and UMAX
The optimization program in Lemma 15 is by itself not overly insightful since there are two fur- ther optimization programs nested in it, from the definitions of UMAX(K1; ..., Rum: P, Unia) and UMIN(K), .... Km P. Umin). In this section, we describe a general framework for getting closed form solutions for UMAX and UMIN, which we apply in subsequent sections for m and m 2.
We start by noting that the feasible regions of UMAX(N), ...; Kimi P, Umin) and UMIN(MI,.... ..., KmiP, P. Umin) are identical. There m + 1 moment conditions, in the form of m + 1 cquality constraints, all linear in the m + 1 q.'s W.L.o.g. we assume that wo > xi > > Zm (we don't 't need to consider equality since it is equivalent to setting qi to 0), we get that the m + 1 moment equality constraints for fixed x; linearly independent since the coefficients are x! for j = O, ..., m and the I; are distinct. We can thus solve uniquely for the to get
m
1)' Kmm Kmm-jmmpppp (x
(2)
1g xz))
1=0
24

---

where ej is the j-th elementary symmetric polynomial and 2- are all 20.
except 24
(x(x_1) = ey(2o 14 1:41: Im)
Σ
02 Ki Sm 61
Defining the qi as function of = (ID, .... Fm), we can rewrite the optimization problems with only m + +1 instead of 2m + 2 variables so that
UMIN(K61.... ..... Kmm Umin)
UMAX Fims Umin) =
m
min
Σ (<))a
max
Σ (()))
s.t.
(:(0) 2 for all i E {0...., m) 12 0o 21 > Fm 2 Umin
(( 2
for all E (0,.... m)
12 0o
2m 2 U Umin
To get an analytical solution for this optimization problem, we note that for m and m 2, the derivative of the objective with respect to each variable is either non-negative or non- con-posiieve on the entire feasible region.
Lemma 16. Let <
and Umin (0.1), or p (0, and Umin O. Let m E {1,2) and Ummin- Then for all x (Zo..... Fm) so that q3 (z) 2 0 for all
1 2 To > > ... >
j E (O...., m). holds thut
Σ En(ora
120 0 ifi =i=m m (mod 2) Iso
Oxg
if + (mod 2)
for all i = -....., m. where the are function of zo. ...,.. Im as defined in Equation (2).
We conjecture that Lemma also holds for m and can be proven almost analogously to our proof for 2. For results, only investigate I-representative and 2-representative panels and prove Lemma 16 for the respective ma the corresponding sections. then apply solve explicitly for UMIN and UMAX.
A.3.3 1-representative panels
We'll first consider the case = 1. We prove Lemma 16 for m = 1 and then use it to solve for UMIN and UMAX. By Lemma 15, the proof of the first, "upper bound", part of Theorem 8 will follow (the proof of the second, "lower bound", part can be found in Appendix A.4).
Proof of Lemma 16, m = 1. Recall that w.l.o.g. we assume in Equation (2) to get
> x1. We can solve for d as
To
11
20
30 37
We'll now first treat the case + and return to p = 0 at the end.
Let's calculate the derivatives of the objective without the outer p-th root:
Oxo 19029 + () = pzd
1-1 Ki
31
+
21
+ x
K1 21
T0
(To
)
(2o σ1 )2
K1
F1
p-1
20 xf
pao
20
To
T1
x
4n
pzd
p-1
En 31
(902g + q1
41
pzd
p-
Or,
Cu 1''
25

---

To determine the sign of the two expressions in parenthesis, we let f(z) = x² and note that df de
(1O) pad and # (z1) = paf while 2n = is the difference quotient of for [ ao].
< pat for < 0, f is convex, so z
For E (0, 1), I is concave, so we get pad par p- > oh of
za-21
20 p Since 40, 21 2 0, we get that
s 20
if = OAPE (1= <0) if ffi=lApE (0.1)) (i= 0A <0)
1 + 9 )
dz:
To finish the proof, we note that
1 (a00% ) +1
Org (o + u)a7)²
(go=) + q)
p
Oag
so p < the sign switches when considering the objective function instead of the objective function without the p-th root. This implies the lemma for p o O.
Let's now turn to the case p = We note that the sign of the objective doesn't change when taking the logarithm, so it suffices to show that
i
0 if 0
(40 log(ro)) qı log(<1))
0x.
if
Taking the derivatives, we get
1
log(#)) - log(
(go log(zo) + qı log(a1)) -Q0
Oro
TD
Zg
0
log(z0) - log(x1)
(go log(zo) + q log(xr)) q1
dm
311
20
If we let f(x) = log(x), again, the expressions in the parenthesis is the difference between the derivative of at zo and 21, respectively, minus the difference quotient of f for [21, Since is concave, the lemma for p = 0 follows.
We now apply Lemma 16 solve for UMIN and UMAX.
Lemma 17. Let < 1 and umin E 10, or E (0, 1] and Umin = Let K1 E (Umine 1). Then UMAX(11; Py Mmin) K1 and
-mmin
1-81
Ummnn"
if +
UMIN ( Umin)
Mmin
Mimin
(Umin)
Mmin
=p==0
Proof. W.L.ogg. we assume > T1. Thus, the constraints 9a 2 0 are equivalent to K1 2 I1 and To 2 K1. We solve for UMIN and UMAX by finding the minimum and maximum of their defining optimization program from Lemma 14.
Finding the maximum: By Lemma 16, we know that the objective (non-strictly) increases 2o decreases. The only lower bounds on Tp are 2n 2 K1 and 2hg >> I1, so we know there is a maximum either at zo K1 (where the first lower bound is tight) or for æ 2 Ki (the only case in which zo can't be tight to the first lower bound since zo > x1). Since I1, we know that Φ S K1, the second case becomes I1 K1. These two cases, To Kj and I1 = K1, imply, respectively,
is the weighted mean of 2o and
and qu = O, so the other variable doesn't it affect the objective.
We thus get that maximum is attained at
Zo = K1, Go 1, I1 E [uminn K1): Q1 = 0 or E (81, 1), qu = 0, 21 R1, Ø1 1.
In both cases, the objective value is Ki.
Finding the minimum: By Lemma 16, we know that the objective (non-strictly) decreases as xo increases. The only upper bound on Zo 2o I 1. Similarly, we know that the objective (non-strictly) decreases decreases. The only lower bound on is 21 objective takes its minimum value
Umin- Thus, we know that the
K1 Umin
K1
To
1,
go
T Umin+
41 1 Umin
Mmin
Plugging these values into the objective gives the lemma statement.
26

---

We know have the tools to prove the first part of the main theorem, Theorem 8, the upper bound on e-accuracy of 1-representative panel.
Proof of Theorem 8, upper bound. We first consider the case I 0 and Umin = 0. Since uc.p(a) up (a) [0, 1] for all a A, know that (UCp(()) up, p(a) for all e A. Thus, C is l-accurate.
Let's consider the case 1 and Umin (0,1) or (0, and umin 0. By Lemma 15, know that any 1-representative panel is E-acourate with
= max UMAX(FI1P. PP Umin) UMIN(K1, K2;P, umin)
[Kx+j+1 Minin [Ma+] 1
1 where [Mayl a d matrix with entry Mi at position (i.j) and M ž 0 means that
Dositive-semi-defiiie Since both matrices are 1 x 1 and 1, the constraints are equivalent to Ri 2 Umin and 2 ki.
If both constraints are strict, we know the values of UMIN and UMAX by Lemma 17. There remains strict (recall Lemma 14 for the definitions of
the case when least one of the two inequalities UMAX and UMIN in this case). Let's again assume w.l.og. that z0 > ø1. Since Ki is the weighted
mean zo and ø1 (with weights go and 91, respectively), and both To. 21 [Maiin 1], we know that
61 Umin implies Similarly, K1 implies 2g 1, Q1 0, UMIN(1;;2) Umin) UMAXUM;AXPP Umiin)
umin: Go = O, so UMIN Mmmin's Mminn UMAX( (MMAX(mmiii P. Umiin) Umin-
In either case, if one of the two constraints UMIN(KI, #2; p, Umin) O. Since there always exists point at which all constraints followed, and UMAX(K1, K2; Mmin) UMIN (K1, K2; P; Umin) 2 0 at any such point, as follows immediately from their definition, we can restrict the constraints being strict, get that any 1-representative panel is E-accurate for p * 0 with
not tight, UMAX(KI, K2; P, Umin)
strictly
K1 Mmuin
1 - 161
K1
Umin
82
Umin
Mnii
s.t.
Umin
1,
and for ( with
max Ki
K1 Mgin
s.t.
Umin < Ki < 1.
We'll now solve these two optimization programs, starting with the case p a 0. We let f(Ri) = be the objective of the optimization program. We take the first
K1 Ummm
1-61
umin?
Umin
I-umin
derivative of to get
1-1
df dRi
1
Umin
Ki
Umin
Umin
p
Mgin
tmmin
umin
Setting this equal to zero, we get that
1-1
P Umin" Ø
1 Umin
Umin
Umin
p
1 Umin
Umin
We know that both the left hand side as well as everything within the parenthesis on the right hand side is positive for Rn (Umin 1), without introducing or loosing solutions for Kı E (umin 1). We do so and solve for i to get
raise the above equality the (1 p)/p-th power
+
Umin
1 Umin p
Mymin
Umin
(3)
Uuiin
1 Uminn P
Unin"
27

---

Taking the second derivative of f, we see that for K1 E [Rimin+ 1/,
d d (dx))² - - R1
-
Umin p) 2
Umin
Uminn
- 0,
1
Umin
1
Umin
Umin
so f is concave [tmmin- 1]. We
that (Umiu) f(1) O, and we know from above that f(x) > O for some x E (Umin: 1). Thus, we know that has an extreme point on [Umiin 1), which
know has to be at Kл specified in Equation (3), and is maximized on (Umin: 1) for this Ki.
Plugging Equation (3) into ʃ. we get that
f(x1)
1
p
1
Mmin
Umiin
Mmni
Mentn SN
p
Umin
1 Umin
which gives & from the theorem statement, for p and umin E (0,1) or E (0, 1) and umin E [0, 1).
Let's now solve the optimization program the remaining case p = 0 and Umin E (0, 1). Again, we let f(11) = K1 Umin
1-K1
be the objective of corresponding optimization program. We take the
first derivative of f. to get
df
1-61 1-umin In (mmin).
Umin
dki
Umin
Setting this equal to and solving for K1, get
In
+
1 (1 Mmmi))
Maniu
(4)
In
Menti
Taking the second derivative of we see that for K1 E [Remius 1/.
d² (dx1)²
= - ( 1
I-my Main
Umin
In (1mii) I 0.
Umin
so f is concave on [mmin 1]. Similar to before, we can see that [(umin) = [(1) = 0, and we know from above that f(x) > 0 for some E (Umin, 1). Thus, know that f has extreme points on [umin= 1]. which we know has to be at K1 as specified in Equation (4), and f maximized on (Umins 1) for this K1.
Plugging Equation (4) into f. we get that
11)
Umiu
Uymin
-11
max
f(x1) = =1+
In
In
In
Manin
Manta
which gives & from the theorem statement for O and
Mmin E (0, 1).
A.3.4 2-representative panels
We will first prove Lemma 16 for m which we'll then apply to solve for UMIN and UMAX. Together with Lemma 15 the proof of the first, "upper bound", part of Theorem will follow (the proof of the second, "lower bound", part can be found in Appendix A.4).
Let's consider
Proof of Lemma 16, m = 2. From Equation (2) we obtain that
4o (xo F1) (20 x22)
(R2 (x1 + x22 + 21222)
Q1 (01 - mo) (212 - F22
(R2 mi (no + x2) mo42))
42
(R2 kI + x1) + xo21)
(22 Fo vn)(13 - x1
28

---

We now calculate the derivative of the objective without the outer p-th root. We'll treat the case p = 0 separately the end.
(3) v0) (x2 x0)
Σ
1oprr
+ 30990
Oxo
(0o - 21 (20 - 222) (x2 K21)
xf
+
91
(2))
(2) - 20) (2) - x22)
422
x31 x1))
Q2
(22
Wo
(x2 - 20) (22 - x1
90
p
0
To
To 322
x
q1 qi(31 x22 + (I2 N1)
(0)
Fo ) (1) T2)
x/2
92 (2 21) + (x1 K1
(02 - 20) - σ1)
90
x
p p-1
40
To 11
Ty T2
x (12 - mo0
(12 Rij (rg x2) + x022) + (x2 81) xo)
(x1 ro) (00 x2)
K2 Ki (I1 + x2) + 21
x2 (28) - x0)
(K2 Ki (w0 + x + x 1) + (x) - K1) k1) Fo)
(02 xo (x3 - 21
R2g K1 11 + x22) + 11
z
10 3 1222-
p00
p-1
-P2
F0
21
F0 2/2
To determine the sign of the last line we consider the function f: R20 - R2o where f(x) = xº, We let P be the unique 2 polynomial for which P(xo) = f(xo), P(x1) = f(x1). P(rz) = (1x) using the Lagrange basis polynomials:
(x 21) x22
(x - No) x22)
(x - -000(s xz1
P(x) = z (xo z1 1 x22)
x
+ xo (x2 20)( xI
(x1
xo (x1 x22
We can now note that
d.
x/ 2 zー-22
22 2n 21
df (2o) pag
(20)=
dr
30 41
x2
dr
so that
( df
dP
Σ
qart
(sn)
dx (10)
90
amo
dr
i=0
Analogously, for T1 and 22 we obtain
= 41
pxd
p-1
21 22
222 20
P 81-20
91
df
(x1)
dP
dP
(m1)
O.r
31
300
F1
D2
dr
dx
i=0
222
P 32 Fo
df
dP dx
92
pr2
1-1
22
01
20p
42
(x²) dr
(x2)
Oxa
322 300
222
==0
We now prove that f can intersect in at most 3 points with a degree-2 polynomial. If we let L
P(x) azad tajx² + ao for some ap, ai 0g, get that de (f (f-P) P)) p(p 1 Since
29

---

x is monotone and non-negative (and we know 22 * 0 since the three points P is interpolating dx² (f P) has most one (single) root if a2 and p(p 1) are either both positive or both negative, and no root otherwise. We conclude that f - has at most 3 roots, and that 02 0 when p (0, 1) while d2
through are not collinear) d²
when p p~ 0.
Since we know æo, 21, 22 are 3 distinct roots of f we know that all roots are all single, and therefore that which one of f and P is greater 'switches' at each root. In particular, if p E (0. 1), we know that 02 < 0, so P(x) < f() for æ > zo and æ E (12,01). while P(x) > f(x) for x < 22 and (01,20). Therefore
df (mn)
dP
df
dP
dP
dx (xo) > 0,
dx (z1)
(x1)
0,
(x2)
dx (x2) > 0.
da
de
da
Similarly, for p < O, we know that 02 > 0. so P(z) > f(x) for x > xo and
E (02, σ1), while
P(x) < f(x) for x < 22 and x E (0), 20) Therefore
de (mn)
df
dP
df dr
dP dx
df
dP
(zo) < 0,
(x))
(21) > 0,
(12)
(x2) < 0.
dr
dr
dx
dx.
Since qo q1, 92 2 0, we get that
i
8
50
if 0.2 if
p (0.1),
y < O.
0r:
IS
if
0x:
2
To finish the proof, we note that
2
Σ
Σ
q:
Σ
qac
aro
Oxo
so p < 0 the sign switches when considering the objective function instead of the objective function without the p-th root. This implies the lemma for p o O.
We now turn to the case p- = 0. Taking the logarithm of objective doesn't change the sign of its derivative, so it suffices to show that
a Dzg
12
if m
(mod 2)
Σ % In(2a)
if + m (mod 2)
Taking the derivative of the objective with respect to zi. we obtain similarly to the case before that
Σ ại In(zz)
2
1
+ In(xa))o
(x) - vo) + (x2 - Io)
= 20 ro
Izo
(go (3o x22)
1=0
In(x1))
In(zi)(22 - -Ki)
+ 01
(x1 20
(0) 20 20) x22)
(n(22)
In(r2) (x) - -K1)
+ 92
(x'2 v.)
(x22 20) x1)
In In(xo) - 1l( 2 20-22
In(x:) - In(x2))
20
zg 21
= 370
20 I1
20 22
To determine the sign of the last line we consider the function f R>0 + R>o where f(x) = In(x). We let P be the unique degree-2 polynomial for which P(xo) f(zo). P(x1) = fI1)). P(Iz) f(22) using the Lagrange basis polynomials:
(x - 2z x2)
(a- zo)(x -22)
(x 20) (I x1)
P(x) In(
+ In(x1)
+ II(x22)
(xo - 2n xx) - x²)
(x) 10)(01 - xz)
(x2 20) x.
We can now note that
dP
dx (zo) In(xn) In(x1) ) 10ー22
In(wr) - >I(((22)
No 12 21
df (xo) =
21 -2
20 ø1
Fo 22
dx
30

---

so that
0
Σ
qiot
20
df
(5o)
de
dP
(xo)
Ooo
dx
dx
Analogously, for 2ı and 22, obtain
(
df
dP
Σ
q:
91
(x1)
(21)
1x
dx
dx
df
dP
Σ q:
92
(12)
dx (Iz)
dx2
dr
We now prove that can intersect in at most 3 points with degree-2 polynomial. If we let P(x)= = u2 + aaxx ag for some an; 01 02, we get that -= ( P) = -1/=² 2a2. Since 1/x² d²
monotone and non-negative, de (J P) has at most one (single) root if a2 non-positive and no root otherwise. We conclude that ʃ - P has at most 3 roots.
We know To 11, T2 are distinet roots of ʃ P, so we know that d2 < 0 (a2 cannot be zero since the three points P is interpolating through are not collinear) and that all roots are all single. Therefore, which one of f and P is greater 'switches' each root. Since a2 0, P(x) < f(x) for 20. it follows that also P(x) < f(x) for (I2, x1). while P(x) f(x) for x < 22 and æ E (0). Therefore
df dx dx (Io) O,
dP
df
dP
df
dP
(2n)
(x1) dx
dr (x)) <0,
(x2)
dx. (x2) 0:
dx
the lemma for p 0 follows.
We now apply Lemma 16 solve for UMIN and UMAX. Note that in the lemma statement, the case p 0 is the same as * O when replacing the weighted p-mean by weighted geometric mean. Lemma 18. Let p < 1 and 1 > Rn Kainn and K2
x > Umin 2 Then, if f O,
14mmm
UMIN(K1, K2: P, Umin)
(K1 Umin )
N2 Umin
R2 k
1
+
Umin P
2i + umin? 2
Ki Umin
K2
2u 16 + Umin
2
and
UMAX(111, K2;P, Mmiin)
Kij
(1 - k1)²
Ni
p
1i2
2111
182
2 +
1 K5
If 0.
(1 12
UMAX(NI, Koj O, Umin)
Ki - Pi2
and
(ng - "umin 22 +
122 Umin 13
UMIN(RI, Ki;; O, Umin)
(umin) <2 20--2 Pamin
Ki Umin
Proof. W.Loog. we assume Tp > æ1 > x2. Since the weighted mean of W1, 22 is Ki, we can furthermore assume w.l.o.g. that mn >>
(If xo > K1, then also < K1; if Ki. then
? = 82 = 0, which is still captured by xo > 21 Ki > 22 and yo 42 0: 3o K6 is not possible).
31

---

We now use this to rewrite the constraints qi 2 0 in terms of Fo. 21, 22. For qu, we obtain
1
40 2 0 +
(N2 (i + x2) + x1122) 2 0
(0 11 (2) x2)
+ fig 11 21 (x2 k1) 2 0
R2 -
Ki 82
+ 41 S Ki +
(5)
Ki 32
Similarly, for 91 and 22, we obtain
K1
21 2 0 45 20 2 K1
(6)
K1 T2
K2 K
4> 12
K|
(7)
R2 1
Q2
2
0
21 2 K1
(8)
30 K1
We now solve for UMIN and UMAX by finding the minimum and maximum of their defining optimization program from Lemma 14.
Finding the minimum: We'll first assume p + O. By Lemma 16, we know that increasing #1 will (non-strictly) decrease the objective. The upper bounds on 2ı are Constraint (5) and æ1 < xo S 1.
Thus, we know that there is a minimum either for I = Ki + Ra-xi
Xy K-- (tight to the upper bound
given by Constraint (5)) or for To < K1 +
Nig Na-
(the only case in which x can't take this value
K1-
62-28 so the second case becomes 81-22"
since 3 To). By Constraint (6), we know 20
R1 +
To = K1 N
We first consider the case = Ki + Ka K2-1281
We get that
N1-02
61-22
K2g Ni
M22-2281
+ x22
82-P281 12
40
61 22
K1 22
(iin
3i (350
T22
NiNa - Ryn
t tw2nn - -
K2
K1-22
(ro 11 (350 x22)
(a( -22)
K2 Ni 122
0,
Fo 11 ) (20 22/2
so the value of zo won't affect the objective. Furthermore,
K2 (2o + m22) + ZD
N2 122-82 rb) N2 P2N1 x2)) K1 x2
k1 12
(162 - Ki (In + I22 + (11 - 222)
(N2 D2K1 2aKi + x022) Z2h1 22 + x3))
(K1 =22)²
N2 28251 + 2z
Kj
Q2 40
Q1
K2 2x2k1 + x2
so the objective becomes
1/P
(K1 - x2
K2 12h1
122 x
K2 212/61 + +x²
K1 - D22
+
Kig
2
+ 2
$2
if
(9)
ng (x)-
K2 I2K1
(x2)
=fp=0. O.
(10)
K1 22
32

---

In both cases, the objective is univariate function in T2. We will show that it is monotonically increasing on the interval [0, K1), which implies that the minimum is achieved at I2 umin. which implies 21 = Ka-UmmK11 Since Ni (1 + Mmmin) > K2 + Mmiin by assumption in the lemma statement, if follows that 21 < 1. We know that 2o doesn't I affect the objective, so we can just set Zo to be any
value in (#1, 11. Plugging this in, we get
Jin E (II, 1]
20 0
12 Mmin R1
(R) Mmmin) )2
21
K1
Umin
91
K2 Uminn + Umin 2
(11)
K2 1o]
Min
R2 2 + Mmin
We'll now show for the case p A 0 that Equation (9) is monotonically increasing on [0, k1). To do that, we first drop the p-th root and take the derivative of the expression without the root (with respect to 12), to caleulate its sign. We get
(K2
xt) of p-1 ((p 2) 2(p - 1)8102 + pm3) + 22 (pn2 - 2(p - 1) + (p - 22)=2)
(k2 22 xス)²
where we write 2 for N2ー for brevity. Since K2 N³ > 0 and K2 2x, + x²2 K2 ks K1-82
(Ki x²)² > O, we can drop those terms without changing the sign of the expression. We simplify
further to get
x ((p 2)5² 2(p 1)x122 + pa,) 2 (pR2 2(p 1)x11² + 2)x
= (sp-1 + 2 )((2 2m + =3)) 2x 2x (N2 K122) + 2n² 1 (N102 - x²))
= (xf p- + x p-1 |((2) - x2) - x2) ) - 2x (m: - -x2) + 2x -2))
-
Since 11 > 22 and x U2, divide by 2(k²1 x2)( x2) without changing the sign, to get:
pr
pa
x x2
2
T1 I2
If we let fx) px--1, it follows immediately from the Hermite Hadamard inequality that the above expression is non-negative for p E (0, 1) and non-positive for O.
By the chain rule, taking the p-th root switches the sign of the derivative if p < 0 and does if E (0, 1). Thus, we can conclude that the derivative of Equation (9) on [0, x1) is non -egative for all p < 0 and p E (0, 1).
Let's next show for the case p = that Equation (10) is also monotonically increasing on [0, K1). The proof is very similar the proof right above for Equation (9). First, we note that taking the logarithm of Equation (10) doesn't change the sign of its derivative, so we just need to show that the derivative of the logarithm is non-negative. This derivative is:
(K2 - 1k2=~x) (2(1) (2)(2) In(x:)) + 222 (22-22)0 22221+22) 2(12 k122)
(k2 2x + x²)²
where again we write Ij for 82-8281 for brevity. Since N2 - xf > and K2 2x102 + x2 R2 - n² + (r, - x22²² > O, we can drop those terms without changing the sign of the expression. We simplify further to get
81-22
2(ki =22((1)(22) In(xz)) + (k2 - 23 - 2I2 + xx2)
(x2-2z)(mm
x(122 k1222)
2(m1 (2)(2)) In(xx1) +
1
+
Ki - D2
(1i 2x2k1 + xz)
322
K2 I2//1
2(k1 x2)((1(22) - In(x1)) +
+ 21
(x1 [x1 -22).
22
33

---

Since K1 > and x1 > 22, we can divide by 2(m1 - -22) x2) without changing the sign to get
In(x)) ) - (2(22)
21
22
2
T1 I22
If we let f(z) 1/z, it follows immediately from the Hermite-Hadamart inequality that the above expression is non-negative Thus, we can conclude that Equation (10) on [0, K1) is non-negative.
Ni- We get analogous equations for Qu: Q1, as in the earlier case (with go and 91 switched, naturally), so we get the same objective as in Equations (9) and (10), which we know minimized for z2 umin- Analogously to above,
It remains to consider the case
R2 Ka-2281
this implies Zg = K2 1mind61 We know that Zo > Umin since K2 - Uminki1 Umin (K1 (min) =
Kimin
K2 xŹ + (Ai Umin) )² > so since I1 doesn't 't affect the objective, we can just set to be any
value in (22, To). We get
(k) Uminn )2 162 2u 11 + Umunn 2
Wmin
370
20
81
Umin
21 E (I2, To)
91 0
(12)
R2g 12
Umin
K2 1 + Umin
We know that the objective is minimized for either the variable assignments from Solution (11) or from Solution (12). We note that in fact both assignments give the same objective value, thus, the global minimum. This value is exactly UMIN(KI, K2; P, Umin) in the lemma statement.
Finding the maximum: By Lemma 16, we know that decreasing I1 will (non-strictly) increase the objective. The lower bounds 21 that we have are Constraint (8) and ø1 > x2 2 Umin- se-ri (tight to the lower bound (the only case in which xi can't take this value
Thus, we know that there is maximum either for Iı = Ki
given by Constraint (8)) for D2 2 K1
Zo-Ni
ma- so the second case becomes
since Ø1 > 22). By Constraint (7), we know that x2 I K1
22 20 -1
We first consider the case X1 K1
K2-n7
We get that
20 -1
20 -k1
K2 Ki (20
+
To zo 20-K1
20 K1
(I'2 0o (x2 x1)
wi x 20
K2
(I'2 _T0 x11
K22 (300 -11)
= 0, (x2 Fo 222 F1
so the value of 22 won't affect the objective. Furthermore,
K2 K1 (20g + x2) + x022
11 1a
T22)
za --
20
(K2 - Ki (N0 + x2) x - x2)²
(K120 K2 xa + Ky Ky (K1 R2 20 + K122)
(xo - =2
K2 2x,300 +
20
k
40 1 Q1 K2
34

---

so the objective becomes
N2 - k2
(go K2)
[130 162 ) 1/p
26
if pf 0
(13)
K2 - 2x110 + 20
N2 2k1 + +20
20 - K1
~2-19
(DO)
22 -2-22110008)
[61-00
K2
ng 2ng to
if = 0
(14)
20
K1
In both cases, this a univariate function in zg. We know that 8120 Ei= q,r,20 -i= q:47
R2, so we have Zo E [Kg 1]. In fact, note that if S 0, the inequality is strict since T2 > 0 and at least 2 of the yi are positive (else xa K2), well-defined for all valid z6 and p. We'll show that Equations (13) and (14) are monotonically increasing on the interval [x3 ([x2 . for E (0, 1)). This implies that the maximum is achieved
have 20 E ( and Equations (13) and (14)
K Since Hi (1 + Umin) K2 + Umins by assumption in the lemma statement, it follows that 21 > Umin- We know that 22 doesn't 't affect the objective, can just set
F5 = 1, which gives σ1 I-NI
D2 to be any value in [umin 21). Plugging this in, we get
R2 k
40
K2 - 2Kk +
R2
(1 k2)²
(15)
T1
91
K1
K2 2ni +
D2 E [umiar F1 = 0.
We now show that for p * 0, Equation (13) is monotonically increasing on (2) ((A2 1] for p E (0, 1)). This proof is almost analogous to the minimization part. First, we note that Equation (13) is identical to Equation (9) with
replaced by zo. We can do the same algebraic steps, now noting that since 11 < K2/K11 S Ty and #1 < Tp. diving by 2(k² - x0)(21 xo) doesn't change the sign. We thus get, analogously the minimization part, that the sign of the derivative of Equation (13) without the outer p-th root is the same as the sign of
Pr pro
+ p
20 x
2
30 x
Again, by the Hermite Hadamard inequality with f(x) pr- it follows immediately that the above expression is non-negative for E (0, 1) and non-positive for < O. By the chain rule, taking the p-th root switches the sign of the derivative p < and does not if p E (0, 1). Thus, we can conclude that the derivative of Equation (13) on M2 1] ((x2 for p E (0, 1)) is non-negative for all
p 0 and p E (0, 1).
Let's next show for the case = that Equation (14) is monotonically increasing on [2 1]. Also this proof almost analogous to the minimization part. We note that Equation (14) is identical to Equation (10) with replaced by To. We can do the same algebraic steps, now noting that since 61 < K2/ /1 S Fo and Jı < no. diving by 2(kg za) Fo) doesn't 't change the sign. We thus get, analogously to the minimization part, that the sign of the derivative of Equation (13) without the outer p-th root is the same as the sign of
+ 21
In(2n) - In(x1)
22g
2
Co
.2a
If we let f(z) 1/x, it follows immediately from the Hermite Hadamard incquality that the above expression is non-negative. Thus, we can conclude that Equation (14) on [22 is non-negative.
It remains to consider the case 22
- We get analogous equations for 4o. Q1, i22 as in the earlier case (with qi and 42 switched, naturally), so get the same objective as Equations (9) and (10), which we know maximized for Fo Analogously to above, this
implies I22 Ka We know that 22 < 1 since (1 x1) (K1 x22 R2 x + (1 x1)² 0.
35

---

so since 2i doesn't affect the objective, we can just set it to be any value in (I2, We get
N2 N
z0
40
K2 - 2n +
(02, Fo)
91 = 0
(16)
K2
(1 - K1
22
42 R2
R1
2x1 +
We know that the objective is maximized for either the variable assignments from Solution (15) or from Solution (16). We note that in fact both assignments give the same objective value, thus, the global maximum. This value is exactly UMAX(K1, K2; p, Umin) in the lemma statement.
We now have the tools prove the main theorem.
Proof of Theorem 9, upper bound. We first consider the case S 0 and Umin = 0. Since uc.p uc,p(a), (a) [0, 1] for all a A, we know that ( up (a)) S for all E A. Thus, C is I-accurate.
Let's now consider the remaining cases < and Umin (0,1) p E (0, and Unin 0. By Lemma 15, we know that any 2-representative panel C is g-accurate with
= max UMAX(111, R2: P, Mmin) - UMIN K2: K21,
Umia)
(Retoli,=oo [(1 + Umin )Ngt++ Ki+j+2 Umin "minhitssiij-a
where [M is a d x d matrix with entry Mi,j at position (i,5) and M > 0 means that M is rositive-emmidefinte. The first matrix [N++)],,=0 thus is definite if and only if its trace and determinant are non-negative, i.e. Ky + Ai = +1+ K2 2 and det([ketsli,
and hence positive semi-
R2 - xf 2 0. The second matrix is 1 x and thus positive semi-definite if and
only if (1 Umin )k1 K2 Miin 2 0. These conditions equivalent to A2 oî and 1s Imiia
tmmm
+iiiii which implies 0 2 (N1 1)((1 Umin)) or T+omii
We can combine the two inequalities get K1 2 equivalently [umin 1). This gives us the constraints 2 N² 2 Umin in the theorem statement, except with weak instead of strict inequalities.
2 and 1 2 2
tat 14
Thus, we Il next show that if any of the 4 inequalities is not strict, then UMAX(K1, K2iP, Mmin) UMIN(K1, Keip, Umia) = (see Lemma 14 for the definition of UMAX and UMIN).
First, if k = K2, we get that E nx7 E gas; which by the arithmetic-quadratcc inequality only holds if xr = any value). Thus, UMAX(K1, N2: P. Umin) = UMIN(N1, fiz; p, M 162-
(unless 9, 0 for some i, in which case the corresponding can take
Next, if K1
K2 ammn we get that I+4min
= K1 (1 + Umin)) - K2
Unin
T (2x + Iyymmin
x²)) - Umnin
Σ 1=0
qa (1;;; + Xytimin
2 Umin) +
Menmin Umin
Σ q:(1 - xx) Muuin).
Since q:(1 - xx)(1; Mmin) 2 0 for x; E [umins 1]. it follows that x; = Umin or I; = for all i = 1, To obtain first moment Ki, the weights (q:) need to be 1-x1_ for umin and 8i -umin I-Maiin for 1, which also gives second moment K2 Ki (1 + umin) - Umin as desired. It follows that
I-ttain
1/p
UMAX(61 P, umin) = UMIN(K1, Kig P, Umin)
1-81 Umin P + 81 1
Manin
I-Mmin
36

---

Lastly, both K1 = 1 and K1 Umin imply xa = K2, so the first case applies.
Since there always exists a point which all constraints UMAX(R1, #2: P, (mmin) - UMIN(K1, K2; Mmin) 2 at any such point, as follows immediately from their definition, we can restrict the constraints to being strict without changing the value of the optimization program. This allows us to plug in the equations for UMAX and UMIN from Lemma 18 obtain the upper bounds from the theorem statement.
strictly followed, and
A.4 Lower-bounding the e-aceuracy of m-representative panels
The proofs of Theorems 8 and consist of two parts: showing that every 1- and 2-representative panel is e-accurate for the in the statement of the respective theorem, and then showing that this cannot be made smaller. We proved the first part in Appendix A.3. Here, we show the second part: For any e' < ε (and p 1, Umin E [0, 1)), for as specified in the respective theorem statements, there exists 1- or 2-representative panel that is not a'accurate.
The two lower bound proofs similar: We first show helper lemma (Lemmas 19 and 20) that, intuitively, says that if the worst-case utilities giving UMAX and UMIN in the upper bound are integers divided by [Fl, there are two panels in which each feature-valle (or intersection of two Srature-values, appears in the same share of individuals and the two panels have the highest and lowest welfare possible for panels with first moment Kn (and second moment K2) and individual utilities in [Umins 1), as specified by UMAX and UMIN in Lemmas 17 and 18.
A.4.1 1-representative panels
Lemma 19. Let p < and Umin E [0, 1), or p E (0, 1) and Umin O. Let é be an inte- ger, and K1, Umin E Q such that 1 > K1 Umin and Lumins (Ki E L. Then, there exist two panels C {(r1. V1)...., "rr.yr]], C' ((ri.n))...... (T'T. yr)} with individuals of types in I = {ui..... yrr with [F] 2 features and an alternative s.t. u,(a) E [Mminn 11 for all yi E I, so that each feature value appears in the same share in C and C¹, i.e. Σ EMEII P.Vi =Ey,ez r'y: and
1/8
8i Ki-ttii + 1-81 Umia 2) T-Mmio
if #0
(a) UMIN P, Umin)
I-Mmin 1-81
(Umin)
1-Mmon
ify - 0
and ue' (a)) UMAX(11151 Umin) K1.
Proof. F= (f.....,fi fe) and Vy {0, 13 for all f E F. We let yı be the type that has value 1
for all features, i.c. (f. = for all f F, = 0, 1. Welet
YN, [y: F.: (ff 1}| Exi Y Yu (v Kff v(f. = 1} Lumin
be the set of all possible types that have value 1 for exactly tKS and Eumai of their features, respectively. We let I = { } U Yx, U Yumm..
(ea E (eumin E E individuals of type y1 and of (e Ex1) E Z individuals of each of the (cusm types in Y Yomm. We let C' be the panel consisting of individual for each type in Yz,.
Let's now define the panels. We let C be the panel consisting of (Eri - llImmin
We need to confirm that for every feature f E F, each value u E Vy appears in the same share of C and C'. Since there are only two values, and 1, for each feature, it suffices to show that value 1 appears in the same share of individuals in C and C' for any feature.
To keep the math concise moving forward, we'll 'Il define binomial coefficients with negative bottom entry as zero. This precisely handles the cases Umin < I/E, i.c. Umin = O, and Ki < 1/C, i.e. k = below.
Consider any feature f E F. First, we can see that a fraction of / Ki of the individuals in C' have value for feature f. Also for we get that a fraction of
(IK1 tumin ) ((x + (e- (N1) (ewmin (
(R1 Umin) + (1 .8g M1)um Ki
(lK) (utmiu) (Everte) (e (xg) ) (
(K1 Ummin
+ (1 - -K1)
37

---

of the individuals in C' have value 1 for feature f.
We let be alternative such that af};) i/t for all E F and 0, 1; i.e., individual's utility is the number of features for which they have value 1, divided by the total number of features. Thus, K1- Furthermore, the individuals of type y1 get utility and the individuals of a type in Yumin get utility Umin Note that thus all individuals y E I get utility in [umin from a, as needed. The share of individuals with utility 1 in C is
all individuals in C' get utility Kn from a, so uCr,p(a)
(LK1 - Lumin) (eVeNIE)
K1 Umin
(EK) Emmin ) (eamin) + (e (K-exI)) (
Umin
and the share of with utility umin in C' is 1
Ki Kimin
1-k
Applying the definition of panel
I 1-Hmin I-umit
welfare, we find that (c) is as specified in the lemma.
Proof of Theorem 8, lower bound. Given any umin E [0, and p 1, we'll show that we can construct population P. an alternative a so that the utility of every individual in the population for in [mmnn 1], and a 1-representative panel C in P. such that |uc.p(a) up,)(a) gets as close to as desired (in particular, greater than any fixed e' < e) if the size of the population and the number of features is sufficiently large. This implies that there are 1-representative panels C that are not e' -accurate for any e' < E. To make it clear that depends on p and umin- we'll we'll write
1-2 1- Mmin Manin"
P p.
+
Manin Bainn I 1-umiin
for p O. (p 0 A Umin 0)
E(p, Umin)
1 + In (1/umtn)
-imi
In
In (1//mmi)
-1)
for p = 0 A Umiin > 0
for p S 0 Umin = 0
for as defined in the theorem statement.
Let's first consider the case that p S 0, Umin = O, where we want to show that for any E' < 1 E(p, Umin) there exists a 1-representative panel that is not e' -cccuuraee. By Theorem 11, we know that for any [F), there exists 1-representative panel that not e-accurate for any E <
we set F large enough in terms of e', for example |F] > + [1/(1- =')), we get that
F F
[1/(1- 1/(1-=)) >5' I+ (1/(11-==)
so there exists a 1-representative panel that is not e'aaccurate.
We now turn to the case p and Umin E (0, 1) or p (0, 1) and Umin 0, noting that these cases cover all of "p > 0", "p- < 0 A Umin > 0," and "p = 0 A Menin > 0," which are all remaining cases. We let
thiin I- Miiin 2
p
Muria Memin In
T-p
Munin Mminn I -umin"
if +
+in In
Manin)
if 0
Mysin
to be the value in (Mmin+ 1) maximizing the difference between UMIN(R1;PP umin) and UMAX(E1;P, p. Umin), as found in Equations (3) and (4), so that
UMAX(MI; P; Umin)) UMIN(N1;P Umin) E(p, epp,umin))
as shown in the proof of the first part of this thcorem.
We now consider a fixed |F| l, and let umin = [Eumii 1/e and hn [ 1/l be the smallest rational numbers with as denominator that are greater than Umin and fi1, respectively. We assume l is large enough so that 1 > A Amin, which is always possible since K1 E (Manin 1). Then, Lemma 19 tells us that for any p < 1, Mmnn E (0, 1) or p E 1). Umin = O, there exist two panels (r': yr)} with features, so that each feature value appears in the same frequency in C and C', and that there exists an alternative that has the maximum and minimum social welfare possible for a panel with first moment in and minimum population utility amin. i... UMAX(R1; p, @min) and UMIN(R1: ; p, @min), respectively.
C= ((),
(FT,
C' = {(r(,')
38

---

Now, note that as L - oo, we get that A1 - K1 and Amin - Umin- Since UMAX(K1; p. Mmin) and UMIN P. Umin) are continuous for p Umin (0, or p 1), Umin 0, and K1 E [Mminn 1), we get that as + 0o,
UMAX(R1;P) (min) UMAX(K1;P Umin), and therefore also
UMIN(R1:PP Umin) - UMIN(K1;P. Umiu);
Iue p(a) - uc pc)p = UMAX(R1;P, umin)) -UMIN((R1;2 p, Umnin) - <(p, Umin).
We now construct a population P that consists of the individuals in C once and n' times each individual in C'. Since each feature value appears in the same share of C and C", it also appears in the same share of P, so C and C' are 1-representative panels in P. If we let n' - co, we see that
=E ritn' n'r WE n'+1 (ur(a))p
up up))(a)=
Σ BEI
(((l((a))== =ucpp uc),)()),
so (a)) ue (c)p p(c',p()) uc,((a) as n'
Putting it all together, we get that as E, + xc, |up,p(a) uc.p(a)) - E(p, Umin) for the representative panel C in P. In particular, this implies that for any ā > O. for all E and n' large enough, (e(p, Umin) (up.p(a) - "cCppa))] < 5. we set 5 E(p, Mmii) - E' > (and notice that always jup,p(a) uc,p(a) S <pp Umin) as shown in the first, upper bound, part of the proof), it follows that for any < <p, umin), for all and n' large enough, (() - (a) E (s', Es,, Umin)], and in particular, [up (a) > e'. Thus, C' is a 1-representative panel that is not e' accurate. O
A.4.2 2-representative panels
T-x; These are the values of the v's in the optimization programs for UMIN(K11 K2; Umin) and UMAX(KI, K2, Mmin). respectively, that are not equal umin and 1, respectively, obtained in Lemma 18.
To simplify notation moving forward, we define À Ka- and X
Lemma 20. Let < 1 and Umin E [0, 1), orp E (0, and Umin = O. Let l be an integer, R1, N2 E Q so that 1 > K1 > Kmin and K2 > Ki > Umin as well as Lumin eX, LX E Z. Then, there exist two panels C = { ((TI.V))...... (IT....,,(TT.B7 yr C' ={(T' (11,.,1,...... (r'r. VT)} with individuals of types in I = {yn, .............. ..) with [F = E features and alternative s.I. (a(aa) E [Mainn foror all yi E I, so that each tpple up to two twofeuuure values appears in the same share in and C', L.e.,oor every F C such that FF| < 2 and (uy)seF, it holds that Ey'ez I's II,EF (e uy) Σ Eyerr I Vf( and (a) = UMIN(K1, K2; P. umin) and uc' p(a) UMAXXK1, K2i Umin).
T+Mmii
Proof. Let == = (J,,..,frl) and V = 1] for all / E F. We let y be the type that has value 1 for all features, i.c. (f = for all f f F 0, let
Y = WIf E F: vff = 1H = EA}. Yx = {v lif e F: :(f((f = 131 = EX), and
Yumia = 1 F v(f, = 131 = {umin}
be the set of all possible types that have value 1 for exactly eA, ex, and bumin of their features, respectively. We let I {8i) UYUUYUU Ux U Y Yumi.
Let's now define the panels. We let C be the panel consisting of c(111 umin )² (enreii)) individuals of each of the (AA) types in YA and of c(K2 xi) E Z individuals of each of the (evim)) types in Yum... where is any number so that c(K1 - Umin)) ) (eeming
(( ) ()) E Z. We let C' be the panel consisting of c' (1 )2 individuals of each of the (ex) types in Yx and of c' c((22 xx) (() e individuals of type y/, where c' is any number so that c((1 - (( ). (m2 xn)
Z.
We now confirm that for every feature f E F, each value v E Vy appears in the same share of C and C. Since there are only two values, 0 and 1, for each feature, it suffices show that value 1 appears in the same share of individuals in C and C' for any feature.
To keep the math concise moving forward, we'll define binomial coefficients with negative bottom entry as zero. Here, this precisely handles the cases Mmnin < 1/6, i.e. Umin = 0, X < 1/f, i.e. À and X' < 1/C, i.e. X' = 0.
39

---

Consider any feature f E F. For C, we get that a fraction of
c(K1 Mminn ( (ea ( ((4-1) + c(12 - n²) (emmin-)
8-1
(K) Ummn) )21 + (K2 kz) Mimin
c(KI- ummin) )² (eumun (ea) + c(K2 - n ((a) (enema)
(K1 Umin )2 + (Ki2 m2))
(K) Umin (K2 UminkK) + (K2 ki) Umin
(K) Umin) + (A2 k
of the individuals in C have value 1 for feature f. For C², we get that a fraction of
d(1 k1) (1 dk2 - (ex)
c¹(1 k1 ((x) + c((22 x9) (1-k1) + (K2 - x2)
(1 ki (K2 x²)
(1 - k1) - K2) + (K2 - n2))
n2)2 + (Ki2 n2))
K9
of the individuals in C' have value 1 for feature f.
Let's now confirm that for every pair of features fi, f2 E F, each pair of values 02) E V1, x V/a appears in the same share of C' and C'. Since there are only two values, 0 and 1, for each feature, by symmetry it suffices to show that values (1, 1) and (0,0) appear in the same share of individuals in C and C' for any pair of features. Consider any features fi, f2 E F. The case fi fz follows from the single-feature case above, so we assume fi + fz. We get that the fraction of individuals in C that have value 1 for fi and f2 are
c(R11 Umia (2 Evemmn (3522) + c(N22 - -x7) (WW) (G)
(Pmmin
c(K1 Mrnin) )2 (evmiin Cew + c(122 - k27) (2N) (Priuti))
(Ni umin) )2 (8-1)
1(EA-11) + (R2 N9)
(Eumin (8-1)
I(K1 K22) f-1
R1
(Ai) Umin) )2 + (K2 - n2?))
We get that the fraction of individuals in C' that have value for fi and fz
d((1 - k2) ( + d(222 - 10) (ex) (1- k2)) (11 c²(1 - <1(1-k))2 (()) + -k
(1-1) (K2 n2)
I(K1 K2)
- (ex)
(1 31 3 (N2 x
{-
Let's now turn to the share of individuals with values (0, 0) for some pair of features. We get that the fraction of individuals in C' that have value 0 for fi and f2 are
c(R1 umin) )2( (ever (EE)) + c(K2 (( (-2)
c(K1 - Uminn ) Amnain ( (2n) + c(t22 - kz7) (erian))
(K1 Umin) ) ()(E-(x-1) + (122 k2?) Umin Futmin
[(x] K2) 8-1
(2-1) 1)
(f-1)
Kl
[K] Umminn )2 + (k2 - x3]
We get that the fraction of individuals in C' that have value 0 for fi and fz is
c'(1 - x11-)))?((0) (1-k1)² ckk2 - (2)
(1 (1-X"0000'''''
[(K1 K2)
(1-1) (1 x + (k2 nZ)
K1
{
We note that in the math above, setting binomial coefficients with a negative bottom entry as zero handles precisely the cases Unnin < 2/C, i.e. lumii E (0, 1), A 2/2, i.c. Lx E (0, 1}. and X' < 2/C, ie. eX E (0.1).
We now let a be an alternative such that a(f. () i/l for all f E F and i = 0, 1; i.e. an individual's utility is the number of features for which they have value 1, divided by the total number of features. Thus, the individuals of type y1 get utility 1, the individuals of a type in Y, get utility X, the individuals of type Yx get utility X, and the individuals of a type in Y Yumin get utility Umin- Note that thus all individuals y e I get utility in [umin. 1] from a, needed.
40

---

The share of individuals with utility À in C is
c(Ki1 Umin) )2 ) (eumme) (G)) c(K1 Umuin) )a (emmiii (ew) + c(122 - xit (ea) (ramiie
(ki Umin )²
K2
2ng Manin + Manin
and the share of individuals with utility Umin in Cs
c(r2 -
)
162 2 21s Ummu + Umminn
c(K1 - Umin (2 ((aim))) (G)) + ok22
n (1) (camme)
K2
The share of individuals with utility 1 in C' is
c(1 k1) (xx) d(( - K 32 (x)) + c' ck -e(
(1 N1)²
2nz + K2
and the share of individuals with utility X' in C' is
d (n2 xz) (ex) c'(1 <(1-x1)3 (2x) + c' (k2 (ex)
(N2 k2))
2111 + K22
Applying the definition of panel welfare, we find that (a) and uc paa) are as specified in the lemma statement.
Proof of Theorem 9. lower bound. Given any Umin E [0, 1) and p < 1. we' ll show that we can construct population P, an alternative a so that the utility of every individual in the population for is in (Mnin: 1]. and a 2-reppresetaative panel C in P, such that |uc.p(a) "p,p(a) gets as close to as desired (in particular, greater than any fixed e' < <) if the size of the population and the number of features is sufficiently large. This implies that there are 2-representative panels C that are not -accurate for any <.
To make it clear that e depends on and Wminn we'll write s(p, Umin) for the we get from Theorem 9 for some p and Wmin-
Let's first consider the case that S O, Umin = O, where we want to show that for any E' < 1 = E(p, Umin) there exists 1-representative panel that is not e'aaccurate. By Theorem 11, we know that for any [F) there exists a 2-representative panel that is not e-accurate for any E < (1F1-2)/ 2)
set F large enough in terms of e', for example |F] 1 + [2/(1 e') we get that
F - 2
F 22/ et) +1 >6
2/(1
8')1 (1)
-
so there exists a 2-representative panel that is not eacccurate.
We now turn to the case < 1 and umin E (0, or p (0, 1) and Uman O. noting that these cases cover all of "p > 0", "p < 0 Umin > 0," and "p = 0 A umin > 0," which are all remaining cases. We fix any such p and Uniin- We write ςं and Hi the values of Kj and H2 that achieve the optimum in the optimization program from the theorem statement, i.e. being the values maximizing the difference between UMIN(K1, K2; P, Mmnin) and UMAX(R1, R2; p, Mmnin) that
UMAX($1 K&: Mmin) - UMIN HD:: P, Umin) = E(p, Mmin).
We let be an integer and A = Texil/a, R3 [ex; 1/c, and umin = [cumin 1/c be the smallest numbers with as denominator that are greater than <T. KGz. and Umnin, respectively. Furthermore, we pick e large enough so that > R > R + and Ri > (RT)² umins which we know is possible since > K
Itūmin
Momte and K3 > (ni)² > Umin-
1+umin
We now consider a set of [F] = = (At 4min) Ri) E Z features and let A R5 Amin
K] -mmn
-i and X = 1-# We get that et, ex Z. Lemma 20 tells us that there exist two panels ((1,,)), (rr, C² = ((r(.))), ,i),.., ((r.yT) with & features, so that each tuple of up to two feature values appears in the same frequency in C and C', and that there exists an
41

---

alternative a that has the maximum and minimum social welfare possible for a panel with first moment Ri. second moment K2. and minimum population utility Umin i.c., UMAX R2: p, mmin) and UMIN(R], R2; P, Mminn) respectively.
Now, note that UMAX K2: P, Umin) and UMIN(K1, K2; Umin) are continuous for < 1, Umin E (0, or p E (0, 1), Umin = 0, and K1 and K2 in the feasible region, we get that as 00,
00, we get that Ri Kij Rf kij, and Umin Umin- Since
UMAX(R R2;p, umin) - UMAX(N], R22 P. Umin), UMIN(Ri, Rgjp, (min) 7 UMIN (xi, Ki Umiin)
and therefore also
|ue p (a)) (c))(a)] = UMAX(R P2; Umin) UMIN(R;, p. Umin) e(p, Umiu).
We now construct a population P that consists of the individuals in C once and n' times each individual in C Since each tuple of up to two feature values appears in the same share of C and C² it also appears in the same share of P, so C and C' are 2-representative panels in P. If we let n' + oc, we see that
7i n'r'
up up)
Σ WEZ
n'+1 (ur(a))p
Σ ULEI
r((u(a))) ue (())
so (a) uc, (a) luct,(a)) uc.p as n'' + xc.
Putting it all together, representative panel C in P. In particular, this implies that for any d > O. for all and n' large enough, [p,, Umin) jup (up,p(a) - (a))l
get that as n, xc, lup,p(a) (c)p - e(p, Umin) for the
8. If we set d =(p, umin) E' (and notice that always jup (()) uc, (a) S E(p, Umin) as shown in the first, upper bound, part of the proof), it follows that for any e' s(p umin), for all and n' large enough, ((p (a)] (E', E((, umin)], and in particular, (() (c) > e'. Thus, C is 2-representative panel in P that is not g accurate.
A.5 Proof of Theorem 11
To keep the math in the proof concise, we use the (well-known) extension of binomial coefficients to allow for negative integers in the top part. We then apply the Chu- Shu-Vandermoode identity for generalized binomial coefficients multiple times throughout the proof.
Definition 21 ([13, Definition 3.1.)). Let & E Zzo and n E Z. We define the generalized binomial coefficient as (x) n(n (I.--))..nnk-+1)
There is a nice identity for binomial coefficients with a negative top part, which will be useful for the proof.
Lemma 22 ([13, Proposition 3.16.J). Let le E Zzo and n E Z. Then
n (m)
(-1) 1 n-1) 1)
A key part of our proof is the so called Chu- Vandermon identity, first stated by mathematician Chu Shih-chieh already in 1303.
Theorem 23 ([13, Theorem 3.29.J). Let K Z20 nI, m E Z. Then
n + m
m k - i
k
We refer [13] for contemporary proofs of Lemma 22 and Theorem 23.
Proof Theorem II. For this proof, we'll construct two panels, C and C', of equal size that are m-rrepresentative with respect to each other, i.e., for every m S m, every m-tuple of feature values appears in the same number of individuals in C and C'. We'll construct an alternative that gives one
42

---

person in C utility O, while every person in panel C' has utility at least - ( m)/ We then let P be the population consisting of the individuals in C and C', so C' is a m-representative panel in P with welfare at least (IF) -m) |FI for while to overall population has welfare 0.
First, note that if [F| I m, the bound in the theorem follows trivially. Thus, let F = (f1,-... ft] for é = F > m. Let V = {0.1) for all f E F. Let ze be the type that has value 0 for all features, i.c. (f( = 1-1 for all f E F 0, 1. For j E (0,....m]. we let Y {v: : If E 0) = 1| =j} be the set of all types that have value 0 for exactly j features.
We define C to be the panel consisting of one individual of type ye and (<m=-))) individuals of each type y E y, for j E {o...... .m.j. # m mod 2. We define C' to be the panel consisting of (mm=)))) individuals of each type E Y, for j E {o...., m,,.j = m mod 2. We'll first prove that the number of individuals in C, k and in C', denoted I', is indeed the same. Let's first calculate is and K':
( ((-i-1) 11
m mm}) (
==1+
Σ
m j |X/==1
Σ mm)..... jmm mod?
jE( m. j mod 2
V- Σ
m (1----1
-
Σ
(=
m -
(E(O.....m)) JEm
mod 2
jEm mod 2
where the two right equalities follow from Lemma 22 and the fact that |T,] = ()) We now note that by Theorem 23,
Σ
m
m ;) :) (
(ml (m)) m
1,
==
which immediately implies k = k'.
Next, we'll argue that C and C' are m-representatiiv in respect to each other, i.e., any m-tuple for feature values for m E [m] appears in C with the same frequency as C². Since k = k,, this means it appears in the same number of individuals in C as in C².
Let F C F. |F| m. be any set of m S m features in F and let V = (uf)seF E EX SEF Vy be any assignment of values to these features. Let ky and ky be the number of individuals in C and C², respectively, with feature values V. We thus want to show that ky = k,, for all V.
For any V, let i = Juy E VV Uy 0| be the number of zeros in this assignment. For j = {o,.... m J. since there are - m feature values not defined by V. out of which j j-ú i are zeros. j < i, we know that no type in Y, has feature values V. since types in Y, have value 0 for less features than required by V. Type yo has feature values if and only if i m since it is all zeros..
the number of types in Y, that have feature values V is (f-m) if
We get that
by = 1/ m
Σ
L ((-j-1) - 1)
(1 -
( m
1 m]
Σ
(E m m 5
m )
(G-mm)
m-j
jE m)
jEft.....m
jæm mod
fmm mod 2
f. ( 1) ( m = Σ
1 ()
m (m-
;)
(
e m
j )
m
m
() mod
JE jE( m)
jmm
jmm mnd
where again the two right equalities follow from Lemma 22, We now note that
Σ m - (,=))
m
m-
m m-t m-i- )
(" m
m - m
j 0
where the last equality follows from Theorem 23. Now, note that since i S m, the bottom part of ("h- m-:) is at least its top part, so by Definition 21, we get
i 171 m
(
if < m if m
1 m
43

---

This immediately implies ky = Ky.
We let P be the population consisting of all individuals in C and C'. Since for any m, any m-tuple of feature values appears in the same share individuals in C and in C", we know they also appear in the same share in P. Thus, C and C' are m-representativv panels in P.
We now define alternative a such that aff.
i/l for all F. = 0, 1. That is, an individual gets benefit L/e for each feature value that is 1. Thus, individual ye has utility 0, and any individual y E Y, for j E {0, ................................ m has utility (8 - j)/E. In particular, note that the utility from a for any individual in P is in [0, 1], required.
The p-mean, for p I O, of a list of numbers including is so the welfare of P up However, all individuals in C' have at least utility (e mm/e. Since for any p, the p-mean of list of numbers is at least as big as the smallest number in the list, uc p())p(a) 2 ê-m We conclude that for this alternative a and mn-representative panel C' in P.
E
e- m
lue x()) up (())
The theorem statement follows.
A.6 Additional details and results from empirical experiments
Appendices A. A.6.3 contain additional details the datasets used for the empirical experiments. Appendix A.6,4 contains the plots for E-approximate m-representatiie panels that are not in the main part of the paper.
A.6.1 European nation-wide panel
For this panel, 30,000 letters were mailed to invite individuals to participate. 1.727 individuals volunteered to be in the candidate pool; the desired panel size was 110. Seven features were being considered when selecting the panel, which we list in Table 2.
Table 2: The features considered in selecting panel EURl
Features
Values
Gender Age
Male, Female, Other
16-29, 30-44, 45-59, 60+ 12 distinct regions
Place of residence within the country
Educational attainment
3 levels
Concern aboutt-linatteeeeee chune
eeneeeene,,,,, eeieelye
concerned, Not at all concerned, Other White, Non-white
Ethnicity
Residential density
Urban, Rural
We obtained the underlying population data from the 2016 European Social Survey [19]. The dataset contains 1,959 respondents with cost-stratiiication weights to account for sampling and participation bias. We dropped 44 people from the dataset: 40 because they had missing data and 4 because they younger than 16, the minimum age set for the assembly. Furthermore, since the European Social Survey only has the fields 'Male' and 'Female' for gender, we removed the 12 individuals with gender 'Other' from the pool candidates, reducing the size 1,715.
One of the seven features considered was "Concern about climate change". Only 4 individuals in the pool of candidates had the value "Not at all concerned"', making it impossible to even form I-representative panel of the desired size with this candidate pool. We thus excluded this feature from analysis.
note that due to its limited sample size of 1,959, the European Social Survey doesn't 't contain person for all possible tuples of feature values, for > 3. However, this is not concerning for our positive results on the existence of m-repreesentative panels, since these are tuples of feature values that appear in sufficiently small share of the population that an merepreeeentatie panel would
44

---

satisfy the corresponding quota by containing 0 or individuals with that tuple of feature values. In our experiments, for tuples of feature values that didn't appear in the European Social Survey, we enforced that 0 people on the panel have this tuple of feature values, tightening the constraints on the existence of m-rrepresentative panels.
A.6.2 Australian state-wide panels 1 &
These two panels were being conducted in series with overlap in the pool of candidates and individuals on the panels. Initially, 25,000 letters were mailed to invite individuals to participate, with additional letters being sent to groups with expected low participation rates. 1,070 individuals volunteered to be the first candidate pool, from which panel of 50 candidates was selected. For the second panel, additional individuals were recruited for the candidate pool, then including 1,145 individuals (some of which were on the first panel). A panel of 328 individuals was selected. Four features were being considered when selecting the panels, which list in Table 3.
Table 3: The features considered in selecting panels Ausl and Aus2
Features
Values
Sex
Male, Female
Age
18 18-24, 25-34, 35 44, 45 54,54,,55 55-64, 65+ Metropolitan, Regional Owner/Oceupier, Tenant
Residential density
Residential-stanee status
We obtained the underlying population data from the Australian Burcau of Statistics' 2021 Census data [1]. Up to small deviations due to differential privacy noise being applied to the dataset, obtained the exact population share of each feature value tuple including "Sex", "Age", and "Residential Density". However, the publicly available data from the Australian Census separates between individuals and dwellings, that data the intersection of the "Residential status" feature with the features "Age" and "Sex" is available. We therefore dropped the residential status feature in our analysis.
A.6.3 Australian state-wide panel 3
For this panel, individuals could self-register interest in participating. 3,500 individuals did so, and emailed invitation to participate. 518 of those individuals ended up volunteering be in the candidate pool; the desired panel size was 45. Four features were being considered when selecting the panel, which we list in Table 4.
Table 4: The features considered in selecting panel Aus3
Features
Values
Gender
Male, Female, Non-binary, would prefer
net say
Age
18 18-24, 25 34, 35 44, 45-54, 55, 55-64,666666 65-74, 75+
Place of residence within the state
3 distinct regions Yes, No, Unsure, Unsure-1
Ability attend all panel sessions
We obtained the underlying population data from the Australian Bureau of Statisties' 2021 Census data [1]. Since the Australian Census only has the fields 'Male' and "Female' for sex, we removed the 9 individuals with gender 'Non-binary' or 'I would prefer not to say' from the pool of candidates, reducing the size to 509. Additionally, the feature 'Ability to attend all panel sessions' cannot be obtained for the underlying population, by itself or in intersection with other features. Thus, we only consider this feature individually, ensuring that at most 1 1/45 of the individuals of the values 'No", 'Unsure', or "Unsure-1" as was the requirement for the actually selected panel. For each feature value tuple including "Gender" (without "Other"), "Age", and "Place of residence".
the panel have each
45

---

we obtained the exact population share, up to small deviations due to differential privacy noise being applied to the dataset.
A.6.4 Additional plots for s-approximate m-rereesetttteeee panels
Aus2
AUS3
desired panel
desired panel size
miniumm approx. error
minimum approx. error
04
0d
D0 200
433
502
300
3000
100
100
200 300
400
200
panel size k
panel size
Figure 4: The smallest for which e-approximate m-representattie panels exist as function of the panel size & for selected m E [[F]]. The dashed lines show the desired panel sizes.
clear how convert the feature 'Ability to attend all panel sessions' quota to use for e-approximate m-representation. As described in Appendix A.6.3, we thus only consider panels for which most 1/45 of the individuals on the panel have each the values 'No', 'Unsure', or "Unsure-1', as the requirement for the actually selected panel. These constraints make panels of size greater than 389 impossible, which is why plot for AUS3 in Figure does not extend beyond this value of k.
In AUS3,
46


Reviews:
[{"review_id": "L6RHRCxEx2", "reviewer": "Reviewer_o2qy", "summary": "The paper explores descriptive representation in the context citizens' assembly, focusing on the worst-case guarantees of 2-representative panels (i.e., representative of the underlying population over intersections of features). The paper quantitatively shows that 2-representative panels can more accurately estimate $p$-mean social welfare, and presents theoretical and experimental results.", "questions": "The authors are encouraged but not required to answer the questions mentioned in “Strengths & Weaknesses” above.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n+ The paper provides a strong motivation for studying 1- and 2-representative panels with clear practical implications. The paper could be strengthened by discussing limitations of current methods (a real-world situation like Example 7?) and plans for trying out 2-representative assemblies in practice.\n+ The authors give tight bounds for the worst-case guarantee of 1-representative panels (as a function of $p$ and the minimum utility $u_{\\mathrm{min}}$).\n+ Overall the paper is well written and the presentation is clear.\n\nWeaknesses\n- The paper could be strengthened by highlighting its technical contributions, e.g., which results are the most challenging to prove, and how the authors overcome the challenges. Is the upper bound in Theorem 9 tight, and is there any concrete evidence that the optimization program in Theorem 9 does not admit a closed-form solution?\n- 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 $q_i k$ 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).\n- 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$)? 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).\n\nTypos\n- Line 87: \"foundational results ... has\".\n- Page 7: the printed version of Figure 1 is hard to read.\n- Line 309: missing a period.", "was_revised": true, "final_justification": "Most (if not all) of my comments are constructive suggestions. The authors responded that they would revise the paper accordingly. A few short and clear points were provided under \"Strengths and Weaknesses.\"", "rebuttal": "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.\n\n> Is the upper bound in Theorem 9 tight? \n\nFor 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. \n\n> ... and is there any concrete evidence that the optimization program in Theorem 9 does not admit a closed-form solution? \n\nWe 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.\n\n> 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). \n\nThank 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.\n\n> 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$)? \n\nThank 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. \n\nWe 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:\n\n| $k$ | too small panel sizes, $\\varepsilon=1$ | range of good panel sizes, $\\varepsilon \\sim \\Theta(1/n)$ | critical panel size $c$ | panel sizes for which pool is 'too skewed', $\\varepsilon\\sim\\Theta(1-\\frac{c}{n})$ | largest possible $k$-rep. panel size in additive definition |\n| - | ----------------- | ----------- | --- | ------------- | --------------------- |\n| **1** | 1-5               | 6-632    | 632   | 633+          | 640                   |\n| **2** | 1-27              | 28-233   | 233   | 234+          | 278                   |\n| **3** | 1-59              | 60-126   | 126   | 127+          | 210                   |\n\nWe 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.\n\nIn 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.\n\nWe will add a discussion of these new insights and the additional experimental results in the revised paper.\n\n\n> 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).\n\nWe 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."}, {"review_id": "eZkeIeV1Fc", "reviewer": "Reviewer_jovN", "summary": "The paper studies citizens’ assemblies. Its goal is to determine whether descriptively representative panels make welfare-optimal decisions for the broader population.\n\nThe authors use the notion of m-representatives and show that 1-representatives are accurate for the arithmetic mean, but not necessarily for other means. They show that for 2-representatives, the worst-case accuracy is better than in the 1-representative case.\n\nFinally, the paper presents an empirical analysis, showing the relationship between the representation level and panel size in practice.", "questions": "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.)", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "My overall evaluation of this paper is very positive.\n\n+Assemblies are one of the most interesting recent topics within computational social choice.\n\n+The paper is extremely clearly written and well-positioned within the literature.\n\n+The concept of *m*-representation is intuitive and elegant, and the paper provides bounds on the accuracy of such representation.\n\n+The paper includes an empirical analysis, showing, among other things, that it is indeed possible to select 2-representative panels in real-world instances.\n\nSide notes:\n\n-Minor issue regarding the plots: the text size is too small to read comfortably.\n\n-I'm not sure the title accurately reflects the paper's content. It is catchy but not very descriptive.", "was_revised": true, "final_justification": "My evaluation remains unchanged.\nI'm still in favor of accepting the paper.", "rebuttal": "Thank you for the review. We will increase the text size in the plots in the final version.\n\n> 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.)\n\nThis is a fair question; our answer is twofold. \n\nFirst, 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:\n\n* Noothigattu et al. A Voting-Based System for Ethical Decision Making. AAAI 2018. (Section 5, Step II.)\n* Balseiro et al. Contextual Standard Auctions with Budgets: Revenue Equivalence and Efficiency Guarantees. Management Science 2023. (Section 2, first paragraph.) \n* Freedman et al. Adapting a Kidney Exchange Algorithm to Align with Human Values. Artificial Intelligence 2020. (Section 3.3.)\n\nSecond, 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."}, {"review_id": "5vENugmQft", "reviewer": "Reviewer_4ra7", "summary": "For citizen assemblies a panel of individuals is selected from the population in a way that proportionally reflects the population’s composition across multiple features, such as age, gender, and ethnicity. However, even when an individuals preferences are only determined by their features, an optimal decision for a (1-)representative panel must not be optimal for the population. In this paper, the authors explore how close the social welfare of a representative panel aligns with the social welfare of the entire population. They show that the welfare aligns significantly better when every combination of two features is proportionally represented in the panel, where welfare is measured using the p norm of individual utilities with $p < 1$. Depending on the size and diversity of the volunteer pool, it may not be possible to select such a panel. To address this, the authors include an experimental section in which they assess the feasibility using data from four past citizen assemblies.", "questions": "* 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?\n\n* 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?\n\n* What was the rationale behind the selection of the four specific citizen assemblies used in the experimental evaluation?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The paper is well-written and addresses a relevant question in the context of selecting citizen assemblies. The long introduction effectively motivates the research and clearly presents the main questions and results. However, some parts are difficult to follow without prior knowledge of the model, which is introduced in the subsequent section. \n\nThe related work section feels rushed and lacks a structured overview of relevant literature. A proper discussion of existing approaches and how this work relates to them is necessary in my opinion.\n\nThe main theoretical results seem significant, their proofs are deferred to the appendix. The paper does provide an outline of the proof for one of the key results (Theorem 9). However, an important concept—the 'moment problem'—is never properly introduced or explained, despite its apparent centrality to the argument.\n\nIn the experimental section, the authors check whether a 2-proportional panel of desired size can be found for four real-world instances. While this provides some insight, the small number of instances limits the ability to draw broader conclusions about feasibility. This limitation may be due to the inavailability of data, though this is not explicitly addressed in the paper.", "was_revised": true, "final_justification": "The authors have addressed my questions. However, the weaknesses and limitations identified in my original review remain. Therefore, I have decided to keep my score unchanged.", "rebuttal": "Thank you for the review. We will implement your suggestions, including expanding the related work introducing the moment problem in more detail. \n\n> 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?\n\nThe 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:\n\nFlanigan et al. Fair Sortition Made Transparent. NeurIPS 2022. (Section 2, second paragraph.)\n\n> 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?\n\nWe 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.\n\n> What was the rationale behind the selection of the four specific citizen assemblies used in the experimental evaluation?\n\nWe 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."}, {"review_id": "LTaSzdCExF", "reviewer": "Reviewer_KBwz", "summary": "The paper studies how well the welfare of representative citizen assemblies translates to the welfare of the underlying population. In particular, the paper focuses on 1- and 2-representative panels, which mirror the population with respect to the proportion of individuals possessing one or two protected attributes, such as, for example, being male and a parent.\n\nThe welfare notion considered is p-welfare, the power mean welfare: when p = 1 it captures utilitarian welfare; when p = 0 it captures Nash social welfare; and for negative p it becomes increasingly egalitarian. The question studied is how good an additive approximation the panel’s p-welfare–optimal outcome is to the p-welfare of the underlying population.\n\nFor p ≤ 1 and 1-representative assemblies, the authors prove tight bounds on the additive approximation gap ε. For 2-representative committees, they show upper bounds as well as a lower bound in the case when some alternative provides zero utility to some type. On real-world data, the authors demonstrate the feasibility of selecting 2-representative citizen assemblies.", "questions": "Could you elaborate on epsilon‐accuracy - for example, why you focus on additive approximations rather than multiplicative ones? \n\nIt would also be helpful if you could discuss lower bounds on the worst‐case epsilon‐accuracy when u_min > 0. Additionally, could you expand on your utility assumption, namely that individuals’ utilities for alternatives derive from the attributes those alternatives possess? \n\nFinally, 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?", "limitations": "It’s questionable whether people’s preferences for various options can truly be captured by demographic attributes like gender or age. While it’s reasonable to assume that individuals with similar characteristics with form clusters of some sort, this approach inevitably misrepresents a substantial portion of the group - particularly when we rely on the limited set of attributes commonly used in practice.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper is very well written and well motivated. It tackles a practically driven theoretical problem, and as a result must contend with quite involved mathematics that don’t yield neat closed-form solutions. In that light, Figure 1 is especially valuable for visualizing and understanding the resulting bounds.\n\nMoreover, the theoretical findings are backed up by experiments demonstrating that 2-representative citizen panels often exist in practice. Taken together, this evidence suggests we should consider moving beyond single-member representation in real-world applications.\n\nThat said, the paper could be clearer in its exposition of ε-accuracy and in guiding the reader through how to interpret the additive approximations (see my questions on this point). It would also benefit from a more in-depth discussion of the challenges involved in proving a lower bound for 2-representative panels when \nu_min >0.\n\n____\nMinor comments:\n\nPage 4 Line 177: doesn't -> does not\n\nPage 6 Line 236: or alternative -> for an alternative\n\nPage 7 Line 276: doesn't -> does not", "was_revised": true, "final_justification": "Well-written, well-rounded paper.", "rebuttal": "Thank you for the review. We will correct the typos you pointed out in the final version of the paper.\n\n> Could you elaborate on epsilon‐accuracy - for example, why you focus on additive approximations rather than multiplicative ones?\n\nWe 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$. \n\nThat 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. \n\n> It would also be helpful if you could discuss lower bounds on the worst‐case epsilon‐accuracy when $u_{min} > 0$. \n\nFor 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. \n\n\n> Additionally, could you expand on your utility assumption, namely that individuals’ utilities for alternatives derive from the attributes those alternatives possess?\n\nThis is a fair question; our answer is twofold. \n\nFirst, 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:\n\n* Noothigattu et al. A Voting-Based System for Ethical Decision Making. AAAI 2018. (Section 5, Step II.)\n* Balseiro et al. Contextual Standard Auctions with Budgets: Revenue Equivalence and Efficiency Guarantees. Management Science 2023. (Section 2, first paragraph.) \n* Freedman et al. Adapting a Kidney Exchange Algorithm to Align with Human Values. Artificial Intelligence 2020. (Section 3.3.)\n\nSecond, 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. \n\n\n> 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?\n\nThe 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:\n\nFlanigan et al. Fair Sortition Made Transparent. NeurIPS 2022. (Section 2, second paragraph.)"}, {"review_id": "kf2nXMyp3T", "reviewer": "Reviewer_ibjw", "summary": "This paper studies the role of descriptive representation in collective decision making. They show that requiring representation for pairs of demographic features (2-representation) significantly improves worse-case welfare guarantees beyond today's single-feature quotas. They demonstrate through empirical analysis that 2-representation is generally feasible in practice.", "questions": "As discussed in weaknesses, some questions and suggestions include:\n\n1. 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.\n2. Can the modeling assumptions be weaken?\n3. Would be good to add discussions on more related works so that we can have a better sense of how this work stands among relevant works in this area.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. Theoretical results are interesting and concrete. They prove that 1-representation is perfect for utilitarian social welfare but can be arbitrarily bad for $p < 1$. They then derive explicit $\\epsilon$-accuracy bounds for both 1- and 2-representation via a moment problem reduction.\n2. Practical feasibility of finding 2-representative panels is shown through empirical analysis.\n\nWeaknesses:\n\n1. In addition to the feasibility of finding 2-representative panels, I'm also curious about the welfare of 2-representative panels compared with 1-representative panels on real-world datasets. Would be good if the authors could show this.\n2. Modeling assumptions are strong. For example, utilities are additive across features. I understand that this is necessary for theoretical analysis, but just not sure how much practitioners can still get out of this paper with these assumptions.\n3. The related works section should be more about how this work stands among the works on computational social choice, instead of trying to persuade the reviewers that NeurIPS is a suitable venue foe this paper.", "was_revised": true, "final_justification": "My questions have been nicely addressed. This is a solid work with both interesting theoretical results and empirical validations. However, I'm still left with a bit of concern about whether NeurIPS would be the perfect venue for this work (which is why I gave a 4 instead of 5). Thus, I decided to maintain my rating.", "rebuttal": "Thank you for the review. We would be happy to add more discussion of related work, as you suggested. \n\n> 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.\n\nReal 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.\n\n> Modeling assumptions are strong. For example, utilities are additive across features. ... Can the modeling assumptions be weakened?\n\nArguably, the only potentially restrictive assumption is the one on utilities. But we believe it is reasonable for the following reasons. \n\nFirst, 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:\n\n* Noothigattu et al. A Voting-Based System for Ethical Decision Making. AAAI 2018. (Section 5, Step II.)\n* Balseiro et al. Contextual Standard Auctions with Budgets: Revenue Equivalence and Efficiency Guarantees. Management Science 2023. (Section 2, first paragraph.) \n* Freedman et al. Adapting a Kidney Exchange Algorithm to Align with Human Values. Artificial Intelligence 2020. (Section 3.3.)\n\nSecond, 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. \n\nThat 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."}]

Author rebuttal:

Meta-review: The paper studies citizens' assemblies and shows that intersectionality improves social welfare compared to the traditional approach of proportional representation by individual features.

The reviewers found the paper to be nicely written and the topic of the paper to be interesting. The reviewers found the concept of m-representation to be intuitive and appreciated the results of the paper. I think this paper would be a nice addition to NeurIPS.

The reviewers had several suggestions that I hope the authors can incorporate for the camera-ready version, given the additional page. (1) Reviewer o2qy had an interesting suggestion about the multiplicative notion. The authors have provided additional interesting experimental results in the rebuttal. I think this is a nice result that should be added to the paper. (2) The text size in some of the plots is too small. Please consider editing these plots to make the text bigger. (3) Please expand the discussion of the related work. This paper is relevant to NeurIPS as many prior works are published here, so please expand the related work without focusing on showing how this paper is relevant to the community. (4) Please include your answer to Reviewers KBwz and jovN about uniformity in the final version.
Decision: Accept (poster)