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.