Probably Approximately Consensus: On the Learning Theory of Finding Common Ground

1. Problem Definition

The paper addresses the challenge of identifying a "consensus region" (common ground) within a community of users on online deliberation platforms (e.g., Polis, Remesh). Unlike standard consensus methods that simply aggregate approval for specific statements, this work aims to find a contiguous region in an opinion space that maximizes net agreement, weighted by the salience (frequency/importance) of the issues.

• Setting: The problem is modeled in a one-dimensional (1D) opinion space. This 1D space is assumed to be derived from high-dimensional data (e.g., text embeddings) via dimensionality reduction.
• Inputs:
  • $n$ voters, each with an approval interval $I_c \subset \mathbb{R}$ representing the range of issues they agree with.
  • A set of $m$ sampled issues (points) $x_1, \dots, x_m$ drawn i.i.d. from an underlying distribution $P(x)$, which represents the salience of different topics.
• Goal: Find a hypothesis interval $\hat{I} = [a, b]$ that maximizes the expected net agreement score.
• Labeling:
  • Individual label: $L_c(x) = +1$ if $x \in I_c$, else $-1$.
  • Combined label: $l(x) = \sum L_c(x) = 2k - n$, where $k$ is the number of voters approving $x$.
• Objective: Maximize the expected value of the combined label within the chosen interval:
  $$\Phi(I) = \mathbb{E}_{x \sim P}[l(x) \cdot \mathbb{1}\{x \in I\}] = \int_I l(x) dP(x)$$
  This formulation inherently weights the consensus by the probability distribution of issues, ensuring that agreement on salient topics contributes more to the score than agreement on trivial or rare topics.

2. Methodology

A. Empirical Risk Minimization (ERM) Algorithm

Since the true distribution $P(x)$ is unknown, the authors propose an ERM approach using a finite sample $S$. The goal is to maximize the empirical objective:
$$\hat{\Phi}_S(I) = \frac{1}{m} \sum_{i=1}^m l(x_i) \cdot \mathbb{1}\{x_i \in I\}$$

• Key Insight (Proposition 3.1): The optimal interval $\hat{I}_{ERM}$ can always be chosen such that its endpoints are sample points from $S$.
• Reduction to Maximum Subarray Sum:
  1. Sort the sample points: $x_{(1)} \le x_{(2)} \le \dots \le x_{(m)}$.
  2. Compute the score $h(i) = l(x_{(i)})$ for each sorted point.
  3. The problem reduces to finding indices $j, k$ that maximize $\sum_{i=j}^k h(i)$.
• Algorithm: The authors utilize Kadane's Algorithm to solve this Maximum Subarray Sum problem in $O(m)$ time.
  • Complexity: With naive score computation, total time is $O(nm + m \log m)$. Using a sweep-line algorithm to compute scores, the complexity improves to $O((n+m) \log(n+m))$.

B. Theoretical Guarantees (PAC Learning)

The paper establishes Probably Approximately Correct (PAC) learning guarantees for the ERM solution.

• Function Class: The class of functions $G = \{g_R(x) = l(x) \cdot \mathbb{1}\{x \in R\} \mid R \text{ is an interval}\}$.
• Pseudo-Dimension: The authors prove that the pseudo-dimension of this function class is 2 (Lemma 4.1), provided $l(x)$ is not identically zero.
• Sample Complexity: Based on the pseudo-dimension ($d_{PD}=2$) and the bound on the label values ($M_0 = n$), they derive a sample complexity bound. To achieve an error $\epsilon$ with probability $1-\delta$, the number of samples $m$ must satisfy:
  $$m \ge O\left( \frac{n^2}{\epsilon^2} \left( \ln \frac{n}{\epsilon} + \ln \frac{1}{\delta} \right) \right)$$
  This ensures that the empirical solution $\hat{I}_{ERM}$ is within $2\epsilon$ of the optimal true consensus interval with high probability.

C. Query Strategies (Active Learning)

To address the practical cost of querying users, the paper explores strategies to reduce the number of queries:

1. Random Subsampling: Querying a random fraction of voters for each point. Results show this degrades performance quickly unless voter intervals are correlated.
2. Intelligent Querying (Binary Search): Instead of querying all voters for all points, the algorithm performs a binary search to determine the exact approval interval for each voter.
   • For each voter, the algorithm finds the boundaries of their approval interval using $O(\log m)$ queries.
   • Result: This "active" approach dramatically reduces the total number of queries required to identify the optimal region, making the method scalable for human-in-the-loop systems.

3. Key Contributions

1. Formal Problem Definition: A rigorous definition of consensus finding as a passive learning problem in 1D, incorporating issue salience via an underlying distribution.
2. Efficient Algorithm: An $O(m)$ ERM algorithm based on Kadane's method to find the optimal consensus interval.
3. Theoretical Bounds: PAC-learning guarantees with a sample complexity analysis based on a pseudo-dimension of 2.
4. Query Optimization: Demonstration that active learning strategies (binary search on voter intervals) can significantly reduce query costs while maintaining optimality.

4. Experimental Results

The authors conducted experiments with $n=100$ voters and various distributions (Uniform, Truncated Normal, Exponential).

• Sample Complexity Tightness: The experiments showed that the algorithm finds nearly optimal regions using far fewer samples than the theoretical upper bound suggests.
• Query Reduction:
  • Randomly querying fewer voters led to a rapid decline in consensus quality.
  • Intelligent Querying: When using the binary search approach, the system could identify the optimal region with only slightly more than 30 queries per voter (even when sampling $10^5$ points), demonstrating high efficiency.
• Distribution Sensitivity: Performance was more robust under Truncated Normal distributions (where opinions cluster centrally) compared to Uniform distributions, suggesting that correlated voter behaviors aid generalization.

5. Significance and Future Work

• Significance: This work bridges social choice theory and computational learning theory. It provides the first formal PAC-learning framework for finding consensus intervals that account for issue salience, moving beyond heuristic methods used in platforms like Polis.
• Applications:
  • Online Deliberation: Improving tools for distilling agreement in large-scale discussions.
  • AI Alignment: Using consensus intervals to filter or reward AI-generated content that aligns with human values (RLAIF).
• Future Directions:
  • Extending the model to multi-dimensional spaces (e.g., finding consensus in 2D or 3D opinion spaces).
  • Developing more sophisticated active learning strategies.
  • Validating the approach on real-world datasets from platforms like Pol.is.
  • Exploring alternative normative definitions of consensus.

In summary, the paper provides a mathematically grounded, computationally efficient, and practically scalable method for identifying "common ground" in complex social discussions, with provable guarantees on performance and sample efficiency.