betaFeedback

WorksComputer Science

Interlacing Committees with Edge-Expansion

Abstract

Approval-based committee selection has recently been studied through the lens of interlacing, a framework for studying polarization in approval elections, in which committees induce a similarity graph over voters. The quality of committees is then evaluated through the connectivity of the resulting graph. We revisit the connectivity measures used in this framework and propose edge-expansion, a classical graph-theoretic measure with well-established connections to polarization in networks, as the optimization objective. We provide a theoretical foundation for this proposal by relating interlacing to classical models of information diffusion and by comparing edge-expansion with previously proposed connectivity objectives, identifying qualitative differences in the structural properties they capture. Finally, we study the computational complexity of optimizing edge-expansion, showing that hardness persists even for voter-interval preferences, while the problem is polynomial-time solvable for every fixed committee size, with an improved dependence on the committee size for voter-candidate-interval preferences.

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 kk, and quasi-polynomial complexity for polylogarithmic kk 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 NN of n∈Nn \in\mathbb{N} voters wish to select a committee of k∈Nk \in\mathbb{N} members from a set MM of m∈Nm \in\mathbb{N} candidates. Voter i∈Ni \in N approves a subset of candidates Ai⊆MA_i \subseteq M. The support of candidate c∈Mc \in M is the set of voters approving cc given by Vc={i∈N∣c∈Ai}V_c = \{i \in N \mid c \in A_i\}. The profile of voters A=(Ai)i∈NA = (A_i)_{i \in 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), 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), the set of possible results, i.e., kk-sized subsets of MM, is denoted by C={C⊆M∣∣C∣=k}\mathcal{C} = \{C \subseteq M \mid|C| = k\}. The result of an election is determined by a voting rule, a function that maps elections to a committee C∈CC \in\mathcal{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), we define the preferences graph of EE to be the unweighted undirected graph GE=(N,EE)G^E = (N, E^E), where

EE={{i,j}∈(N2)∣Ai∩Aj≠∅}.E^E = \left\{\{i,j\} \in\binom{N}{2} \mid A_i \cap A_j \ne\varnothing\right\}.

Example 1 (Running example). Consider an election with voters N={v1,v2,v3,v4}N = \{v_1, v_2, v_3, v_4\}, candidates M={a,b,c,d}M = \{a, b, c, d\}, committee size k=3k = 3, and approval ballots Av1={a,b,c}A_{v_1} = \{a, b, c\}, Av2={a,d}A_{v_2} = \{a, d\}, Av3={b,d}A_{v_3} = \{b, d\}, Av4={c}A_{v_4} = \{c\}. For example, Av1∩Av2={a}A_{v_1} \cap A_{v_2} = \{a\}, so {v1,v2}\{v_1, v_2\} is an edge of the preferences graph. In contrast, Av2∩Av4=∅A_{v_2} \cap A_{v_4} = \varnothing, so {v2,v4}\{v_2, v_4\} is not an edge. Thus, EE={{v1,v2},{v1,v3},{v1,v4},{v2,v3}}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 1a.

The running example, showing the full preferences graph and committee-induced graphs

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∈CC \in\mathcal{C}, we denote by GCE=(N,ECE)G^E_C = (N, E^E_C) the spanning subgraph of GEG^E in which two voters are adjacent iff they jointly approve a candidate in CC.

ECE={{i,j}∈EE∣Ai∩Aj∩C≠∅}.E^E_C = \left\{\{i,j\} \in E^E \mid A_i \cap A_j \cap C \ne\varnothing\right\}.

The election parameter is omitted from graph notation when clear from context.

Running example (continued). Consider the committee C0={a,b,d}C_0 = \{a,b,d\}. The edges {v1,v2}\{v_1,v_2\}, {v1,v3}\{v_1,v_3\}, and {v2,v3}\{v_2,v_3\} remain in the committee graph, witnessed respectively by aa, bb, and dd. However, although {v1,v4}∈EE\{v_1,v_4\} \in E^{\mathcal{E}}, its only witnessing candidate is c∉C0c \notin C_0. Hence this edge does not belong to EC0EE^{\mathcal{E}}_{C_0}. Consequently, GC0EG^{\mathcal{E}}_{C_0} consists of a triangle on v1,v2,v3v_1,v_2,v_3 and the isolated voter v4v_4, as shown in fig:1b.

Connectivity Objectives. Following Dong et al., PAIRS and CONS are numerical scores of committees. For C∈CC \in\mathcal{C}, define

PAIRS⁡(C,E):=∣ECE∣,\operatorname{PAIRS}(C,\mathcal{E}) := \lvert E^{\mathcal{E}}_C\rvert,
CONS⁡(C,E):=∣{{u,v}∈(N2)∣u∼Cv}∣.\operatorname{CONS}(C,\mathcal{E}) := \left\lvert\left\{\{u,v\} \in\binom{N}{2} \mid u \sim_C v\right\}\right\rvert.

where u∼Cvu \sim_C v means that uu and vv are connected by a path in GCEG^{\mathcal{E}}_C. We overload the objective names for the associated voting rules: PAIRS(E\mathcal{E}) and CONS(E\mathcal{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}), we say that ff distinguishes between C,C′C,C' if their scores differ, and does not distinguish between them otherwise.

Definition 2 (Connecting Committees). A committee CC is connecting if GCEG^{\mathcal{E}}_C is connected, and non-connecting otherwise.

Running example (continued). Besides C0C_0, consider C1={a,c,d}C_1 = \{a,c,d\}. Its committee graph is the path v3−v2−v1−v4v_3 - v_2 - v_1 - v_4; see fig:1c.

Each of C0,C1C_0,C_1 induce three edges, and hence PAIRS⁡(C0,E)=PAIRS⁡(C1,E)=3\operatorname{PAIRS}(C_0,\mathcal{E}) = \operatorname{PAIRS}(C_1,\mathcal{E}) = 3. Thus, PAIRS does not distinguish between them and may in particular select the non-connecting committee C0C_0.

References

  1. [1]Lada A. Adamic and Natalie Glance. 2005. The political blogosphere and the 2004 US election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery. 36–43.
  2. [2]Yann Algan, Nicolo Dalvit, Quoc-Anh Do, Alexis Le Chapelain, and Yves Zenou. 2026. Friendship Networks and Political Opinions. American Economic Review 116, 6 (June 2026), 2202–41. doi:10.1257/aer.20231344DOI
  3. [3]Noga Alon. 1997. On the edge-expansion of graphs. Combinatorics, Probability and Computing 6, 2 (1997), 145–152.DOI
  4. [4]Noga Alon and Vitali D Milman. 1985. λ1, isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory, Series B 38, 1 (1985), 73–88.DOI
  5. [5]Salvatore Barbaro. 2025. Election methods and political polarization. Mathematical Social Sciences 135 (2025), 102417.DOI
  6. [6]Roger L Berger. 1981. A necessary and sufficient condition for reaching a consensus using DeGroot’s method. J. Amer. Statist. Assoc. 76, 374 (1981), 415–418.
  7. [7]Robert Bond and Solomon Messing. 2015. Quantifying Social Media’s Political Space: Estimating Ideology from Publicly Revealed Preferences on Facebook. American Political Science Review 109, 1 (2015), 62–78. doi:10.1017/S0003055414000525DOI
  8. [8]Felix Brandt and Felix Fischer. 2007. PageRank as a weak tournament solution. In International Workshop on Web and Internet Economics. Springer, 300–305.DOI
  9. [9]Markus Brill, Jonas Israel, Evi Micha, and Jannik Peters. 2025. Individual representation in approval-based committee voting: M. Brill et al. Social Choice and Welfare 64, 1 (2025), 69–96.
  10. [10]Thomas Bühler and Matthias Hein. 2009. Spectral clustering based on the graph p-Laplacian. In Proceedings of the 26th annual international conference on machine learning. 81–88.
  11. [11]Burak Can, Ali Ihsan Ozkes, and Ton Storcken. 2015. Measuring polarization in preferences. Mathematical Social Sciences 78 (2015), 76–79.DOI
  12. [12]Jeff Cheeger. 1970. A lower bound for the smallest eigenvalue of the Laplacian, Problems in analysis (Papers dedicated to Salomon Bochner, 1969).
  13. [13]Morris H DeGroot. 1974. Reaching a consensus. Journal of the American Statistical association 69, 345 (1974), 118–121.DOI
  14. [14]Théo Delamazure, Łukasz Janeczko, Andrzej Kaczmarczyk, and Stanisław Szufa. 2024. Selecting the Most Conflicting Pair of Candidates. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI-24, Kate Larson (Ed.). International Joint Conferences on Artificial Intelligence Organization, 2766–2773. doi:10.24963/ijcai.2024/306 Main Track.
  15. [15]Peter M DeMarzo, Dimitri Vayanos, and Jeffrey Zwiebel. 2003. Persuasion bias, social influence, and unidimensional opinions. The Quarterly journal of economics 118, 3 (2003), 909–968.DOI
  16. [16]Chris Dong, Martin Bullinger, Tomasz Wąs, Larry Birnbaum, and Edith Elkind. 2025. Selecting Interlacing Committees. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, Detroit MI USA, 630–638.arxiv.org/abs/2509.02519
  17. [17]Edith Elkind and Martin Lackner. 2015. Structure in dichotomous preferences. In Proceedings of the 24th International Conference on Artificial Intelligence (Buenos Aires, Argentina) (IJCAI’15). AAAI Press, 2019–2025.arxiv.org/abs/1505.00341
  18. [18]Piotr Faliszewski, Andrzej Kaczmarczyk, Krzysztof Sornat, Stanisław Szufa, and Tomasz Wąs. 2023. Diversity, Agreement, and Polarization in Elections. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23, Edith Elkind (Ed.). International Joint Conferences on Artificial Intelligence Organization, 2684–2692. doi:10.24963/ijcai.2023/299 Main Track.DOI
  19. [19]Morris P Fiorina. 2017. Unstable majorities: Polarization, party sorting, and political stalemate. Hoover Institution Press.
  20. [20]Morris P. Fiorina, Samuel J. Abrams, and Jeremy Pope. 2004. Culture War? The Myth of a Polarized America. Longman.
  21. [21]James Flamino, Alessandro Galeazzi, Stuart Feldman, Michael W Macy, Brendan Cross, Zhenkun Zhou, Matteo Serafino, Alexandre Bovet, Hernán A Makse, and Boleslaw K Szymanski. 2023. Political polarization of news media and influencers on Twitter in the 2016 and 2020 US presidential elections. Nature Human Behaviour 7, 6 (2023), 904–916.DOI
  22. [22]Michael R Garey and David S Johnson. 2002. Computers and intractability. Vol. 29. wh freeman New York.
  23. [23]Michael R Garey, David S Johnson, and Larry Stockmeyer. 1974. Some simplified NP-complete problems. In Proceedings of the sixth annual ACM symposium on Theory of computing. 47–63.DOI
  24. [24]Kiran Garimella, Gianmarco De Francisci Morales, Aristides Gionis, and Michael Mathioudakis. 2018. Quantifying Controversy on Social Media. Trans. Soc. Comput. 1, 1, Article 3 (Jan. 2018), 27 pages. doi:10.1145/3140565DOI
  25. [25]William V Gehrlein. 2005. Probabilities of election outcomes with two parameters: the relative impact of unifying and polarizing candidates. Review of Economic Design 9, 4 (2005), 317–336.DOI
  26. [26]Michelle Girvan and Mark EJ Newman. 2002. Community structure in social and biological networks. Proceedings of the national academy of sciences 99, 12 (2002), 7821–7826.pubmed.ncbi.nlm.nih.gov/12060727
  27. [27]Michał T Godziszewski, Paweł Batko, Piotr Skowron, and Piotr Faliszewski. 2021. An analysis of approval-based committee rules for 2D-Euclidean elections. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 5448–5455.DOI
  28. [28]Pedro Guerra, Wagner Meira Jr, Claire Cardie, and Robert Kleinberg. 2013. A measure of polarization on social media networks based on community boundaries. In Proceedings of the international AAAI conference on web and social media, Vol. 7. 215–224.
  29. [29]Ruben Interian, Ruslan G. Marzo, Isela Mendoza, and Celso C. Ribeiro. 2023. Network polarization, filter bubbles, and echo chambers: an annotated review of measures and reduction methods. International Transactions in Operational Research 30, 6 (2023), 3122–3158. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/itor.13224 doi:10.1111/itor.13224DOI
  30. [30]Matthew O. Jackson. 2008. Learning and Networks. In Social and Economic Networks. Princeton University Press, Princeton, N.J., Chapter 8.
  31. [31]Peng Jia, Anahita MirTabatabaei, Noah E Friedkin, and Francesco Bullo. 2015. Opinion dynamics and the evolution of social power in influence networks. SIAM review 57, 3 (2015), 367–397.DOI
  32. [32]Martin Lackner and Piotr Skowron. 2023. Multi-winner voting with approval preferences. Springer Nature.
  33. [33]Tom Leighton and Satish Rao. 1999. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM (JACM) 46, 6 (1999), 787–832.DOI
  34. [34]Jure Leskovec, Kevin J Lang, and Michael Mahoney. 2010. Empirical comparison of algorithms for network community detection. In Proceedings of the 19th international conference on World wide web. 631–640.arxiv.org/abs/1004.3539
  35. [35]D.A. Levin and Y. Peres. 2026. Markov Chains and Mixing Times: Second Edition. American Mathematical Society.
  36. [36]Nolan McCarty, Keith T Poole, and Howard Rosenthal. 2005. Polarized America: The dance of ideology and unequal riches. (2005).
  37. [37]Isaac D Mehlhaff. 2024. A group-based approach to measuring polarization. American Political Science Review 118, 3 (2024), 1518–1526.
  38. [38]Bojan Mohar. 1989. Isoperimetric numbers of graphs. Journal of combinatorial theory, Series B 47, 3 (1989), 274–291.DOI
  39. [39]Mark EJ Newman. 2006. Modularity and community structure in networks. Proceedings of the national academy of sciences 103, 23 (2006), 8577–8582.pubmed.ncbi.nlm.nih.gov/16723398
  40. [40]Reza Olfati-Saber and Richard M Murray. 2004. Consensus problems in networks with switching topology and time-delays. IEEE Transactions on automatic control 49, 9 (2004), 1520–1533.
  41. [41]Jianbo Shi and Jitendra Malik. 2000. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence 22, 8 (2000), 888–905.
  42. [42]James Singer. 1938. A theorem in finite projective geometry and some applications to number theory. Trans. Amer. Math. Soc. 43, 3 (1938), 377–385.DOI
  43. [43]Lin Xiao and Stephen Boyd. 2004. Fast linear iterations for distributed averaging. Systems & Control Letters 53, 1 (2004), 65–78.
  44. [44]Yuan Zhang, Laia Castro, Frank Esser, and Alexandre Bovet. 2026. Measuring Structural Political Fragmentation. arXiv:2601.05093 [cs.SI] https://arxiv.org/abs/2601.05093

Paper details

vlnc:W_ec2xcjeu
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents