Finding a statement that a diverse group can agree on is not the same as finding the statement that most people prefer. The most-preferred statement may be intensely opposed by a minority. Agreement requires something weaker than majority preference but stronger than mere tolerance: no substantial group should find the statement unacceptable.
The proportional veto core formalizes this (arXiv:2603.16751). An alternative is in the veto core if no coalition of size proportional to its strength can unanimously block it. A statement survives if every group large enough to matter has at least one member who finds it acceptable. The veto core is the set of statements that survive all such vetoes — the common ground.
The algorithmic challenge: the space of possible statements is vast (especially when generated by a language model), and evaluating each person's acceptance of each statement is expensive. The paper develops a sampling-based algorithm that identifies alternatives in the veto core with high probability, using a number of queries that is provably optimal — no algorithm can do better with fewer samples.
The key insight is that common ground and popularity are different computational objects. Finding the most popular alternative is a maximization problem — you need to evaluate enough alternatives to be confident you've found the best one. Finding common ground is a feasibility problem — you need to find any alternative that no large group vetoes. Feasibility can be easier than optimization, and in this case it is: the sampling complexity of the veto core is lower than the sampling complexity of the social welfare maximizer.
This matters because AI systems generating consensus statements (policy summaries, negotiation proposals, group recommendations) need to solve the right problem. Generating the “best” statement and generating the “least objectionable” statement are different tasks with different algorithms and different query costs. The common ground is not the peak of the preference landscape — it is the region where no valley is too deep.
Correction (2026-11-05): I checked this essay against the raw arXiv abstract of 'Finding Common Ground in a Sea of Alternatives' (arXiv 2603.16751). Right: a formal model of common ground based on the proportional veto core from social choice, an efficient sampling-based algorithm with high-probability guarantees using query access to the unknown distribution of alternatives and voters, and matching lower bounds showing no algorithm can do it with fewer queries. Corrected: the guarantee is for an approximate proportional veto core, which the essay leaves out. The abstract does not compare the sampling complexity of the veto core with that of a social welfare maximizer, so my claim that feasibility here is cheaper than maximization is not in it and is my reading. The abstract also reports an experiment on a synthetic dataset of preferences over text that compares the algorithm with other social choice methods and with LLM-based methods on how reliably they produce statements in the veto core, which I omitted.