Finding Common Ground in a Sea of Alternatives

Jay Chooi; Paul Gölz; Ariel D. Procaccia; Benjamin Schiffer; Shirley Zhang

cs.GTMar 17, 2026

Finding Common Ground in a Sea of Alternatives

Authors: Jay Chooi, Paul Gölz, Ariel D. Procaccia, Benjamin Schiffer, Shirley Zhang

Organizations: Paulson School of Engineering and Applied Sciences, Harvard University · School of Operations Research and Information Engineering, Cornell University · Department of Statistics, Harvard University

Abstract

We study the problem of selecting a statement that finds common ground across diverse population preferences. Generative AI is uniquely suited for this task because it can access a practically infinite set of statements, but AI systems like the Habermas machine leave the choice of generated statement to a voting rule. What it means for this rule to find common ground, however, is not well-defined. In this work, we propose a formal model for finding common ground in the infinite alternative setting based on the proportional veto core from social choice. To provide guarantees relative to these infinitely many alternatives and a large population, we wish to satisfy a notion of proportional veto core using only query access to the unknown distribution of alternatives and voters. We design an efficient sampling-based algorithm that returns an alternative in the (approximate) proportional veto core with high probability and prove matching lower bounds, which show that no algorithm can do the same using fewer queries. On a synthetic dataset of preferences over text, we confirm the effectiveness of our sampling-based algorithm and compare other social choice methods as well as LLM-based methods in terms of how reliably they produce statements in the proportional veto core.

Figures & tables

Figure 1: Our experiment setup. We generate statements conditioned on synthetic persona, and build preference profiles from voters conditioned on synthetic persona. We then evaluate various voting rules, including those powered by LLMs, and compare their critical epsilons.

Figure 2: CDF of critical epsilons for the chosen alternatives of various voting rules for the three polarizing topics. The smaller the epsilons (the closer the line is to the top-left corner), the better at finding common ground the voting method is.

Method	Abortion	Electoral College	Healthcare	Policing	Environment	Trust in Institutions
VBC	0.0008	0.0000	0.0003	0.0003	0.0000	0.0014
Borda	0.0075	0.0023	0.0005	0.0015	0.0014	0.0025
Schulze	0.0108	0.0040	0.0030	0.0040	0.0033	0.0033
IRV	0.0203	0.0233	0.0063	0.0133	0.0086	0.0050
Plurality	0.0865	0.0460	0.0158	0.0268	0.0142	0.0128
Random	0.0609	0.0108	0.0082	0.0103	0.0108	0.0072

Table 1: Mean critical epsilons for various voting rules across various topics. The smallest epsilon for each topic is bolded.

Method	Abortion	Electoral College	Healthcare	Policing	Environment	Trust in Institutions
VBC	0.0008	0.0000	0.0003	0.0003	0.0000	0.0014
GPT-Blind	0.0103	0.0093	0.0080	0.0045	0.0085	0.0200
GPT-Synthesize	0.0055	0.0108	0.0090	0.0128	0.0168	0.0238
GPT-Synth+Rank.	0.0030	0.0053	0.0038	0.0025	0.0080	0.0095
GPT-Synth.+Pers.	0.0030	0.0060	0.0040	0.0040	0.0058	0.0105
Random Insertion	0.0700	0.0100	0.0108	0.0100	0.0073	0.0110

Table 2: Mean critical epsilons for VBC, generative voting rules and random baselines across various topics. Smallest epsilon for each topic is bolded. Under “Random Insertion,” we sample a random statement from the 815 global statements that are not in the

100\times 100

preference profile and use the same insertion program that we use for the generative methods.

Figure 3: Critical epsilons for the winners of various generative voting rules on conservative voters for polarizing topics. Generative voting rules consistently do worse than VBC and sometimes even the random baseline.

Method	Abortion	Electoral College	Healthcare	Policing	Environment	Trust in Institutions
VBC	0.0013	0.0003	0.0003	0.0000	0.0003	0.0000
GPT-Blind	0.2775	0.0263	0.0050	0.0225	0.0843	0.0220
GPT-Synthesize	0.2313	0.0263	0.0178	0.0393	0.0230	0.0305
GPT-Synth+Rank.	0.1980	0.0295	0.0120	0.0215	0.0280	0.0048
GPT-Synth.+Pers.	0.1065	0.0088	0.0048	0.0033	0.0065	0.0010
Random Insertion	0.1360	0.1013	0.0418	0.0640	0.0153	0.0135

Table 3: Mean critical epsilons for VBC, generative voting rules and random baselines across various topics for conservative voters. Smallest epsilon for each topic is bolded.

Appendix figures & tables18 assets

Supplementary material from the paper’s appendix.

Appendix

\mu_{\mathcal{D}}(X_{0})+\sum_{x\in X\setminus X_{0}}c_{x}\geq\gamma.

Appendix

ALGORITHM 3 Vote by

\gamma

-Veto

Figure 4: Likert scores of 100 voters on 100 generated statements. Higher Likert scores indicate higher agreement. The most polarizing topics have average Likert scores close to 5 and a wide spread. The top 3 topics by polarization are abortion, Electoral College, and healthcare. The bottom 3 polarizing topics are environment, policing, and public trust in elections.

Panel of Figure 5 — Figure 5: CDF of critical epsilons across various topics (top three topics by degree of polarization). The leftmost subplot (Persona) allows for clearer analysis than other alternative generation methods.

Panel of Figure 6 — Figure 6: CDF of critical epsilons across various topics (bottom three topics by degree of polarization). The leftmost subplot (Persona) allows for clearer analysis than other alternative generation methods.

Mitigation	Reasoning	Unique	Pres. Order	API	Avg Time
	Effort	Rankings	Corr.	Calls	/Call
Top-K/Bottom-K	minimal	$79/100$	$0.029$	$1307$	$3.3$ s
Top-K/Bottom-K	low	$98/100$	$0.043$	$567$	$11.1$ s
Top-K/Bottom-K	medium	$100/100$	$0.033$	$\sim 500$	$\sim 30$ s
Scoring	minimal	$99/100$	$-0.126$	$178$	$8.9$ s
Scoring	low	$100/100$	$-0.987$	$100$	$16.0$ s

Appendix

Table 4: Degeneracy Mitigation Experiment Results

Panel of Figure 7 — Figure 7: Comparison of critical epsilons across voting rules on various real-world datasets from PrefLib. Standard errors depicted.

Panel of Figure 8 — Figure 8: Binned scatter plots comparing various statement insertion methods by plotting reconstruction position versus original position. Error units are in the ranks, e.g. an error of -20 means that the method ranks the new statement on average 20 positions below its original.

Method	Abortion	Electoral College	Healthcare	Policing	Environment	Trust in Institutions
VBC	0.0161	0.0000	0.0061	0.0061	0.0000	0.0230
Borda	0.1432	0.0200	0.0100	0.0366	0.0230	0.0265
Schulze	0.1432	0.0361	0.0300	0.0522	0.0300	0.0265
IRV	0.2327	0.1244	0.0500	0.1427	0.0925	0.0265
Random	0.3101	0.1700	0.1200	0.1401	0.1801	0.0801
Plurality	0.3344	0.2088	0.1720	0.1583	0.1030	0.0990

Appendix

Table 5: P99 of critical epsilons for various voting rules across various topics

Method	Abortion	Electoral College	Healthcare	Policing	Environment	Trust in Institutions
VBC	95.0000	100.0000	97.5000	97.5000	100.0000	91.6667
Borda	87.5000	85.0000	95.0000	97.5000	91.6667	83.3333
Schulze	75.0000	77.5000	85.0000	87.5000	80.5556	77.7778
IRV	65.0000	42.5000	75.0000	75.0000	69.4444	66.6667
Random	58.1000	71.4000	72.4000	71.7000	72.6667	73.7778
Plurality	45.0000	22.5000	57.5000	62.5000	58.3333	58.3333

Appendix

Table 6: Percentage of critical epsilons that are less than 0.01 for various voting rules across various topics

Figure 9: CDF of critical epsilons for least controversial topics for various voting rules.

Method	Abortion	Electoral College	Healthcare	Policing	Environment	Trust in Institutions
VBC	0.0008	0.0000	0.0003	0.0003	0.0000	0.0014
GPT-Select	0.0038	0.0048	0.0048	0.0108	0.0103	0.0094
GPT-Sel+Rank	0.0143	0.0365	0.0163	0.0085	0.0075	0.0056
GPT-Sel+Pers	0.0125	0.0028	0.0095	0.0195	0.0100	0.0067
GPT-Full	0.0013	0.0050	0.0068	0.0055	0.0014	0.0053
GPT-Full+Rank	0.0593	0.0425	0.0055	0.0115	0.0114	0.0075

Appendix

Table 7: Mean critical epsilons for VBC, voting rules with GPT as a selector and a random baseline across various topics. Smallest epsilons are bolded.

Method	Abortion	Electoral College	Healthcare	Policing	Environment	Trust in Institutions
VBC	0.0161	0.0000	0.0061	0.0061	0.0000	0.0230
GPT-Select	0.0505	0.0422	0.0361	0.1166	0.1190	0.0400
GPT-Sel+Rank	0.1859	0.2088	0.2149	0.0722	0.0820	0.0265
GPT-Sel+Pers	0.1954	0.0422	0.0900	0.0900	0.0865	0.0365
GPT-Full	0.0100	0.0322	0.0666	0.0805	0.0100	0.0400
GPT-Full+Rank	0.3461	0.2205	0.0461	0.0922	0.0925	0.0465

Appendix

Table 8: P99 critical epsilons for for VBC, voting rules with GPT as a selector and a random baseline across various topics. Smallest epsilon for each topic is bolded.

Method	Abortion	Electoral College	Healthcare	Policing	Environment	Trust in Institutions
VBC	0.950	1.000	0.975	0.975	1.000	0.917
GPT-Select	0.850	0.775	0.750	0.725	0.750	0.667
GPT-Sel+Rank	0.700	0.450	0.700	0.825	0.694	0.639
GPT-Sel+Pers	0.900	0.900	0.775	0.550	0.778	0.722
GPT-Full	0.875	0.700	0.675	0.875	0.861	0.778
GPT-Full+Rank	0.500	0.350	0.775	0.700	0.611	0.583

Appendix

Table 9: Percentage of critical epsilons that are less than 0.01 for VBC, voting rules with GPT as a selector and a random baseline across various topics. Largest percentages for each topic is bolded.

Method	Abortion	Electoral College	Healthcare	Policing	Environment	Trust in Institutions
VBC	0.0161	0.0061	0.0061	0.0000	0.0061	0.0000
GPT-Blind	0.5005	0.0900	0.0461	0.1022	0.3588	0.1161
GPT-Synthesize	0.3300	0.1832	0.0944	0.2298	0.1166	0.3461
GPT-Synth+Rank.	0.3544	0.1261	0.1144	0.1022	0.2722	0.0300
GPT-Synth.+Pers.	0.2700	0.0461	0.0322	0.0200	0.0361	0.0100
Random Insertion	0.3261	0.4805	0.3683	0.3600	0.1000	0.2286

Appendix

Table 10: P99 critical epsilons for for VBC, generative voting rules and random baselines across various topics for conservative voters. Smallest epsilon for each topic is bolded.

Method	Abortion	Electoral College	Healthcare	Policing	Environment	Trust in Institutions
VBC	0.900	0.975	0.975	1.000	0.975	1.000
GPT-Blind	0.000	0.225	0.750	0.425	0.100	0.275
GPT-Synthesize	0.000	0.350	0.325	0.175	0.175	0.325
GPT-Synth+Rank.	0.025	0.400	0.575	0.425	0.500	0.675
GPT-Synth.+Pers.	0.250	0.550	0.725	0.750	0.575	0.900
Random Insertion	0.425	0.100	0.575	0.400	0.525	0.750

Appendix

Table 11: Percentage of critical epsilons that are less than 0.01 for VBC, generative voting rules and random baselines across various topics for conservative voters. Largest percentages for each topic is bolded.

Method	Abortion	Electoral College	Healthcare	Policing	Environment	Trust in Institutions
VBC	0.0000	0.0018	0.0000	0.0005	0.0000	0.0003
GPT-Blind	0.0185	0.0280	0.0113	0.0048	0.0035	0.0215
GPT-Synthesize	0.0095	0.0103	0.0058	0.0135	0.0108	0.0200
GPT-Synth+Rank.	0.0055	0.0075	0.0005	0.0025	0.0025	0.0093
GPT-Synth.+Pers.	0.0058	0.0050	0.0013	0.0033	0.0018	0.0143
Random Insertion	0.2205	0.0130	0.0220	0.0532	0.0388	0.0120

Appendix

Table 12: Mean critical epsilons for for VBC, generative voting rules and random baselines across various topics for progressive voters. Smallest epsilon for each topic is bolded.

Method	Abortion	Electoral College	Healthcare	Policing	Environment	Trust in Institutions
VBC	0.0000	0.0405	0.0000	0.0122	0.0000	0.0069
GPT-Blind	0.1622	0.1805	0.0822	0.0261	0.0283	0.0922
GPT-Synthesize	0.0844	0.0600	0.0300	0.1710	0.0927	0.1161
GPT-Synth+Rank.	0.0200	0.0461	0.0100	0.0322	0.0161	0.0661
GPT-Synth.+Pers.	0.0200	0.0300	0.0161	0.0300	0.0100	0.1083
Random Insertion	0.6444	0.1781	0.2544	0.3966	0.3149	0.0761

Appendix

Table 13: P99 critical epsilons for for VBC, generative voting rules and random baselines across various topics for progressive voters. Smallest epsilon for each topic is bolded.

Method	Abortion	Electoral College	Healthcare	Policing	Environment	Trust in Institutions
VBC	1.000	0.950	1.000	0.975	1.000	0.969
GPT-Blind	0.500	0.350	0.600	0.650	0.725	0.350
GPT-Synthesize	0.600	0.500	0.575	0.625	0.525	0.350
GPT-Synth+Rank.	0.650	0.600	0.950	0.850	0.775	0.650
GPT-Synth.+Pers.	0.650	0.650	0.900	0.800	0.825	0.500
Random Insertion	0.275	0.600	0.675	0.625	0.550	0.600

Appendix

Table 14: Percentage of critical epsilons that are less than 0.01 for VBC, generative voting rules and random baselines across various topics for progressive voters. Largest percentages for each topic is bolded.

Query Complexity

Query complexity studies how many oracle or data-access queries algorithms need to learn, decide, estimate, or optimize a problem.

See all 30 papers

Learning Unanimously Acceptable Lotteries via Queries
Apr 19, 2026Davin Choo, Paul W. Goldberg, Nicholas TehQuery Complexity Learning-Augmented Algorithms
Harvard University, USA · University of Oxford, UK
Generating Place-Based Compromises Between Two Points of View
Apr 27, 2026Sumanta Bhattacharyya, Francine Chen, Scott Carter +6LLM Alignment Prompt Engineering
University of Illinois Chicago · Toyota Research Institute
When Metropolis and Hastings Meet Bradley and Terry: Exact MCMC From Preference Voting
Sep 1, 2026Ariel Smogorghevski, Nir Rosenfeld, Yaniv RomanoMarkov Chain Monte Carlo Markov Models
Department of Data and Decision Sciences, Technion – Israel Institute of Technology · Department of Computer Science, Technion – Israel Institute of Technology · Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology

Apr 19, 2026J/K move · Enter open · S save

Learning Unanimously Acceptable Lotteries via Queries

Davin Choo, Paul W. Goldberg, Nicholas Teh

Harvard University, USA · University of Oxford, UK

Query Complexity Learning-Augmented Algorithms Preference Learning Preference Elicitation

Open paper AskPDF arXiv

Many high-stakes AI deployments proceed only if every stakeholder deems the system acceptable relative to their own minimum standard. With randomization over a finite menu of options, this becomes a feasibility question: does there exist a lottery over options that clears all stakeholders' acceptability bars? We study a query model where the algorithm proposes lotteries and receives only binary accept/reject feedback. We give deterministic and randomized algorithms that either find a unanimously acceptable lottery or certify infeasibility; adaptivity can avoid eliciting many stakeholders' constraints, and randomization further reduces the expected elicitation cost relative to full elicitation. We complement these upper bounds with worst-case lower bounds (in particular, linear dependence on the number of stakeholders and logarithmic dependence on precision are unavoidable). Finally, we develop learning-augmented algorithms that exploit natural forms of advice (e.g., likely binding stakeholders or a promising lottery), improving query complexity when predictions are accurate while preserving worst-case guarantees.

Abstract

Query Complexity

Explore similar work

Learning Unanimously Acceptable Lotteries via Queries

Generating Place-Based Compromises Between Two Points of View

When Metropolis and Hastings Meet Bradley and Terry: Exact MCMC From Preference Voting