{"id":"07b697be-25ec-4f8e-bdea-cebc1810d841","arxiv_id":"2504.20508","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A random panel of size roughly (1/epsilon)^2 times a logarithmic factor guarantees near-optimal social outcomes with high probability, with matching lower bounds in participatory budgeting and facility location.","lead":"This paper proposes a new way to measure how representative a randomly selected citizen panel is, using the Wasserstein distance from statistics. It then derives nearly tight formulas for the panel size needed to guarantee efficiency and fairness in participatory budgeting and facility location.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.9's proof assumes balanced panels select endpoint facilities; an interior tie-break can give failure probability 1/10 for k=2, leaving the T=2 tightness claim unproven.","rationale":"The main upper-bound theorems, especially Theorem 2.5 and its participatory-budgeting applications, are technically sound modulo small constant-factor and scaling fixes. The reader's CONDITIONAL verdict is therefore appropriate. However, the stress-test pass found a more concrete gap than those listed by the reader: the proof of Theorem 4.9 relies on an unjustified dichotomy about the panel decision function selecting 0 or 1. A panel-optimal function may select an interior minimizer on balanced panels, and for k=2 this makes the constructed instance yield failure probability 1/10 rather than the claimed 1/4. This means the 'does not hold for T=2' tightness claim is not proven as stated. The concern is load-bearing only for the tightness narrative, not for the central constructive bounds: Theorem 4.2's O(log(1/delta)) guarantee for every T>2 remains intact, and the reduction's tie-breaking can be made worst-case for upper bounds. The recommended action is to keep the paper conditional while requiring the authors to repair or restate Theorem 4.9, either by choosing an adversarial distribution that defeats interior tie-breaking or by explicitly assuming a tie-breaking convention and stating the lower bound under that convention.","tokens_in":34299,"tokens_out":48447,"duration_ms":499223,"concrete_test":"Enumerate the k=2 counterexample exactly: n=5 with locations (0,0,1,1,0), C=[0,1], and panel decision function returning the unique median, except on panels with one 0 and one 1, where it returns 0.5. Compute P[d(q(S),0) >= 2*(2/5)] over all 10 panels. If the result is 1/10, the proof of Theorem 4.9's construction is refuted; then test whether a minority fraction p=0.2 at point 1 (with the rest at 0 and a unique median at 0) restores failure probability >= 1/4 for this tie-breaking rule.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The facility-location tightness result for T=2 (Theorem 4.9) is not established by the argument given. The proof considers a population with k agents at 0, k agents at 1, and one pivotal agent, then asserts that, conditioned on the panel omitting the pivotal agent, the panel decision function selects 0 with probability at least 1/2 or 1 with probability at least 1/2. This is invalid: a panel-optimal function may choose an interior point when the panel is balanced. Concretely, take k=2, n=5, locations (0,0,1,1,0), and q* = 0. Social-Opt = 2/5, so 2*Social-Opt = 0.8. Define a panel decision function that returns the unique median when it exists and returns 0.5 whenever the panel contains one agent at 0 and one agent at 1 (a valid tie-breaking choice, since every point in [0,1] minimizes panel cost on such a panel). Enumerating all C(5,2)=10 panels, the event d(q(S),q*) >= 0.8 occurs only for the panel {1,1}, with probability 1/10, not 1/4. Thus the specific construction in Theorem 4.9 fails for this admissible tie-breaking rule. This does not invalidate the upper bound Theorem 4.2, but it means the claimed tightness at T=2 is unsupported as written; the theorem either needs a different adversarial instance (e.g., a small minority at the far point) or a qualification on tie-breaking.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a Wasserstein-distance-based definition of eps-representative panels and uses it as a unified tool to study panel complexity in two social choice settings: participatory budgeting and facility location. The main upper bounds state that uniformly random panels of size O((1/eps)^2 (log ell + log(1/delta))) are eps-representative for ell real-valued features (Theorem 2.5), and that this yields near-tight panel complexity bounds for welfare and core fairness in participatory budgeting and for facility-location welfare and outlier control. Lower bounds are obtained through camouflaged populations and reduce to an external sample-complexity lower bound. The paper also gives an impossibility result for purely multiplicative guarantees in participatory budgeting and a multiple-facility extension.","tokens_in":34561,"tokens_out":30331,"duration_ms":326823,"significance":"If the results are correct, the paper makes a useful conceptual contribution by connecting sortition panel representativeness to statistical sample complexity. Theorem 2.5 is clean, general, and likely to be reusable beyond the two applications studied. A notable strength is that the lower bounds apply to arbitrary panel decision functions subject only to the assumed deliberation guarantee, rather than to specific voting rules. The appendix contains substantial proofs for the upper and lower bounds, and the high-level framework is a promising way to make the panel-size question quantitative. The main qualifications are that the guarantees are conditional on uniform panel selection and on panel-level behavior assumptions, both of which are stated explicitly by the authors.","major_comments":[{"comment":"The proof of the T=2 tightness lower bound is invalid as written. The claim that, conditioned on the panel omitting the pivotal agent, the panel decision function selects 0 with probability at least 1/2 or selects 1 with probability at least 1/2 is false for balanced panels: when a panel contains equal numbers of 0- and 1-agents, every point in [0,1] is panel-optimal, so an admissible tie-breaking rule may select an interior point. Concretely, for k=2 with population locations (0,0,1,1,0), let the decision function return the unique median when one exists and return 0.5 on balanced panels. This function is a valid panel-optimal choice, but enumerating all C(5,2)=10 panels gives failure probability 1/10 for the event d(q(S),q*) >= 2*Social-Opt, not the claimed 1/4. Thus the assertion that the guarantee of Theorem 4.2 does not hold for T=2 is not established by the supplied argument. The theorem may be repairable, for example by taking K agents at each endpoint with K large relative to k, but a corrected proof is needed.","section":"Appendix E.1, Theorem 4.9"},{"comment":"The reduction steps for the outlier upper bound do not account for ties among panel-optimal facilities. In the proof of Lemma 4.6, the strict inequality sum_{i in S} d_X(q*,x_i) > sum_{i in S} d_X(qbar(S,I),x_i) is used whenever qbar(S,I) differs from q*, but this fails when q* is also panel-optimal. For example, with population locations (0,1,1), q*=1, T=3, and panel S={0,1}, both 0 and 1 have panel cost 1, so a far point can be panel-optimal while q* is also a minimizer. In the reduced instance J the image of q* may then be chosen by the tie-breaking rule, and condition (i) fails for the selected point. The same issue reappears in Lemma 4.8 when q* and a far alternative have equal f_S values. The proof should track the set of panel-optimal points (equivalently, worst-case tie-breaking) rather than an arbitrary selected point; as written, Theorem 4.2 does not control adversarial tie-breaking.","section":"Lemmas 4.6 and 4.8 (proof of Theorem 4.2)"},{"comment":"The statement of Theorem 3.6 says the panel size is k = Omega((1/eps)^2 (m log(1/eps) + log(1/delta))), but the proof and the intended upper bound require k = O(...); this is the opposite inequality and must be corrected. In the same proof, the covering condition ||y - y'||_1 <= eps/(2B) gives |sum_j y_j/B - sum_j y'_j/B| <= eps/(2B^2), which is not at most eps/2 when B < 1. The argument therefore needs a covering radius of eps*B/2 for the budget-fraction comparison (the covering number remains O((1/eps)^m) after scaling the simplex), or an equivalent repair. These are technical fixes, but they are needed for the proof of the core-transfer claim to be valid for the full stated range of budgets.","section":"Theorem 3.6"}],"minor_comments":[{"comment":"The proof uses an eps/(12 rho)-covering but then claims the panel is (eps/12)-representative; with this combination, inequality (2) only follows when rho=1. The intended argument presumably needs (eps/(12 rho))-representativeness, which is consistent with the stated O((1/eps)^2 m log(1/eps)) bound since rho is a constant.","section":"Theorem 3.2, proof"},{"comment":"In the proof, the definition of S2 should be the complement of S1; as printed, 'S2 = [n] \\ S2' is a typo and should read S2 = [n] \\ S1.","section":"Lemma 4.5"},{"comment":"The equivalence 'q(S)=0 iff sum_{i in S} x_i <= (T/2)k' assumes a specific tie-breaking rule at equality; for the upper bound this is harmless because q(S)=T implies sum_{i in S} x_i >= (T/2)k, but the text should state the implication rather than the equivalence.","section":"Theorem 4.2, proof"},{"comment":"The 'without loss of generality' assumption that q1 != 1 and q2 != 1 is not valid when the decision function returns (1,1) on the all-zero input; in that case a simpler instance with all agents at 0 already gives the desired failure, so the proof should split into cases.","section":"Theorem 4.15"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid contribution with a coherent framework and extensive appendix proofs, but the facility-location lower-bound proof for T=2 and the tie-handling in the outlier reduction both have genuine gaps that affect stated claims. I believe these are repairable within the scope of the paper, and the participatory-budgeting issues are constant/typo-level, so I do not recommend rejection. The authors should be asked to either fix the reductions or explicitly weaken the claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a serious look. The Wasserstein representativeness definition (Section 2.2) is genuinely new in the sortition literature and gives a panel-size-independent benchmark that makes panel complexity comparisons meaningful. The reduction lemmas (2.3 and 2.4) are clean, and Theorem 2.5 is a strong general tool with immediate applications. I spot-checked the participatory budgeting upper bounds (Theorems 3.2 and 3.6) and the facility location upper bounds (Theorems 4.2 and 4.11); the core-coalition transfer and the metric-map reduction both hold, and the lower bounds via camouflaged populations are clever and correctly reduce to external sample complexity results.\n\nThat said, the reader's report underweights one real problem. The stress-test note on Theorem 4.9 is correct: the proof assumes that a panel decision function on a balanced panel (k zeros, k ones) chooses an endpoint with probability at least 1/2. That is false. A valid panel-optimal function can tie-break by choosing the midpoint, and then the distance to the population optimum is less than 2*Opt. The concrete k=2 example in the stress-test is correct and kills the proof as written. This is not a cosmetic gap: the theorem's claim that the upper bound fails for T=2 is currently unsupported. It may be salvageable with a different adversarial construction, but as written it needs to be fixed or removed.\n\nOther issues are minor and fixable: Theorem 3.6 says k = Omega where it should be O; Theorem 4.11 applies Theorem 2.5 to features bounded by a constant T while Theorem 2.5 is stated for [0,1]-valued features (scaling fixes this); and there are '/BD' placeholder artifacts and small typos. None of these affect the main upper bounds.\n\nThe paper is honest about its modeling assumptions—uniform sampling and panel decisions satisfying exact or approximate welfare/core guarantees—and flags them in Section 5, which is appropriate.\n\nWho this is for: computational social choice researchers, especially those working on sortition, participatory budgeting, or sample-based facility location. The upper-bound framework will likely be reused. It deserves peer review, but the referee should require a fix or removal of Theorem 4.9 before acceptance.","headline":"A genuinely useful representativeness framework with near-tight upper bounds, but the T=2 tightness result has a real proof gap that needs fixing before the paper is accepted.","tokens_in":35143,"tokens_out":4214,"would_cite":true,"duration_ms":45565,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B14","91B72"],"pacs":[],"model":"deepseek-v4-flash","headline":"Randomly selected panels of size $O((1/\\varepsilon)^2(\\log \\ell + \\log(1/\\delta)))$ are representative of the whole population, and near-tight panel complexity bounds follow for participatory budgeting and facility location.","keywords":["sortition","panel complexity","representative panels","Wasserstein distance","participatory budgeting","facility location","core fairness","sampling without replacement"],"falsifier":"For a population split evenly between 0 and 1, simulate uniform $k$-panels and compare the measured fraction failing $\\varepsilon$-representativeness with the concentration bound $\\exp(-\\varepsilon^2 k/4)$; any systematic excess would falsify the lemma on which all upper bounds rest.","tokens_in":34037,"feed_emoji":"🗳️","tokens_out":16214,"duration_ms":151584,"temperature":0.7,"pith_summary":"Sortition asks how many randomly chosen citizens are enough for a panel to make decisions that can stand in for the whole population. This paper answers by showing that distributional representativeness is a transferable property: if the panel's and the population's feature distributions are $\\varepsilon$-close in Wasserstein distance, then deliberation guarantees valid on the panel carry over to the population. A uniformly random panel of size $O((1/\\varepsilon)^2(\\log \\ell + \\log(1/\\delta)))$ is $\\varepsilon$-representative for any $\\ell$ real-valued features with probability $1-\\delta$. From this, near-tight panel complexity bounds follow for participatory budgeting with Lipschitz preferences and for facility location, including outlier control in arbitrary metric spaces. The practical upshot is that panel size can be set from the desired accuracy, confidence, and problem dimension rather than by tradition.","feed_headline":"Random panels of size O(1/ε²) are enough to represent everyone","feed_subtitle":"New near-tight bounds set citizen-panel sizes for budgeting and facility location.","key_machinery":"The engine is the Wasserstein-1 distance $W(\\varphi_{[n]}^f,\\varphi_S^f)$ between the empirical feature distributions of the population and the panel, where the metric-space distance is bounded by $1$. Two lemmas carry the analysis: one uses convexity to reduce sampling without replacement to the easier case of independent sampling, and the other supplies a concentration inequality for the Wasserstein distance under sampling without replacement. These turn representativeness into a sample-complexity statement, and an $\\varepsilon$-covering of the policy space converts the social-choice objective into finitely many real-valued features. The lower bounds are mounted by camouflaged populations, where any panel smaller than $\\Omega(hw^2)$ cannot distinguish which of two hidden majority directions is present.","core_discovery":"The central claim is that a uniformly random panel can provably inherit the decision quality of the full population, provided the panel's own decision satisfies a stated guarantee. The paper defines a panel $S$ to be $\\varepsilon$-representative for feature $f$ when the Wasserstein distance between the population distribution $\\varphi_{[n]}^f$ and the panel distribution $\\varphi_S^f$ is at most $\\varepsilon$, and proves that this holds simultaneously for any $\\ell$ real-valued features once $k=O((1/\\varepsilon)^2(\\log \\ell + \\log(1/\\delta)))$. That single transfer lemma drives every positive result: a participatory-budgeting panel whose allocation is near-optimal or core-fair for its members yields an allocation that is near-optimal or core-fair for the whole population, and a facility-location panel that minimizes total distance to its members yields a near-optimal facility in metric spaces whose Assouad dimension (a covering-scale notion of dimension) is bounded. The paper also gives almost matching lower bounds via camouflaged populations, which look nearly uniform to any small panel while hiding a sign vector that a successful decision rule would have to recover.","pith_inferences":["Because the representativeness bound is independent of the population size $n$, the same formula applies to a small town and a large country; a convener learning panel size from this theorem would never need to know the population count.","The transfer argument is modular: any social-choice setting whose objective can be approximated by finitely many Lipschitz features should inherit a similar $O((1/\\varepsilon)^2 \\log(1/\\varepsilon))$ panel complexity, making indivisible participatory budgeting and committee selection natural next targets.","If stratified or quota-based selection is introduced, the Wasserstein transfer would need a weighted or conditional version; these uniform-selection bounds are the natural baseline to test whether stratification can shrink panels without losing representativeness.","The impossibility of a purely multiplicative guarantee in participatory budgeting means additive slack is intrinsic, so any deployed sortition-based budgeting process should publish an explicit additive error budget alongside the chosen allocation."],"forward_implications":["A participatory-budgeting panel of size $O((1/\\varepsilon)^2 m\\log(1/\\varepsilon))$ whose allocation is within additive $\\tau$ and multiplicative $\\rho$ of the panel optimum produces expected population social cost within $\\rho\\cdot\\mathrm{Opt}+\\tau+\\varepsilon$.","A panel of size $O((1/\\varepsilon)^2(m\\log(1/\\varepsilon)+\\log(1/\\delta)))$ that is $(\\eta,\\tau,\\rho)$-core-fair for its members is $(\\eta+\\varepsilon,\\tau+\\varepsilon,\\rho)$-core-fair for the whole population with probability at least $1-\\delta$.","In any metric space, a panel that minimizes total distance to its members keeps the facility within $T\\cdot\\mathrm{Opt}$ with probability $1-\\delta$ once $k=O(\\log(1/\\delta))$, for any constant $T>2$, and no such guarantee holds at $T=2$.","In a metric space of Assouad dimension $t$, panel size $O((1/\\varepsilon)^2 t\\log(1/\\varepsilon))$ gives expected social cost at most $(1+\\varepsilon)\\mathrm{Opt}$, and the lower bound $\\Omega((1/\\varepsilon)^2 t)$ for the $\\ell_\\infty$ cube shows the dependence on $t$ is necessary.","For multiple facilities on the line, $k=O(1/\\varepsilon^2)$ suffices for an additive $\\varepsilon$ guarantee on expected social cost, independent of the number of facilities."],"supporting_citations":[{"why":"Supplies the probability inequality for sums of bounded random variables used to compare sampling with and without replacement.","marker":"[36]"},{"why":"Provides the bounded-differences property of Wasserstein distance used by the concentration inequality.","marker":"[51]"},{"why":"Supplies the McDiarmid-style concentration bound for sampling without replacement used to derive Lemma 2.4.","marker":"[47]"},{"why":"Gives the expected Wasserstein bound for independent samples from which Theorem 2.5 starts.","marker":"[14]"},{"why":"Supplies the sample-complexity lower bound behind the camouflaged-population constructions used for lower bounds.","marker":"[16, Lemma 5.10]"},{"why":"The previous tight panel complexity result for facility location in finite metric spaces that this paper extends to infinite spaces and other settings.","marker":"[9]"},{"why":"Defines the participatory budgeting model and its core, on which the approximate core fairness definitions rest.","marker":"[19]"}],"fun_headline_variants":["Random panels of size O(1/ε²) represent everyone","O(1/ε²) random citizens can represent a whole population","Small random panels match population-wide decisions near-optimally","Near-tight bounds set citizen panel size for fair collective choices","For budgeting and facility location, O(1/ε²) panel members suffice"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that panels are drawn uniformly at random from the whole population and that the panel's actual decision process meets the assumed guarantee, such as near-optimal panel cost or panel-level core fairness; if selection is stratified or deliberations behave differently, the stated sizes have no force.","fun_headline_variants_meta":{"raw":{"variants":["Random panels of size O(1/ε²) represent everyone","O(1/ε²) random citizens can represent a whole population","Small random panels match population-wide decisions near-optimally","Near-tight bounds set citizen panel size for fair collective choices","For budgeting and facility location, O(1/ε²) panel members suffice"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000471,"raw_usage":{"total_tokens":2356,"prompt_tokens":970,"completion_tokens":1386,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":586,"completion_tokens_details":{"reasoning_tokens":1294}},"tokens_in":586,"tokens_out":1386,"duration_ms":13636,"temperature":1.0,"reasoning_tokens":1294,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:29:34.628968+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a population split evenly between 0 and 1, simulate uniform $k$-panels and compare the measured fraction failing $\\varepsilon$-representativeness with the concentration bound $\\exp(-\\varepsilon^2 k/4)$; any systematic excess would falsify the lemma on which all upper bounds rest.","supporting_citations":[{"cited_title":"Hoeffding","cited_arxiv_id":null,"evidence_quote":"Supplies the probability inequality for sums of bounded random variables used to compare sampling with and without replacement."},{"cited_title":"Sambale and A","cited_arxiv_id":null,"evidence_quote":"Supplies the McDiarmid-style concentration bound for sampling without replacement used to derive Lemma 2.4."},{"cited_title":"Caragiannis, E","cited_arxiv_id":null,"evidence_quote":"The previous tight panel complexity result for facility location in finite metric spaces that this paper extends to infinite spaces and other settings."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the participatory budgeting model and its core, on which the approximate core fairness definitions rest."}],"review_version":1}