Probably Approximately Consensus: On the Learning Theory of Finding Common Ground
arXiv:2604.21811v1 [cs.LG] 23 Apr 2026
Carter Blair1† , Ben Armstrong2 , Shiri Alouf-Heffetz3 , Nimrod Talmon3 , Davide Grossi4 1 University of Waterloo, 2 Tulane University, 3 Ben Gurion University, 4 University of Groningen † [email protected]
Abstract A primary goal of online deliberation platforms is to identify ideas that are broadly agreeable to a community of users through their expressed preferences. Yet, consensus elicitation should ideally extend beyond the specific statements provided by users and should incorporate the relative salience of particular topics. We address this issue by modelling consensus as an interval in a onedimensional opinion space derived from potentially high-dimensional data via embedding and dimensionality reduction. We define an objective that maximizes expected agreement within a hypothesis interval where the expectation is over an underlying distribution of issues, implicitly taking into account their salience. We propose an efficient Empirical Risk Minimization (ERM) algorithm and establish PAC-learning guarantees. Our initial experiments demonstrate the performance of our algorithm and examine more efficient approaches to identifying optimal consensus regions. We find that through selectively querying users on an existing sample of statements, we can reduce the number of queries needed to a practical number.
1
Introduction
Identifying regions of maximal approval, or common ground, within an opinion space is a fundamental task for understanding collective sentiment and informing group decisions. This is particularly relevant for text-based online deliberation platforms such as Polis1 [Small et al., 2021] and Remesh2 , which aim to distill areas of agreement from complex social discussions. In some approaches, like those used by Polis, opinions are represented as points in a metric space derived through embedding and dimensionality reduction where proximity signifies similarity. This spatial approach to opinion representation has roots in both political theory [Merrill and Grofman, 1999] and social choice [Bulteau et al., 2021] and allows for a geometric interpretation of consensus. 1 2
https://pol.is https://www.remesh.ai/
Platforms for online deliberation typically gather opinions of participants through their approval or disapproval of specific statements. While a statement represents a single point in the broader opinion space a set of broadly agreeable statements can be naturally viewed as a contiguous region of related viewpoints. Separately, the salience of the issues is critical for meaningful consensus. For instance, in a discussion about AI development, a statement like “Historically most progress on AI has been made in academia” might receive universal approval. However, this may be an opinion that all users take for granted, and thus may not be at the core of the debate. In contrast, opinions on whether AI models should be open-source, open-weights, or closed-source are discussed and debated more broadly. If an opinion in this “intellectual property” region is also highly approved, it might represent a more meaningful consensus statement. Thus, an ideal consensus region should reflect high approval on salient segments of the discussion, rather than primarily including points receiving widespread approval, which are less relevant. Our goal is to query participants about their approval preferences in order to find a region of responses that maximizes approval. In this paper, we assume that preferences are single-peaked along one dimension. This one-dimensional (1D) space can be thought of as a relevant dimension derived from higher-dimensional opinion space (e.g., via embedding and dimensionality reduction). We focus on the passive learning setting: given a sample of issues (points) drawn from an underlying distribution and labelled by voters, how do we best identify the interval representing maximum consensus? We formalize this problem, provide an efficient algorithm for finding an empirical solution, and derive PAC-style theoretical guarantees on its performance. This work serves as a foundation for more complex scenarios, including active learning where one might query voters strategically.3 The main contributions of this paper are: • A formal problem definition for passive 1D intervalbased consensus finding, incorporating the notion of issue salience through an underlying distribution. • An efficient Empirical Risk Minimization (ERM) algorithm for this problem. 3 In the Polis context, this is referred to as opinion or comment routing [Small et al., 2021].
2
Figure 1: A conceptual representation of approval intervals for different users along a 1D opinion spectrum.
• PAC learning analysis, including the pseudo-dimension of the function class and sample complexity bounds. • Experimental validation and exploration of query strategies that make learning optimal regions dramatically more efficient.
1.1
A: AI development should proceed unhindered by regulation, focusing on maximizing progress. B: AI safety should primarily be governed by industry selfregulation and market forces. C: Government regulation of AI development is important for ensuring public safety and ethical alignment. D: Development of AI capabilities beyond a certain threshold (e.g., superhuman intelligence) should be permanently banned. Our framework aims to identify an interval (depicted in blue) on this 1D spectrum that best represents the overall consensus, considering both the approval patterns of individuals and the relative salience (frequency) of different positions. 4
We address a learning problem in one dimension (1D). We are provided with n initial intervals, denoted Ic ⊂ R for c = 1, . . . , n. These can be conceptualized as representing the approval region of n distinct voters over a continuous space of issues x ∈ R. The primary goal is to determine a single hypothesis interval Iˆ ⊂ R that best summarizes or agrees with these voter intervals, according to an objective function defined below. This is considered within a passive learning framework where issues are sampled i.i.d. from an underlying, possibly unknown, distribution P (x)5 . Definition 2.1 (Individual Label Function). Let Ic ⊂ R be an individual voter interval. The label function Lc (x) for an issue x ∈ R with respect to interval Ic is defined as: Lc (x) = 2 · 1 {x ∈ Ic } − 1. Thus, Lc (x) = +1 if x ∈ Ic (the voter approves the issue) and Lc (x) = −1 if x ∈ / Ic (the voter disapproves or does not endorse the issue within this interval). Definition 2.2 (Combined Label Function). Let I1 , . . . , In ⊂ R be n known voter intervals. The combined label function l(x) for any issue x ∈ R is the sum of the individual labels:
A Concrete Example
To illustrate our one-dimensional model, consider the ongoing discussion surrounding artificial intelligence (AI) safety. This debate encompasses a spectrum of views, from strong advocacy for rapid, unhindered AI development to calls for stringent regulation or even moratoria due to safety concerns4 . Such opinions, though multifaceted, can often be projected onto a principal axis representing, for example, a “progress vs. precaution” spectrum. Along this dimension, individuals may have an interval of acceptable stances, as depicted by the green regions in Figure 1. Further, the distribution of opinions (depicted in yellow) might have more mass around moderate positions as a larger number of moderate opinions were put forward by users. Specific stances within this AI safety opinion space might be mapped to points along this dimension. For example:
https://futureoflife.org/open-letter/pause-giant-ai-experiments/
Problem Definition
l(x) =
n X c=1
Lc (x) = 2
n X
1 {x ∈ Ic } − n.
(1)
c=1
So, if an issue x is approved by exactly k of these n voters (i.e., x falls into k of the Ic intervals), then l(x) = 2k − n. The function l(x) is an integer taking values in {−n, −n + 2, . . . , n − 2, n}. This function l(x) represents the net agreement among the n voters regarding issue x; a positive value indicates that more voters approve x than disapprove,Pand a negative value indicates the opposite. If n ϕ(x) = ( c=1 1 {x ∈ Ic })/n is the fraction of voters approving x, then l(x) = n(2ϕ(x) − 1).
2.1
Objective Function: Maximizing Net Agreement
Our goal is to find a hypothesis interval Iˆ ∈ H, where H = {[a, b] : a, b ∈ R, a ≤ b} is the class of all closed intervals, that represents the region of maximum consensus. We quantify consensus by the total net agreement accumulated within the chosen interval, weighted by the probability of issues appearing there. ˆ For each voter c, we want Consider a candidate interval I. ˆ issues within I to align with their preference Ic . That is, we prefer x to be in both Iˆ and Ic (contributing +1 to Lc (x)) or outside both, and we dislike x being in Iˆ but outside Ic (contributing −1Pto Lc (x)). Summing over all voters, the quantity l(x) = c Lc (x) reflects the overall net agreement at point x. A desirable consensus interval Iˆ should contain issues x where l(x) is predominantly positive. This intuition leads to maximizing the expected value of l(x) for issues x ˆ that fall within the hypothesis interval I. 5 For example, in the case of Pol.is, this underlying distribution is generated by the participants of the deliberation writing statements.
Definition 2.3 (True Objective Function). Given the combined label function l(x) and the underlying issue distribution P (x), the quality of a hypothesis interval I ∈ H is measured by the objective function Φ(I): Z Φ(I) = Ex∼P [l(x)1 {x ∈ I}] = l(x)dP (x). (2) I ∗
The goal is to find an interval I = arg maxI∈H Φ(I). This objective Φ(I) directly calculates the expected contribution to the net agreement score from issues within the interval I. One can also think of maximizing Φ(I) as equivalent to maximizing the average agreement between the voters’ labels Lc (x) and the label assignedPby the interval I, LI (x) = 2·1 {x ∈ I}−1, specifically n1 c E[Lc (x)LI (x)], up to scaling and additive constants. In practice, the true distribution P (x) is unknown. We are instead given a sample of m issues S = {x1 , . . . , xm } drawn i.i.d. from P (x). We therefore use an empirical version of the objective. Definition 2.4 (Empirical Objective Function). Given a sample S = {x1 , . . . , xm } drawn i.i.d. from P (x), the empirical objective function Φ̂S (I) for an interval I ∈ H is the sample average of the net agreement within the interval: m
Φ̂S (I) =
1 X l(xi )1 {xi ∈ I} . m i=1
(3)
The Empirical Risk Minimization (ERM) principle seeks the interval IˆERM = arg maxI∈H Φ̂S (I). Observe that maximizingPΦ̂S (I) is equivalent to maximizm ing the unnormalized sum i=1 l(xi )1 {xi ∈ I}.
3
Algorithm for Passive Interval Selection
The function l(x) is a step function, with its value changing only at the endpoints ac , bc of the given voter intervals ˆ is an Empirical Risk Ic . The problem of maximizing Φ̂S (I) Minimization (ERM) task. Proposition P 3.1. The interval IˆERM that maximizes the empirical sum xi ∈Iˆ l(xi ) over m sample issues x1 , . . . , xm (assuming m ≥ 1) can be chosen such that its endpoints are sample issues. That is, IˆERM = [x(j) , x(k) ] for some 1 ≤ j ≤ k ≤ m, where x(1) ≤ x(2) ≤ · · · ≤ x(m) are the sorted sample issues. n o ˆ = Pm l(xi )1 xi ∈ Iˆ . Consider an inProof. Let S(I) i=1 terval I ′ = [a, b] that maximizes this sum. The value of S(I ′ ) depends only on the set of sample issues contained within I ′ . If I ′ contains no sample issues, S(I ′ ) = 0. If I ′ contains sample issues, let x(j ′ ) be the smallest sample issue in I ′ and x(k′ ) be the largest sample issue in I ′ . The interval [x(j ′ ) , x(k′ ) ] contains exactly the same set of sample issues as I ′ . Therefore, S([x(j ′ ) , x(k′ ) ]) = S(I ′ ). Thus, an optimal interval whose endpoints are from the set of sample issues can always be constructed.
Algorithm 1 ERM for 1D Interval Selection (assuming m ≥ 1) 1: Input: Sample issues x1 , . . . , xm ; voter intervals I1 , . . . , I n . 2: Output: ERM interval IˆERM = [x(j ∗ ) , x(k∗ ) ]. 3: For Pneach sample issue xs , compute its score l(xs ) = 2 c=1 1 {xs ∈ Ic } − n. 4: Sort the sample issues to get x(1) ≤ x(2) ≤ · · · ≤ x(m) . Let h(i) = l(x(i) ). 5: Initialize Smax ← −∞. 6: Initialize Scurrent ← 0. 7: Initialize j ∗ ← 1, k ∗ ← 1 (placeholders, assuming m ≥ 1). 8: Initialize jcand ← 1. 9: for i = 1 to m do 10: Scurrent ← Scurrent + h(i) 11: if Scurrent > Smax then 12: Smax ← Scurrent 13: j ∗ ← jcand 14: k∗ ← i 15: end if 16: if Scurrent < 0 then 17: Scurrent ← 0 18: jcand ← i + 1 19: end if 20: end for 21: if Smax = −∞ and m ≥ 1 then ▷ All h(i) are negative or m = 0 case not fully handled by above loop if no positive subarray. If all h(i) are negative, find max h(i) . 22: Smax ← h(1) ; j ∗ ← 1; k ∗ ← 1; 23: for i = 2 to m do 24: if h(i) > Smax then 25: Smax ← h(i) ; j ∗ ← i; k ∗ ← i; 26: end if 27: end for 28: end if 29: IˆERM = [x(j ∗ ) , x(k∗ ) ]. 30: return IˆERM .
Proposition 3.1 implies that the problem reduces to finding indices j ∗ and k ∗ (with 1 ≤ j ∗ ≤ k ∗ ≤ m) that maxiPk mize the sum Sj,k = i=j h(i) , where h(i) = l(x(i) ) is the combined label of the i-th sorted sample issue x(i) . This is the Maximum Subarray Sum problem on the array of scores H = [h(1) , . . . , h(m) ]. Algorithm 1 details this process. The Maximum Subarray Sum component (lines 5-15) uses Kadane’s algorithm [Bentley, 1984]. The standard Kadane’s algorithm finds the maximum sum; if all elements are negative, it might return 0 (for an empty subarray) or the largest single negative element depending on initialization. The version presented, initializing Smax to −∞, is designed to find the interval [x(j) , x(k) ] Pk maximizing i=j l(x(i) ), even if this sum is negative. If all l(xi ) are negative, it will find the x(i) with the least negative l(x(i) ). A slight modification (lines 16-21) ensures that
if all subarray sums are negative (including single elements), it correctly picks the one with the largest (least negative) sum, corresponding to a single point interval.
achievable patterns for (b1 (R), b2 (R), b3 (R)), preventing pseudo-shattering of 3 points. (Detailed proof in the appendix).
3.1
Theorem 4.2 (Sample Complexity). Let P dim(G) = dP D = 2 and M0 = n. For any ϵ > 0 and δ ∈ (0, 1), if the number of i.i.d. samples m satisfies
Algorithmic Complexity of ERM
The ERM interval IˆERM can be found efficiently. The primary computational steps are: 1. Computing the scores l(xi ) for all m sample points. Naively, this takes O(nm) time by checking each point against each of the n voter intervals Ic .
32M02 ϵ2
dP D ln
32eM0 ϵ
1 , δ
(4)
2. Sorting the sample points xi to obtain x(i) and their associated scores h(i) . This takes O(m log m) time.
+ ln(4e(dP D + 1)) + ln
3. Applying Kadane’s algorithm (Algorithm 1, lines 5-15) to the m scores h(i) , which runs in O(m) time.
then with probability at least 1 − δ, supR∈H |Φ(R) − Φ̂S (R)| ≤ ϵ. This implies that the ERM hypothesis R̂ERM satisfies Φ(R̂ERM ) ≥ Φ(R∗ ) − 2ϵ, where R∗ = arg maxR∈H Φ(R). For dP D = 2, 32n2 32en 1 m≥ 2 2 ln + ln(12e) + ln . ϵ ϵ δ
The total time complexity using this naive score computation is O(nm + m log m). Alternatively, a sweep-line algorithm can be used to compute all l(xi ) values more efficiently. This involves creating a sorted list of all 2n endpoints of the given intervals Ic and all m sample points xi . The sweep processes these O(n + m) points in order. As an endpoint of an Ic is crossed, the count of active intervals (used to determine l(x) for points in that segment) is updated. When a sample point xi is encountered, its l(xi ) value is computed based on the current count of intervals it falls into. This approach takes O((n + m) log(n + m)) time for both sorting the critical points and performing the sweep to assign scores. If the sample points xi are already sorted by this process, the subsequent Kadane’s algorithm step takes O(m). Thus, the total complexity using the sweep-line method is O((n + m) log(n + m)).
4
m≥
Theoretical Analysis
We establish Probably Approximately Correct (PAC) learning guarantees for the ERM approach. Let H be the hypothesis class of all intervals [a, b] ⊂ R. The true objective for R ∈ H is Φ(R) = Ex∼P [l(x)1 {x ∈ R}], and the empirical Pm 1 objective is Φ̂S (R) = m i=1 l(xi )1 {xi ∈ R}. To analyze the uniform convergence of Φ̂S (R) to Φ(R), we consider the properties of the function class gR (x) = l(x)1 {x ∈ R}. The complexity of uniform convergence depends on the function class G = {gR (x) : R ∈ H}. The functions gR (x) ∈ G are bounded by M0 = maxx |l(x)| = n. Lemma 4.1. The pseudo-dimension of the function class G = {gR (x) = l(x)1 {x ∈ R} : R is an interval in R}, denoted P dim(G), is 2, provided l(x) is not identically zero on R. Proof. (Sketch) To show P dim(G) ≥ 2: Choose two points x1 < x2 where l(x1 ), l(x2 ) ̸= 0. Appropriate thresholds r1 , r2 can be chosen such that the outcomes 1{l(xj )1 {xj ∈ R} > rj } depend on 1 {xj ∈ R} or 1 − 1 {xj ∈ R}. Since intervals can shatter two points for indicators (VCdim = 2), G can pseudo-shatter two points. To show P dim(G) ≤ 2: For any three points x1 < x2 < x3 and any thresholds r1 , r2 , r3 , the pattern of (1 {x1 ∈ R} , 1 {x2 ∈ R} , 1 {x3 ∈ R}) cannot achieve (1, 0, 1). This limitation on indicator patterns restricts the
Proof. (Sketch) The proof of the sample complexity (Theorem 4.2) relies on standard uniform convergence arguments. First, the pseudo-dimension of the function class G = {gR (x) = l(x)1 {x ∈ R}} is determined to be 2, as established in Lemma 4.1. A uniform convergence bound is then applied. This bound, which is based on methods detailed in Anthony and Bartlett (2009, Ch. 17) [Anthony and Bartlett, 2009], relates the probability of the maximum deviation between the true expectation Φ(R) and the empirical expectation Φ̂S (R) to the L1 -covering numbers of G. Specifically, we use the inequality: P sup |E[g] − ÊS [g]| > ϵ g∈G (5) −mϵ2 . ≤ 4N1 (ϵ/8, G, 2m) exp 32M02 where M0 = n is the bound on |l(x)|. This is derived from the bound given in Theorem 17.1 in Anthony and Bartlett (2009) [Anthony and Bartlett, 2009]. To bound the L1 -covering number N1 (ϵ/8, G, 2m), the functions g ∈ G are affinely transformed into a scaled func′ 0 tion class G ′ = { g+M 2M0 : g ∈ G}. Functions in G map to [0, 1], and this scaling preserves the pseudo-dimension, so P dim(G ′ ) = 2. Theorem 18.4 from Anthony and Bartlett (2009) is then used to bound the L1 -covering number of G ′ : dP D 2e ′ N1 (η, G , N ) ≤ e(dP D + 1) . η This bound for N1 (·, G ′ , ·) is related back to N1 (·, G, ·) by adjusting the scale factor, yielding: d 32eM0 P D N1 (ϵ/8, G, 2m) ≤ e(dP D + 1) . ϵ Substituting this covering number bound into the uniform convergence inequality, the resulting expression is set to be
less than or equal to δ. This inequality is then solved for the sample size m, leading to the sample complexity formula presented in Theorem 4.2: 32M02 32eM0 m≥ d ln + ln(4e(dP D + 1)) P D ϵ2 ϵ (6) 1 + ln . δ This ensures that with probability at least 1 − δ, the empirical objective is uniformly within ϵ of the true objective for all hypotheses in H. A detailed proof is presented in the appendix. The above sample complexity is O
5
2 n ϵ2
ln nϵ + ln 1δ
.
Experiments
In this section we describe our experimental framework, introduce specific experiments, and present their results. The primary goals of our current experiments are: 1. Gauge the tightness of the bound on sample complexity identified in Theorem 4.2. 2. Explore methods by which we may identify optimal consensus regions using a reduced number of queries.
5.1
Experimental Framework
We begin by describing the procedures we follow in initializing an experimental setting. This includes how we select the regions approved by each voter, and the distributions from which we sample. Through all experiments presented in this paper, we have used n = 100 voters and performed 100 randomly initialized trials with each set of parameters. Constructing Voter Approval Intervals Each voter approves a single interval in our 1D space. The location and size of this region is not dictated by our theoretical results. To simulate a wide variety of users we construct each voter’s approvals based on three parameters: minimum width wmin , maximum width wmax , and center point p. These parameters allow us to simulate settings where users are highly agreeable (very large approval intervals), highly disagreeable (very small approval intervals), and where both types exist (large gap between wmin and wmax ). Interval construction occurs as follows: We select a width w ∈ [wmin , wmax ], and a center point p ∈ [0, 1], both uniformly at random. From p we construct the interval (p − w w 2 , p + 2 ). When this would result in the interval extending above 1, or below 0, we add the “missing” width to the other side of the interval (thus, p is not always the actual center point of the interval). In our experiments, we use four specific ranges of approved region sizes. These are chosen to demonstrate the quality of outcomes across a range of scenarios. The absence of a small region size is intentional – when all voters approve very small regions, there is typically no area with a positive l(x), resulting in an optimal “region” containing a single point.
Sampling Points Through our experiments we consider three distributions from which we sample points. As with voter approval intervals, the choice of these distributions does not affect the applicability of our theoretical results to our experiments but provides insight as to how extensions of our theoretical algorithm could behave under differing empirical conditions. In particular, our sampling distributions are: 1. U (0, 1); The uniform distribution between 0 and 1. 2. N (0, 1, 0.5, 0.1); The truncated Normal distribution with µ = 0.5, σ = 0.1, bounded in [0, 1]. 3. Exp(4); The truncated Exponential distribution with λ = 4, bounded in [0, 1].
5.2
Experimental Results
Our experimental results are divided into three sections. We first examine how tightness of the lower bound on sample complexity from Section 4. Subsequently, we explore the quality of two approaches to reducing the total number of queries asked of voters. First by asking fewer voters about each sampled point and, second, by asking each voter about fewer samples. Sampling Fewer Points We first examine our sample complexity results. In Figure 2 we decrease the number of sampled points used in identifying the best region beginning from ϵ12 ln nϵ + ln 1δ (a factor of n2 below our upper bound) reducing to 10 sampled points. Figure 2 shows that, across distributions, in most cases we can use far fewer samples than our upper bound on sample complexity and attain the same quality as guaranteed theoretically. Of course, as we decrease the number of samples the quality of the best discovered region begins to reduce. In order to develop more empirically practical procedures for identifying consensus regions our subsequent experiments consider two strategies for reducing the total number of sample evaluations performed. Querying Fewer Voters A straightforward approach to reducing the cost of running our procedure is to ask fewer voters whether they approve of each sampled point. Several techniques exist that are suitable for estimating the number of queries required at each point x to be confident in the value of l(x). However, in this work we simply explore the effect of asking some constant fraction of voters for their evaluation of each sample. In Figure 3 we decrease the proportion of voters being queried. At each step we sample a random subset of voters with size proportional to the amount shown in the x-axis. This approach provides a linear decrease in the overall cost of identifying a region of consensus. Based on the results shown in Figure 2 we sample 10,000 points for each experiment shown in Figure 3. However, the results show that this approach very quickly reduces the quality of the underlying region. We hypothesize that this reduction in performance is related to both the relatively low number of voters we use in our experiment (n = 100) and the fact that each voter’s approved region is sampled uniformly at random. Since the location
Figure 2: The fraction of regions with a score within ϵ of the optimal region’s score as the number of sampled points decreases from 1 ln nϵ + ln 1δ to 10. Note that, due to computational limitations, the maximum number of samples displayed is a factor of n2 below our ϵ2 upper bound found in Section 4. In general, our approach finds nearly optimal regions using far fewer samples than theoretically necessary. Here ϵ = δ = 0.01 and we perform 100 trials for each different number of samples to get an empirical estimate of δ.
of one voter’s region does not inform the location of any other voter’s region, the consensus interval does not generalize well. In contrast, if voter intervals were correlated, we hypothesize that the quality of the interval would reduce at a slower rate with a decreasing fraction of voters sampled. This hypothesis offers an explanation for why the quality of the optimal region decreases less quickly under the Truncated Normal distribution: As this region is centred around the middle of the 1D interval, when voters approve of larger regions, the optimal region is more likely to be in the center also. This bias towards the center leads to better generalization of the consensus interval. Querying Voters Intelligently Rather than asking a subset of voters about each sampled point, we can instead ask each voter about a subset of sampled points. We can perform a binary search-like procedure to find both endpoints of each voter’s approved region. For each voter v, this search proceeds as follows: 1. Ask v whether they approve some sampled point until finding a point that they approve. We ask about points at particular fractions through the entire list of ordered samples following the pattern { 21 , 14 , 34 , 18 , 28 , ...} (First the median point, then the lower quartile point, then the upper quartile point etc). 2. Given an approved sample point p, determine the leftmost extent of v’s continuous approval that includes p. Let Rbound be the current right boundary of the search (initially p) and Lbound be the current left boundary (initially the first sample point in the dataset). Repeatedly query v on the sample point q midway between Lbound and Rbound . If q is approved, update Rbound to q (as the approval extends at least this far left). If q is disapproved, update Lbound to be the sample point immediately to the right of q. Continue until Lbound and
Rbound converge, identifying the left edge of approval and thereby labeling all queried points. 3. Perform step 2 on the points to the right of p. We show in Figure 4 the number of sampled points used in the experiment shown in Figure 2 and the average number of points upon which each voter must be queried in order to find the best region. For example, when we sample 105 points, we typically identify the optimal region using only slightly more than 30 queries per voter. This active approach to querying voters dramatically reduces the number of queries required to identify the optimal region. Such an approach is vital for any application of this method to human settings.
6
Related Work
The problem of identifying consensus or aggregating preferences connects to several research streams. Qiu [Qiu, 2024] presents a “Representative Social Choice” model, framing social choice as statistical learning and using VC dimension and Rademacher complexity for generalization bounds. This aligns with our PAC learning approach (using pseudodimension). However, our work focuses on finding an optimal 1D consensus interval that maximizes a net agreement score, given known voter intervals and sampled issues, rather than Qiu’s axiomatic focus. Platforms like Polis [Small et al., 2021] use computational techniques like PCA and k-means to identify consensus from user votes. However, its methods are heuristic and descriptive, lacking the formal objective function optimization and provable PAC guarantees central to our work. Our approach formalizes consensus as maximizing E[l(x)1 {x ∈ I}] and provides an algorithm with theoretical performance bounds. Halpern et al. [Halpern et al., 2023] also addresses challenges in Polis-like systems, specifically incomplete approval votes, by modelling the task as approval-based committee se-
Figure 3: The fraction of regions with a score within ϵ of the optimal region’s score as we query a decreasing fraction of voters. In all cases ϵ = δ = 0.01 and we sample 10000 points from the distribution. Each set of parameters is run for 100 randomly initialized trials. Quality of the best region found decreases rapidly as fewer voters are queried.
Figure 4: Average number of points required to identify each voter’s approved region compared with the total number of sampled points for voters approving a region with width in 0.4, 0.6).
lection. They develop adaptive algorithms to achieve fairness guarantees like Justified Representation. While they also learn from partial information, their goal of committee selection contrasts with our PAC-based optimization of a consensus interval from known voter intervals and sampled issues. Anshelevich et al. [Anshelevich et al., 2018] also consider preferences within a metric space, where both voters and alternatives are points, and preferences are determined by proximity. While their use of a metric space for preferences is similar to our 1D issue space, their focus on distortion with ordinal inputs contrasts with our PAC learning approach. Finally, very related to our work is [Elkind et al., 2024], which studied the problem of consensus formation in metric spaces where coalitions form iteratively around points eliciting wider support. That work, however, abstracts away from the problem of identifying such consensus points, which has been the explicit focus of the work presented here.
7
Conclusion and Future Work
This paper introduced a formal framework for passive PAC learning of a consensus interval in a one-dimensional opin-
ion space. We defined an objective function based on aggregated voter approval intervals, presented an efficient ERM algorithm using Kadane’s method, and derived sample complexity bounds based on a pseudo-dimension of 2 for the associated function class. These results provide a theoretical basis for identifying regions of maximal approval with provable guarantees. Future work could pursue several directions: Active Learning: Developing algorithms for the “PAC Queries” setting, where voter labels are acquired strategically to minimize query costs while learning the consensus interval or individual voter intervals. Higher Dimensions: Extending the model and analysis to find consensus regions in multi-dimensional spaces, which is more directly applicable to complex data like text embeddings. This will involve different hypothesis classes (e.g., axis-aligned rectangles or balls). Alternative Objectives: Exploring different normative definitions of “consensus.” For example, we considered the overlap between voter intervals and the consensus interval as desirable and the overlap between the consensus interval and the complement of voter intervals as a negative. However, one could also argue that a lack of overlap between voter intervals and the consensus interval is also undesirable. AI Alignment: Integrating the consensus-finding framework to distill salient regions of acceptable AI expression. Learned consensus intervals could operate as filters or inform the reward mechanisms within RLAIF [Lee et al., 2023]. Empirical Validation: We motivated our paper with applications like online deliberation platforms, but tested our method on synthetic data. However, extending to real-world datasets from platforms like Pol.is is necessary in order to understand how well our algorithms would perform in practice. The overall goal of this line of research is to identify computationally viable methods for salient consensus elicitation in complex collective decision-making settings.
References [Anshelevich et al., 2018] Elliot Anshelevich, Onkar Bhardwaj, Edith Elkind, John Postl, and Piotr Skowron. Approximating optimal social choice under metric preferences. Artificial Intelligence, 264:27–51, 2018. [Anthony and Bartlett, 2009] Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundations. Cambridge University Press, 2009. [Bentley, 1984] Jon Bentley. Programming pearls: algorithm design techniques. Communications of the ACM, 27(9):865–873, 1984. [Bulteau et al., 2021] Laurent Bulteau, Gal Shahaf, Ehud Shapiro, and Nimrod Talmon. Aggregation over metric spaces: Proposing and voting in elections, budgeting, and legislation. Journal of Artificial Intelligence Research, 70:1413–1439, 2021. [Elkind et al., 2024] Edith Elkind, Davide Grossi, Ehud Shapiro, and Nimrod Talmon. United for change: deliberative coalition formation to change the status quo. Social Choice and Welfare, 63(3):717–746, 2024. [Halpern et al., 2023] Daniel Halpern, Gregory Kehne, Ariel D Procaccia, Jamie Tucker-Foltz, and Manuel Wüthrich. Representation with incomplete votes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 5657–5664, 2023. [Lee et al., 2023] Harrison Lee, Samrat Phatale, Hassan Mansoor, Thomas Mesnard, Johan Ferret, Kellie Lu, Colton Bishop, Ethan Hall, Victor Carbune, Abhinav Rastogi, et al. Rlaif vs. rlhf: Scaling reinforcement learning from human feedback with ai feedback. arXiv preprint arXiv:2309.00267, 2023. [Merrill and Grofman, 1999] Samuel Merrill and Bernard Grofman. A unified theory of voting: Directional and proximity spatial models. Cambridge University Press, 1999. [Qiu, 2024] Tianyi Qiu. Representative social choice: From learning theory to ai alignment. arXiv preprint arXiv:2410.23953, 2024. [Small et al., 2021] Christopher Small, Michael Bjorkegren, Timo Erkkilä, Lynette Shaw, and Colin Megill. Polis: Scaling deliberation by mapping high dimensional opinion spaces. Recerca: revista de pensament i anàlisi, 26(2), 2021.
A
Proof of Lemma 4.1
Proof. The pseudo-dimension P dim(G) is the maximum integer d such that there exists a set of d points {x1 , . . . , xd } that can be pseudo-shattered by G. To pseudo-shatter a set of points means there exist thresholds r1 , . . . , rd ∈ R such that for any binary vector (b1 , . . . , bd ) ∈ {0, 1}d , there is a function gR ∈ G (i.e., an interval R) for which 1{gR (xi ) > ri } = bi for all i = 1, . . . , d. If l(x) is identically zero, then gR (x) = 0 for all R, x. Then 1{gR (xi ) > ri } = 1{0 > ri }, which does not depend on R. Thus, no points can be shattered, and P dim(G) = 0. We now assume l(x) is not identically zero, and thus that some voter has a non-empty approval interval. Part 1: Show P dim(G) ≥ 2. We need to show that there exists a set of 2 points that G can pseudo-shatter. Since l(x) is not identically zero, there exist at least two distinct points x1 < x2 where l(x1 ) ̸= 0 and l(x2 ) ̸= 0. (If l(x) is non-zero at only one point, P dim(G) would be 1. The class of intervals allows isolating individual points or pairs, making the existence of two such distinct points x1 , x2 a typical scenario for non-trivial l(x) relevant to this problem). Let x1 < x2 be two points such that l(x1 ) ̸= 0 and l(x2 ) ̸= 0. We define thresholds r1 , r2 based on the signs of l(x1 ), l(x2 ). Case A: l(x1 ) > 0 and l(x2 ) > 0. Let rj = l(xj )/2. Then rj > 0. The condition 1{l(xj )1 {xj ∈ R} > rj } = bj becomes 1{l(xj )1 {xj ∈ R} > l(xj )/2} = bj . If xj ∈ R: 1{l(xj ) > l(xj )/2} = 1 (since l(xj ) > 0). If xj ∈ / R: 1{0 > l(xj )/2} = 0 (since l(xj )/2 > 0). So, bj = 1 {xj ∈ R}. Case B: l(x1 ) < 0 and l(x2 ) < 0. Let rj = l(xj )/2. Then rj < 0. The condition 1{l(xj )1 {xj ∈ R} > rj } = bj becomes 1{l(xj )1 {xj ∈ R} > l(xj )/2} = bj . If xj ∈ R: 1{l(xj ) > l(xj )/2} = 0 (since l(xj ) < 0, e.g., −2 > −1 is false). If xj ∈ / R: 1{0 > l(xj )/2} = 1 (since l(xj )/2 < 0). So, bj = 1 {xj ∈ / R} = 1 − 1 {xj ∈ R}. Case C: l(x1 ) > 0 and l(x2 ) < 0. Let r1 = l(x1 )/2 and r2 = l(x2 )/2. Then b1 = 1 {x1 ∈ R} and b2 = 1 {x2 ∈ / R}. In all cases (A, B, C, and C with signs swapped), the pair (b1 , b2 ) is determined by (1 {x1 ∈ R} , 1 {x2 ∈ R}) or simple transformations thereof. The class of indicator functions {1 {x ∈ R} : R is an interval} has VC-dimension 2, meaning it can shatter a set of two points {x1 , x2 }. That is, all 4 patterns for (1 {x1 ∈ R} , 1 {x2 ∈ R}) are achievable by varying R: • (1 {x1 ∈ R} , 1 {x2 ∈ R}) = (1, 1) by R = [x1 , x2 ]. • (1 {x1 ∈ R} , 1 {x2 ∈ R}) = (0, 0) by R = ∅. • (1 {x1 ∈ R} , 1 {x2 ∈ R}) = (1, 0) by R = [x1 , x1 ].
achieved. Thus, under the condition that l(x) is non-zero at two distinct points x1 , x2 , we can find thresholds r1 , r2 such that all 4 binary patterns for (b1 , b2 ) are generated. Therefore, P dim(G) ≥ 2. Part 2: Show P dim(G) ≤ 2. We must show that no set of 3 points can be pseudoshattered by G. Let x1 < x2 < x3 be any three distinct points in R. Let r1 , r2 , r3 be any three real-valued thresholds. Let bj (R) = 1{gR (xj ) > rj } = 1{l(xj )1 {xj ∈ R} > rj }. For each point xj , l(xj ) is a fixed real number and rj is a fixed threshold. We define two values for each (1) point xj : sj = 1{l(xj ) > rj } (this is the outcome (0)
bj (R) if xj ∈ R) sj = 1{0 > rj } (this is the outcome bj (R) if xj ∈ / R) Thus, for any interval R, the generated binary vector (b1 (R), b2 (R), b3 (R)) is formed as (1{x ∈R}) (1{x2 ∈R}) (1{x3 ∈R}) (s1 1 , s2 , s3 ). Let fR (xj ) = 1 {xj ∈ R}. The vector of indicators (fR (x1 ), fR (x2 ), fR (x3 )) represents which of the three points are included in the interval R. It is a standard result that the class of 1D intervals (a Vapnik-Chervonenkis class) has VC-dimension 2. This means it cannot shatter any set of 3 points. Specifically, for x1 < x2 < x3 , the indicator pattern (fR (x1 ) = 1, fR (x2 ) = 0, fR (x3 ) = 1) cannot be generated by any interval R. If x1 ∈ R and x3 ∈ R for an interval R, then all points between x1 and x3 must also be in R, meaning x2 ∈ R. Thus, fR (x2 ) must be 1 if fR (x1 ) = 1 and fR (x3 ) = 1. Let Pf = {(fR (x1 ), fR (x2 ), fR (x3 )) : R is an interval} be the set of all possible indicator patterns generated on x1 , x2 , x3 by intervals. Since the pattern (1, 0, 1) is not in Pf , the size of Pf is |Pf | ≤ 23 − 1 = 7. The set of output vectors V = {(b1 (R), b2 (R), b3 (R)) : R is an interval} is obtained (0) (1) by applying the fixed mapping (defined by sj , sj for each (v )
(v )
(v )
j) to each vector in Pf . That is, V = {(s1 1 , s2 2 , s3 3 ) : (v1 , v2 , v3 ) ∈ Pf }. Since the mapping is from Pf to V , it must be that |V | ≤ |Pf |. Therefore, |V | ≤ 7. As V contains at most 7 distinct vectors, it cannot be equal to the set of all 23 = 8 binary vectors {0, 1}3 . This means that for any set of 3 points x1 < x2 < x3 and any set of thresholds r1 , r2 , r3 , there is at least one binary pattern in {0, 1}3 that cannot be generated by G. Thus, no set of 3 points can be pseudo-shattered by G, which implies P dim(G) < 3, and therefore P dim(G) ≤ 2. Conclusion: Since P dim(G) ≥ 2 and P dim(G) ≤ 2, we conclude that P dim(G) = 2, provided l(x) is not identically zero (specifically, non-zero on at least two points where the interval class can distinguish them as required for the P dim ≥ 2 construction).
• (1 {x1 ∈ R} , 1 {x2 ∈ R}) = (0, 1) by R = [x2 , x2 ]. In Case A, (b1 , b2 ) directly achieves these 4 patterns. In Case B, if (1 {x1 ∈ R} , 1 {x2 ∈ R}) takes values (1, 1), (0, 0), (1, 0), (0, 1), then (b1 , b2 ) takes values (0, 0), (1, 1), (0, 1), (1, 0) respectively. All 4 patterns are achieved. In Case C, if (1 {x1 ∈ R} , 1 {x2 ∈ R}) takes values (1, 1), (0, 0), (1, 0), (0, 1), then (b1 , b2 ) = (1 {x1 ∈ R} , 1 − 1 {x2 ∈ R}) takes values (1, 0), (0, 1), (1, 1), (0, 0) respectively. All 4 patterns are
B
Proof of Theorem 4.2
Proof. To derive the sample complexity bound, we first note that the functions gR (x) ∈ G are bounded by M0 = maxx |l(x)| = n, since l(x) takes integer values in {−n, . . . , n}. The pseudo-dimension of G, dP D = P dim(G), is 2 as established in Lemma 4.1. For a class of functions G whose members g are bounded such that |g(x)| ≤ M0 , the probability that the empirical
mean ÊS [g] deviates from the true mean E[g] by more than ϵ for any g ∈ G is bounded as: P sup |E[g] − ÊS [g]| > ϵ g∈G
≤ 4N1 (ϵ/8, G, 2m) exp
−mϵ2 32M02
Here, N1 (η, G, 2m) is the L1 -covering number of the class G at scale η for 2m points. To utilize pseudo-dimension bounds for covering numbers, which are typically stated for functions mapping to [0, 1], we introduce a scaled function class G ′ . Let g ∈ G. De′ ′ 0 fine g ′ = g+M 2M0 . These functions g ∈ G map to [0, 1]. ′ The pseudo-dimension of G is the same as that of G, i.e., P dim(G ′ ) = dP D = 2, because pseudo-dimension is invariant under positive affine transformations of the function outputs. Anthony and Bartlett (2009, Theorem 18.4) provide a bound for the L1 -covering number of a class of functions mapping to [0, 1] in terms of its pseudo-dimension dP D : dP D 2e N1 (η, G ′ , N ) ≤ e(dP D + 1) η for N points. We need to relate N1 (ϵ/8, G, 2m) to a covering number for G ′ . The L1 -distance between two functions g1 , g2 ∈ G relates to their scaled versions g1′ , g2′ ∈ G ′ by ES [|g1 − g2 |] = ES [|(2M0 g1′ − M0 ) − (2M0 g2′ − M0 )|] = 2M0 ES [|g1′ − g2′ |]. Thus, an η ′ -cover for G ′ corresponds to a 2M0 η ′ -cover for G. This implies N1 (ϵ0 , G, 2m) = N1 (ϵ0 /(2M0 ), G ′ , 2m). For ϵ0 = ϵ/8, we have: ϵ/8 ′ N1 (ϵ/8, G, 2m) = N1 , G , 2m 2M0 ϵ ′ = N1 , G , 2m 16M0 ϵ . Using the covering number bound for G ′ Let η ′ = 16M 0 with N = 2m points:
N1
dP D ϵ 2e ′ , G , 2m ≤ e(dP D + 1) 16M0 ϵ/(16M0 ) d 32eM0 P D = e(dP D + 1) ϵ
Substituting this into the uniform convergence probability bound: P sup |E[g] − ÊS [g]| > ϵ g∈G
≤ 4e(dP D + 1)
32eM0 ϵ
dP D
exp
−mϵ2 32M02
We want this probability to be at most δ. So we set: d 32eM0 P D −mϵ2 4e(dP D + 1) exp ≤δ ϵ 32M02
To solve for m, we can rearrange and take the natural logarithm: dP D 0 4e(dP D + 1) 32eM mϵ2 ϵ exp ≥ 32M02 δ ! d mϵ2 32eM0 P D 1 · ≥ ln 4e(dP D + 1) 32M02 ϵ δ 32eM0 1 mϵ2 ≥ ln(4e(dP D + 1)) + dP D ln + ln 32M02 ϵ δ Finally, solving for m: 32M02 32eM0 1 m≥ d ln + ln(4e(d + 1)) + ln PD PD ϵ2 ϵ δ .