Introduction
In recent years, rising political polarization has become an increasingly prominent concern for democratic societies, with consequences for social cohesion, public deliberation, and the ability to reach collective decisions. At the same time, parliaments and other elected bodies have become increasingly divided and antagonistic Mehlhaff [37 ] . A natural interpretation is that this political division simply reflects polarization in the electorate: a more polarized society produces a more polarized political environment and, ultimately, more polarized representatives. However, several studies suggest that these two phenomena need not coincide [19 , 20 ] . In particular, this literature distinguishes between mass polarization , occurring within the population, and elite polarization , occurring among the elected representatives of that population McCarty et al. [36 ] . From this perspective, a parliament may not merely reflect the divisions present in society. Rather, it can act as a prism through which the society is perceived, potentially amplifying weak obscuring underlying divisions. This raises the possibility that selecting a less polarized body of representatives may reduce the division within the electorate.
A recent paper by Dong et al. [16 ] tackles this issue by proposing interlacing , a novel model in which the population is represented by a hypergraph, with individual voters as vertices and candidates as hyperedges linking their approving voters. This hypergraph induces a voter graph in which two voters are connected whenever they jointly approve a candidate. Each committee induces a voter network through shared representation by the selected candidates, yielding a projection of the society through the lens of the committee. Committees are then evaluated by how well the selected candidates interlace , or interconnect, the voters. To this end, Dong et al. consider two measures. The PAIRS objective measures direct pairwise voter connections via the number of edges in the resulting graph, whereas CONS captures global connectivity by counting path connected-pairs of voters.
The interlacing model rests on the intuition that greater connectivity of the induced network corresponds to greater cohesion, and thus less polarization. However, we believe that the objectives proposed by Dong et al. [16 ] do not capture the full structural picture of polarization. The local nature of PAIRS ignores global connectivity, while CONS assigns the same score to all committees whose induced graphs are connected. Thus, CONS cannot distinguish, for example, between a clique and two cohesive groups joined by a single fragile bridge. This lack of granularity is already noted by Dong et al., who point out settings in which CONS becomes uninformative and suggest shortest-path length as a possible refinement.
More broadly, the interlacing graph records positive relations induced by shared approval, but does not capture how disagreement between different parts of the electorate may persist or dissipate.
In this paper, we retain this voter-network perspective but analyze the robustness of the connections between different parts of the electorate using edge-expansion . We additionally give the induced network a complementary information-diffusion interpretation, in which it governs how voters’ opinions evolve.
Related work
Graph measures of connectivity. Network science characterizes community structure through cohesive groups with relatively sparse connections between them Girvan and Newman [26 ] , while work on network polarization adopts closely related boundary-based notions [28 , 29 ] . From this perspective, the relevant question is not only how well connected the network is, but how easily a large subset can be separated from the collective. We therefore propose the use of edge-expansion Alon [3 ] , also known as the isoperimetric number Mohar [38 ] or Cheeger constant , that measures the worst case ratio between the boundary of a group and its size. We refer to the graph parameter as the Cheeger constant , and to the corresponding committee-selection objective as CHGR. Intuitively, edge-expansion measures the extent to which a graph is bottlenecked, by identifying weak ties of large clusters. It is a classic graph-theoretic measure with established connections to graph clustering and community detection Bühler and Hein [10 ] and other boundary structures used to quantify polarization and political-network separation [28 , 21 ] .
Polarization. Polarization has received rapidly growing attention in recent years in the social choice literature, with most prior work focusing on ordinal preferences. Can et al. [11 ] study how polarization is manifested in preference profiles, and more recent work by Faliszewski et al. [18 ] develops computational measures of polarization. A separate line of work considers polarizing individual alternatives. Gehrlein [25 ] studies candidates that tend to be ranked at the extremes of voters’ preferences; building on this notion, Barbaro [5 ] studies how different voting rules fare in avoiding the election of polarizing candidates. In multiwinner settings, Delamazure et al. [14 ] study the selection of maximally conflicting pairs of candidates under ordinal preferences. To the best of our knowledge, Dong et al. [16 ] were the first to study polarization in approval-based committee selection, through the interlacing framework that we build upon here.
Our contribution
Our results show that CHGR, beyond its intuitive interpretation, substantially refines the PAIRS and CONS measures. In particular, we show that since PAIRS prioritize dense local connections over bridges, it may fail to select even near-perfect committees. On unrestricted profiles, two CONS-optimal committees can have CHGR scores differing by a quadratic factor in the number of voters. On CI profiles the separation asymptotically linear.
A second complementary justification for using CHGR in the context of electing committees, comes from information diffusion. Joint approval is an observable signal of similarity in electoral preferences, so the committee-induced preferences graph can be viewed as a stylized network of potential interaction or information flow. We use the classical DeGroot model DeGroot [13 ] of opinion diffusion as an additional interpretation of the interlacing model, thereby identifying polarized committees with a slower time to reach consensus among voters in the induced voter graph. The latter, in turn, can be bounded by its CHGR value.
We then turn to the computational aspects of finding an optimal CHGR committee. As is the case with PAIRS and CONS, finding a CHGR-optimal committee is NP-hard. In contrast, even finding the CHGR value of a fixed committee is hard, and hardness of finding an optimal committee extends to the restricted VI preferences domain. Yet, we manage to obtain a polynomial-time algorithm for fixed k k k , and quasi-polynomial complexity for polylogarithmic k k k in restricted preference domains.
Preliminaries
Approval-Based Multiwinner Voting. In Approval-Based Multiwinner Voting (see Lackner and Skowron [32 ] for a complete survey), a set N N N of n ∈ N n \in\mathbb{N} n ∈ N voters wish to select a committee of k ∈ N k \in\mathbb{N} k ∈ N members from a set M M M of m ∈ N m \in\mathbb{N} m ∈ N candidates. Voter i ∈ N i \in N i ∈ N approves a subset of candidates A i ⊆ M A_i \subseteq M A i ⊆ M . The support of candidate c ∈ M c \in M c ∈ M is the set of voters approving c c c given by V c = { i ∈ N ∣ c ∈ A i } V_c = \{i \in N \mid c \in A_i\} V c = { i ∈ N ∣ c ∈ A i } . The profile of voters A = ( A i ) i ∈ N A = (A_i)_{i \in N} A = ( A i ) i ∈ N defines the joint preferences of all voters. An election is defined by the tuple E = ( M , N , A , k ) E = (M, N, A, k) E = ( M , N , A , k ) , i.e., the set of candidates, the set of voters, their preferences, and the target committee size. For an election ( M , N , A , k ) (M, N, A, k) ( M , N , A , k ) , the set of possible results, i.e., k k k -sized subsets of M M M , is denoted by C = { C ⊆ M ∣ ∣ C ∣ = k } \mathcal{C} = \{C \subseteq M \mid|C| = k\} C = { C ⊆ M ∣ ∣ C ∣ = k } . The result of an election is determined by a voting rule, a function that maps elections to a committee C ∈ C C \in\mathcal{C} C ∈ C .
Interlacing Committees
2.1. Interlacing Committees. Dong et al. [16 ] formulate an approval profile as a hypergraph in which voters are vertices and each candidate induces a hyperedge containing its approving voters. We use an equivalent voter-graph representation, which is more convenient for the graph-theoretic analysis developed here.
Preferences Graph. For an election E = ( M , N , A , k ) E = (M, N, A, k) E = ( M , N , A , k ) , we define the preferences graph of E E E to be the unweighted undirected graph G E = ( N , E E ) G^E = (N, E^E) G E = ( N , E E ) , where
E E = { { i , j } ∈ ( N 2 ) ∣ A i ∩ A j ≠ ∅ } . E^E = \left\{\{i,j\} \in\binom{N}{2} \mid A_i \cap A_j \ne\varnothing\right\}. E E = { { i , j } ∈ ( 2 N ) ∣ A i ∩ A j = ∅ } .
Example 1 (Running example). Consider an election with voters N = { v 1 , v 2 , v 3 , v 4 } N = \{v_1, v_2, v_3, v_4\} N = { v 1 , v 2 , v 3 , v 4 } , candidates M = { a , b , c , d } M = \{a, b, c, d\} M = { a , b , c , d } , committee size k = 3 k = 3 k = 3 , and approval ballots A v 1 = { a , b , c } A_{v_1} = \{a, b, c\} A v 1 = { a , b , c } , A v 2 = { a , d } A_{v_2} = \{a, d\} A v 2 = { a , d } , A v 3 = { b , d } A_{v_3} = \{b, d\} A v 3 = { b , d } , A v 4 = { c } A_{v_4} = \{c\} A v 4 = { c } . For example, A v 1 ∩ A v 2 = { a } A_{v_1} \cap A_{v_2} = \{a\} A v 1 ∩ A v 2 = { a } , so { v 1 , v 2 } \{v_1, v_2\} { v 1 , v 2 } is an edge of the preferences graph. In contrast, A v 2 ∩ A v 4 = ∅ A_{v_2} \cap A_{v_4} = \varnothing A v 2 ∩ A v 4 = ∅ , so { v 2 , v 4 } \{v_2, v_4\} { v 2 , v 4 } is not an edge. Thus, E E = { { v 1 , v 2 } , { v 1 , v 3 } , { v 1 , v 4 } , { v 2 , v 3 } } E^E = \{\{v_1, v_2\}, \{v_1, v_3\}, \{v_1, v_4\}, \{v_2, v_3\}\} E E = {{ v 1 , v 2 } , { v 1 , v 3 } , { v 1 , v 4 } , { v 2 , v 3 }} . The resulting preferences graph is shown in Figure 1 a.
Figure 1. The running example. (a) shows the full preferences graph, with each edge labeled by the candidate witnessing it. Panels (b)–(d) show committee-induced graphs. Dashed edge in panel (b) belongs to the preferences graph and absent from the committee graph.
Committee-Induced Preferences Graph. (referred to as committee graphs for short). For each committee C ∈ C C \in\mathcal{C} C ∈ C , we denote by G C E = ( N , E C E ) G^E_C = (N, E^E_C) G C E = ( N , E C E ) the spanning subgraph of G E G^E G E in which two voters are adjacent iff they jointly approve a candidate in C C C .
E C E = { { i , j } ∈ E E ∣ A i ∩ A j ∩ C ≠ ∅ } . E^E_C = \left\{\{i,j\} \in E^E \mid A_i \cap A_j \cap C \ne\varnothing\right\}. E C E = { { i , j } ∈ E E ∣ A i ∩ A j ∩ C = ∅ } .
The election parameter is omitted from graph notation when clear from context.
Running example (continued). Consider the committee C 0 = { a , b , d } C_0 = \{a,b,d\} C 0 = { a , b , d } . The edges { v 1 , v 2 } \{v_1,v_2\} { v 1 , v 2 } , { v 1 , v 3 } \{v_1,v_3\} { v 1 , v 3 } , and { v 2 , v 3 } \{v_2,v_3\} { v 2 , v 3 } remain in the committee graph, witnessed respectively by a a a , b b b , and d d d . However, although { v 1 , v 4 } ∈ E E \{v_1,v_4\} \in E^{\mathcal{E}} { v 1 , v 4 } ∈ E E , its only witnessing candidate is c ∉ C 0 c \notin C_0 c ∈ / C 0 . Hence this edge does not belong to E C 0 E E^{\mathcal{E}}_{C_0} E C 0 E . Consequently, G C 0 E G^{\mathcal{E}}_{C_0} G C 0 E consists of a triangle on v 1 , v 2 , v 3 v_1,v_2,v_3 v 1 , v 2 , v 3 and the isolated voter v 4 v_4 v 4 , as shown in fig:1b .
Connectivity Objectives. Following Dong et al., PAIRS and CONS are numerical scores of committees. For C ∈ C C \in\mathcal{C} C ∈ C , define
PAIRS ( C , E ) : = ∣ E C E ∣ , \operatorname{PAIRS}(C,\mathcal{E}) := \lvert E^{\mathcal{E}}_C\rvert, PAIRS ( C , E ) := ∣ E C E ∣ ,
CONS ( C , E ) : = ∣ { { u , v } ∈ ( N 2 ) ∣ u ∼ C v } ∣ . \operatorname{CONS}(C,\mathcal{E}) := \left\lvert\left\{\{u,v\} \in\binom{N}{2} \mid u \sim_C v\right\}\right\rvert. CONS ( C , E ) := { { u , v } ∈ ( 2 N ) ∣ u ∼ C v } .
where u ∼ C v u \sim_C v u ∼ C v means that u u u and v v v are connected by a path in G C E G^{\mathcal{E}}_C G C E . We overload the objective names for the associated voting rules: PAIRS(E \mathcal{E} E ) and CONS(E \mathcal{E} E ) denote a score-maximizing committee, subject to some tie-breaking mechanism.
An optimizing committee need not be unique; unless stated otherwise, the rule returns an arbitrary maximizer. Thus, statements about what a rule may select versus what every optimizer satisfies are distinguished explicitly.
Definition 1 (Distinguishing Committees). For any committee score f ( C , E ) f(C,\mathcal{E}) f ( C , E ) , we say that f f f distinguishes between C , C ′ C,C' C , C ′ if their scores differ, and does not distinguish between them otherwise.
Definition 2 (Connecting Committees). A committee C C C is connecting if G C E G^{\mathcal{E}}_C G C E is connected, and non-connecting otherwise.
Running example (continued). Besides C 0 C_0 C 0 , consider C 1 = { a , c , d } C_1 = \{a,c,d\} C 1 = { a , c , d } . Its committee graph is the path v 3 − v 2 − v 1 − v 4 v_3 - v_2 - v_1 - v_4 v 3 − v 2 − v 1 − v 4 ; see fig:1c .
Each of C 0 , C 1 C_0,C_1 C 0 , C 1 induce three edges, and hence PAIRS ( C 0 , E ) = PAIRS ( C 1 , E ) = 3 \operatorname{PAIRS}(C_0,\mathcal{E}) = \operatorname{PAIRS}(C_1,\mathcal{E}) = 3 PAIRS ( C 0 , E ) = PAIRS ( C 1 , E ) = 3 . Thus, PAIRS does not distinguish between them and may in particular select the non-connecting committee C 0 C_0 C 0 .
For CONS, the component of C 0 C_0 C 0 containing v 1 , v 2 , v 3 v_1,v_2,v_3 v 1 , v 2 , v 3 contributes all 3 connected voter pairs, while v 4 v_4 v 4 is isolated. Hence CONS ( C 0 , E ) = 3 \operatorname{CONS}(C_0,\mathcal{E}) = 3 CONS ( C 0 , E ) = 3 . By contrast, C 1 C_1 C 1 is connected, so every pair of voters is connected and CONS ( C 1 , E ) = ( 4 2 ) = 6 \operatorname{CONS}(C_1,\mathcal{E}) = \binom{4}{2} = 6 CONS ( C 1 , E ) = ( 2 4 ) = 6 . This is the maximum possible CONS value, and therefore C 1 C_1 C 1 is CONS-optimal.
Expansion and CHEEGER
Edge-Expansion. We use the standard edge-expansion terminology and definitions of Mohar [38 ] , adapted to our notation. For a graph G = ( V , E ) G = (V,E) G = ( V , E ) and a set S ⊆ V S \subseteq V S ⊆ V , the boundary of S S S is
∂ G ( S ) = { { u , v } ∈ E ∣ u ∈ S , v ∉ S } . \partial_G(S) = \{\{u,v\} \in E \mid u \in S,\ v \notin S\}. ∂ G ( S ) = {{ u , v } ∈ E ∣ u ∈ S , v ∈ / S } .
For a nonempty proper set S S S , its edge-expansion is
ϕ G ( S ) = ∣ ∂ G ( S ) ∣ min { ∣ S ∣ , ∣ V ∖ S ∣ } . \phi_G(S) = \frac{\lvert\partial_G(S)\rvert}{\min\{\lvert S\rvert,\lvert V \setminus S\rvert\}}. ϕ G ( S ) = min {∣ S ∣ , ∣ V ∖ S ∣} ∣ ∂ G ( S )∣ .
The edge-expansion , or Cheeger constant , of G G G is
h ( G ) = min ∅ ≠ S ⊆ V ∣ S ∣ ≤ ∣ V ∣ / 2 ∣ ∂ G ( S ) ∣ ∣ S ∣ . h(G) = \min_{\substack{\varnothing\ne S \subseteq V\\ \lvert S\rvert\le\lvert V\rvert/2}} \frac{\lvert\partial_G(S)\rvert}{\lvert S\rvert}. h ( G ) = ∅ = S ⊆ V ∣ S ∣ ≤ ∣ V ∣ /2 min ∣ S ∣ ∣ ∂ G ( S )∣ .
Graph parameters are omitted from ∂ ( ) \partial() ∂ ( ) and ϕ ( ) \phi() ϕ ( ) when clear from context. Intuitively, edge-expansion measures the “bottleneckedness” of a graph by seeking a relatively large set with few edges connecting it to the rest of the graph. The complexity of calculating the Cheeger constant of a graph is known to be NP-hard Leighton and Rao [33 ] ; Garey et al. [23 ] .
CHGR Objective. The CHGR score of committee C ∈ C C \in\mathcal{C} C ∈ C is CHGR ( C , E ) : = h ( G C E ) \operatorname{CHGR}(C,\mathcal{E}) := h(G^{\mathcal{E}}_C) CHGR ( C , E ) := h ( G C E ) . The associated rule CHGR(E \mathcal{E} E ) returns an arbitrary maximizing committee.
Running example (continued). Consider the committee C 2 = { a , b , c } C_2 = \{a,b,c\} C 2 = { a , b , c } . Since G C 0 E G^{\mathcal{E}}_{C_0} G C 0 E is disconnected, CHGR ( C 0 , E ) = 0 \operatorname{CHGR}(C_0,\mathcal{E}) = 0 CHGR ( C 0 , E ) = 0 .
For C 1 C_1 C 1 , consider S = { v 2 , v 3 } S = \{v_2,v_3\} S = { v 2 , v 3 } . The path has only the edge { v 1 , v 2 } \{v_1,v_2\} { v 1 , v 2 } crossing this cut, and therefore ϕ G C 1 ( S ) = 1 2 \phi_{G_{C_1}}(S) = \frac{1}{2} ϕ G C 1 ( S ) = 2 1 . Since the graph is connected, every nontrivial cut has at least one boundary edge, and no admissible smaller side has more than two vertices. Thus, CHGR ( C 1 , E ) = 1 2 \operatorname{CHGR}(C_1,\mathcal{E}) = \frac{1}{2} CHGR ( C 1 , E ) = 2 1 . For the star induced by C 2 C_2 C 2 , every nonempty set S S S with ∣ S ∣ ≤ 2 |S| \leq2 ∣ S ∣ ≤ 2 has at least ∣ S ∣ |S| ∣ S ∣ boundary edges. Consequently, CHGR ( C 2 , E ) = 1 \operatorname{CHGR}(C_2,\mathcal{E}) = 1 CHGR ( C 2 , E ) = 1 . The only remaining size-3 committee, { b , c , d } \{b,c,d\} { b , c , d } , induces another four-vertex path and therefore also has CHGR score 1 / 2 1/2 1/2 . Hence C 2 C_2 C 2 is the unique CHGR-optimal committee.
Thus, on this single election, PAIRS fails to distinguish any of the displayed committees, CONS distinguishes connectivity but ties the path and the star, while CHGR further distinguishes the robustness of their connections.
Spatial Preferences Domains
Besides unrestricted approval profiles, we consider three standard domains of spatial one-dimensional preferences Elkind and Lackner [17 ] ; ); Godziszewski et al. [27 ] ; ); Brill et al. [9 ] .
An election is in the voter-interval (VI) domain if there is an ordering v 1 , … , v n v_1,\ldots,v_n v 1 , … , v n of the voters such that every candidate support is an interval of this order. That is, for every c ∈ M c \in M c ∈ M with V c ≠ ∅ V_c \ne\varnothing V c = ∅ , there exist p ≤ q p \leq q p ≤ q such that V c = { v p , … , v q } V_c = \{v_p,\ldots,v_q\} V c = { v p , … , v q } . Similarly, an election is in the candidate-interval (CI) domain if there is an ordering c 1 , … , c m c_1,\ldots,c_m c 1 , … , c m of the candidates such that every nonempty approval ballot is an interval of this order. The voter-candidate-interval (VCI) domain is a generalization of both VI and CI. An election is in the VCI domain if there is a set of voter positions { p v } v ∈ N \{p_v\}_{v\in N} { p v } v ∈ N , a set of candidate positions { p c } c ∈ M \{p_c\}_{c\in M} { p c } c ∈ M , and a set of non-negative radii for voters and candidates { r v } v ∈ N ∪ { r c } c ∈ M \{r_v\}_{v\in N} \cup\{r_c\}_{c\in M} { r v } v ∈ N ∪ { r c } c ∈ M such that
A i = { c ∈ M ∣ [ p v i − r v i , p v i + r v i ] ∩ [ p c − r c , p c + r c ] ≠ ∅ } . A_i = \{c \in M \mid[p_{v_i}-r_{v_i},p_{v_i}+r_{v_i}] \cap[p_c-r_c,p_c+r_c] \ne\varnothing\}. A i = { c ∈ M ∣ [ p v i − r v i , p v i + r v i ] ∩ [ p c − r c , p c + r c ] = ∅ } .
Thus, voters and candidates can be represented by intervals on the real line so that a voter approves a candidate if and only if their intervals intersect. The domains are visualized schematically in Figure 2 .
Figure 2. Schematic illustration of VCI domain. Voters and candidates are embedded on a common one-dimensional spectrum represented by an interval of acceptable political views. Approval is determined by interval intersection.
Candidate Dominance. A candidate c ′ ∈ M c' \in M c ′ ∈ M is dominated by a candidate c ∈ M c \in M c ∈ M if V c ′ ⊊ V c V_{c'} \subsetneq V_c V c ′ ⊊ V c . Dong et al. Dong et al. [16 ] show that a dominance-free VCI election is CI. They continue to argue that in the interlacing model dominated candidates have no effect on the resulting preferences graph. Indeed, if c ′ c' c ′ is dominated by c c c then for every i ≠ j i \ne j i = j we have c ′ ∈ A i ∩ A j → c ∈ A i ∩ A j c' \in A_i \cap A_j \to c \in A_i \cap A_j c ′ ∈ A i ∩ A j → c ∈ A i ∩ A j . Moreover, replacing a dominated candidate in a committee by a candidate that dominates it weakly increases the objective value, since all objectives considered here are monotone under the addition of edges. Thus, an optimal committee can be chosen after removing dominated candidates; if this leaves fewer than k k k candidates, the committee can be completed with removed dominated candidates without changing its committee graph. Dong et al. Dong et al. [16 ] use the same dominance preprocessing in their polynomial-time algorithms for PAIRS and CONS in the VCI domain.
Structural Properties
We now compare the structural behavior of the three interlacing objectives. We first show that optimizing direct overlap can lead to severe failures of global interlacing, and then compare CONS and CHGR once connectivity is achieved.
PAIRS as suboptimal interlacing objective
Theorem 1. For every δ > 0 \delta> 0 δ > 0 , there exists an election admitting a connecting committee such that the unique PAIRS-optimal committee has no connected component containing more than a δ \delta δ -fraction of the voters. Moreover, the unique PAIRS minimizer is the unique connecting committee.
The construction contrasts two size-L L L committees X X X and Y Y Y . We choose L = q ( q − 1 ) + 1 L = q(q-1) + 1 L = q ( q − 1 ) + 1 from a Singer perfect difference set Singer [42 ] and split the electorate into a small population of size ε n \varepsilon n ε n and a large population of size ( 1 − ε ) n (1-\varepsilon)n ( 1 − ε ) n , where ε < δ \varepsilon< \delta ε < δ . The X X X -candidates create a highly regular pattern of dense overlap inside the small population: the perfect-difference-set property ensures that every pair of small voter groups is linked by exactly one X X X -candidate. The Y Y Y -candidates provide the bridges that connect the large population and attach the small voters, making Y Y Y the unique connecting committee.
The parameters are chosen so that these global bridges are expensive in the PAIRS: replacing any X X X - by Y Y Y -member strictly decreases the number of directly linked voter pairs. Hence X X X is the unique PAIRS-optimal committee. Yet under X X X only the ε n \varepsilon n ε n voters in the small population form a nontrivial connected component, while every voter in the large population is isolated. Since ε \varepsilon ε can be arbitrarily small, the largest connected component of the PAIRS optimum can contain an arbitrarily small fraction of the electorate. The full construction and edge-counting proof are given in Appendix A.
Dong et al.’s Example 3.1 shows that PAIRS can fail to distinguish a connected committee from a disconnected one. Theorem 1 gives a stronger asymptotic failure: even when a committee connecting all voters exists, the unique PAIRS optimum may interlace only an arbitrarily small fraction of the electorate, favoring dense local connectivity over bridges necessary for global interlacing.
CONS suboptimal for bottlenecks
In contrast to PAIRS, CONS is, as already observed by Dong et al., a global connectivity objective. Indeed, every connecting committee attains the maximum possible CONS score. The following observation shows that CHGR shares this basic connectivity sensitivity.
Observation 1. Let G G G be an undirected graph. Then h ( G ) = 0 h(G) = 0 h ( G ) = 0 iff G G G is disconnected.
Corollary 2. For a fixed election E \mathcal{E} E :
(1) the CHGR score does not distinguish between committees whose committee graphs are disconnected; and
(2) if a connecting committee exists, every CHGR-optimal committee is connecting.
Thus, both CONS and CHGR return a connecting committee whenever one exists. However, since all connecting committees achieve the same maximal CONS score, it cannot distinguish between them. On the other hand, CHGR exhibits greater granularity among connecting committees, as demonstrated by this example.
Example 2. Let n = 2 x n = 2x n = 2 x with x ≥ 2 x \ge2 x ≥ 2 , let the candidate set be { a , b , c , d } \{a,b,c,d\} { a , b , c , d } , and let k = 3 k = 3 k = 3 . The voters are
Table 1.
For C = { a , b , c } C = \{a,b,c\} C = { a , b , c } , the committee graph consists of two copies of K x K_x K x joined by a single bridge edge. Every committee containing d d d induces K 2 x K_{2x} K 2 x , since every voter approves d d d . Hence all four committees are connected and have the same maximal CONS score ( 2 x 2 ) \binom{2x}{2} ( 2 2 x ) .
For the polarizing committee, all of K x K_x K x gives a cut with one crossing edge. Connectedness gives the matching lower bound, so C H G R ( { a , b , c } , E ) = 1 x \mathrm{CHGR}(\{a,b,c\},\mathcal{E}) = \frac{1}{x} CHGR ({ a , b , c } , E ) = x 1 . For a complete graph K 2 x K_{2x} K 2 x , a side of size s ≤ x s \le x s ≤ x has expansion 2 x − s 2x-s 2 x − s , minimized at s = x s=x s = x , and hence h ( K 2 x ) = x h(K_{2x}) = x h ( K 2 x ) = x . Thus CHGR strictly prefers each committee containing d d d to { a , b , c } \{a,b,c\} { a , b , c } , while CONS ties all four. In particular, under some tie-breaking CONS may select the committee whose graph has a single fragile bridge between two dense voter groups.
Figure 3. (a) Committee { a , b , c } \{a,b,c\} { a , b , c } — two dense communities connected by a weak bridge; ∣ ∂ S ∣ = 1 |\partial S|=1 ∣ ∂ S ∣ = 1 and Cheeger value 1 / x 1/x 1/ x . (b) Any committee containing d d d — all voters form one cohesive collective; ∣ ∂ S ∣ = x 2 |\partial S|=x^2 ∣ ∂ S ∣ = x 2 and Cheeger value x x x . Two committee graphs induced by the same preferences graph. Both committees attain the maximal CONS value (2 x 2^x 2 x ), but their Cheeger values differ by a quadratic factor. The dashed lines indicate minimum-expansion cuts.
Moreover, the polarized committee attains the minimum possible positive CHGR score for any n n n voters, since ∀ S ≠ ∅ \forall S\ne\varnothing ∀ S = ∅ , ∂ ( S ) ≥ 1 \partial(S)\ge1 ∂ ( S ) ≥ 1 and x x x is the largest possible smaller side subset. Also, K n K_n K n attains maximal expansion for every graph over n n n vertices. We therefore obtain a tight Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) worst case ratio between the best and worst CHGR scores of a given election.
CONS vs. CHEEGER on CI profiles
On unrestricted profiles, Example 2 shows that CONS may tie committees whose CHGR scores differ quadratically in the number of voters. On CI profiles the geometry rules out such a gap, but a linear gap remains possible. We first show the upper bound (proof in Appendix B).
Lemma 3 (CI gateway lemma). Let E \mathcal{E} E be a CI election on n ≥ 2 n\ge2 n ≥ 2 voters. Fix a connecting committee C C C and nonempty S ⊆ N S\subseteq N S ⊆ N with ∣ S ∣ ≤ n / 2 |S|\le n/2 ∣ S ∣ ≤ n /2 . Put B = ∣ ∂ G C ( S ) ∣ B=|\partial_{G_C}(S)| B = ∣ ∂ G C ( S ) ∣ . Let R S ⊆ S R_S\subseteq S R S ⊆ S and R S ‾ ⊆ N ∖ S R_{\overline{S}}\subseteq N\setminus S R S ⊆ N ∖ S be the vertices incident to these B B B boundary edges. Then every edge crossing the cut S ∣ S ‾ S\mid\overline{S} S ∣ S in G E G_{\mathcal{E}} G E has at least one endpoint in R S ∪ R S ‾ R_S\cup R_{\overline{S}} R S ∪ R S .
Theorem 4. Let E \mathcal{E} E be a CI election on n ≥ 2 n\ge2 n ≥ 2 voters. For every connecting committee C C C and every feasible committee C ′ C' C ′ ,
CHGR ( C ′ , E ) ≤ n CHGR ( C , E ) . \operatorname{CHGR}(C',\mathcal{E})\le n\operatorname{CHGR}(C,\mathcal{E}). CHGR ( C ′ , E ) ≤ n CHGR ( C , E ) . Consequently every connecting committee is an n n n -approximation for the CHGR objective.
Proof. Let S S S be a smaller side of a CHGR-optimal cut of G C G_C G C , and write s = ∣ S ∣ s=|S| s = ∣ S ∣ , B = ∣ ∂ G C ( S ) ∣ B=|\partial_{G_C}(S)| B = ∣ ∂ G C ( S ) ∣ . Thus 1 ≤ s ≤ n / 2 1\le s\le n/2 1 ≤ s ≤ n /2 and CHGR ( C , E ) = B s \operatorname{CHGR}(C,\mathcal{E})=\frac{B}{s} CHGR ( C , E ) = s B . Let R S R_S R S and R S ‾ R_{\overline{S}} R S be as in Lemma 3. Since each boundary edge has exactly one endpoint on each side, ∣ R S ∣ , ∣ R S ‾ ∣ ≤ B |R_S|,|R_{\overline{S}}|\le B ∣ R S ∣ , ∣ R S ∣ ≤ B . By Lemma 3, every edge of ∂ G C ′ ( S ) \partial_{G_{C'}}(S) ∂ G C ′ ( S ) has an endpoint in R S ∪ R S ‾ R_S\cup R_{\overline{S}} R S ∪ R S . Hence
∣ ∂ G C ′ ( S ) ∣ ≤ ∣ R S ∣ ( n − s ) + ∣ R S ‾ ∣ s ≤ B ( n − s ) + B s = B n . |\partial_{G_{C'}}(S)|\le|R_S|(n-s)+|R_{\overline{S}}|s\le B(n-s)+Bs=Bn. ∣ ∂ G C ′ ( S ) ∣ ≤ ∣ R S ∣ ( n − s ) + ∣ R S ∣ s ≤ B ( n − s ) + B s = B n .
Evaluating C ′ C' C ′ on this particular cut gives CHGR ( C ′ , E ) ≤ B n s = n CHGR ( C , E ) . \operatorname{CHGR}(C',\mathcal{E})\le\frac{Bn}{s}=n\operatorname{CHGR}(C,\mathcal{E}). CHGR ( C ′ , E ) ≤ s B n = n CHGR ( C , E ) .
Theorem 4 applies in particular to every CONS-optimal committee whenever a connecting committee exists. Combined with the standard dominance preprocessing of VCI profiles, it also applies to a connecting committee selected from the reduced CI instance.
The linear factor is asymptotically tight. Moreover, it remains tight even under the natural secondary criterion of maximizing PAIRS among CONS-optimal committees.
Theorem 5 (CONS vs CHGR lower bound). For infinitely many n n n , there exists a dominance-free CI election with two CONS-optimal committees C B , C G C_B,C_G C B , C G such that CHGR ( C G , E ) CHGR ( C B , E ) = Θ ( n ) \frac{\operatorname{CHGR}(C_G,\mathcal{E})}{\operatorname{CHGR}(C_B,\mathcal{E})}=\Theta(n) CHGR ( C B , E ) CHGR ( C G , E ) = Θ ( n ) .
Proof. Let E \mathcal{E} E be an election with k = 4 k=4 k = 4 , candidates ordered a < b < c < d < e a<b<c<d<e a < b < c < d < e , and let the voter multiplicities be
Table 2.
Every ballot is an interval of the displayed candidate order, so the profile is CI. The five candidate supports are pairwise incomparable, so no candidate is dominated. Set C B = { a , b , c , e } C_B=\{a,b,c,e\} C B = { a , b , c , e } , C G = { a , c , d , e } C_G=\{a,c,d,e\} C G = { a , c , d , e } . These are the only connecting size-4 committees. Omitting a a a isolates the { a } \{a\} { a } voter, omitting e e e isolates the { e } \{e\} { e } voter, and omitting c c c separates the voters represented by a , b a,b a , b from those represented by d , e d,e d , e . By contrast, both C B C_B C B and C G C_G C G connect all voters. Thus both are CONS-optimal.
Next, under C B C_B C B , let S B S_B S B consist of the t t t voters of type { d , e } \{d,e\} { d , e } together with the single voter of type { e } \{e\} { e } . In G C B G_{C_B} G C B these t + 1 t+1 t + 1 voters are joined to the rest of the graph only through the single voter of type { c , d , e } \{c,d,e\} { c , d , e } , and each has exactly one edge across this cut. Therefore CHGR ( C B , E ) ≤ ϕ G C B ( S B ) = 1 \operatorname{CHGR}(C_B,\mathcal{E})\le\phi_{G_{C_B}}(S_B)=1 CHGR ( C B , E ) ≤ ϕ G C B ( S B ) = 1 .
For C G C_G C G , partition the voters into six consecutive blocks so that the committee graph contains a spanning blow-up of a six-vertex path, with complete bipartite graphs between consecutive blocks. A case analysis on how a cut intersects these blocks gives a matching linear lower bound on every cut, while a singleton cut gives the corresponding upper bound; hence ( CHGR ( C G , E ) = Θ ( t ) ) = Θ ( n ) (\operatorname{CHGR}(C_G,\mathcal{E})=\Theta(t))=\Theta(n) ( CHGR ( C G , E ) = Θ ( t )) = Θ ( n ) . Details appear in Appendix B.
From the linear bound and CHGR ( C B , E ) ≤ 1 \operatorname{CHGR}(C_B,\mathcal{E})\le1 CHGR ( C B , E ) ≤ 1 , we get
CHGR ( C G , E ) CHGR ( C B , E ) = Ω ( n ) . \frac{\operatorname{CHGR}(C_G,\mathcal{E})}{\operatorname{CHGR}(C_B,\mathcal{E})}=\Omega(n). CHGR ( C B , E ) CHGR ( C G , E ) = Ω ( n ) .
The matching O ( n ) O(n) O ( n ) bound follows from Theorem 4. □
Theorem 5 suggests a worst-case asymptotic order for general CONS. The following corollary demonstrates that this is not solely the result of a carefully crafted adversarial selection but rather the result of a natural CONS tie-breaking scheme using PAIRS.
Corollary 6. On CI profiles that admit a connecting committee, the worst-case multiplicative separation between the CHGR score of a CONS-optimal with PAIRS tie-break committee and the CHGR optimum is Θ ( n ) \Theta(n) Θ ( n ) .
Proof. Let C B , C G C_B,C_G C B , C G as in the proof of Theorem 5. We show that PAIRS ( C B , E ) > PAIRS ( C G , E ) \operatorname{PAIRS}(C_B,\mathcal{E})>\operatorname{PAIRS}(C_G,\mathcal{E}) PAIRS ( C B , E ) > PAIRS ( C G , E ) . Start from the common subcommittee { a , c , e } \{a,c,e\} { a , c , e } . Adding b b b creates exactly the edges between the t + 1 t+1 t + 1 voters of type { a , b } \{a,b\} { a , b } and the t + 1 t+1 t + 1 voters of type { b , c } \{b,c\} { b , c } that were not already covered by a a a or c c c . The marginal PAIRS contribution is therefore ( t + 1 ) 2 (t+1)^2 ( t + 1 ) 2 . Adding d d d instead creates exactly the edges between the t t t voters of type { c , d } \{c,d\} { c , d } and the t t t voters of type { d , e } \{d,e\} { d , e } that were not already covered by c c c or e e e , for a marginal contribution t 2 t^2 t 2 . Consequently, PAIRS ( C B , E ) − PAIRS ( C G , E ) = 2 t + 1 > 0 \operatorname{PAIRS}(C_B,\mathcal{E})-\operatorname{PAIRS}(C_G,\mathcal{E})=2t+1>0 PAIRS ( C B , E ) − PAIRS ( C G , E ) = 2 t + 1 > 0 . Thus, PAIRS tie-breaking selects C B C_B C B . □
Interpretation. The result separates two notions that coincide at the level of mere connectivity. CONS assigns every connecting committee the same maximum score, whereas CHGR distinguishes how robustly the electorate is connected. The CI structure limits the damage: every connecting committee is automatically an n n n -approximation to CHGR. Nevertheless this guarantee is tight, and even a natural secondary objective that rewards additional direct voter links—PAIRS—can force the asymptotically worst-order CHGR outcome. Thus the linear gap is not an artifact of adversarial tie-breaking; it persists under a canonical refinement using the other interlacing objective.
Information Diffusion
In this section we formalize a secondary interpretation for the interlacing model using the DeGroot model of opinion aggregation DeGroot [13 ] ; Berger [6 ] (see also Jackson [30 ] for a broader overview). In a DeGroot process, every agent holds a real-valued opinion. At each synchronous round, agents update their opinions to a weighted average of opinions of the individuals with whom they interact. Interactions are described by a fixed underlying network, with edges weighted by the relative influence individuals have on each other.
We interpret the preferences graph as an approximation of the underlying social interaction network among voters. This interpretation is supported by empirical evidence of a correlation between political similarity and social relationships, including interaction frequency Bond and Messing [7 ] ; Algan et al. [2 ] . Indeed, the correspondence between political orientation and network community structure was demonstrated in early studies Adamic and Glance [1 ] ; Newman [39 ] , and community detection has since become an established tool for studying political polarization Garimella et al. [24 ] ; Interian et al. [29 ] ; Zhang et al. [44 ] .
We first review the relevant Markov-chain and DeGroot background. We then define a DeGroot process induced by a selected committee and characterize when it reaches global consensus. Finally, we relate the convergence rate of this process to the CHGR objective through conductance and mixing time.
Extended formal background can be found in Appendix C.
Interlacing DeGroot Model
We model interactions through the committee graph, so that only connections supported by the selected committee contribute to the diffusion process. For an election E \mathcal{E} E with n ≥ 2 n \ge2 n ≥ 2 voters, and a committee C C C , we describe a symmetric and homogeneous influence diffusion process where ‘similar’ voters (who approve similar candidate) repeatedly meet and average their positions. Let L C = D − A L_C = D - A L C = D − A be the combinatorial Laplacian of G C E G_C^{\mathcal{E}} G C E , with D D D its diagonal degree matrix and A A A its adjacency matrix. For a global susceptibility parameter β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) , we consider
P C ( β ) : = I − β n − 1 L C . P_C^{(\beta)} := I - \frac{\beta}{n-1}L_C. P C ( β ) := I − n − 1 β L C .
Equivalently, every edge incident to voter i i i receives influence weight β / ( n − 1 ) \beta/(n-1) β / ( n − 1 ) , while voter i i i retains self-weight 1 − β d i n − 1 1-\frac{\beta d_i}{n-1} 1 − n − 1 β d i , where d i d_i d i is the degree of i i i in G C G_C G C . The normalization by n − 1 n-1 n − 1 uses the largest possible degree of a committee-induced graph and therefore applies uniformly to all committees. Constant-edge-weight iterations of the form I − α L I-\alpha L I − α L are commonly used in distributed averaging and consensus Olfati-Saber and Murray [40 ] ; Xiao and Boyd [43 ] .
For the mixing-time analysis we take β = 1 / 2 \beta= 1/2 β = 1/2 and abbreviate P C : = P C ( 1 / 2 ) P_C := P_C^{(1/2)} P C := P C ( 1/2 ) . If Q C = I − 1 n − 1 L C Q_C = I-\frac{1}{n-1}L_C Q C = I − n − 1 1 L C , then
P C ( 1 / 2 ) = 1 2 ( I + Q C ) , P_C^{(1/2)} = \frac{1}{2}(I+Q_C), P C ( 1/2 ) = 2 1 ( I + Q C ) ,
the standard half-lazification of Q C Q_C Q C . Lazification maps every eigenvalue λ ∈ [ − 1 , 1 ] \lambda\in[-1,1] λ ∈ [ − 1 , 1 ] to ( 1 + λ ) / 2 ∈ [ 0 , 1 ] (1+\lambda)/2 \in[0,1] ( 1 + λ ) /2 ∈ [ 0 , 1 ] and guarantees self-weight at least 1 / 2 1/2 1/2 Levin and Peres [35 ] .
As a concrete DeGroot model, our results mostly are a consequences of standard DeGroot and Markov process analysis and are therefore omitted. For completeness, they are included in the supplementary material.
Theorem 7. For P C ( β ) P_C^{(\beta)} P C ( β ) , each connected component converges to the arithmetic mean of initial opinions in that component. If C C C is connecting then convergence is to the arithmetic mean of all voters.
Consequently, if G C G_C G C is disconnected, different components may converge to distinct local consensus values.
Corollary 8. A PAIRS-maximizing committee may lead to a fragmented population with distinct local consensus values, even when another feasible committee would lead to global consensus.
Proof idea. Take an election in which the PAIRS-maximizer is disconnected although a connecting committee exists. Assign a distinct initial opinion, constant within each connected component of the PAIRS-maximizer. That opinion profile is already a non-consensus steady state for the PAIRS-maximizer, whereas the connecting committee converges to global consensus regardless of the initial opinion distribution.
Bounded time to consensus. We now obtain a direct connection between the time to reach consensus, equivalent to the mixing time t m i x t_{\mathit{mix}} t mix of a Markov chain, and the CHGR objective. We assume for the rest of this analysis that C C C is connecting.
Theorem 9. For the lazy diffusion process , the CHGR score controls the time to consensus through its bounds on mixing time:
t m i x = Ω ( n h ( G C ) ) , t m i x = O ( n 2 log n h ( G C ) 2 ) t_{\mathit{mix}} = \Omega\left(\frac{n}{h(G_C)}\right), \qquad t_{\mathit{mix}} = O\left(\frac{n^2 \log n}{h(G_C)^2}\right) t mix = Ω ( h ( G C ) n ) , t mix = O ( h ( G C ) 2 n 2 log n )
Importantly, the dependence on n n n is common to all committees in a fixed election and is therefore not committee-specific.
Example 2 illustrates the gap between consensus time of different connecting committees. For n = 2 x n = 2x n = 2 x , there are two committees considered. The first induces a complete graph of all 2 x 2x 2 x voters, and the second induces two copies of K x K_x K x joined by one bridge. Both committees are connected and indistinguishable by CONS. K 2 x K_{2x} K 2 x is the CHGR-maximizer with value x x x , and the polarized bridge graph has CHGR value of 1 / x 1/x 1/ x . The bounds let us assert that the time to consensus ratio is at least
Ω ( n 1 / x n 2 log n x 2 ) = Ω ( x 3 n log n ) = Ω ( n 2 log n ) . \Omega\left(\frac{\frac{n}{1/x}}{\frac{n^2 \log n}{x^2}}\right) = \Omega\left(\frac{x^3}{n \log n}\right) = \Omega\left(\frac{n^2}{\log n}\right). Ω ( x 2 n 2 l o g n 1/ x n ) = Ω ( n log n x 3 ) = Ω ( log n n 2 ) .
Thus, in settings where time to reach consensus is limited or otherwise significant, the choice of a connecting committee can substantially affect how quickly consensus is approached, with CHGR serving as a quantitative proxy for convergence time. An interactive page demonstration of the convergence dynamics is included in the supplementary material.
Complexity
We now turn to the computational cost of bottleneck-sensitive interlacing. The picture is negative at several levels: even obtaining any positive CHGR score is hard, evaluating the score of one fixed committee is hard, and committee selection remains hard under voter-interval structure. We then show that bounded committee size yields an exact XP algorithm in general, while VCIstructure substantially improves its dependence on the committee size.
General Hardness
We begin with the weakest nontrivial selection question. By Observation 1, a committee has positive CHGR score exactly when its committee graph is connected.
Theorem 10. It is N P NP N P -complete to decide whether an election admits a size-k k k committee C C C with CHGR ( C , E ) > 0 \operatorname{CHGR}(C,\mathcal{E}) > 0 CHGR ( C , E ) > 0 . Consequently, outputting a CHGR-optimal committee is N P NP N P -hard.
Proof. Dong et al. Dong et al. [16 ] prove NP-completeness of deciding whether a size-k k k committee connects all voters. By Observation 1, this is equivalent to asking whether some size-k k k committee has positive CHGR score. Membership is immediate by guessing a committee and checking connectivity. Moreover, on the same instance, the optimal CHGR value is positive iff a connecting size-k k k committee exists. Hence, a polynomial-time algorithm for a CHGR-optimal committee would decide the NP-complete problem.
Dong et al. show that generally interlacing is NP-hard for both PAIRS and CONS. However, while these objectives admit polynomial-time calculation of a fixed committee’s value and hardness is the result of the exponential enumeration of possible committees, even evaluating one committee is computationally difficult. Recall that the decision variant of computing the CHGR value of a general graph is known to be NP-complete. The following shows that this extends to committee-induced subgraphs as well.
Theorem 11. For an election E = ( M , N , A , k ) \mathcal{E}=(M,N,A,k) E = ( M , N , A , k ) , a committee C C C of size k k k , and a rational threshold ρ > 0 \rho>0 ρ > 0 , deciding whether CHGR ( C , E ) ≤ ρ \operatorname{CHGR}(C,\mathcal{E})\leq\rho CHGR ( C , E ) ≤ ρ is NP-complete.
The reduction is direct. Given a graph G = ( V , E ) G=(V,E) G = ( V , E ) , create one voter for each vertex and one candidate for each edge, approved by exactly its two endpoint voters, and select the full candidate set. The resulting committee graph is exactly G G G , so ordinary graph-Cheeger decision is reproduced without distortion. The full formal proof is given in Appendix D.§ 1 .
Hardness on Voter-Interval Profiles
Dong et al. manages to mitigate the general hardness result by analyzing restricted preference domains, and obtaining polynomial-time algorithms for both objectives in the VCI domain. Unfortunately, such a restriction does not help for CHGR.
Theorem 12 (VI hardness). Given a voter-interval election E \mathcal{E} E , an integer k k k , and a rational threshold ρ > 0 \rho>0 ρ > 0 , it is NP-hard to decide whether there exists a committee C C C with ∣ C ∣ = k |C|=k ∣ C ∣ = k and CHGR ( C , E ) ≥ ρ \operatorname{CHGR}(C,\mathcal{E})\geq\rho CHGR ( C , E ) ≥ ρ . The hardness holds even when all candidate supports are nonempty and pairwise distinct, and the support family is proper (no support properly contains another).
Reduction overview. We reduce from Unary-3-Partition, in which a set of weighted items is asked to be partitioned into 3-item bins of a predefined target weight B B B . The problem has the additional constraint that each item’s weight is bounded B 4 < a i < B 2 \frac{B}{4}<a_i<\frac{B}{2} 4 B < a i < 2 B , thus ensuring that a set of items with the target weight is composed of exactly 3 items. Unary-3-Partition is known to be NP-complete, even when input is unary-represented Garey and Johnson [22 ] .
The construction encodes a solution as a sequence of cumulative sets of items referred to as stages . A stage h h h encodes all items assigned to the first h h h bins of the solution. For each h < s h<s h < s , stage h h h is represented by two variable phases , 2 h 2h 2 h and 2 h + 1 2h+1 2 h + 1 , which respectively impose a lower and an upper bound on the total weight of the items in the stage.
For each phase p p p and item i i i , there are two alternative candidates A p , i A_{p,i} A p , i and B p , i B_{p,i} B p , i . The construction will force exactly one of them to be selected. We write z p , i = z_{p,i}= z p , i =
{ 1 , A p , i is selected , 0 , B p , i is selected . \begin{cases}
1, & A_{p,i}\text{ is selected},\\
0, & B_{p,i}\text{ is selected}.
\end{cases} { 1 , 0 , A p , i is selected , B p , i is selected .
The interpretation is that z p , i = 1 z_{p,i}=1 z p , i = 1 once item i i i has entered the cumulative collection of completed 3-PARTITION bins. This monotone property is enforced by phase- and item-specific markers, specific prefix cuts. Thus any committee meeting the threshold ensures z p , i = 1 ⇒ z p ′ , i = 1 z_{p,i}=1\Rightarrow z_{p',i}=1 z p , i = 1 ⇒ z p ′ , i = 1 for every subsequent phase p ′ p' p ′ .
Additionally, for each phase p p p and item i i i , two auxiliary weighting candidates, an anchor g p , i g_{p,i} g p , i and a weight-dependent component e p , i e_{p,i} e p , i , are introduced. Together with the two alternative candidates, they create an a i a_i a i -sized multiplier for z p , i z_{p,i} z p , i . This is achieved using a weight probe, a single phase-specific selected prefix, used to measure the cumulative weight effect of all items. At the weight probe, each individual item’s weighting candidates create an a i a_i a i difference in boundary by choosing A p , i A_{p,i} A p , i relative to choosing B p , i B_{p,i} B p , i . Consequently, w p = ∑ i a i z p , i w_p=\sum_i a_i z_{p,i} w p = ∑ i a i z p , i is the cumulative weight encoded in phase p p p .
The two phases associated with a stage encode this same cumulative weight with opposite signs: in an even phase, selecting A p , i A_{p,i} A p , i contributes + a i +a_i + a i to the relevant boundary expression relative to selecting B p , i B_{p,i} B p , i , while in an odd phase it contributes − a i -a_i − a i . Hence the committee-dependent contribution of p p p is proportional to ( − 1 ) p w p (-1)^p w_p ( − 1 ) p w p .
Each phase also includes a small set of calibration candidates with the intended purpose of comparing w p w_p w p against the desired h B hB h B cumulative weight at stage h h h . Even and odd phases impose opposite inequalities on the cumulative weight represented by that stage. The calibration candidates cause the baseline boundary of the weight probe to correspond with the target cumulative weight. The alternating sign then makes weights below the target fail in the even phase and weights above the target fail in the odd phase, so the two phases jointly impose both a lower and an upper bound on the cumulative weight represented by the stage. Therefore, any committee that guarantees the threshold must encode cumulative weight exactly h B hB h B at stage h h h . Consequently, the differences between stages form a valid 3-partition.
The remaining candidates have three auxiliary purposes: they calibrate all diagnostic cuts (i.e., monotonicity markers and weight probes) to one common threshold, force every feasible committee into the intended A / B A/B A / B form, and provide enough surplus to make all nondiagnostic cuts safe, i.e. have expansion above the threshold. The construction is first analyzed through prefix cuts of the voter order. After establishing the required bounds for all prefixes, we separately show that every arbitrary cut is at least as safe, using the interval structure together with large head and tail cliques.
All candidate supports are intervals whose left and right endpoints increase in the same candidate order, so they are pairwise distinct proper VI intervals. The complete construction and proof appear in Appendix D.§ 2 . A Lean formalization certifying the correctness of the proof is included in the supplementary material.
Tractability for Bounded Committee Size
Despite the general hardness results, we obtain tractability for bounded committee size by grouping voters according to their approval behavior with respect to the selected committee, thereby making the combinatorial dependence primarily a function of the committee size k k k , rather than the number of voters.
Fix an election E \mathcal{E} E and a committee C C C , and write G : = G C E = ( V , E ) G := G^{\mathcal{E}}_{C} = (V,E) G := G C E = ( V , E ) . The committee-relative type of a voter is τ C ( v ) : = A v ∩ C \tau_C(v) := A_v \cap C τ C ( v ) := A v ∩ C . Let τ C ( V ) = { τ C ( v ) ∣ v ∈ V } \tau_C(V) = \{\tau_C(v) \mid v \in V\} τ C ( V ) = { τ C ( v ) ∣ v ∈ V } be the set of occurring types. For every α ∈ τ C ( V ) \alpha\in\tau_C(V) α ∈ τ C ( V ) , let V α C V^\mathit{C}_{\alpha} V α C and n α C n^\mathit{C}_{\alpha} n α C denote the corresponding voter class and its cardinality (C C C is omitted from notation when clear from context). Voters of the same type have identical neighborhoods outside their type class, and every nonempty type class induces a clique.
The associated weighted type graph Γ τ ( G ) \Gamma_{\tau}(G) Γ τ ( G ) has τ C ( V ) \tau_C(V) τ C ( V ) as vertices, each type α \alpha α has vertex weight n α n_{\alpha} n α , and an edge connects distinct types α , β \alpha,\beta α , β exactly when α ∩ β ≠ ∅ \alpha\cap\beta\ne\varnothing α ∩ β = ∅ , with edge weight n α ⋅ n β n_{\alpha} \cdot n_{\beta} n α ⋅ n β . A cut S ∣ S ‾ S \mid\overline{S} S ∣ S is called type-respecting if it does not split any type class, i.e., for every α ∈ τ ( V ) \alpha\in\tau(V) α ∈ τ ( V ) , either V α ⊆ S V_{\alpha} \subseteq S V α ⊆ S or V α ∩ S = ∅ V_{\alpha} \cap S = \varnothing V α ∩ S = ∅ . Thus, every type-respecting cut corresponds to a cut of the type graph with the same side size and boundary, in the usual weighted sense.
The following theorem shows that an optimal cut can always be chosen to be type-respecting, with at most one split type when the smaller side has maximum possible size.
Theorem 13. Let G = ( V , E ) G = (V,E) G = ( V , E ) be a committee graph and let c : = ⌊ ∣ V ∣ 2 ⌋ c := \left\lfloor\frac{|V|}{2} \right\rfloor c := ⌊ 2 ∣ V ∣ ⌋ . There exists a Cheeger-optimal cut S ⋆ ∣ S ⋆ ‾ S^\star\mid\overline{S^\star} S ⋆ ∣ S ⋆ such that:
(1) if ∣ S ⋆ ∣ < c |S^\star| < c ∣ S ⋆ ∣ < c , then S ⋆ S^\star S ⋆ is type-respecting;
(2) if ∣ S ⋆ ∣ = c |S^\star| = c ∣ S ⋆ ∣ = c , then S ⋆ S^\star S ⋆ splits at most one voter type.
Proof idea. Below the half-size cap, if an optimal side splits a type, additional voters of that type can be added with nonincreasing boundary marginal until either the type is completed or the cap is reached; optimality forces each such addition to preserve the optimum. At the cap, if two types are split, the sum of the costs of the two opposite one-for-one swaps is nonpositive. Since optimality makes both swap costs nonnegative, both are zero. Repeating a zero-cost transfer eliminates one split type at a time. The full argument, including the cap-swap calculation, is in Appendix D.8.
Proposition 14. Given a weighted type graph with t t t committee-relative voter types, its CHGR score can be computed exactly in 2 O ( t ) poly ( t ) 2^{O(t)}\operatorname{poly}(t) 2 O ( t ) poly ( t ) time.
Proof. Let c : = ⌊ n 2 ⌋ c := \left\lfloor\frac{n}{2} \right\rfloor c := ⌊ 2 n ⌋ . A naive algorithm enumerates all possible 2 t 2^t 2 t cuts. For each cut, if it has weight at most c c c , evaluate its expansion. Then, if its weight is also strictly less than c c c , iterate the remaining t t t types, if any can be split to obtain an exact c c c -sized cut, evaluate its expansion. Discard all other cuts and return the optimal expansion found. Theorem 13 guarantees that at least one optimum is considered by this procedure. Each of the 2 t 2^t 2 t iterations can be completed in poly ( t ) \operatorname{poly}(t) poly ( t ) time, thus obtaining the desired bound. □ \square □
Since a size-k k k committee induces at most 2 k 2^k 2 k committee-relative voter types, the proposition immediately yields the following.
Corollary 15. For an election with m m m candidates and n n n voters, a CHGR-optimal size-k k k committee can be computed in time ( m k ) 2 O ( 2 k ) poly ( n , m ) \binom{m}{k}2^{O(2^k)}\operatorname{poly}(n,m) ( k m ) 2 O ( 2 k ) poly ( n , m ) . Consequently, CHGR committee selection is in XP parameterized by k k k , and is polynomial-time solvable for every fixed k k k .
Although the above result yields polynomial-time solvability for every fixed k k k , the dependence on k k k is doubly exponential and quickly becomes prohibitive. This blow-up is driven by the number of committee-relative voter types, suggesting that preference domains admitting substantially fewer types may yield much more practical algorithms. One such domain is CI. Thus, we obtain the following.
Theorem 16. For an election in the VCI domain, let N = n + m N = n + m N = n + m and k = polylog ( N ) k = \operatorname{polylog}(N) k = polylog ( N ) . A CHGR-optimal size-k k k committee can be computed in quasi-polynomial time.
Proof. For any size-k k k committee, every nonempty committee-relative type is a contiguous interval of the selected candidates. Hence there are at most 1 + ( k 2 ) = O ( k 2 ) 1+\binom{k}{2}=O(k^2) 1 + ( 2 k ) = O ( k 2 ) types, including the empty type. Consequently, CHGR committee selection on CI profiles can be solved in ( m k ) 2 O ( k 2 ) poly ( n , m ) \binom{m}{k}2^{O(k^2)}\operatorname{poly}(n,m) ( k m ) 2 O ( k 2 ) poly ( n , m ) time. In particular, letting N = n + m N = n+m N = n + m , this remains quasi-polynomial even when k = polylog ( N ) k = \operatorname{polylog}(N) k = polylog ( N ) . By the dominance preprocessing of Dong et al., the same bounds extend to VCI profiles. □ \square □
Discussion
Earlier committee-evaluation criteria and axioms are largely voter-centric: they assess a committee through properties or outcomes defined from the perspective of individual voters. Interlacing shifts the unit of analysis from individual voters to the pattern of connections among voters induced by the committee. PAIRS and CONS capture direct overlap and reachability, but our results show that neither captures the robustness of the connections bridging different parts of the electorate.
We use CHEEGER instead, to capture structural robustness, rather than connectivity alone, and is further justified by the information-diffusion interpretation. Under the symmetric DeGroot process studied here, its proportionality to Markov-chain conductance connects this bottleneck measure to standard convergence bounds, making CHEEGER a proxy for the time scale on which the electorate approaches consensus. While there are other global measures, e.g. conductance and normalized cut [35 , 41 ] , we focus on CHEEGER because its cardinality normalization evaluates the strength of cross-community connections relative to the number of voters being connected, without allowing changes in committee-induced within-community density to alter the normalization.
These appealing structural and interpretive properties come at a substantial computational cost. Optimization remains hard even under strong preference structure, although fixing the committee size and exploiting CI structure yield tractable regimes. However, CHEEGER’s close connection to sparse-cut formulations used in graph partitioning and community detection, where spectral, flow-based, and heuristic methods are commonly used in place of exact optimization [34 ] , provides a natural source of algorithmic ideas. Moreover, any such method that guarantees a connecting committee whenever one exists already inherits our universal linear-factor baseline, leaving room to improve over the worst-case behavior attained by an arbitrary—or even PAIRS-maximizing—connecting committee.
A second limitation is that CHEEGER’s still does not distinguish between disconnected graphs. One natural way to soften this behavior is to introduce a damping factor , assigning weight ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) to absent edges of the committee graph while retaining weight 1 1 1 on committee-induced edges. At ε = 0 \varepsilon= 0 ε = 0 this recovers the original model, while for higher values ε \varepsilon ε controls a substantive trade-off between within-component cohesion and tolerance for outliers. Thus, ε \varepsilon ε may be treated as a regularization parameter. A more conservative alternative is to study the limit ε → 0 + \varepsilon\to0^{+} ε → 0 + , using the perturbation only to refine the hard-zero behavior while remaining as close as possible to the original CHEEGER objective. This approach has a methodological analogue in the study of PageRank limit scores as a tournament solution Brandt and Fischer [8 ] .
A further natural extension is to move from binary to weighted committee-induced graphs. Such weights have no immediate canonical interpretation under the original objectives, most notably for the reachability-based CONS objective. Our diffusion perspective makes such weighting particularly natural– the diffusion framework developed here can be viewed as the homogeneous special case in which all committee-induced connections have equal strength. Heterogeneous interaction weights then provide a direct framework for defining and analyzing alternative weighting schemes through their effects on information flow and convergence. Weighted expansion and related cut objectives therefore provide a natural extension of interlacing from the existence and robustness of voter connections to their strength as well. More broadly, these extensions suggest viewing interlacing not as a single objective, but as a framework for studying how committee selection shapes the structure and strength of interactions across the electorate.
References
Appendix A. Proof of the PAIRS pathology
For completeness, we give the full construction and proof of Theorem 1.
Perfect Difference Sets
A q q q -sized subset of Z L \mathbb{Z}_L Z L is said to be a ( L , q ) (L,q) ( L , q ) -Perfect Difference Set if every value in { 1 , … , L − 1 } \{1,\ldots,L-1\} { 1 , … , L − 1 } has a unique expression as a difference of two elements in the set, calculated modulo L L L .
Example: the set { 0 , 1 , 3 } \{0,1,3\} { 0 , 1 , 3 } is a ( 7 , 3 ) (7,3) ( 7 , 3 ) -perfect difference set:
0 − 3 ≡ − 3 ≡ 4 ( m o d 7 ) 0-3\equiv-3\equiv4 \pmod{7} 0 − 3 ≡ − 3 ≡ 4 ( mod 7 )
1 − 3 ≡ − 2 ≡ 5 ( m o d 7 ) 1-3\equiv-2\equiv5 \pmod{7} 1 − 3 ≡ − 2 ≡ 5 ( mod 7 )
0 − 1 ≡ − 1 ≡ 6 ( m o d 7 ) 0-1\equiv-1\equiv6 \pmod{7} 0 − 1 ≡ − 1 ≡ 6 ( mod 7 )
For every q q q such that q − 1 q-1 q − 1 is a prime power, a ( q ( q − 1 ) + 1 , q ) (q(q-1)+1,q) ( q ( q − 1 ) + 1 , q ) -perfect difference set is known to exist Singer [42 ] .
Observation 2. From the above, it follows that we can choose L L L to be arbitrarily large with an appropriate q q q .
Proof of Theorem 1.
Construction. Choose an arbitrarily small positive rational ε < min { δ , 1 } \varepsilon< \min\{\delta,1\} ε < min { δ , 1 } . Select q q q such that q − 1 q-1 q − 1 is a prime power and, for L = q ( q − 1 ) + 1 L=q(q-1)+1 L = q ( q − 1 ) + 1 ,
( L − 1 ) ε 2 − 1 > 0. (1) (L-1)\varepsilon^2-1>0. \tag*{(1)} ( L − 1 ) ε 2 − 1 > 0. (1)
From the above observation, such q q q exists. Let S S S be a ( L , q ) (L,q) ( L , q ) -perfect difference set.
Define two disjoint sets of candidates X = { x 0 , … , x L − 1 } X=\{x_0,\ldots,x_{L-1}\} X = { x 0 , … , x L − 1 } and Y = { y 0 , … , y L − 1 } Y=\{y_0,\ldots,y_{L-1}\} Y = { y 0 , … , y L − 1 } , and set
M = X ∪ Y , k = L . M=X\cup Y,\qquad k=L. M = X ∪ Y , k = L .
Choose n n n sufficiently large so that
n L ∈ N , n ε L 2 ∈ N , ( 1 − ε ) n L ≥ 2 , \frac{n}{L}\in\mathbb{N},\qquad\frac{n\varepsilon}{L^2}\in\mathbb{N},\qquad\frac{(1-\varepsilon)n}{L}\geq2, L n ∈ N , L 2 n ε ∈ N , L ( 1 − ε ) n ≥ 2 ,
and
n > ( 1 + ε ) L 3 ( ε 2 L − 1 ) L 2 − L ( L − 1 ) ε 2 . (2) n>\frac{(1+\varepsilon)L^3}{(\varepsilon^2L-1)L^2-L(L-1)\varepsilon^2}. \tag*{(2)} n > ( ε 2 L − 1 ) L 2 − L ( L − 1 ) ε 2 ( 1 + ε ) L 3 . (2)
Such an n n n exists because ε \varepsilon ε is rational. Note that the denominator is strictly positive as a consequence of (1) :
( ε 2 L − 1 ) L 2 − L ( L − 1 ) ε 2 > ε 2 L 2 − ε 2 L ( L − 1 ) = ε 2 L > 0. (\varepsilon^2L-1)L^2-L(L-1)\varepsilon^2>\varepsilon^2L^2-\varepsilon^2L(L-1)=\varepsilon^2L>0. ( ε 2 L − 1 ) L 2 − L ( L − 1 ) ε 2 > ε 2 L 2 − ε 2 L ( L − 1 ) = ε 2 L > 0.
The voting profile is described as follows. First, we divide the population into two sets of sizes ε n \varepsilon n ε n and ( 1 − ε ) n (1-\varepsilon)n ( 1 − ε ) n . We then divide the large set into L L L equally-sized groups of ( 1 − ε ) n L \frac{(1-\varepsilon)n}{L} L ( 1 − ε ) n voters, each group distinctly approving one candidate from Y Y Y . For every 0 ≤ i ≤ L − 1 0\leq i\leq L-1 0 ≤ i ≤ L − 1 , in the group that approves y i y_i y i there is a single voter who also approves y ( i + 1 ) m o d L y_{(i+1)\bmod L} y ( i + 1 ) mod L . This implies that every candidate in Y Y Y is approved by ( 1 − ε ) n L + 1 \frac{(1-\varepsilon)n}{L}+1 L ( 1 − ε ) n + 1 voters in this set.
Next, we divide the small set of voters into L L L equally-sized groups g 0 , … , g L − 1 g_0,\ldots,g_{L-1} g 0 , … , g L − 1 , each with n ε L \frac{n\varepsilon}{L} L n ε voters. For every 0 ≤ i ≤ L − 1 0\leq i\leq L-1 0 ≤ i ≤ L − 1 and every s ∈ S s\in S s ∈ S , the group g ( i + s ) m o d L g_{(i+s)\bmod L} g ( i + s ) mod L approves x i x_i x i . Consequently, there are q q q groups that approve x i x_i x i .
Finally, each group is further divided into L L L subgroups, each additionally and uniquely approving a candidate from Y Y Y . Thus, each candidate in Y Y Y is approved by n ε L 2 \frac{n\varepsilon}{L^2} L 2 n ε voters in each group g i g_i g i , and therefore the total number of voters for each candidate in the small set is L ⋅ n ε L 2 = n ε L L\cdot\frac{n\varepsilon}{L^2}=\frac{n\varepsilon}{L} L ⋅ L 2 n ε = L n ε . Hence each candidate from Y Y Y is approved by a total of
( 1 − ε ) n L + 1 + n ε L = n L + 1 \frac{(1-\varepsilon)n}{L}+1+\frac{n\varepsilon}{L}=\frac{n}{L}+1 L ( 1 − ε ) n + 1 + L n ε = L n + 1
voters.
Lemma 17. Let Voter 1 from g i g_i g i and Voter 2 from g j g_j g j , where i ≠ j i \ne j i = j . Then they approve exactly one candidate from X X X .
Proof. Existence. WLOG assume i < j i<j i < j . Since S S S is a ( L , q ) (L,q) ( L , q ) -perfect difference set, there are s 1 , s 2 ∈ S s_1,s_2 \in S s 1 , s 2 ∈ S such that
s 2 − s 1 ≡ j − i ( m o d L ) s_2-s_1 \equiv j-i \pmod{L} s 2 − s 1 ≡ j − i ( mod L ) Let t ≡ i − s 1 ( m o d L ) t \equiv i-s_1 \pmod{L} t ≡ i − s 1 ( mod L ) with t ∈ { 0 , … , L − 1 } t \in\{0,\ldots,L-1\} t ∈ { 0 , … , L − 1 } . By construction, x t x_t x t is approved by all groups with index t + s t+s t + s for some s ∈ S s \in S s ∈ S . Since all calculations are taken modulo L L L ,
t + s 1 = i − s 1 + s 1 = i , t + s 2 = i − s 1 + s 2 = i + j − i = j , \begin{aligned}
t+s_1 &= i-s_1+s_1=i,\\
t+s_2 &= i-s_1+s_2=i+j-i=j,
\end{aligned} t + s 1 t + s 2 = i − s 1 + s 1 = i , = i − s 1 + s 2 = i + j − i = j , and therefore g i g_i g i and g j g_j g j both approve x t x_t x t .
Uniqueness. Let r r r be such that x r x_r x r is approved by both g i g_i g i and g j g_j g j . By construction, there are s r 1 , s r 2 ∈ S s_{r1},s_{r2} \in S s r 1 , s r 2 ∈ S such that
r + s r 1 ≡ i ( m o d L ) , r + s r 2 ≡ j ( m o d L ) . r+s_{r1} \equiv i \pmod{L}, \qquad r+s_{r2} \equiv j \pmod{L}. r + s r 1 ≡ i ( mod L ) , r + s r 2 ≡ j ( mod L ) . We get
j − i ≡ ( r + s r 2 ) − ( r + s r 1 ) ≡ s r 2 − s r 1 ≠ 0 ( m o d L ) . j-i \equiv(r+s_{r2})-(r+s_{r1}) \equiv s_{r2}-s_{r1} \ne0 \pmod{L}. j − i ≡ ( r + s r 2 ) − ( r + s r 1 ) ≡ s r 2 − s r 1 = 0 ( mod L ) . Since every nonzero residue modulo L L L is uniquely expressed as the difference of two elements from S S S , we get s r 1 = s 1 s_{r1}=s_1 s r 1 = s 1 , s r 2 = s 2 s_{r2}=s_2 s r 2 = s 2 , and thus r = t r=t r = t .
As there are exactly q q q groups that approve each x i ∈ X x_i \in X x i ∈ X , a consequence of Lemma 17 is that we can partition the set of edges between groups by the candidate in X X X . Moreover, if we consider the edges between groups to be a single edge weighted by the number of edges between each pair of groups (henceforth referred to as “multi-edges”), then we get a partition into q q q -cliques for each candidate in X X X .
Committee Y Y Y connects all voters: each y i y_i y i connects its large group, the designated bridge voters connect consecutive large groups around the cycle, and every small-set voter approves one member of Y Y Y . Moreover, Y Y Y is the unique connecting committee. Indeed, if a committee omits some y i y_i y i , then a non-bridge voter in the corresponding large group is isolated; such a voter exists by the choice of n n n . Since ∣ Y ∣ = k |Y|=k ∣ Y ∣ = k , every connecting committee is therefore exactly Y Y Y .
Since M = X ∪ Y M=X\cup Y M = X ∪ Y and k = L k=L k = L , every feasible committee is obtained from X X X by replacing t t t members of X X X with t t t members of Y Y Y , for some 0 ≤ t ≤ L 0 \le t \le L 0 ≤ t ≤ L . We compare all such committees.
Note that it is sufficient to show that the difference between the number of edges removed from G X G_X G X and the number of edges added to it by replacing t t t candidates from X X X with candidates from Y Y Y is strictly positive for every 0 < t ≤ L 0<t\le L 0 < t ≤ L .
For a given t t t , let ℓ \ell ℓ be the number of groups that approve none of the X X X candidates that were not replaced.
The number of edges removed from G X G_X G X is as follows:
Each candidate replaced from X X X removes all edges from its respective q q q -clique, since it is the only common X X X candidate between voters in these groups. Each group has size n ε L \frac{n\varepsilon}{L} L n ε and thus each multi-edge of the clique is weighted by ( n ε L ) 2 \left(\frac{n\varepsilon}{L}\right)^2 ( L n ε ) 2 . There are q ( q − 1 ) 2 = L − 1 2 \frac{q(q-1)}{2}=\frac{L-1}{2} 2 q ( q − 1 ) = 2 L − 1 such multi-edges (the number of edges in a q q q -clique).
Total: t ⋅ L − 1 2 ( n ε L ) 2 t\cdot\frac{L-1}{2}\left(\frac{n\varepsilon}{L}\right)^2 t ⋅ 2 L − 1 ( L n ε ) 2 .
For each of the ℓ \ell ℓ groups that approve none of the remaining X X X candidates, all the edges in the group are removed. Since this is a n ε L \frac{n\varepsilon}{L} L n ε -clique, n ε L ( n ε L − 1 ) / 2 \frac{n\varepsilon}{L}\left(\frac{n\varepsilon}{L}-1\right)/2 L n ε ( L n ε − 1 ) /2 edges are removed per group.
Total: ℓ ⋅ n ε L ( n ε L − 1 ) 2 \ell\cdot\frac{\frac{n\varepsilon}{L}\left(\frac{n\varepsilon}{L}-1\right)}{2} ℓ ⋅ 2 L n ε ( L n ε − 1 ) .
The number of edges added from the t t t added Y Y Y candidates is as follows:
For each of the candidates from Y Y Y , there are ( 1 − ε ) n L + 1 \frac{(1-\varepsilon)n}{L}+1 L ( 1 − ε ) n + 1 voters in the large set from the initial division. All these voters are now connected in a clique.
Total: t ⋅ ( ( 1 − ε ) n L + 1 ) ( 1 − ε ) n L 2 t \cdot\frac{\left(\frac{(1-\varepsilon)n}{L}+1\right)\frac{(1-\varepsilon)n}{L}}{2} t ⋅ 2 ( L ( 1 − ε ) n + 1 ) L ( 1 − ε ) n .
For each candidate from Y Y Y , the ( 1 − ε ) n L + 1 \frac{(1-\varepsilon)n}{L}+1 L ( 1 − ε ) n + 1 voters in the large set are connected to the n ε L \frac{n\varepsilon}{L} L n ε voters in the small set.
Total: t ( ( 1 − ε ) n L + 1 ) n ε L t\left(\frac{(1-\varepsilon)n}{L}+1\right)\frac{n\varepsilon}{L} t ( L ( 1 − ε ) n + 1 ) L n ε .
For each multi-edge removed from X X X , each of the t t t added candidates from Y Y Y adds ( n ε L 2 ) 2 \left(\frac{n\varepsilon}{L^2}\right)^2 ( L 2 n ε ) 2 edges: within each group, the voters are secondarily partitioned by the candidates in Y Y Y , and each of these sets of voters has size n ε L 2 \frac{n\varepsilon}{L^2} L 2 n ε .
Total: t 2 L − 1 2 ( n ε L 2 ) 2 t^2\frac{L-1}{2}\left(\frac{n\varepsilon}{L^2}\right)^2 t 2 2 L − 1 ( L 2 n ε ) 2 .
Lastly, for each of the ℓ \ell ℓ groups that are unrepresented by the remaining X X X candidates, the sets of partitioned voters who approve one of the added Y Y Y candidates are connected in a clique.
Total: ℓ ⋅ t n ε L 2 ( n ε L 2 − 1 ) 2 \ell\cdot t\frac{\frac{n\varepsilon}{L^2}\left(\frac{n\varepsilon}{L^2}-1\right)}{2} ℓ ⋅ t 2 L 2 n ε ( L 2 n ε − 1 ) .
We get that the difference in edges is given by
t ( L − 1 2 ( n ε L ) 2 − ( ( ( 1 − ε ) n L + 1 ) ( 1 − ε ) n L 2 + ( ( 1 − ε ) n L + 1 ) n ε L + t L − 1 2 ( n ε L 2 ) 2 ) ) + ℓ ( n ε L ( n ε L − 1 ) 2 − t n ε L 2 ( n ε L 2 − 1 ) 2 ) . t\left(\frac{L-1}{2}\left(\frac{n\varepsilon}{L}\right)^2-\left(\frac{\left(\frac{(1-\varepsilon)n}{L}+1\right)\frac{(1-\varepsilon)n}{L}}{2}+\left(\frac{(1-\varepsilon)n}{L}+1\right)\frac{n\varepsilon}{L}+t\frac{L-1}{2}\left(\frac{n\varepsilon}{L^2}\right)^2\right)\right)
+\ell\left(\frac{\frac{n\varepsilon}{L}\left(\frac{n\varepsilon}{L}-1\right)}{2}-t\frac{\frac{n\varepsilon}{L^2}\left(\frac{n\varepsilon}{L^2}-1\right)}{2}\right). t 2 L − 1 ( L n ε ) 2 − 2 ( L ( 1 − ε ) n + 1 ) L ( 1 − ε ) n + ( L ( 1 − ε ) n + 1 ) L n ε + t 2 L − 1 ( L 2 n ε ) 2 + ℓ ( 2 L n ε ( L n ε − 1 ) − t 2 L 2 n ε ( L 2 n ε − 1 ) ) .
First, consider the ℓ \ell ℓ term:
n ε L ( n ε L − 1 ) 2 − t n ε L 2 ( n ε L 2 − 1 ) 2 ≥ n ε L ( n ε L − 1 ) 2 − L n ε L 2 ( n ε L 2 − 1 ) 2 ( t ≤ L ) = 1 2 n ε L ( n ε L − n ε L 2 ) = n 2 ε 2 ( L − 1 ) 2 L 3 ≥ 0. \begin{aligned}
\frac{\frac{n\varepsilon}{L}\left(\frac{n\varepsilon}{L}-1\right)}{2}-t\frac{\frac{n\varepsilon}{L^2}\left(\frac{n\varepsilon}{L^2}-1\right)}{2}
\ge\frac{\frac{n\varepsilon}{L}\left(\frac{n\varepsilon}{L}-1\right)}{2}-L\frac{\frac{n\varepsilon}{L^2}\left(\frac{n\varepsilon}{L^2}-1\right)}{2}\qquad(t\le L) \\
&= \frac{1}{2}\frac{n\varepsilon}{L}\left(\frac{n\varepsilon}{L}-\frac{n\varepsilon}{L^2}\right) \\
&= \frac{n^2\varepsilon^2(L-1)}{2L^3}\ge0.
\end{aligned} 2 L n ε ( L n ε − 1 ) − t 2 L 2 n ε ( L 2 n ε − 1 ) ≥ 2 L n ε ( L n ε − 1 ) − L 2 L 2 n ε ( L 2 n ε − 1 ) ( t ≤ L ) = 2 1 L n ε ( L n ε − L 2 n ε ) = 2 L 3 n 2 ε 2 ( L − 1 ) ≥ 0.
Therefore, it only remains to show that the t t t term is strictly positive:
L − 1 2 ( n ε L ) 2 − ( ( ( 1 − ε ) n L + 1 ) ( 1 − ε ) n L 2 + ( ( 1 − ε ) n L + 1 ) n ε L + t L − 1 2 ( n ε L 2 ) 2 ) = 1 2 L 4 ( n 2 ε 2 ( L − 1 ) L 2 − ( ( 1 − ε ) n L + 1 ) ( 1 + ε ) n L 3 − t ( L − 1 ) n 2 ε 2 ) = n 2 L 4 ( n ( ( L ε 2 − 1 ) L 2 − t ( L − 1 ) ε 2 ) − ( 1 + ε ) L 3 ) ≥ n 2 L 4 ( n ( ( L ε 2 − 1 ) L 2 − L ( L − 1 ) ε 2 ) − ( 1 + ε ) L 3 ) > 0 , \begin{aligned}
\frac{L-1}{2}\left(\frac{n\varepsilon}{L}\right)^2-\left(\frac{\left(\frac{(1-\varepsilon)n}{L}+1\right)\frac{(1-\varepsilon)n}{L}}{2}+\left(\frac{(1-\varepsilon)n}{L}+1\right)\frac{n\varepsilon}{L}+t\frac{L-1}{2}\left(\frac{n\varepsilon}{L^2}\right)^2\right) \\
&= \frac{1}{2L^4}\left(n^2\varepsilon^2(L-1)L^2-\left(\frac{(1-\varepsilon)n}{L}+1\right)(1+\varepsilon)nL^3-t(L-1)n^2\varepsilon^2\right) \\
&= \frac{n}{2L^4}\left(n\left((L\varepsilon^2-1)L^2-t(L-1)\varepsilon^2\right)-(1+\varepsilon)L^3\right) \\
&\ge\frac{n}{2L^4}\left(n\left((L\varepsilon^2-1)L^2-L(L-1)\varepsilon^2\right)-(1+\varepsilon)L^3\right) \\
&>0,
\end{aligned} 2 L − 1 ( L n ε ) 2 − 2 ( L ( 1 − ε ) n + 1 ) L ( 1 − ε ) n + ( L ( 1 − ε ) n + 1 ) L n ε + t 2 L − 1 ( L 2 n ε ) 2 = 2 L 4 1 ( n 2 ε 2 ( L − 1 ) L 2 − ( L ( 1 − ε ) n + 1 ) ( 1 + ε ) n L 3 − t ( L − 1 ) n 2 ε 2 ) = 2 L 4 n ( n ( ( L ε 2 − 1 ) L 2 − t ( L − 1 ) ε 2 ) − ( 1 + ε ) L 3 ) ≥ 2 L 4 n ( n ( ( L ε 2 − 1 ) L 2 − L ( L − 1 ) ε 2 ) − ( 1 + ε ) L 3 ) > 0 ,
where the last inequality follows from (2) .
Thus every committee with 1 ≤ t ≤ L 1\le t\le L 1 ≤ t ≤ L has strictly fewer PAIRS edges than X X X , so X X X is the unique PAIRS maximizer.
For completeness, the same ledger identifies the opposite extreme. For fixed t t t , the PAIRS score is nonincreasing in ℓ \ell ℓ , and ℓ ≤ t \ell\le t ℓ ≤ t : every uncovered small group is incident, through its q q q approved X X X -candidates, only to removed candidates, while each removed X X X -candidate is approved by exactly q q q groups. Hence the score of any committee with parameter t t t is at least the score obtained by substituting ℓ = t \ell=t ℓ = t . This lower envelope is strictly decreasing in t t t . Indeed, since n ε / L 2 ∈ N n\varepsilon/L^2 \in\mathbb{N} n ε / L 2 ∈ N we have n ε ≥ L 2 n\varepsilon\ge L^2 n ε ≥ L 2 , and a direct subtraction shows that its decrease from t t t to t + 1 t+1 t + 1 is minimized at t = L − 1 t=L-1 t = L − 1 and is at least
n 2 L 3 [ n ( L 2 ε 2 − L ε 2 − L + ε 2 ) − L 2 − L ε 2 ] > 0 , \frac{n}{2L^3}\left[n\left(L^2\varepsilon^2-L\varepsilon^2-L+\varepsilon^2\right)-L^2-L\varepsilon^2\right]>0, 2 L 3 n [ n ( L 2 ε 2 − L ε 2 − L + ε 2 ) − L 2 − L ε 2 ] > 0 ,
where the final inequality follows from (2) . Consequently the unique PAIRS-minimizing committee is obtained at t = ℓ = L t=\ell=L t = ℓ = L , namely Y Y Y .
Under X X X , all ε n \varepsilon n ε n voters in the small set form one connected component, while every voter in the large set is isolated. Thus the largest connected component of the unique PAIRS-optimal committee has size exactly ε n < δ n \varepsilon n<\delta n ε n < δ n . This proves the theorem.
Appendix B. CONS Sub-optimality Proofs
Proof of CI Gateway Lemma
Proof of Lemma 3. Fix a CI candidate order and list the candidates of C C C with nonempty support in that order as c 1 < ⋯ < c r c_1<\cdots<c_r c 1 < ⋯ < c r . Since G C G_C G C is connected, every voter approves at least one selected candidate.
First observe that the supports of consecutive selected candidates intersect. Indeed, if the supports of c i c_i c i and c i + 1 c_{i+1} c i + 1 were disjoint, no voter could approve a selected candidate weakly to the left of c i c_i c i and another selected candidate weakly to the right of c i + 1 c_{i+1} c i + 1 : by the CI property such a voter would approve both c i c_i c i and c i + 1 c_{i+1} c i + 1 . The preferences graph would therefore split between the selected candidates on the two sides, contradicting connectedness.
Suppose a cut edge results by two voters that jointly approve a candidate d d d . First, candidates belonging to C C C satisfy the claim by definition. Now consider an arbitrary candidate d ∉ { c 1 , … , c r } d\notin\{c_1,\ldots,c_r\} d ∈ / { c 1 , … , c r } . Suppose first that c i < d < c i + 1 c_i<d<c_{i+1} c i < d < c i + 1 . Every voter approving d d d also approves at least one selected candidate. If that selected candidate lies weakly to the left of c i c_i c i , the CI property forces the voter to approve c i c_i c i ; if it lies weakly to the right of c i + 1 c_{i+1} c i + 1 , the voter must approve c i + 1 c_{i+1} c i + 1 . Hence the support of d d d is contained in the union of the supports of c i c_i c i and c i + 1 c_{i+1} c i + 1 .
If neither c i c_i c i nor c i + 1 c_{i+1} c i + 1 crosses the cut, then, because their supports intersect, both supports lie on the same side of the cut, so d d d cannot create a crossing edge. If exactly one of them crosses, every crossing edge created by d d d has an endpoint in the support of that crossing selected candidate. If both cross, both endpoints lie in the union of two crossing selected supports. Whenever a selected candidate crosses the cut, every voter in its support is incident to an edge of ∂ G C ( S ) \partial G_C(S) ∂ G C ( S ) . Thus in all cases every crossing edge created by d d d has an endpoint in R S ∪ R S ‾ R_S\cup R_{\overline{S}} R S ∪ R S .
The same argument applies to candidates before c 1 c_1 c 1 or after c r c_r c r : their support is contained in the support of the nearest selected candidate, and if they cross the cut that selected candidate crosses it as well.
Proof Details for the CI Worst Case Cheeger Ratio
Proof. For C G C_G C G , consider the following six voter blocks:
X 1 ∣ { a } - and { a , b } -voters X 2 ∣ { a , b , c } -voters X 3 ∣ { b , c } -voters X 4 ∣ { c , d } -voters X 5 ∣ { c , d , e } - and { d , e } -voters X 6 ∣ { e } -voter. \begin{aligned}
X_1 &\mid\{a\}\text{- and }\{a,b\}\text{-voters}\\
X_2 &\mid\{a,b,c\}\text{-voters}\\
X_3 &\mid\{b,c\}\text{-voters}\\
X_4 &\mid\{c,d\}\text{-voters}\\
X_5 &\mid\{c,d,e\}\text{- and }\{d,e\}\text{-voters}\\
X_6 &\mid\{e\}\text{-voter.}
\end{aligned} X 1 X 2 X 3 X 4 X 5 X 6 ∣ { a } - and { a , b } -voters ∣ { a , b , c } -voters ∣ { b , c } -voters ∣ { c , d } -voters ∣ { c , d , e } - and { d , e } -voters ∣ { e } -voter.
Their sizes are
t + 2 , t , t + 1 , t , t + 1 , 1. t+2,\quad t,\quad t+1,\quad t,\quad t+1,\quad1. t + 2 , t , t + 1 , t , t + 1 , 1.
The graph G C G G_{C_G} G C G contains as a spanning subgraph the blow-up of the path
X 1 − X 2 − X 3 − X 4 − X 5 − X 6 , X_1-X_2-X_3-X_4-X_5-X_6, X 1 − X 2 − X 3 − X 4 − X 5 − X 6 ,
where every consecutive pair of blocks is complete bipartite. Denote this spanning subgraph by H H H . Since adding edges cannot decrease expansion,
h ( G C G ) ≥ h ( H ) . h(G_{C_G}) \ge h(H). h ( G C G ) ≥ h ( H ) .
Fix a nonempty S ⊆ N S \subseteq N S ⊆ N with s = ∣ S ∣ ≤ n / 2 s = |S| \le n/2 s = ∣ S ∣ ≤ n /2 . Put x i = ∣ S ∩ X i ∣ x_i = |S \cap X_i| x i = ∣ S ∩ X i ∣ and, for 1 ≤ i ≤ 5 1 \le i \le5 1 ≤ i ≤ 5 ,
r i = min { x i , ∣ X i ∣ − x i } , R = ∑ i = 1 5 r i . r_i = \min\{x_i, |X_i|-x_i\}, \qquad R = \sum_{i=1}^{5} r_i. r i = min { x i , ∣ X i ∣ − x i } , R = i = 1 ∑ 5 r i .
For each of the first four interfaces X i − X i + 1 X_i-X_{i+1} X i − X i + 1 , its contribution B i B_i B i to the boundary satisfies
B i ≥ t r i and B i ≥ t r i + 1 , B_i \ge t r_i \qquad\text{and} \qquad B_i \ge t r_{i+1}, B i ≥ t r i and B i ≥ t r i + 1 ,
because the neighboring block has size at least t t t . Hence
∣ ∂ H ( S ) ∣ ≥ t 2 R . |\partial_H(S)| \ge\frac{t}{2}R. ∣ ∂ H ( S ) ∣ ≥ 2 t R .
If R ≥ s / 3 R \ge s/3 R ≥ s /3 , then
∣ ∂ H ( S ) ∣ s ≥ t 6 . \frac{|\partial_H(S)|}{s} \ge\frac{t}{6}. s ∣ ∂ H ( S ) ∣ ≥ 6 t .
Suppose now that R < s / 3 R < s/3 R < s /3 . If s = 1 s=1 s = 1 , every vertex of H H H has degree at least t t t , so the expansion of S S S is at least t t t . Let s ≥ 2 s \ge2 s ≥ 2 . Among X 1 , … , X 5 X_1,\ldots,X_5 X 1 , … , X 5 , not all blocks can have at most half of their vertices in S S S , since then s ≤ R + 1 < s / 3 + 1 s \le R+1 < s/3+1 s ≤ R + 1 < s /3 + 1 , a contradiction. Nor can all five blocks have at least half of their vertices in S S S : writing M = ∑ i = 1 5 ∣ X i ∣ = n − 1 M=\sum_{i=1}^{5}|X_i|=n-1 M = ∑ i = 1 5 ∣ X i ∣ = n − 1 , this would give
s ≥ M − R > M − s / 3 , s \ge M-R > M-s/3, s ≥ M − R > M − s /3 ,
so s > 3 M / 4 > n / 2 s>3M/4>n/2 s > 3 M /4 > n /2 , again a contradiction. Therefore, along the path X 1 , … , X 5 X_1,\ldots,X_5 X 1 , … , X 5 there is either a block split exactly in half or a pair of adjacent blocks with opposite strict majorities. In the former case an adjacent interface contributes at least t 2 / 2 t^2/2 t 2 /2 crossing edges; in the latter case the interface between the opposite-majority blocks contributes at least t 2 / 4 t^2/4 t 2 /4 . Thus in either case
∣ ∂ H ( S ) ∣ ≥ t 2 4 . |\partial_H(S)| \ge\frac{t^2}{4}. ∣ ∂ H ( S ) ∣ ≥ 4 t 2 .
Since s ≤ n / 2 = ( 5 t + 5 ) / 2 s \le n/2=(5t+5)/2 s ≤ n /2 = ( 5 t + 5 ) /2 ,
∣ ∂ H ( S ) ∣ s ≥ t 2 2 n = t 2 10 t + 10 ≥ t 20 . \frac{|\partial_H(S)|}{s} \ge\frac{t^2}{2n} = \frac{t^2}{10t+10} \ge\frac{t}{20}. s ∣ ∂ H ( S ) ∣ ≥ 2 n t 2 = 10 t + 10 t 2 ≥ 20 t .
We conclude that
CHGR ( C G , E ) ≥ t 20 . \operatorname{CHGR}(C_G,\mathcal{E}) \ge\frac{t}{20}. CHGR ( C G , E ) ≥ 20 t .
Conversely, the single { e } \{e\} { e } voter has degree t + 1 t+1 t + 1 in G C G G_{C_G} G C G , so
CHGR ( C G , E ) ≤ t + 1. \operatorname{CHGR}(C_G,\mathcal{E}) \le t+1. CHGR ( C G , E ) ≤ t + 1.
Thus CHGR ( C G , E ) = Θ ( t ) \operatorname{CHGR}(C_G,\mathcal{E})=\Theta(t) CHGR ( C G , E ) = Θ ( t ) .
For a Markov chain P P P with stationary distribution π \pi π and a non-trivial cut S ∣ S ˉ S \mid\bar{S} S ∣ S ˉ , the conductance of S S S is defined as
Φ ( S ) = ∑ i ∈ S , j ∈ S ˉ π i P i j min { π ( S ) , π ( S ˉ ) } . \Phi(S)=\frac{\sum_{i\in S,j\in\bar{S}}\pi_iP_{ij}}{\min\{\pi(S),\pi(\bar{S})\}}. Φ ( S ) = min { π ( S ) , π ( S ˉ )} ∑ i ∈ S , j ∈ S ˉ π i P ij .
where π ( . ) \pi(.) π ( . ) is the total sum of weights in the stationary distribution of nodes in the subset. Conductance of P P P is then defined as
Φ ( P ) : = min ∅ ≠ S ⊊ V Φ ( S ) . \Phi(P):=\min_{\varnothing\ne S\subsetneq V}\Phi(S). Φ ( P ) := ∅ = S ⊊ V min Φ ( S ) .
If P P P is symmetric and has nonnegative eigenvalues, spectral theory and the Cheeger inequalities Cheeger [12 ] ; Alon and Milman [4 ] bound the mixing time as a function of conductance, yielding
Ω ( 1 Φ ( P ) ) ≤ t m i x ≤ O ( 1 Φ ( P ) 2 log 1 π m i n ) \Omega\left(\frac{1}{\Phi(P)}\right) \le t_{mix} \le O\left(\frac{1}{\Phi(P)^2}\log\frac{1}{\pi_{min}}\right) Ω ( Φ ( P ) 1 ) ≤ t mi x ≤ O ( Φ ( P ) 2 1 log π min 1 )
With π m i n \pi_{min} π min the minimal entry in the stationary distribution.
Mixing time. We use standard terminology and results from finite Markov-chain theory; unless stated otherwise, the background in this subsection follows Levin and Peres [35 ] . The mixing time of a Markov process t m i x t_{mix} t mi x is the number of steps needed for a Markov chain to approach its stationary distribution within a fixed convention accuracy threshold, regardless of its initial state. A Markov chain is guaranteed to converge to a stationary distribution if P P P is aperiodic and irreducible. For a Markov chain P P P with stationary distribution π \pi π and a non-trivial cut S ∣ S ˉ S \mid\bar{S} S ∣ S ˉ , the conductance of S S S is defined as
Φ ( S ) = ∑ i ∈ S , j ∈ S ˉ π i P i j min { π ( S ) , π ( S ˉ ) } \Phi(S) = \frac{\sum_{i \in S,j \in\bar{S}} \pi_i P_{ij}}{\min\{\pi(S),\pi(\bar{S})\}} Φ ( S ) = min { π ( S ) , π ( S ˉ )} ∑ i ∈ S , j ∈ S ˉ π i P ij
where π ( . ) \pi(.) π ( . ) is the total sum of weights in the stationary distribution of nodes in the subset. Conductance of P P P is then defined as
Φ ( P ) : = min ∅ ≠ S ⊊ V Φ ( S ) . \Phi(P) := \min_{\varnothing\ne S \subsetneq V} \Phi(S). Φ ( P ) := ∅ = S ⊊ V min Φ ( S ) .
If P P P is symmetric and has nonnegative eigenvalues, spectral theory and the Cheeger inequalities Cheeger [12 ] ; Alon and Milman [4 ] bound the mixing time as a function of conductance, yielding
Ω ( 1 Φ ( P ) ) ≤ t m i x ≤ O ( 1 Φ ( P ) 2 log 1 π m i n ) \Omega\left(\frac{1}{\Phi(P)}\right) \le t_{mix} \le O\left(\frac{1}{\Phi(P)^2}\log\frac{1}{\pi_{min}}\right) Ω ( Φ ( P ) 1 ) ≤ t mi x ≤ O ( Φ ( P ) 2 1 log π min 1 )
With π m i n \pi_{min} π min the minimal entry in the stationary distribution.
DeGroot and consensus. In a classic DeGroot model, interactions are described by an influence matrix P P P in which P i j P_{ij} P ij is the relative influence that agent i i i assigns to agent j j j ’s opinion DeMarzo et al. [15 ] . The weights are relative in the sense that, for each agent, the total influence assigned across all agents is normalized to one; equivalently, P P P is row-stochastic. Let x ( t ) x(t) x ( t ) denote the vector of agents’ opinions at time t t t . The DeGroot update is
x ( t + 1 ) = P x ( t ) . x(t+1) = P x(t). x ( t + 1 ) = P x ( t ) .
The same matrix can be viewed as the transition matrix of a Markov chain, which allows the convergence of the averaging process to be studied using standard spectral and mixing tools.
It is standard in DeGroot-type opinion-dynamics models to interpret the diagonal entry P i i P_{ii} P ii as agent i i i ’s self-reliance, and positive self-weights P i i > 0 P_{ii} > 0 P ii > 0 are a common modeling assumption Jia et al. [31 ] . If we examine each connected component individually, P P P reduced to the nodes of the connected component is irreducible, and the positive self-weights make it aperiodic. Thus, convergence of each component separately is guaranteed. Moreover, the opinion value of each agent converges to the same consensus value which is a weighted average of the agents initial opinions DeGroot [13 ] ; Berger [6 ] ; Olfati-Saber and Murray [40 ] . Under the DeGroot interpretation, convergence of the Markov chain to its stationary distribution corresponds to convergence of opinions to a steady state, namely consensus. Accordingly, the Markov-chain mixing time coincides, up to the chosen accuracy convention, with the time required for the DeGroot process to reach approximate consensus for normalized initial opinions.
Proof of Theorem 7
Proof. Any restriction of P C ( β ) P_C^{(\beta)} P C ( β ) to the connected component yields an aperiodic irreducible matrix, guaranteeing convergence. Since the matrix is symmetric, it is doubly stochastic. A standard result for finite Markov chains is that every doubly stochastic transition matrix admits the uniform stationary distribution. Thus, for a connected component B ⊆ N B \subseteq N B ⊆ N
lim t → ∞ x i ( t ) = 1 ∣ B ∣ ∑ j ∈ B x j ( 0 ) for every i ∈ B , \lim_{t \to\infty} x_i(t) = \frac{1}{|B|} \sum_{j \in B} x_j(0) \qquad\text{for every } i \in B, t → ∞ lim x i ( t ) = ∣ B ∣ 1 j ∈ B ∑ x j ( 0 ) for every i ∈ B ,
with x ( 0 ) x(0) x ( 0 ) the initial opinions of voters. In particular, if C C C is connecting, B = N B = N B = N . □ \square □
Proof of Theorem 9
Proof. As discussed above, the stationary distribution is uniform. Thus, the conductance of S ⊆ N S \subseteq N S ⊆ N with 0 < ∣ S ∣ ≤ n / 2 0 < |S| \le n/2 0 < ∣ S ∣ ≤ n /2 is
Φ C ( β ) ( S ) = ∑ i ∈ S , j ∉ S 1 n ( P C ( β ) ) i j ∣ S ∣ / n = β n − 1 ∣ ∂ G C ( S ) ∣ ∣ S ∣ . \Phi_C^{(\beta)}(S) = \frac{\sum_{i \in S, j \notin S} \frac{1}{n}(P_C^{(\beta)})_{ij}}{|S|/n} = \frac{\beta}{n-1}\frac{|\partial G_C(S)|}{|S|}. Φ C ( β ) ( S ) = ∣ S ∣/ n ∑ i ∈ S , j ∈ / S n 1 ( P C ( β ) ) ij = n − 1 β ∣ S ∣ ∣ ∂ G C ( S ) ∣ .
Consequently,
Φ ( P C ( β ) ) = β n − 1 h ( G C ) . \Phi\left(P_C^{(\beta)}\right) = \frac{\beta}{n-1}h(G_C). Φ ( P C ( β ) ) = n − 1 β h ( G C ) .
In particular, for β = 1 / 2 \beta= 1/2 β = 1/2
Φ ( P C ( 1 / 2 ) ) = h ( G C ) 2 ( n − 1 ) . \Phi\left(P_C^{(1/2)}\right) = \frac{h(G_C)}{2(n-1)}. Φ ( P C ( 1/2 ) ) = 2 ( n − 1 ) h ( G C ) .
Since the lazy process with β = 1 / 2 \beta= 1/2 β = 1/2 admits nonnegative eigenvalues, the conductance bounds imply the requested bounds. □ \square □
Appendix D. Omitted Proofs for the Complexity Section
Fixed-committee CHEEGER evaluation
Proof of Theorem 11. Membership follows from a cut certificate: a nonempty set S S S with ∣ S ∣ ≤ ∣ N ∣ / 2 |S| \le|N|/2 ∣ S ∣ ≤ ∣ N ∣/2 certifies the answer whenever
∣ ∂ G C ( S ) ∣ ∣ S ∣ ≤ ρ . \frac{|\partial G_C(S)|}{|S|} \le\rho. ∣ S ∣ ∣ ∂ G C ( S ) ∣ ≤ ρ .
For hardness, reduce from the Cheeger decision problem on a general graph Leighton and Rao [33 ] ; Garey et al. [23 ] G = ( V , E ) G = (V,E) G = ( V , E ) . Set
N = V , M = E , N = V, \qquad M = E, N = V , M = E ,
and for every v ∈ V v \in V v ∈ V let A v A_v A v consist of the edges of G G G incident to v v v . Set C = E C = E C = E and k = ∣ E ∣ k = |E| k = ∣ E ∣ . Two voters jointly approve a committee member exactly when the corresponding vertices are adjacent in G G G , and hence
The construction has ∣ V ∣ |V| ∣ V ∣ voters, ∣ E ∣ |E| ∣ E ∣ candidates, and 2 ∣ E ∣ 2|E| 2∣ E ∣ approval incidences, so it is polynomial. Therefore
CHGR ( C , E ) ≤ ρ ⟺ h ( G ) ≤ ρ . \operatorname{CHGR}(C,E) \le\rho\quad\Longleftrightarrow\quad h(G) \le\rho. CHGR ( C , E ) ≤ ρ ⟺ h ( G ) ≤ ρ .
NP-hardness of exact-size CHEEGER selection on VI.
Problem Statement
We study the computational complexity of the following decision problem.
VI-Exact-Cheeger
Input: VI election E = ( M , N , A , k ) \mathcal{E}=(M,N,A,k) E = ( M , N , A , k ) and a threshold ρ ∈ Q + \rho\in\mathbb{Q}^{+} ρ ∈ Q + .
Question: Does a committee C ∈ C C \in\mathcal{C} C ∈ C satisfying CHGR ( C , E ) ≥ ρ \operatorname{CHGR}(C,\mathcal{E}) \ge\rho CHGR ( C , E ) ≥ ρ exists?
Equivalently, the question is whether there exists C ⊆ M C \subseteq M C ⊆ M with ∣ C ∣ = k |C|=k ∣ C ∣ = k and
h ( G C E ) ≥ ρ . h(\mathcal{G}_{C}^{\mathcal{E}}) \ge\rho. h ( G C E ) ≥ ρ .
For the hardness proof, we reduce from the following unary variant of 3-Partition.
Strict-Unary-3-Partition
Input: Positive integers a 1 , … , a q , B a_1,\ldots,a_q,B a 1 , … , a q , B , encoded in unary, where
q = 3 s , ∑ i = 1 q a i = s B , q=3s,\qquad\sum_{i=1}^{q}a_i=sB, q = 3 s , i = 1 ∑ q a i = s B ,
and
B 4 < a i < B 2 \frac{B}{4}<a_i<\frac{B}{2} 4 B < a i < 2 B
for every i i i .
Question: Is there a partition of the items into s s s pairwise disjoint sets T 1 , … , T s \mathcal{T}_1,\ldots,\mathcal{T}_s T 1 , … , T s such that for every j j j ,
∑ i ∈ T j a i = B ? \sum_{i\in\mathcal{T}_j}a_i=B? i ∈ T j ∑ a i = B ?
Unary-3-Partition is known to be NP-complete Garey and Johnson [22 ] . We prove NP-hardness by a polynomial-time reduction
\textsc{Strict-Unary-3-Partition}\leq_p\textsc{VI-Exact-Cheeger}.
More precisely, from a source instance I I I we construct an instance ( E ∗ , ρ ) (\mathcal{E}^{*},\rho) ( E ∗ , ρ ) such that
I is a YES-instance ⟺ ( E ∗ , ρ ) is a YES-instance of VI-Exact-Cheeger . I\text{ is a YES-instance}\quad\Longleftrightarrow\quad(\mathcal{E}^{*},\rho)\text{ is a YES-instance of VI-Exact-Cheeger}. I is a YES-instance ⟺ ( E ∗ , ρ ) is a YES-instance of VI-Exact-Cheeger .
Theorem 18. VI-Cheeger-Exact is NP-hard, even when every candidate support is nonempty and the candidate supports are pairwise distinct proper intervals.
Reduction idea
The construction outputs an election E ∗ \mathcal{E}^{*} E ∗ ; unless stated otherwise, graph notation below refers to this constructed instance. It encodes a solution as a sequence of cumulative sets of items referred to as stages , with the interpretation that stage h h h encodes all items assigned to the first h h h bins of the solution. For each h < s h<s h < s , stage h h h is represented by two variable phases , 2 h 2h 2 h and 2 h + 1 2h+1 2 h + 1 , which respectively impose a lower and an upper bound on the total weight of the items in the stage. The final stage h = s h=s h = s is represented only by the final even phase 2 s 2s 2 s , as its upper weight bound follows from the total weight of all items.
For each phase p p p and item i i i , there are two alternative candidates A p , i A_{p,i} A p , i and B p , i B_{p,i} B p , i . The construction will force exactly one of them to be selected. We write
z p , i = { 1 , A p , i is selected , 0 , B p , i is selected . z_{p,i}=
\begin{cases}
1, & A_{p,i}\text{ is selected},\\
0, & B_{p,i}\text{ is selected}.
\end{cases} z p , i = { 1 , 0 , A p , i is selected , B p , i is selected .
The intended interpretation is that z p , i = 1 z_{p,i}=1 z p , i = 1 once item i i i has entered the cumulative collection of completed 3-PARTITION bins. This monotone property is enforced by phase and item specific markers, specifically selected prefix cuts, in which if candidate A p , i A_{p,i} A p , i is selected but A p + 1 , i A_{p+1,i} A p + 1 , i is not, then the expansion drops below the threshold. Thus any committee meeting the threshold ensures z p , i = 1 ⇒ z p ′ , i = 1 z_{p,i}=1\mathbin{\Rightarrow}z_{p',i}=1 z p , i = 1 ⇒ z p ′ , i = 1 for every subsequent phase p ′ p' p ′ .
Additionally, for each phase p p p and item i i i , two auxiliary weighting candidates, an anchor g p , i g_{p,i} g p , i and a weight-dependent component e p , i e_{p,i} e p , i are introduced. Together with the two alternative candidates, they create an a i a_i a i -sized multiplier for z p , i z_{p,i} z p , i . This is achieved using a weight probe, a single phase specific selected prefix, used to measure the cumulative weight effect of all items. At the weight probe, each individual item’s weighting candidates create an a i a_i a i difference in boundary by choosing A p , i A_{p,i} A p , i relative to choosing B p , i B_{p,i} B p , i . Consequently,
w p = ∑ i a i z p , i w_p = \sum_i a_i z_{p,i} w p = i ∑ a i z p , i
is the cumulative weight encoded in phase p p p .
The two phases associated with a stage encode this same cumulative weight with opposite signs: in an even phase, selecting A p , i A_{p,i} A p , i contributes + a i +a_i + a i to the relevant boundary expression relative to selecting B p , i B_{p,i} B p , i , while in an odd phase it contributes − a i -a_i − a i . Hence the committee-dependent contribution of phase p p p is proportional to ( − 1 ) p w p (-1)^p w_p ( − 1 ) p w p .
Each phase also includes a small set of calibration candidates with the intended purpose of comparing w p w_p w p against the desired h B hB h B cumulative weight at stage h h h . Even and odd phases impose opposite inequalities on the cumulative weight represented by that stage. The calibration candidates cause the baseline boundary of the weight probe to correspond with the target cumulative weight. The alternating sign then makes weights below the target fail in the even phase and weights above the target fail in the odd phase, so the two phases jointly impose both a lower and an upper bound on the cumulative weight represented by the stage. Therefore, any committee that guarantees the threshold must encode cumulative weight exactly h B hB h B at stage h h h .
Because
B 4 < a i < B 2 , \frac{B}{4} < a_i < \frac{B}{2}, 4 B < a i < 2 B ,
every set of total weight B B B necessarily contains exactly three items. Consequently, the differences between stages form a valid 3-partition.
The remaining candidates have three auxiliary purposes: they calibrate all diagnostic cuts (i.e., monotonicity markers and weight probes) to one common threshold, force every feasible committee into the intended A / B A/B A / B form, and provide enough surplus to make all nondiagnostic cuts safe, i.e. have expansion above the threshold. The construction is analyzed first through prefix cuts of the voter order, which are where the monotonicity markers and weight probes are placed. This does not assume that a minimum-expansion cut is a prefix: after establishing the required bounds for all prefixes, we separately show that every arbitrary cut is at least as safe, using the interval structure together with the large head and tail cliques.
Construction
The Neutral Phase. For the analysis, it is useful to first consider a simplified version of a variable phase, which we call a neutral phase . A neutral phase is constructed from the same calibration, weighting, and alternative candidates, with additional scaffolding candidates that control fixed numerical values used in the construction, and serves as a common baseline against which the actual phases will later be compared.
A phase should not be thought of as an isolated gadget whose candidates are contained within it. Rather, Ω \Omega Ω specifies a fixed-size window in the voter order, and candidate intervals typically extend from one such window into the next. Let X p X_p X p denote the beginning of phase p p p . We describe a candidate in phase p p p by a local pair ( a , b ) (a,b) ( a , b ) , meaning that its approval interval is
[ X p + a + 1 , X p + 1 + b ] . [X_p+a+1, X_{p+1}+b]. [ X p + a + 1 , X p + 1 + b ] .
Thus a a a specifies the position of its left endpoint relative to the beginning of the current phase, whereas b b b specifies the position of its right endpoint relative to the beginning of the following phase. Specifically, set
X 1 = ( T − 1 ) Q + 1 , X 0 = X 1 − Ω X_1=(T-1)Q+1,\qquad X_0=X_1-\Omega X 1 = ( T − 1 ) Q + 1 , X 0 = X 1 − Ω
for a parameter T T T that we calculate later. Then for each phase p p p X p = X 0 + p Ω X_p=X_0+p\Omega X p = X 0 + p Ω is the start of phase p p p .
Since the intervals of voters approving each candidate extend between phases, the geometry of a neutral phase is easiest to describe through the positions at which candidates begin. Set
q = 3 s , r = 2 s + 1 , ν = r q , W = s B . q = 3s,\qquad r = 2s + 1,\qquad\nu= rq,\qquad W = sB. q = 3 s , r = 2 s + 1 , ν = r q , W = s B .
And define
J = 100 ( ν + 3 ) , Ξ = ( J + 1 ) W , ε = 10 r Ξ + 10 , J = 100(\nu+ 3),\qquad\Xi= (J + 1)W,\qquad\varepsilon= 10r\Xi+ 10, J = 100 ( ν + 3 ) , Ξ = ( J + 1 ) W , ε = 10 r Ξ + 10 ,
v = 50 ( ε + ν + W + J + 1 ) , Λ = 2 v , v = 50(\varepsilon+ \nu+ W + J + 1),\qquad\Lambda= 2v, v = 50 ( ε + ν + W + J + 1 ) , Λ = 2 v ,
H = 100 ( ν + r + 10 ) Λ , Ω = 12 H + 4 q v . H = 100(\nu+ r + 10)\Lambda,\qquad\Omega= 12H + 4qv. H = 100 ( ν + r + 10 ) Λ , Ω = 12 H + 4 q v .
As discussed above each phase has size Ω \Omega Ω . The first 8 H 8H 8 H positions are used by the scaffold. The item gadgets then appear in order, with
ξ i = 8 H + 4 v ( i − 1 ) , \xi_i = 8H + 4v(i - 1), ξ i = 8 H + 4 v ( i − 1 ) ,
so the starting patterns of consecutive items are spaced 4 v 4v 4 v apart. Relative to ξ i \xi_i ξ i , the two alternatives begin at
ξ i + v − 1 and ξ i + v , \xi_i + v - 1 \qquad\text{and}\qquad\xi_i + v, ξ i + v − 1 and ξ i + v ,
the auxiliary weighting candidate e p , i e_{p,i} e p , i begins at
in the neutral phase, and the anchor g p , i g_{p,i} g p , i begins at
Figure 4. The item gadget for item i i i . The left endpoints of the four candidates lie in the 4 v 4v 4 v -wide item window of phase p p p , while their right endpoints lie in phase p + 1 p+1 p + 1 . In the neutral template, e p , i e_{p,i} e p , i starts at ξ i + 3 v \xi_i + 3v ξ i + 3 v ; in the actual construction this start is shifted by σ p a i \sigma_p a_i σ p a i .
The neutral scaffold consists of seven fixed candidates, whose local coordinates are
Table 4.
Here, as above, ( a , b ) (a,b) ( a , b ) means that the candidate interval starts at position a a a relative to the current phase and ends at position b b b relative to the following phase. Among these scaffold candidates, c 1 c_1 c 1 and c 4 c_4 c 4 are the calibration candidates .
Note that these are only the starting positions: the corresponding candidate intervals extend into the following phase according to their second local coordinate.
We concatenate 2 s + 1 2s + 1 2 s + 1 copies of the neutral phase template, each spanning Ω \Omega Ω positions in the voter order. These copies form the variable phases p = 0 , … , 2 s p = 0,\ldots,2s p = 0 , … , 2 s . We then apply the phase-specific modifications described below.
Phase-Specific Modifications. Actual phases are obtained from the neutral template by introducing the phase-specific information. For each variable phase p p p , let
σ p = ( − 1 ) p . \sigma_p = (-1)^p. σ p = ( − 1 ) p .
The weighting candidate e p , i e_{p,i} e p , i for item i i i is moved from its neutral starting position ξ i + 3 v \xi_i + 3v ξ i + 3 v to
ξ i + 3 v − σ p a i . \xi_i + 3v - \sigma_p a_i. ξ i + 3 v − σ p a i .
Thus, the weight candidate of each item has offset of a i a_i a i from the neutral phase’s position. σ p \sigma_p σ p changes the orientation of the offset in even and odd phases.
In addition, the two calibration candidates in phase p p p are similarly modified. Let
b p = ⌊ p 2 ⌋ B . b_p = \left\lfloor\frac{p}{2} \right\rfloor B. b p = ⌊ 2 p ⌋ B .
The calibration value is set to be
δ p = { − p ε − J W + b p , p odd , 0 , p even . \delta_p =
\begin{cases}
-p\varepsilon- JW + b_p, & p\ \text{odd},\\
0, & p\ \text{even}.
\end{cases} δ p = { − pε − J W + b p , 0 , p odd , p even .
Then the right endpoint of c 1 c_1 c 1 is shifted by + δ p +\delta_p + δ p , while the right endpoint of c 4 c_4 c 4 is shifted by − δ p -\delta_p − δ p .
Figure 5. A single phase. The phase consists of a scaffold block followed by q q q item windows.
There are two endpoint exceptions to the common phase template. Phase 0 omits the first three scaffold candidates c 0 c_0 c 0 , c 1 c_1 c 1 , c 2 c_2 c 2 . After the last variable phase, the construction contains one final scaffold-only phase: it contains the scaffold candidates but no item gadgets. The final phase-specific intervals are therefore summarized below.
Table 3.
Table 5.
Finally, we embed the phased construction inside a larger voter order. We call the area that contains the concatenated phases the active region.
The active region begin in X 1 X_1 X 1 and we denote by η = X r + 8 H + v − 1 \eta= X_r + 8H + v - 1 η = X r + 8 H + v − 1 the right endpoint of the active region; the total number of voters is denoted by n n n . Their exact values are chosen later so that every prefix through the active region lies on the smaller side of the Cheeger cut and so that there is ample padding on both sides.
We use this padding to add two fixed candidates. The head candidate is approved by voters [ 1 , X 1 ] [1, X_1] [ 1 , X 1 ] , while the tail candidate is approved by voters [ η + 1 , n ] [\eta+ 1, n] [ η + 1 , n ] . Thus each end of the construction forms a large clique in the committee graph. These cliques make prefixes lying sufficiently far outside the phased construction automatically safe, allowing the remainder of the proof to focus on cuts through the active region.
Figure 6. The overall active region. The head and tail indicate padded cliques that continue beyond the active construction. Inside the active region, the construction concatenates the variable phases, and each stage is represented by two consecutive phases.
Finally, we set the committee size k = r ( 3 q + 7 ) + 6 k = r(3q + 7) + 6 k = r ( 3 q + 7 ) + 6 and the threshold ρ = 1 Q \rho= \frac{1}{Q} ρ = Q 1 for Q = 10 ( r + 3 ) Ω Q = 10(r + 3)\Omega Q = 10 ( r + 3 ) Ω .
Proof- general machinery
A common threshold for all active prefixes. The active region satisfies
η − X 1 + 1 < Q . \eta- X_1 + 1 < Q. η − X 1 + 1 < Q .
Since
X 1 = ( T − 1 ) Q + 1 , X_1 = (T - 1)Q + 1, X 1 = ( T − 1 ) Q + 1 ,
every integer t ∈ [ X 1 , η ] t \in[X_1, \eta] t ∈ [ X 1 , η ] satisfies
( T − 1 ) Q < t < T Q (T - 1)Q < t < TQ ( T − 1 ) Q < t < T Q
and lies below n / 2 n/2 n /2 . The Cheeger requirement at this prefix is
∣ ∂ G C ( P t ) ∣ ≥ t Q . \lvert\partial_{G_C}(P_t) \rvert\ge\frac{t}{Q}. ∣ ∂ G C ( P t )∣ ≥ Q t .
∣ ∂ G C ( P t ) ∣ \lvert\partial_{G_C}(P_t) \rvert ∣ ∂ G C ( P t )∣ is an integer, therefore it must be that ∣ ∂ G C ( P t ) ∣ ≥ T \lvert\partial_{G_C}(P_t) \rvert\ge T ∣ ∂ G C ( P t )∣ ≥ T . Thus, for every prefix cut we only need to lower bound the boundary by T T T to show its expansion meets the threshold.
For completeness, every nontrivial prefix outside the active window is automatically safe for the intended committee as well. If
1 ≤ t < X 1 , 1 \le t < X_1, 1 ≤ t < X 1 ,
the head clique contributes
t ( X 1 − t ) ≥ t , t(X_1 - t) \ge t, t ( X 1 − t ) ≥ t ,
so in particular
∣ ∂ G C ( P t ) ∣ ≥ min { t , n − t } Q . \lvert\partial_{G_C}(P_t) \rvert\ge\frac{\min\{t,n-t\}}{Q}. ∣ ∂ G C ( P t )∣ ≥ Q min { t , n − t } .
If
the tail clique contributes
( t − η ) ( n − t ) ≥ n − t , (t-\eta)(n-t) \ge n-t, ( t − η ) ( n − t ) ≥ n − t ,
and therefore again
∣ ∂ G C ( P t ) ∣ ≥ min { t , n − t } Q . (3) \lvert\partial_{G_C}(P_t) \rvert\ge\frac{\min\{t,n-t\}}{Q}. \tag*{(3)} ∣ ∂ G C ( P t )∣ ≥ Q min { t , n − t } . (3)
Signed contribution. Fix a committee C C C and a prefix P t = { 1 , … , t } P_t = \{1,\ldots,t\} P t = { 1 , … , t } . For a voter x ≤ t x \le t x ≤ t , let R C ( x ) R_C(x) R C ( x ) be the rightmost voter that shares a selected candidate with x x x . Since every selected candidate’s support is an interval of voters, x x x is adjacent to every voter between x x x and R C ( x ) R_C(x) R C ( x ) . Hence the number of boundary edges incident to x x x and crossing P t P_t P t , to which we also call the contribution of x x x , is
max { 0 , R C ( x ) − t } . \max\{0,R_C(x)-t\}. max { 0 , R C ( x ) − t } .
Therefore
∣ ∂ G C ( P t ) ∣ = ∑ x = 1 t max { 0 , R C ( x ) − t } . (4) \lvert\partial G_C(P_t)\rvert= \sum_{x=1}^{t}\max\{0,R_C(x)-t\}. \tag*{(4)} ∣ ∂ G C ( P t )∣ = x = 1 ∑ t max { 0 , R C ( x ) − t } . (4)
This identity counts simple graph edges exactly: even if several selected candidates generate the same edge, the edge appears only once, and the rightmost selected interval containing x x x describes the entire contiguous set of rightward neighbors of x x x .
We call
the signed contribution of voter x x x . Equivalently, voter x x x may be viewed as row x x x of the adjacency matrix; R C ( x ) − t R_C(x)-t R C ( x ) − t measures how far that row extends beyond the prefix boundary, with negative values retained for algebraic bookkeeping. The signed contribution lower bounds the actual contribution of x x x to the boundary:
max { 0 , R C ( x ) − t } ≥ R C ( x ) − t \max\{0,R_C(x)-t\} \ge R_C(x)-t max { 0 , R C ( x ) − t } ≥ R C ( x ) − t
The signed contribution is only a lower-bound device; it need not equal the actual contribution of a voter. In particular, it may be negative. For the boundary we get
∣ ∂ G C ( P t ) ∣ ≥ ∑ x = 1 t R C ( x ) − t . \lvert\partial G_C(P_t)\rvert\ge\sum_{x=1}^{t} R_C(x)-t. ∣ ∂ G C ( P t )∣ ≥ x = 1 ∑ t R C ( x ) − t .
We now use these prefix-boundary calculations to show that every committee meeting the threshold must have the intended form.
For one complete neutral phase, the signed contributions of all Ω \Omega Ω voters in the phase sum to the same value L L L , independently of which alternative A p , i A_{p,i} A p , i or B p , i B_{p,i} B p , i is selected for each item. Choosing A p , i A_{p,i} A p , i rather than B p , i B_{p,i} B p , i changes where the contribution appears within the phase, but not its total over the complete phase. Later, when considering a prefix that falls inside a phase, we use a window of the same length Ω \Omega Ω consisting of a suffix of the preceding phase and a prefix of the current one. For the monotone choices used by the intended committee—once an item switches from B B B to A A A , it never switches back—the signed contribution of every such interior window is at least L L L . Since signed contribution lower-bounds the actual boundary, this gives a uniform lower bound on all nondiagnostic prefixes.
Soundness- from VI to 3-PARTITION
The soundness proof is composed of three parts:
Every feasible committee has normal form : must select all "fixed" candidates and exactly one of A p , i , B p , i A_{p,i},B_{p,i} A p , i , B p , i for each item in each phase.
Every feasible committee admits monotonicity: z p , i = 1 → z p + 1 , i = 1 z_{p,i}=1 \mathbin{\to} z_{p+1,i}=1 z p , i = 1 → z p + 1 , i = 1 for every phase p p p .
Every feasible committee admits the desired cumulative weight for each stage: the weight probes of stage h h h derive w 2 h ≥ h B w_{2h}\ge hB w 2 h ≥ h B and w 2 h + 1 ≤ h B w_{2h+1}\le hB w 2 h + 1 ≤ h B .
Normal Form. We first derive the following lemma.
Lemma 19 (Deletion lemma). Let K K K be a committee, let c ∈ K c\in K c ∈ K , and let u , v ∈ K ∖ { c } u,v\in K\setminus\{c\} u , v ∈ K ∖ { c } be respectively the selected candidates immediately preceding and following c c c in the interval order. Write their supports as
[ ℓ x + 1 , r x ] , x ∈ { u , c , v } . [\ell_x+1,r_x],\qquad x\in\{u,c,v\}. [ ℓ x + 1 , r x ] , x ∈ { u , c , v } .
For a prefix P t = { 1 , … , t } P_t = \{1,\ldots,t\} P t = { 1 , … , t } , deleting c c c from the committee removes exactly
[ min { t , ℓ v } − ℓ c ] + [ r c − max { t , r u } ] + \left[\min\{t,\ell_v\}-\ell_c\right]_+ \left[r_c-\max\{t,r_u\}\right]_+ [ min { t , ℓ v } − ℓ c ] + [ r c − max { t , r u } ] +
edges from ∂ ( P t ) \partial(P_t) ∂ ( P t ) , where [ x ] + = max { x , 0 } [x]_+ = \max\{x,0\} [ x ] + = max { x , 0 } .
Proof. A voter can lose neighbors when c c c is deleted only if c c c is responsible for extending its rightmost reach beyond that provided by the preceding selected candidate u u u . These are precisely the voters
ℓ c < x ≤ ℓ v . \ell_c < x \le\ell_v. ℓ c < x ≤ ℓ v .
Among them, only voters lying in P t P_t P t contribute to the loss across the prefix cut, so the number of affected rows is
[ min { t , ℓ v } − ℓ c ] + . \left[\min\{t,\ell_v\}-\ell_c\right]_+. [ min { t , ℓ v } − ℓ c ] + .
For every such affected row, candidate c c c extends the rightmost reach to r c r_c r c , whereas after deleting c c c the reach falls to r u r_u r u . Only neighbors lying to the right of the cut contribute to ∂ ( P t ) \partial(P_t) ∂ ( P t ) , so each affected row loses
[ r c − max { t , r u } ] + \left[r_c-\max\{t,r_u\}\right]_+ [ r c − max { t , r u } ] +
crossing edges.
Multiplying the number of affected rows by the loss per row gives
[ min { t , ℓ v } − ℓ c ] + [ r c − max { t , r u } ] + , \left[\min\{t,\ell_v\}-\ell_c\right]_+ \left[r_c-\max\{t,r_u\}\right]_+, [ min { t , ℓ v } − ℓ c ] + [ r c − max { t , r u } ] + ,
as claimed. □
Calculation of T T T . We first calculate the signed contribution of a complete neutral phase and use it to express the target boundary threshold. Fix a neutral phase p p p , and measure voter positions locally from X p X_p X p . For 1 ≤ x ≤ Ω 1 \le x \le\Omega 1 ≤ x ≤ Ω , let f p ( x ) f_p(x) f p ( x ) denote the signed contribution of voter X p + x X_p+x X p + x to the prefix ending at X p + 1 X_{p+1} X p + 1 , and let
F p ( u ) : = ∑ x = 1 u f p ( x ) . F_p(u) := \sum_{x=1}^{u} f_p(x). F p ( u ) := x = 1 ∑ u f p ( x ) .
Thus F p ( Ω ) F_p(\Omega) F p ( Ω ) is the total signed contribution of the rows of phase p p p across its right boundary.
Recall that a candidate represented by the local pair ( a , b ) (a,b) ( a , b ) begins at local voter a + 1 a+1 a + 1 and has right endpoint X p + 1 + b X_{p+1}+b X p + 1 + b . Since the candidate intervals in the neutral template are proper and consecutive candidates overlap, between two consecutive candidate starts the rightmost reach is given by the candidate that started most recently. Hence, if a candidate with pair ( a , b ) (a,b) ( a , b ) is followed by a candidate starting at a ′ + 1 a' + 1 a ′ + 1 , then it contributes
to F p ( Ω ) F_p(\Omega) F p ( Ω ) .
We first observe that the total does not depend on which alternative is chosen for an item. Fix item i i i and abbreviate ξ = ξ i \xi=\xi_i ξ = ξ i and v = v v=v v = v . Immediately before the alternative pair, the rightmost reach has offset ξ − v \xi-v ξ − v . If A p , i A_{p,i} A p , i is selected instead of B p , i B_{p,i} B p , i , then on the single row at local position ξ + v \xi+v ξ + v the signed contribution increases by
( ξ + v ) − ( ξ − v ) = 2 v . (\xi+v)-(\xi-v)=2v. ( ξ + v ) − ( ξ − v ) = 2 v .
On the following 2 v 2v 2 v rows, from ξ + v + 1 \xi+v+1 ξ + v + 1 through ξ + 3 v \xi+3v ξ + 3 v , the right endpoint of A p , i A_{p,i} A p , i is one position earlier than that of B p , i B_{p,i} B p , i , decreasing the signed contribution by 1 on each row. The total change is therefore
Consequently,
is independent of all alternative choices. We may therefore calculate it assuming that B p , i B_{p,i} B p , i is selected for every item i i i . Under this choice, the scaffold candidates control successive row blocks of lengths
H , 1 , 2 H − 1 , H , 1 , 4 H − 1 , v H,\quad1,\quad2H-1,\quad H,\quad1,\quad4H-1,\quad v H , 1 , 2 H − 1 , H , 1 , 4 H − 1 , v
with respective signed contributions per row
− 2 H , − H , 0 , 5 H , 6 H , 7 H , 8 H − v . -2H,\quad-H,\quad0,\quad5H,\quad6H,\quad7H,\quad8H-v. − 2 H , − H , 0 , 5 H , 6 H , 7 H , 8 H − v .
Their total contribution is therefore
L s c = H ( − 2 H ) + 1 ( − H ) + ( 2 H − 1 ) 0 + H ( 5 H ) + 1 ( 6 H ) + ( 4 H − 1 ) ( 7 H ) + v ( 8 H − v ) = 31 H 2 + 8 H v − v 2 − 2 H . L_{\mathrm{sc}} = H(-2H) + 1(-H) + (2H-1)0 + H(5H) + 1(6H)
+ (4H-1)(7H) + v(8H-v)
= 31H^2 + 8Hv - v^2 - 2H. L sc = H ( − 2 H ) + 1 ( − H ) + ( 2 H − 1 ) 0 + H ( 5 H ) + 1 ( 6 H ) + ( 4 H − 1 ) ( 7 H ) + v ( 8 H − v ) = 31 H 2 + 8 H v − v 2 − 2 H .
Now consider item i i i . Write ξ i = ξ i \xi_i=\xi_i ξ i = ξ i . Apart from the extra terminal part after the last item, the three relevant row blocks are controlled by B p , i B_{p,i} B p , i , e p , i e_{p,i} e p , i , and g p , i g_{p,i} g p , i . Their lengths are respectively
2 v , v , v 2v,\quad v,\quad v 2 v , v , v
and their signed contributions per row are
ξ i + v + 1 , ξ i + v + 1 + J , ξ i + 3 v . \xi_i+v+1,\quad\xi_i+v+1+J,\quad\xi_i+3v. ξ i + v + 1 , ξ i + v + 1 + J , ξ i + 3 v .
Thus the standard contribution of item i i i is
L i = 2 v ( ξ i + v + 1 ) + v ( ξ i + v + 1 + J ) + v ( ξ i + 3 v ) = 4 v ξ i + 6 v 2 + v ( J + 3 ) . L_i = 2v(\xi_i+v+1) + v(\xi_i+v+1+J) + v(\xi_i+3v)
= 4v\xi_i + 6v^2 + v(J+3). L i = 2 v ( ξ i + v + 1 ) + v ( ξ i + v + 1 + J ) + v ( ξ i + 3 v ) = 4 v ξ i + 6 v 2 + v ( J + 3 ) .
Since
ξ i = 8 H + 4 v ( i − 1 ) , \xi_i = 8H + 4v(i-1), ξ i = 8 H + 4 v ( i − 1 ) ,
we have
∑ i = 1 q ξ i = 8 q H + 2 q ( q − 1 ) v , \sum_{i=1}^{q}\xi_i = 8qH + 2q(q-1)v, i = 1 ∑ q ξ i = 8 q H + 2 q ( q − 1 ) v ,
and hence
∑ i = 1 q L i = 32 q H v + ( 8 q 2 − 2 q ) v 2 + q v ( J + 3 ) . \sum_{i=1}^{q}L_i = 32qHv + (8q^2-2q)v^2 + qv(J+3). i = 1 ∑ q L i = 32 q H v + ( 8 q 2 − 2 q ) v 2 + q v ( J + 3 ) .
For the last item, g q g_q g q remains the rightmost-started candidate for 4 H 4H 4 H rows, whereas the standard item calculation above counted only v v v of them. We must therefore add the terminal contribution
L e n d = ( 4 H − v ) ( ξ q + 3 v ) = ( 4 H − v ) ( 8 H + ( 4 q − 1 ) v ) = 32 H 2 + ( 16 q − 12 ) H v − ( 4 q − 1 ) v 2 . L_{\mathrm{end}} = (4H-v)(\xi_q+3v)
= (4H-v)(8H+(4q-1)v)
= 32H^2 + (16q-12)Hv - (4q-1)v^2. L end = ( 4 H − v ) ( ξ q + 3 v ) = ( 4 H − v ) ( 8 H + ( 4 q − 1 ) v ) = 32 H 2 + ( 16 q − 12 ) H v − ( 4 q − 1 ) v 2 .
Combining the scaffold, item, and terminal contributions gives
F p ( Ω ) = L s c + ∑ i = 1 q L i + L e n d = 63 H 2 + ( 48 q − 4 ) H v + ( 8 q 2 − 6 q ) v 2 + q v ( J + 3 ) − 2 H = L . F_p(\Omega) = L_{\mathrm{sc}} + \sum_{i=1}^{q}L_i + L_{\mathrm{end}}
= 63H^2 + (48q-4)Hv + (8q^2-6q)v^2 + qv(J+3) - 2H
= L. F p ( Ω ) = L sc + i = 1 ∑ q L i + L end = 63 H 2 + ( 48 q − 4 ) H v + ( 8 q 2 − 6 q ) v 2 + q v ( J + 3 ) − 2 H = L .
Thus every complete neutral phase has the same total signed contribution, independently of its alternative choices:
F p ( Ω ) = L . F_p(\Omega)=L. F p ( Ω ) = L .
We set T = L − ε T=L-\varepsilon T = L − ε .
Finally, We use Lemma 19 to show that every feasible committee has normal form.
Lemma 20 (Normal form). Let K K K be a committee of size k k k such that
h ( G K ) ≥ ρ . h(G_K) \ge\rho. h ( G K ) ≥ ρ . Then K K K contains every fixed candidate and, for every phase–item pair ( p , i ) (p,i) ( p , i ) , exactly one of the two alternative candidates A p , i A_{p,i} A p , i and B p , i B_{p,i} B p , i .
Proof. As previously argued, every diagnostic prefix in the active region must have boundary at least T T T .
We first establish a uniform reserve bound. At every diagnostic prefix used below, even the graph obtained by selecting all available candidates has boundary at most
T + R , R : = W + ν Λ . T+R,\qquad R:=W+\nu\Lambda. T + R , R := W + ν Λ. Hence, if omitting a candidate c c c decreases the boundary of some diagnostic prefix by more than R R R , then c c c must belong to every feasible committee. Indeed, if the deletion loss at P t P_t P t is Δ c > R \Delta_c>R Δ c > R , then any committee omitting c c c satisfies
∣ ∂ G K ( P t ) ∣ ≤ T + R − Δ c < T . \lvert\partial G_K(P_t)\rvert\le T+R-\Delta_c<T. ∣ ∂ G K ( P t )∣ ≤ T + R − Δ c < T . contradicting feasibility.
We now apply the deletion-rectangle lemma to the fixed candidates. For each fixed candidate, we choose the corresponding diagnostic prefix and obtain the following deletion losses:
2 H 2 , H − δ p , ( 4 H − 1 ) ( H + δ p ) , 2H^2,\qquad H-\delta_p,\qquad(4H-1)(H+\delta_p), 2 H 2 , H − δ p , ( 4 H − 1 ) ( H + δ p ) , ( v − 1 ) ( H − v ) , ( v + σ p a i ) J , ( v − 1 ) ( 2 v − 1 − J ) , (v-1)(H-v),\qquad(v+\sigma_{p a_i})J,\qquad(v-1)(2v-1-J), ( v − 1 ) ( H − v ) , ( v + σ p a i ) J , ( v − 1 ) ( 2 v − 1 − J ) , together with the analogous losses for the remaining scaffold candidates. By the parameter inequalities, every relevant deletion loss is larger than R R R . Therefore every such fixed candidate must be selected.
The endpoint candidates are forced directly. If the head candidate is absent, voter 1 1 1 is isolated, while if the tail candidate is absent, voter n n n is isolated. In either case,
h ( G K ) = 0 < ρ . h(G_K)=0<\rho. h ( G K ) = 0 < ρ . Thus every feasible committee contains all fixed candidates.
There are
r ( 2 q + 7 ) + 6 r(2q+7)+6 r ( 2 q + 7 ) + 6 fixed candidates.
It remains to consider the alternative candidates. Fix a phase–item pair ( p , i ) (p,i) ( p , i ) and suppose that neither A p , i A_{p,i} A p , i nor B p , i B_{p,i} B p , i is selected. At the corresponding forcing prefix, once A p , i A_{p,i} A p , i is absent, deleting B p , i B_{p,i} B p , i causes a loss of
( 2 v − σ p a i ) ( 2 v + 1 ) . (2v-\sigma_{p a_i})(2v+1). ( 2 v − σ p a i ) ( 2 v + 1 ) . By the parameter inequalities,
( 2 v − σ p a i ) ( 2 v + 1 ) > R . (2v-\sigma_{p a_i})(2v+1)>R. ( 2 v − σ p a i ) ( 2 v + 1 ) > R . Hence the boundary of that prefix would be smaller than T T T , contradicting feasibility. Therefore every feasible committee contains at least one of A p , i A_{p,i} A p , i and B p , i B_{p,i} B p , i for every ( p , i ) (p,i) ( p , i ) .
There are r q rq r q such alternative pairs. Consequently, every feasible committee contains at least
r ( 2 q + 7 ) + 6 + r q = r ( 3 q + 7 ) + 6 = k r(2q+7)+6+rq=r(3q+7)+6=k r ( 2 q + 7 ) + 6 + r q = r ( 3 q + 7 ) + 6 = k candidates. Since the committee size is exactly k k k , all of these lower bounds must be tight. Hence every fixed candidate is selected and exactly one alternative candidate is selected from every pair { A p , i , B p , i } \{A_{p,i},B_{p,i}\} { A p , i , B p , i } . □
Monotonicity. By the normal-form lemma, every feasible committee contains exactly one of A p , i A_{p,i} A p , i and B p , i B_{p,i} B p , i for every phase–item pair ( p , i ) (p,i) ( p , i ) . We may therefore define
z p , i : = { 1 , if A p , i is selected , 0 , if B p , i is selected . z_{p,i} := \begin{cases} 1, & \text{if } A_{p,i}\text{ is selected}, \\ 0, & \text{if } B_{p,i}\text{ is selected}. \end{cases} z p , i := { 1 , 0 , if A p , i is selected , if B p , i is selected .
We show that these choices are monotone across phases. For every p ≥ 1 p \ge1 p ≥ 1 and item i i i , consider the marker prefix ending at
μ p , i : = X p + ξ i + v , \mu_{p,i} := X_p + \xi_i + v, μ p , i := X p + ξ i + v ,
the leftmost endpoint of the support of candidate A p , i A_{p,i} A p , i . At this prefix, the boundary satisfies
∣ ∂ ( P μ p , i ) ∣ = L + Λ z p , i − Λ z p − 1 , i + C p , i , |\partial(P_{\mu_{p,i}})| = L + \Lambda z_{p,i} - \Lambda z_{p-1,i} + C_{p,i}, ∣ ∂ ( P μ p , i ) ∣ = L + Λ z p , i − Λ z p − 1 , i + C p , i ,
where C p , i C_{p,i} C p , i collects the phase-specific perturbations. These perturbations satisfy ∣ C p , i ∣ ≤ Ξ |C_{p,i}| \le\Xi ∣ C p , i ∣ ≤ Ξ .
Indeed, up to the neutral baseline L L L , changing the choice in phase p p p from B p , i B_{p,i} B p , i to A p , i A_{p,i} A p , i increases the boundary at the marker by Λ \Lambda Λ , whereas making the same change in the preceding phase decreases it by Λ \Lambda Λ . All remaining phase-specific changes contribute the error term C p , i C_{p,i} C p , i .
Suppose now that, for some p p p and i i i ,
z p − 1 , i = 1 and z p , i = 0. z_{p-1,i} = 1 \qquad\text{and} \qquad z_{p,i} = 0. z p − 1 , i = 1 and z p , i = 0.
Then
∣ ∂ ( P μ p , i ) ∣ = L − Λ + C p , i ≤ L − Λ + Ξ . |\partial(P_{\mu_{p,i}})| = L - \Lambda+ C_{p,i} \le L - \Lambda+ \Xi. ∣ ∂ ( P μ p , i ) ∣ = L − Λ + C p , i ≤ L − Λ + Ξ.
By the parameter inequalities, Λ > ε + Ξ \Lambda> \varepsilon+ \Xi Λ > ε + Ξ . Since T = L − ε T = L - \varepsilon T = L − ε , we get that
∣ ∂ ( P μ p , i ) ∣ < L − ε = T . |\partial(P_{\mu_{p,i}})| < L - \varepsilon= T. ∣ ∂ ( P μ p , i ) ∣ < L − ε = T .
This contradicts the common-threshold condition for feasible committees.
Cumulative Weight. For every phase p p p , define the cumulative weight encoded by that phase as
w p : = ∑ i = 1 q a i z p , i . w_p := \sum_{i=1}^{q} a_i z_{p,i}. w p := i = 1 ∑ q a i z p , i .
Recall that σ p = ( − 1 ) p \sigma_p = (-1)^p σ p = ( − 1 ) p . We now show that the designated weight probe in phase p p p compares w p w_p w p with the intended cumulative target ⌊ p / 2 ⌋ B \left\lfloor p/2 \right\rfloor B ⌊ p /2 ⌋ B .
For every variable phase p p p , let
τ p : = X p + 1 + 3 H . \tau_p := X_{p+1} + 3H. τ p := X p + 1 + 3 H .
We claim that
∣ ∂ ( P τ p ) ∣ − T = σ p ( w p − ⌊ p 2 ⌋ B ) . |\partial(P_{\tau_p})| - T = \sigma_p \left(w_p - \left\lfloor\frac{p}{2} \right\rfloor B\right). ∣ ∂ ( P τ p ) ∣ − T = σ p ( w p − ⌊ 2 p ⌋ B ) .
We obtain this identity by comparing the boundary at τ p \tau_p τ p with the neutral baseline L L L . Fix an item i i i . The displacement of the weighting candidate e p , i e_{p,i} e p , i from its neutral position changes the boundary at the probe by
σ p J a i . \sigma_p J a_i. σ p J a i .
This contribution is independent of which alternative is selected. The choice between A p , i A_{p,i} A p , i and B p , i B_{p,i} B p , i contributes an additional σ p a i \sigma_p a_i σ p a i precisely when A p , i A_{p,i} A p , i is selected. To see this, compare the two choices at the probe. The unique row at the left endpoint of A p , i A_{p,i} A p , i gains Λ = 2 v \Lambda= 2v Λ = 2 v crossing edges when A p , i A_{p,i} A p , i is selected. On the following
Λ − σ p a i \Lambda- \sigma_p a_i Λ − σ p a i
rows, the rightmost reach is one position smaller than under the B p , i B_{p,i} B p , i choice. Hence the net difference is
Λ − ( Λ − σ p a i ) = σ p a i . \Lambda- (\Lambda- \sigma_p a_i) = \sigma_p a_i. Λ − ( Λ − σ p a i ) = σ p a i .
Since this term occurs exactly when z p , i = 1 z_{p,i}=1 z p , i = 1 , the total contribution of item i i i relative to the neutral phase is
σ p J a i + σ p a i z p , i . \sigma_p J a_i+\sigma_p a_i z_{p,i}. σ p J a i + σ p a i z p , i .
Summing over all items and using
∑ i = 1 q a i = W \sum_{i=1}^{q} a_i=W i = 1 ∑ q a i = W
gives
σ p J W + σ p w p = σ p ( J W + w p ) . \sigma_p JW+\sigma_p w_p=\sigma_p(JW+w_p). σ p J W + σ p w p = σ p ( J W + w p ) .
The calibration candidates contribute the remaining phase-dependent term. At the probe τ p \tau_p τ p , their total change from the neutral baseline is
δ p + 1 − δ p . \delta_{p+1}-\delta_p. δ p + 1 − δ p .
Consequently,
∣ ∂ ( P τ p ) ∣ = L + σ p ( J W + w p ) + δ p + 1 − δ p . |\partial(P_{\tau_p})|=L+\sigma_p(JW+w_p)+\delta_{p+1}-\delta_p. ∣ ∂ ( P τ p ) ∣ = L + σ p ( J W + w p ) + δ p + 1 − δ p .
By the definition of the calibration offsets,
δ p + 1 − δ p = − ε − σ p ( J W + ⌊ p 2 ⌋ B ) . \delta_{p+1}-\delta_p=-\varepsilon-\sigma_p\left(JW+\left\lfloor\frac{p}{2}\right\rfloor B\right). δ p + 1 − δ p = − ε − σ p ( J W + ⌊ 2 p ⌋ B ) .
Substituting this into the preceding expression yields
∣ ∂ ( P τ p ) ∣ = L + σ p ( J W + w p ) − ε − σ p ( J W + ⌊ p 2 ⌋ B ) = L − ε + σ p ( w p − ⌊ p 2 ⌋ B ) . \begin{aligned}
|\partial(P_{\tau_p})|=L+\sigma_p(JW+w_p)-\varepsilon-\sigma_p\left(JW+\left\lfloor\frac{p}{2}\right\rfloor B\right) \\
&=L-\varepsilon+\sigma_p\left(w_p-\left\lfloor\frac{p}{2}\right\rfloor B\right).
\end{aligned} ∣ ∂ ( P τ p ) ∣ = L + σ p ( J W + w p ) − ε − σ p ( J W + ⌊ 2 p ⌋ B ) = L − ε + σ p ( w p − ⌊ 2 p ⌋ B ) .
Since T = L − ε T=L-\varepsilon T = L − ε , we obtain
∣ ∂ ( P τ p ) ∣ − T = σ p ( w p − ⌊ p 2 ⌋ B ) . \boxed{|\partial(P_{\tau_p})|-T=\sigma_p\left(w_p-\left\lfloor\frac{p}{2}\right\rfloor B\right)}. ∣ ∂ ( P τ p ) ∣ − T = σ p ( w p − ⌊ 2 p ⌋ B ) .
Now let K K K be a feasible committee. By the common-threshold lemma,
∣ ∂ ( P τ p ) ∣ ≥ T |\partial(P_{\tau_p})|\ge T ∣ ∂ ( P τ p ) ∣ ≥ T
for every weight probe. Hence
σ p ( w p − ⌊ p 2 ⌋ B ) ≥ 0. \sigma_p\left(w_p-\left\lfloor\frac{p}{2}\right\rfloor B\right)\ge0. σ p ( w p − ⌊ 2 p ⌋ B ) ≥ 0.
For every 0 ≤ h < s 0\le h<s 0 ≤ h < s , the even phase p = 2 h p=2h p = 2 h therefore gives
w 2 h ≥ h B , w_{2h}\ge hB, w 2 h ≥ h B ,
whereas the following odd phase p = 2 h + 1 p=2h+1 p = 2 h + 1 gives
w 2 h + 1 ≤ h B . w_{2h+1}\le hB. w 2 h + 1 ≤ h B .
By monotonicity,
z 2 h , i ≤ z 2 h + 1 , i for every i , z_{2h,i}\le z_{2h+1,i}\qquad\text{for every }i, z 2 h , i ≤ z 2 h + 1 , i for every i ,
and since all source weights are positive,
w 2 h ≤ w 2 h + 1 . w_{2h}\le w_{2h+1}. w 2 h ≤ w 2 h + 1 .
Thus
h B ≤ w 2 h ≤ w 2 h + 1 ≤ h B , hB\le w_{2h}\le w_{2h+1}\le hB, h B ≤ w 2 h ≤ w 2 h + 1 ≤ h B ,
and consequently
w 2 h = w 2 h + 1 = h B for every 0 ≤ h < s . \boxed{w_{2h}=w_{2h+1}=hB}\qquad\text{for every }0\le h<s. w 2 h = w 2 h + 1 = h B for every 0 ≤ h < s .
For the final even phase p = 2 s p=2s p = 2 s , the weight probe gives
w 2 s ≥ s B . w_{2s}\ge sB. w 2 s ≥ s B .
On the other hand,
w 2 s ≤ ∑ i = 1 q a i = W = s B . w_{2s} \le\sum_{i=1}^{q} a_i = W = sB. w 2 s ≤ i = 1 ∑ q a i = W = s B .
Therefore
w 2 s = s B . w_{2s}=sB. w 2 s = s B .
The sets encoded by the even phases therefore have cumulative weights 0 , B , 2 B , … , s B 0, B, 2B, \ldots, sB 0 , B , 2 B , … , s B . By monotonicity, the differences between consecutive stages form disjoint bins, and each such difference has total weight exactly B B B . As noted in the reduction idea, the strict bounds
B 4 < a i < B 2 \frac{B}{4}<a_i<\frac{B}{2} 4 B < a i < 2 B
imply that every bin contains exactly three items. Hence these stage differences form a valid solution to the source Strict-Unary-3-Partition instance.
Completeness
Suppose now that the source instance admits a valid partition into bins D 0 , … , D s − 1 D_0,\ldots,D_{s-1} D 0 , … , D s − 1 , each of total weight B B B . For each item i i i , let bin ( i ) \operatorname{bin}(i) bin ( i ) denote the index of its bin. We select every fixed candidate and, in phase p p p , select
A p , i ⟺ bin ( i ) < ⌊ p 2 ⌋ , A_{p,i}\Longleftrightarrow\operatorname{bin}(i)<\left\lfloor\frac{p}{2}\right\rfloor, A p , i ⟺ bin ( i ) < ⌊ 2 p ⌋ ,
and select B p , i B_{p,i} B p , i otherwise.
This committee has exactly the required size. Its alternative choices are monotone across the phases, and the cumulative weight encoded by phase p p p is
w p = ⌊ p 2 ⌋ B . w_p=\left\lfloor\frac{p}{2}\right\rfloor B. w p = ⌊ 2 p ⌋ B .
Consequently, by the weight-probe identity proved above, every weight probe has boundary exactly T T T .
It remains to show that no other cut has expansion below the target. Prefix cuts. We first consider prefixes of the voter order. Temporarily return to the neutral construction: set all calibration offsets to zero and move each weighting candidate e p , i e_{p,i} e p , i back to its neutral starting position ξ i + 3 v \xi_i+3v ξ i + 3 v .
For a neutral phase p p p , let F p ( u ) F_p(u) F p ( u ) denote the total signed contribution of its first u u u rows. We have already shown that every complete neutral phase satisfies
F p ( Ω ) = L . F_p(\Omega)=L. F p ( Ω ) = L .
Changing the choice of a single item from B B B to A A A adds a nonnegative quantity to F p ( u ) F_p(u) F p ( u ) at every intermediate position u u u : the difference starts at zero, rises when the left endpoint of A A A is reached, and then decreases back to zero before the end of the item pattern. Since the committee constructed above makes monotone choices across phases, it follows that
F p − 1 ( u ) ≤ F p ( u ) for every 0 ≤ u ≤ Ω . F_{p-1}(u)\le F_p(u) \qquad\text{for every } 0\le u\le\Omega. F p − 1 ( u ) ≤ F p ( u ) for every 0 ≤ u ≤ Ω.
Consider a prefix whose endpoint lies u u u positions into phase p p p . The suffix of phase p − 1 p-1 p − 1 together with the prefix of phase p p p contains exactly Ω \Omega Ω rows, and its signed contribution is
F p − 1 ( Ω ) − F p − 1 ( u ) + F p ( u ) ≥ F p − 1 ( Ω ) = L . \begin{aligned}
F_{p-1}(\Omega)-F_{p-1}(u)+F_p(u)\ge F_{p-1}(\Omega) \\
&=L.
\end{aligned} F p − 1 ( Ω ) − F p − 1 ( u ) + F p ( u ) ≥ F p − 1 ( Ω ) = L .
The actual contribution of every row is at least its signed contribution, and rows outside this window contribute a nonnegative number of crossing edges. Hence every interior prefix of the neutral construction has boundary at least L L L .
The left and right ends require only the corresponding endpoint check. At the left end, define
[ u ] [ a , b ] : = max { 0 , min { u , b } − a } . [u]_{[a,b]}:=\max\{0,\min\{u,b\}-a\}. [ u ] [ a , b ] := max { 0 , min { u , b } − a } .
A direct row count shows that the head candidate together with the truncated scaffold of phase 0 changes the hypothetical complete-neutral profile by
Γ ( u ) = 2 H [ u ] 0 , H + H [ u ] H , H + 1 ≥ 0. \Gamma(u) = 2H[u]_{0,H} + H[u]_{H,H+1} \ge0. Γ ( u ) = 2 H [ u ] 0 , H + H [ u ] H , H + 1 ≥ 0.
Thus the missing scaffold candidates at the beginning do not decrease the neutral lower bound. At the other end, the final scaffold-only phase provides exactly the continuation of the row-reach profile required by the same argument up to η \eta η ; the tail begins only after this point. Therefore
∣ ∂ n e u t r a l ( P t ) ∣ ≥ L for every X 1 ≤ t ≤ η . \boxed{\lvert\partial_{\mathrm{neutral}}(P_t)\rvert\ge L \qquad\text{for every } X_1 \le t \le\eta.} ∣ ∂ neutral ( P t )∣ ≥ L for every X 1 ≤ t ≤ η .
We now restore the phase-specific modifications. The calibration offsets can affect a prefix only near a scaffold transition. Outside these neighborhoods, the two opposite calibration shifts cancel exactly. Inside such a neighborhood, but away from the weight probe, direct counting of the scaffold rows gives the stronger neutral bound
∣ ∂ n e u t r a l ( P t ) ∣ ≥ L + H . \lvert\partial_{\mathrm{neutral}}(P_t)\rvert\ge L + H. ∣ ∂ neutral ( P t )∣ ≥ L + H .
Since ∣ δ p ∣ ≤ D \lvert\delta_p\rvert\le D ∣ δ p ∣ ≤ D , restoring the calibration can decrease the boundary there by at most 2 D 2D 2 D . Finally, restore the source-weight displacement of the candidates e p , i e_{p,i} e p , i . Moving the start of e p , i e_{p,i} e p , i by a i a_i a i positions can change the boundary of any voter set by at most
a i ( J + 1 ) . a_i(J+1). a i ( J + 1 ) .
Since the total source weight is W W W , the change contributed by one phase is at most
Ξ = ( J + 1 ) W , \Xi= (J+1)W, Ξ = ( J + 1 ) W ,
and over all variable phases the total possible change is at most r Ξ r\Xi r Ξ .
We can therefore distinguish three kinds of active prefixes. Outside the calibration neighborhoods,
∣ ∂ ( P t ) ∣ ≥ L − r Ξ > L − ε = T . \lvert\partial(P_t)\rvert\ge L-r\Xi> L-\varepsilon= T. ∣ ∂ ( P t )∣ ≥ L − r Ξ > L − ε = T .
Inside a calibration neighborhood but away from its weight probe,
∣ ∂ ( P t ) ∣ ≥ L + H − 2 D − r Ξ ≥ T , \lvert\partial(P_t)\rvert\ge L+H-2D-r\Xi\ge T, ∣ ∂ ( P t )∣ ≥ L + H − 2 D − r Ξ ≥ T ,
by the parameter inequalities. At the weight probe itself we already know that
∣ ∂ ( P τ p ) ∣ = T . \lvert\partial(P_{\tau_p})\rvert= T. ∣ ∂ ( P τ p )∣ = T .
Hence
∣ ∂ ( P t ) ∣ ≥ T for every X 1 ≤ t ≤ η . \boxed{\lvert\partial(P_t)\rvert\ge T \qquad\text{for every } X_1 \le t \le\eta.} ∣ ∂ ( P t )∣ ≥ T for every X 1 ≤ t ≤ η .
Arbitrary cuts. The preceding argument only concerns prefixes, whereas the Cheeger constant minimizes over all voter sets. We now show that the same threshold holds for every cut of the constructed committee graph.
Put
a : = X 1 , b : = η , a := X_1,\qquad b := \eta, a := X 1 , b := η ,
and define
K L : = P a , W m i d : = P b ∖ P a , K R : = V ∖ P b . K_L := P_a,\qquad W_{\mathrm{mid}} := P_b \setminus P_a,\qquad K_R := V \setminus P_b. K L := P a , W mid := P b ∖ P a , K R := V ∖ P b .
The head and tail candidates make K L K_L K L and K R K_R K R cliques. The parameter choices give
b − a ≤ Q , b ≤ Q T , n ≤ 2 Q ( T + 1 ) , b-a \le Q,\qquad b \le QT,\qquad n \le2Q(T+1), b − a ≤ Q , b ≤ QT , n ≤ 2 Q ( T + 1 ) ,
and
T + 2 ≤ a , T + 2 ≤ n − b , n < 2 ( n − b ) . T+2 \le a,\qquad T+2 \le n-b,\qquad n < 2(n-b). T + 2 ≤ a , T + 2 ≤ n − b , n < 2 ( n − b ) .
In particular, both endpoint cliques have size at least T + 2 T+2 T + 2 , while K R K_R K R contains more than half of the voters.
The graph induced by the constructed committee is connected: the head, the scaffold candidates c 3 c_3 c 3 in successive phases, and the tail form a chain of overlapping selected intervals.
We first establish one consequence of the voter-interval structure. If i < j < k i<j<k i < j < k and voters i i i and k k k are adjacent, then the selected candidate that they jointly approve is approved by every voter between them. Hence
i < j < k , i ∼ k ⟹ i ∼ j and j ∼ k . i<j<k,\qquad i\sim k\quad\Longrightarrow\quad i\sim j\text{ and }j\sim k. i < j < k , i ∼ k ⟹ i ∼ j and j ∼ k .
Orient every graph edge from its smaller endpoint to its larger endpoint. For a voter set U U U , let
F + ( U ) : = ∣ { i j ∈ E : i < j , i ∈ U , j ∉ U } ∣ F^{+}(U):=\left|\{ij\in E:i<j,\ i\in U,\ j\notin U\}\right| F + ( U ) := ∣ { ij ∈ E : i < j , i ∈ U , j ∈ / U } ∣
be the number of crossing edges directed from U U U to its complement. Clearly
F + ( U ) ≤ ∣ ∂ ( U ) ∣ , F^{+}(U)\leq|\partial(U)|, F + ( U ) ≤ ∣ ∂ ( U ) ∣ ,
and equality holds whenever U U U is a prefix.
Lemma 21 (Separator lemma). If
K L ⊆ U ⊆ V ∖ K R , K_L\subseteq U\subseteq V\setminus K_R, K L ⊆ U ⊆ V ∖ K R , then
∣ ∂ ( U ) ∣ ≥ T . |\partial(U)|\geq T. ∣ ∂ ( U ) ∣ ≥ T . Proof. Minimize F + ( U ) F^{+}(U) F + ( U ) over all sets satisfying
K L ⊆ U ⊆ V ∖ K R , K_L\subseteq U\subseteq V\setminus K_R, K L ⊆ U ⊆ V ∖ K R , and, among all minimizers, choose one of maximum cardinality.
Suppose that its membership vector contains consecutive entries ( 0 , 1 ) (0,1) ( 0 , 1 ) at voters j , j + 1 j,j+1 j , j + 1 . Both voters lie in W m i d W_{\mathrm{mid}} W mid , so either one may change sides without violating the endpoint conditions.
Let
α = ∣ { i < j : i ∈ U , i ∼ j } ∣ , β = ∣ { i < j : i ∈ U , i ∼ j + 1 } ∣ , \alpha=\left|\{i<j:i\in U,\ i\sim j\}\right|,\qquad
\beta=\left|\{i<j:i\in U,\ i\sim j+1\}\right|, α = ∣ { i < j : i ∈ U , i ∼ j } ∣ , β = ∣ { i < j : i ∈ U , i ∼ j + 1 } ∣ , and let
γ = ∣ { i > j + 1 : i ∉ U , j ∼ i } ∣ , δ = ∣ { i > j + 1 : i ∉ U , j + 1 ∼ i } ∣ . \gamma=\left|\{i>j+1:i\notin U,\ j\sim i\}\right|,\qquad
\delta=\left|\{i>j+1:i\notin U,\ j+1\sim i\}\right|. γ = ∣ { i > j + 1 : i ∈ / U , j ∼ i } ∣ , δ = ∣ { i > j + 1 : i ∈ / U , j + 1 ∼ i } ∣ . By the interval property above, every earlier neighbor of j + 1 j+1 j + 1 is also a neighbor of j j j , while every later neighbor of j j j is also a neighbor of j + 1 j+1 j + 1 . Therefore
α ≥ β , δ ≥ γ . \alpha\geq\beta,\qquad\delta\geq\gamma. α ≥ β , δ ≥ γ . If we add j j j to U U U , then
F + ( U ∪ { j } ) − F + ( U ) = γ − α . F^{+}(U\cup\{j\})-F^{+}(U)=\gamma-\alpha. F + ( U ∪ { j }) − F + ( U ) = γ − α . If γ ≤ α \gamma\leq\alpha γ ≤ α , this operation does not increase F + F^{+} F + . It either decreases it, contradicting minimality, or preserves it while increasing ∣ U ∣ |U| ∣ U ∣ , contradicting the choice of the minimizer.
We may therefore assume γ > α \gamma>\alpha γ > α . Instead remove j + 1 j+1 j + 1 from U U U . Then
F + ( U ∖ { j + 1 } ) − F + ( U ) = β − δ ≤ α − γ < 0 , F^{+}(U\setminus\{j+1\})-F^{+}(U)=\beta-\delta\leq\alpha-\gamma<0, F + ( U ∖ { j + 1 }) − F + ( U ) = β − δ ≤ α − γ < 0 , again contradicting minimality.
Thus a minimizing set has no adjacent ( 0 , 1 ) (0,1) ( 0 , 1 ) transition. Since it contains the entire left endpoint clique and excludes the entire right endpoint clique, it must be a prefix P t P_t P t for some
a ≤ t ≤ b . a\leq t\leq b. a ≤ t ≤ b . The prefix bound proved above gives
F + ( P t ) = ∣ ∂ ( P t ) ∣ ≥ T . F^{+}(P_t)=|\partial(P_t)|\geq T. F + ( P t ) = ∣ ∂ ( P t ) ∣ ≥ T . Hence the minimum possible value of F + F^{+} F + under the endpoint conditions is at least T T T , and consequently every admissible U U U satisfies
∣ ∂ ( U ) ∣ ≥ F + ( U ) ≥ T . |\partial(U)|\geq F^{+}(U)\geq T. ∣ ∂ ( U ) ∣ ≥ F + ( U ) ≥ T .
We can now consider an arbitrary nonempty voter set U U U with
∣ U ∣ ≤ n 2 . |U| \le\frac{n}{2}. ∣ U ∣ ≤ 2 n .
If U U U splits either endpoint clique, let that clique have size d d d and let s ′ s' s ′ of its voters lie in U U U , where 1 ≤ s ′ < d 1 \le s' < d 1 ≤ s ′ < d . The edges internal to the clique already contribute
s ′ ( d − s ′ ) ≥ d − 1 ≥ T + 1 s'(d-s') \ge d-1 \ge T+1 s ′ ( d − s ′ ) ≥ d − 1 ≥ T + 1
crossing edges. Hence
∣ U ∣ ≤ n 2 ≤ Q ( T + 1 ) ≤ Q ∣ ∂ ( U ) ∣ . |U| \le\frac{n}{2} \le Q(T+1) \le Q|\partial(U)|. ∣ U ∣ ≤ 2 n ≤ Q ( T + 1 ) ≤ Q ∣ ∂ ( U ) ∣.
Suppose next that neither endpoint clique is split and
U ∩ K L = ∅ . U \cap K_L = \varnothing. U ∩ K L = ∅ .
The set U U U cannot contain K R K_R K R , since ∣ K R ∣ > n / 2 |K_R| > n/2 ∣ K R ∣ > n /2 . Therefore
U ⊆ W m i d , U \subseteq W_{\mathrm{mid}}, U ⊆ W mid ,
and hence
∣ U ∣ ≤ ∣ W m i d ∣ = b − a ≤ Q . |U| \le|W_{\mathrm{mid}}| = b-a \le Q. ∣ U ∣ ≤ ∣ W mid ∣ = b − a ≤ Q .
Since the graph is connected and U U U is a nonempty proper subset,
∣ ∂ ( U ) ∣ ≥ 1 , |\partial(U)| \ge1, ∣ ∂ ( U ) ∣ ≥ 1 ,
so again
∣ U ∣ ≤ Q ∣ ∂ ( U ) ∣ . |U| \le Q|\partial(U)|. ∣ U ∣ ≤ Q ∣ ∂ ( U ) ∣.
The only remaining possibility is that neither endpoint clique is split and
K L ⊆ U . K_L \subseteq U. K L ⊆ U .
Again U U U cannot contain K R K_R K R , so the separator lemma applies and gives
∣ ∂ ( U ) ∣ ≥ T . |\partial(U)| \ge T. ∣ ∂ ( U ) ∣ ≥ T .
Moreover,
∣ U ∣ ≤ b ≤ Q T . |U| \le b \le QT. ∣ U ∣ ≤ b ≤ QT .
Thus
∣ U ∣ ≤ Q ∣ ∂ ( U ) ∣ . |U| \le Q|\partial(U)|. ∣ U ∣ ≤ Q ∣ ∂ ( U ) ∣.
These cases exhaust all nonempty sets with ∣ U ∣ ≤ n / 2 |U| \le n/2 ∣ U ∣ ≤ n /2 . Therefore
∣ ∂ ( U ) ∣ ∣ U ∣ ≥ 1 Q = ρ \frac{|\partial(U)|}{|U|} \ge\frac{1}{Q} = \rho ∣ U ∣ ∣ ∂ ( U ) ∣ ≥ Q 1 = ρ
for every such U U U , and hence
h ( G K ) ≥ ρ . h(G_K) \ge\rho. h ( G K ) ≥ ρ .
This proves completeness.
D.7.2. Polynomiality. It remains to verify that the construction has polynomial size. Let ℓ \ell ℓ denote the unary encoding length of the source instance. With the source notation used above,
ℓ = ( s + 1 ) B + 3 s + 1 , \ell= (s+1)B+3s+1, ℓ = ( s + 1 ) B + 3 s + 1 ,
so in particular
s , B , W ≤ ℓ . s,\ B,\ W \le\ell. s , B , W ≤ ℓ .
Substituting these bounds successively into the parameter definitions shows that the number of voters satisfies
n = O ( ℓ 19 ) , n = O(\ell^{19}), n = O ( ℓ 19 ) ,
while the number of candidates is
Thus even an explicit voter–candidate approval matrix contains only
entries.
All construction parameters and interval endpoints are obtained from the source instance by a fixed number of additions and multiplications of polynomially bounded integers. The reduction can therefore generate the voters and candidates and determine every approval by testing membership in the corresponding voter interval, all in time polynomial in ℓ \ell ℓ .
Type-graph structure and exact evaluation
For completeness, we give the structural proof underlying Theorem 13 and the exact type-graph search used in Corollary 14.
Fix a committee graph G = ( V , E ) G=(V,E) G = ( V , E ) . When the committee is fixed, write τ ( v ) \tau(v) τ ( v ) for a voter’s committee-relative type, τ ( V ) \tau(V) τ ( V ) for the occurring types, V α V_\alpha V α for the corresponding voter class, and n α n_\alpha n α for its size.
Lemma 22 (Completion of a partially selected type). Let
c : = ⌊ ∣ V ∣ 2 ⌋ , c := \left\lfloor\frac{|V|}{2} \right\rfloor, c := ⌊ 2 ∣ V ∣ ⌋ , and let S ⊆ V S\subseteq V S ⊆ V be a Cheeger-optimal smaller side with 1 ≤ ∣ S ∣ < c 1\leq|S|<c 1 ≤ ∣ S ∣ < c . Suppose that S S S splits a type α \alpha α . Then, for every
U ⊆ V α ∖ S with ∣ U ∣ ≤ c − ∣ S ∣ , U\subseteq V_\alpha\setminus S \qquad\text{with}\qquad|U|\leq c-|S|, U ⊆ V α ∖ S with ∣ U ∣ ≤ c − ∣ S ∣ , the set S ∪ U S\cup U S ∪ U is also Cheeger-optimal. Consequently S S S can be extended, without losing optimality, until either the whole type is selected or the cut has cardinality $c.
Proof. Write h : = h ( G ) h:=h(G) h := h ( G ) and choose v ∈ S ∩ V α v\in S\cap V_\alpha v ∈ S ∩ V α . Put R : = S ∖ { v } R:=S\setminus\{v\} R := S ∖ { v } . Since S S S is optimal,
∣ ∂ G ( S ) ∣ = h ∣ S ∣ , |\partial_G(S)|=h|S|, ∣ ∂ G ( S ) ∣ = h ∣ S ∣ ,
whereas
∣ ∂ G ( R ) ∣ ≥ h ∣ R ∣ . |\partial_G(R)|\geq h|R|. ∣ ∂ G ( R ) ∣ ≥ h ∣ R ∣.
For R ≠ ∅ R\ne\varnothing R = ∅ this is the definition of h h h , because ∣ R ∣ < c |R|<c ∣ R ∣ < c ; for R = ∅ R=\varnothing R = ∅ it is 0 ≥ 0 0\geq0 0 ≥ 0 . Hence
∣ ∂ G ( S ) ∣ − ∣ ∂ G ( R ) ∣ ≤ h (5) |\partial_G(S)|-|\partial_G(R)|\leq h \tag*{(5)} ∣ ∂ G ( S ) ∣ − ∣ ∂ G ( R ) ∣ ≤ h (5)
All voters in V α V_\alpha V α have the same neighbors outside the type class. If α ≠ ∅ \alpha\ne\varnothing α = ∅ , the type class is a clique, so after one voter of this type is added there is one fewer same-type vertex outside the cut and one more inside; the next boundary marginal is therefore smaller by 2 2 2 . If α = ∅ \alpha=\varnothing α = ∅ , there are no same-type edges and the marginal is unchanged. Thus successive additions of voters of type α \alpha α have nonincreasing boundary marginals.
Every voter added from V α ∖ S V_\alpha\setminus S V α ∖ S therefore has boundary marginal at most the quantity in (5) , and hence at most h h h . For every admissible U U U ,
∣ ∂ G ( S ∪ U ) ∣ ≤ h ∣ S ∣ + h ∣ U ∣ = h ∣ S ∪ U ∣ . |\partial_G(S\cup U)|\leq h|S|+h|U|=h|S\cup U|. ∣ ∂ G ( S ∪ U ) ∣ ≤ h ∣ S ∣ + h ∣ U ∣ = h ∣ S ∪ U ∣.
Because 1 ≤ ∣ S ∪ U ∣ ≤ c 1\leq|S\cup U|\leq c 1 ≤ ∣ S ∪ U ∣ ≤ c , the definition of h h h gives the reverse inequality. Equality follows, so S ∪ U S\cup U S ∪ U is Cheeger-optimal. □
Proof of Theorem 13. Start from any Cheeger-optimal smaller side S S S , with 1 ≤ ∣ S ∣ ≤ c 1\leq|S|\leq c 1 ≤ ∣ S ∣ ≤ c . While ∣ S ∣ < c |S|<c ∣ S ∣ < c and S S S splits a type α \alpha α , apply Lemma 22 to add voters of type α \alpha α until either V α ⊆ S V_\alpha\subseteq S V α ⊆ S or ∣ S ∣ = c |S|=c ∣ S ∣ = c . Every such extension preserves optimality. If a type is completed below the cap, the number of split types decreases. Thus if the process terminates below the cap, the resulting optimum is type-respecting.
Now suppose ∣ S ∣ = c |S|=c ∣ S ∣ = c and S S S splits two distinct types. Choose
u , v ∈ S , u ′ ∈ V τ ( u ) ∖ S , v ′ ∈ V τ ( v ) ∖ S , u,v\in S,\qquad u'\in V_{\tau(u)}\setminus S,\qquad v'\in V_{\tau(v)}\setminus S, u , v ∈ S , u ′ ∈ V τ ( u ) ∖ S , v ′ ∈ V τ ( v ) ∖ S ,
with τ ( u ) ≠ τ ( v ) \tau(u)\ne\tau(v) τ ( u ) = τ ( v ) , and consider
S u = S ∖ { u } ∪ { v ′ } , S v = S ∖ { v } ∪ { u ′ } . S_u=S\setminus\{u\}\cup\{v'\},\qquad S_v=S\setminus\{v\}\cup\{u'\}. S u = S ∖ { u } ∪ { v ′ } , S v = S ∖ { v } ∪ { u ′ } .
Set
Δ u : = ∣ ∂ G ( S u ) ∣ − ∣ ∂ G ( S ) ∣ , Δ v : = ∣ ∂ G ( S v ) ∣ − ∣ ∂ G ( S ) ∣ . \Delta_u:=|\partial_G(S_u)|-|\partial_G(S)|,\qquad
\Delta_v:=|\partial_G(S_v)|-|\partial_G(S)|. Δ u := ∣ ∂ G ( S u ) ∣ − ∣ ∂ G ( S ) ∣ , Δ v := ∣ ∂ G ( S v ) ∣ − ∣ ∂ G ( S ) ∣.
Optimality and size preservation give Δ u , Δ v ≥ 0 \Delta_u,\Delta_v \ge0 Δ u , Δ v ≥ 0 . Voters of the same type have identical neighborhoods outside their own type class. Adding the two swap differences therefore cancels all contributions from vertices outside the two involved classes, leaving
Δ u + Δ v = 41 [ τ ( u ) ∩ τ ( v ) ≠ ∅ ] − 21 [ τ ( u ) ≠ ∅ ] − 21 [ τ ( v ) ≠ ∅ ] ≤ 0. (6) \Delta_u+\Delta_v=4\mathbf{1}[\tau(u)\cap\tau(v)\ne\varnothing]-2\mathbf{1}[\tau(u)\ne\varnothing]-2\mathbf{1}[\tau(v)\ne\varnothing]\le0. \tag*{(6)} Δ u + Δ v = 4 1 [ τ ( u ) ∩ τ ( v ) = ∅ ] − 2 1 [ τ ( u ) = ∅ ] − 2 1 [ τ ( v ) = ∅ ] ≤ 0. (6)
If the two types intersect, both are nonempty and the displayed quantity is zero; if they are disjoint, the first term vanishes. Since the two types are distinct, they cannot both be empty. Together with Δ u , Δ v ≥ 0 \Delta_u,\Delta_v\ge0 Δ u , Δ v ≥ 0 , this forces both swap costs to be zero. Repeat the zero-cost transfer, removing one selected voter of the first type and adding one unselected voter of the second type. At every intermediate cut both types are still split until one reaches an endpoint; the same two-swap calculation applies because the cut remains cap-size and optimal. After finitely many steps one of the two types is no longer split and no other type membership has changed. Repeating whenever two split types remain terminates with an optimal cap-size side that splits at most one type. This proves the theorem. □
Exact evaluation from the type graph. Let
T : = τ ( V ) , n α : = n α , c : = ⌊ ∣ V ∣ 2 ⌋ . T:=\tau(V),\qquad n_\alpha:=n_\alpha,\qquad c:=\left\lfloor\frac{|V|}{2}\right\rfloor. T := τ ( V ) , n α := n α , c := ⌊ 2 ∣ V ∣ ⌋ .
For X ⊆ T \mathcal{X}\subseteq T X ⊆ T , put
s X : = ∑ β ∈ X n β s_{\mathcal{X}}:=\sum_{\beta\in\mathcal{X}}n_\beta s X := β ∈ X ∑ n β
and
B X : = ∑ β ∈ X , γ ∈ T ∖ X { β , γ } ∈ E τ ( G ) n β n γ . B_{\mathcal{X}}:=\sum_{\substack{\beta\in\mathcal{X},\ \gamma\in T\setminus\mathcal{X}\\
\{\beta,\gamma\}\in E_\tau(G)}}n_\beta n_\gamma. B X := β ∈ X , γ ∈ T ∖ X { β , γ } ∈ E τ ( G ) ∑ n β n γ .
This is exactly the boundary of the type-respecting side represented by X \mathcal{X} X . For the cap-size case, fix a prospective split type α ∈ T \alpha\in T α ∈ T and a set X ⊆ T ∖ { α } \mathcal{X}\subseteq T\setminus\{\alpha\} X ⊆ T ∖ { α } of types lying wholly on the selected side. Set
x : = c − s X . x:=c-s_{\mathcal{X}}. x := c − s X .
Whenever 1 ≤ x ≤ n α − 1 1\le x\le n_\alpha-1 1 ≤ x ≤ n α − 1 , any choice of x x x voters from V α V_\alpha V α yields the same boundary:
B α , X ( x ) = ∑ β ∈ X , γ ∈ T ∖ ( X ∪ { α } ) { β , γ } ∈ E τ ( G ) n β n γ + ∑ β ∈ X { α , β } ∈ E τ ( G ) ( n α − x ) n β + ∑ γ ∈ T ∖ ( X ∪ { α } ) { α , γ } ∈ E τ ( G ) x n γ + 1 α ≠ ∅ x ( n α − x ) . (7) \begin{aligned}
B_{\alpha,\mathcal{X}}(x)
={}&\sum_{\substack{\beta\in\mathcal{X},\ \gamma\in T\setminus(\mathcal{X}\cup\{\alpha\})\\
\{\beta,\gamma\}\in E_\tau(G)}}n_\beta n_\gamma\\
&+\sum_{\substack{\beta\in\mathcal{X}\\\{\alpha,\beta\}\in E_\tau(G)}}(n_\alpha-x)n_\beta
+\sum_{\substack{\gamma\in T\setminus(\mathcal{X}\cup\{\alpha\})\\\{\alpha,\gamma\}\in E_\tau(G)}}xn_\gamma\\
&+\mathbf{1}_{\alpha\ne\varnothing}x(n_\alpha-x). \tag*{(7)}
\end{aligned} B α , X ( x ) = β ∈ X , γ ∈ T ∖ ( X ∪ { α }) { β , γ } ∈ E τ ( G ) ∑ n β n γ + β ∈ X { α , β } ∈ E τ ( G ) ∑ ( n α − x ) n β + γ ∈ T ∖ ( X ∪ { α }) { α , γ } ∈ E τ ( G ) ∑ x n γ + 1 α = ∅ x ( n α − x ) . (7)
The last term counts edges crossing inside a split nonempty type, which is a clique. Consequently
h ( G ) = min { min X ⊆ T 1 ≤ s X ≤ c B X s X , min α ∈ T , X ⊆ T ∖ { α } x = c − s X , 1 ≤ x ≤ n α − 1 B α , X ( x ) c } . (8) h(G)=\min\left\{
\min_{\substack{\mathcal{X}\subseteq T\\1\le s_{\mathcal{X}}\le c}}\frac{B_{\mathcal{X}}}{s_{\mathcal{X}}},
\min_{\substack{\alpha\in T,\ \mathcal{X}\subseteq T\setminus\{\alpha\}\\x=c-s_{\mathcal{X}},\ 1\le x\le n_\alpha-1}}\frac{B_{\alpha,\mathcal{X}}(x)}{c}
\right\}. \tag*{(8)} h ( G ) = min ⎩ ⎨ ⎧ X ⊆ T 1 ≤ s X ≤ c min s X B X , α ∈ T , X ⊆ T ∖ { α } x = c − s X , 1 ≤ x ≤ n α − 1 min c B α , X ( x ) ⎭ ⎬ ⎫ . (8)
Every expression on the right is the expansion of an actual smaller side, while Theorem 13 guarantees that one of these candidates is optimal. The first minimum has at most 2 ∣ T ∣ 2^{|T|} 2 ∣ T ∣ candidates and the second at most ∣ T ∣ 2 ∣ T ∣ − 1 |T|2^{|T|-1} ∣ T ∣ 2 ∣ T ∣ − 1 candidates, proving Corollary 14.
Technion- Israel Institute of Technology Email address: gili.bielous@campus.technion.ac.il
Technion- Israel Institute of Technology Email address: reshefm@technion.ac.il