Finding Common Ground in a Sea of Alternatives

This paper proposes a formal model and an efficient sampling-based algorithm for finding common ground across diverse preferences in an infinite alternative space by targeting the proportional veto core, while also establishing theoretical query lower bounds and validating the approach through synthetic experiments.

The Gist

Imagine you are trying to organize a massive town hall meeting with thousands of people who all have very different opinions. Some are loud, some are quiet, some are angry, and some are hopeful. Your goal is to find one single sentence that everyone can agree on—a "common ground" statement that doesn't make anyone feel ignored or attacked.

This paper is about how to use Artificial Intelligence (AI) to find that perfect sentence, and why the usual ways of doing it often fail.

The Problem: The "Tyranny of the Majority"

Think of the current way we use AI for this (like the "Habermas machine" mentioned in the paper) as a popularity contest.

• The AI generates 16 possible sentences.
• Everyone votes on them.
• The winner is the one with the most votes.

The Flaw: In a popularity contest, a small group of people (a minority) can be completely ignored. If 51% of people hate a specific idea, but 49% love it, the 49% gets nothing. The "common ground" becomes just "what the majority wants," which isn't true common ground; it's just a majority rule.

The Solution: The "Veto Core" (The Safety Net)

The authors propose a new way to think about fairness called the Proportional Veto Core (PVC).

The Analogy: The "No-Go Zone" Game
Imagine you are picking a movie for a group of friends.

• The Old Way: You pick the movie with the most "Yes" votes.
• The New Way (PVC): You ask, "Is there a movie that a specific group of friends can veto?"

If a group of friends makes up 30% of the crowd, they have the power to say, "We will veto any movie that isn't in our top 70% of choices."

• If a movie is so polarizing that a large chunk of people (say, 30%) would rather watch anything else than watch it, that movie is blocked. It cannot be the winner.
• The "Common Ground" is any movie that nobody has the power to block.

This ensures that even small groups have a say. If 10% of people hate a statement, and that statement is terrible for them, the math says they have enough "veto power" to knock it out of the running.

The Challenge: The Infinite Ocean of Ideas

Here is the tricky part: In the real world, there aren't just 16 movie options. There are infinite possible sentences an AI could write.

• How do you find the one perfect sentence in an infinite ocean of text?
• You can't ask everyone to vote on every single sentence; that would take forever.

The Paper's Innovation: The "Taste Tester" Algorithm
The authors designed a clever, efficient sampling method. Imagine you are a chef trying to find the perfect soup recipe, but there are infinite ingredients.

1. Generative Queries (The Soup Pot): You ask the AI to "stir the pot" and pull out a random sample of 100 sentences (like scooping a spoonful of soup).
2. Discriminative Queries (The Taste Test): You don't ask people to rank all 100. Instead, you ask a voter, "Which of these two is the worst?" or "Which of these is your least favorite?"
3. The Elimination Process: You keep asking voters to eliminate their least favorite options from the sample. You do this over and over.
4. The Result: Eventually, you are left with one sentence that no one in your sample hated enough to eliminate.

The paper proves mathematically that this method is fast and guaranteed to find a sentence that represents true common ground, even if you only ask a tiny fraction of the total population.

The Experiments: AI vs. Humans

The researchers tested this against real-world scenarios using AI personas (fake people with different political views).

• The Results:
  • Old Methods (Schulze, Plurality): These often picked statements that were polarizing. They were like picking a movie that 51% loved but 49% hated.
  • The New Method (Veto Core): This method consistently found statements that almost everyone could accept.
  • AI Generators: When they asked the AI to just "write a new sentence" without using their math, the AI sometimes did well, but often failed if it didn't understand the specific mix of people. The math-based method was much more reliable.

The Big Takeaway

This paper gives us a mathematical safety net for AI democracy.

It tells us that to find true agreement in a divided world, we shouldn't just look for what the majority likes. Instead, we should look for what nobody is allowed to hate. By using a "veto" system where minority groups can block extreme options, we ensure that the final decision is a true bridge between all sides, not just a victory for the loudest voice.

In short: Don't just count the votes; check who has the power to say "No." If you can't say "No" to a statement, then it's probably a good one for everyone.

Technical Summary

1. Problem Statement

The paper addresses the challenge of selecting a single statement that represents common ground across a diverse population with polarized preferences. This problem is increasingly relevant in the era of Large Language Models (LLMs), which can generate a practically infinite set of alternative statements (e.g., for deliberation platforms like the "Habermas machine").

Key Challenges:

• Infinite Alternative Space: Traditional social choice theory assumes a finite set of candidates. Here, the space of statements is continuous or infinite, generated by an LLM from an unknown distribution.
• Limitations of Current Methods: Existing AI deliberation tools often rely on majoritarian voting rules (like Schulze or Plurality). These rules tend to override minority preferences, failing to guarantee that the selected statement is acceptable to cohesive minority groups.
• Lack of Formal Guarantees: There is no rigorous definition of "common ground" that ensures minority influence in an infinite alternative setting, nor are there efficient algorithms to find such statements with limited access to voter preferences.

2. Methodology and Model

2.1 Theoretical Framework: $\epsilon$-Proportional Veto Core ($\epsilon$-PVC)

The authors propose the $\epsilon$-Proportional Veto Core ($\epsilon$-PVC) as the formal definition of common ground.

• Definition: An alternative $a$ is in the $\epsilon$-PVC if no coalition of voters $T$ can "block" it. A coalition blocks $a$ if they can find a set of alternatives $S$ such that:
  1. Every voter in $T$ prefers every alternative in $S$ to $a$.
  2. The measure (probability mass) of $S$ under the distribution $D$ is greater than $1 - \frac{|T|}{n} + \epsilon$.
• Intuition: If a coalition represents a fraction $p$ of the population, they can veto any statement unless there is a set of alternatives with mass $> 1-p$ that they all prefer. The parameter $\epsilon$ allows for approximation; a smaller $\epsilon$ implies a stricter guarantee of common ground.
• Critical $\epsilon$: For any statement, the critical $\epsilon$ is the smallest value for which the statement lies in the $\epsilon$-PVC. A statement with a critical $\epsilon$ close to 0 is an excellent common-ground candidate.

2.2 Information Access Model

Since the alternative space is infinite and voter preferences are unknown, the algorithm operates under a query-based model:

• Generative Queries: Sample alternatives from an unknown distribution $D$ (e.g., querying an LLM).
• Discriminative Queries:
  • Min-queries: Given a set of alternatives, return a voter's least favorite.
  • Pairwise queries: Given two alternatives, return a voter's preference.

2.3 Algorithms

The paper presents efficient sampling-based algorithms to find an element in the $\epsilon$-PVC:

• Algorithm 2 (Sampling + Min-Queries):
  1. Sample $\tau = \tilde{O}(1/\epsilon^2)$ alternatives from $D$.
  2. Iteratively select a random voter and remove their least favorite alternative from the current set (using a min-query).
  3. Repeat until one alternative remains.
  4. Result: With high probability, the remaining alternative is in the $\epsilon$-PVC.
• Pairwise Adaptation: The algorithm can be adapted to use pairwise queries by simulating min-queries via $O(m)$ comparisons, maintaining the same theoretical guarantees.
• Computing Critical $\epsilon$: For finite sets, the authors provide a polynomial-time algorithm (Algorithm 1) based on max-flow/min-cut to compute the exact critical $\epsilon$ of a given alternative.

3. Key Contributions

1. Formal Model for Infinite Alternatives: Introduced the $\epsilon$-PVC, extending the classic Proportional Veto Core to infinite spaces defined by a probability distribution. This provides explicit outcome guarantees for voter coalitions of all sizes.
2. Sample Complexity Bounds:
   • Upper Bound: Proved that $\tilde{O}(1/\epsilon^2)$ generative and min-queries are sufficient to find an element in the $\epsilon$-PVC with high probability. Crucially, this bound is independent of the number of voters ($n$) and the size of the alternative space.
   • Lower Bound: Proved matching lower bounds of $\Omega(1/\epsilon^2)$. This establishes that identifying a common-ground statement is statistically harder than simply generating one (which requires only $\tilde{O}(1/\epsilon)$ queries).
3. Efficient Computation: Developed a max-flow based algorithm to compute the critical $\epsilon$ in polynomial time for finite instances, generalizing previous work on the PVC.
4. Empirical Validation: Extensive experiments using synthetic data generated by LLMs (GPT-5-mini) and persona-based voters.

4. Experimental Results

The authors evaluated various voting rules and generative methods on synthetic datasets covering polarized topics (e.g., Abortion, Electoral College).

• Performance of Voting Rules:

  • Veto-By-Consumption (VBC): The sampling-based algorithm (Algorithm 2) consistently achieved a critical $\epsilon \approx 0$, effectively finding common ground even with limited subsamples.
  • Majoritarian Rules: Schulze, Instant Runoff Voting (IRV), and Plurality consistently produced alternatives with significantly higher critical $\epsilon$ values (often an order of magnitude worse than VBC), indicating they frequently select polarizing statements that minorities strongly oppose.
  • Borda Count: Performed better than Schulze/Plurality but worse than VBC.

• Generative Voting Rules (LLM-based):

  • LLMs asked to generate new statements (e.g., "GPT-Synthesize") generally produced statements with low critical $\epsilon$, suggesting LLMs have an intuitive alignment with the PVC concept.
  • Robustness Check: When tested on clustered voter populations (e.g., strictly conservative voters), generative LLM rules degraded significantly, often performing worse than random baselines. In contrast, VBC maintained near-perfect performance ($\epsilon \approx 0$), demonstrating its robustness to ideological skew.

• Information Requirements: Providing LLMs with more information (rankings, personas) helped slightly but did not close the gap with the theoretical VBC algorithm.

5. Significance and Implications

• Theoretical Advancement: The paper bridges the gap between social choice theory and generative AI, providing the first rigorous framework for "common ground" in infinite alternative spaces.
• Practical Application for AI Deliberation: The results suggest that current AI deliberation tools (like the Habermas machine) relying on Schulze voting may inadvertently marginalize minorities. Replacing these with Veto-based selection or sampling-based PVC algorithms could significantly improve democratic outcomes.
• Efficiency: The finding that sample complexity is independent of population size ($n$) is profound. It implies that finding common ground in a society of millions requires the same number of queries as in a small group, provided the alternatives are sampled from the correct distribution.
• Distribution Sensitivity: The paper highlights that the choice of the alternative distribution $D$ is critical. If $D$ is not representative or neutral, the guarantees of the $\epsilon$-PVC may not hold, emphasizing the need for careful prompt engineering or distribution design in AI systems.

In summary, the paper provides a mathematically rigorous, computationally efficient, and empirically validated method for using AI to find genuine common ground in polarized societies, ensuring that minority voices are not overridden by simple majoritarianism.