Interlacing Committees with Edge-Expansion

Gili Bielous, Reshef MeirarXiv 2026 · arXiv

TL;DR

This paper introduces edge-expansion (the Cheeger constant) as a superior metric for selecting representative committees that minimize political polarization. By focusing on the structural robustness of voter networks rather than simple connectivity, the authors provide a framework that better facilitates information diffusion and consensus-building in divided societies.

What Problem Does This Paper Address?

In modern democracies, elected bodies often reflect or even amplify the polarization of the electorate. Recent research into "interlacing" suggests that we can evaluate a committee by the voter network it induces: two voters are "connected" if they both approve at least one candidate selected for the committee.

Previous objectives for this task, such as PAIRS (counting total edges) and CONS (counting connected pairs of voters), have significant blind spots. PAIRS favors dense local clusters at the expense of global connectivity, while CONS cannot distinguish between a robustly integrated society and two hostile groups joined by a single "fragile bridge." The authors seek a metric that captures the robustness of social connections—how hard it is to split the electorate into two isolated camps.

Methods

The authors propose the CHGR objective, which optimizes the Cheeger constant (or edge-expansion) of the committee-induced voter graph.

  1. Graph Theory: They define the Cheeger constant as the minimum ratio of edges crossing a "cut" (a split in the population) to the size of the smaller side of that cut. A high Cheeger constant means there are no significant bottlenecks in communication.
  2. Opinion Dynamics: They link this metric to the DeGroot model of information diffusion. In this model, voters update their opinions based on their neighbors in the network. The authors prove that a committee with a higher CHGR score leads to a faster time-to-consensus among the electorate.
  3. Complexity Analysis: They investigate the computational cost of finding optimal committees, proving NP-hardness even in restricted "spatial" preference domains where voters and candidates are arranged on a 1D political spectrum.
  4. Algorithms: They develop an XP algorithm that is polynomial-time solvable for a fixed committee size ($k$), utilizing the concept of "voter types" to reduce the search space.

Datasets

As a theoretical paper in computational social choice, it does not use empirical datasets. Instead, it employs:

  • Synthetic Preference Profiles: Specifically designed to demonstrate the "pathologies" of previous metrics (e.g., the "PAIRS pathology" where an optimal committee leaves most voters isolated).
  • Spatial Domains: Mathematical models like Voter-Interval (VI) and Candidate-Interval (CI) profiles, which simulate one-dimensional political spectrums.

Key Insights and Ideas

  • The "Fragile Bridge" Problem: A major "aha" moment is the demonstration that previous metrics can't see bottlenecks. As shown in Figure 3, two graphs can have the identical maximum connectivity score (CONS), but one is a robust single community while the other is two polarized groups connected by a single vulnerable link.
Comparison of a "fragile bridge" vs. a cohesive collective. Both have the same CONS score, but the bridge has a much lower Cheeger value.
  • Connectivity vs. Robustness: The paper proves that optimizing for direct overlap (PAIRS) can lead to a "fragmented population," where the winning committee fails to connect the vast majority of the electorate, even when a fully connecting committee is available.
  • Consensus Proxy: By relating CHGR to Markov-chain mixing times, the authors turn a purely structural graph property into a quantitative proxy for how quickly a society can overcome disagreement.

Key Results

  • Structural Refinement: The authors show that on unrestricted profiles, two committees that appear equally good under previous metrics can have CHGR scores differing by a quadratic factor relative to the number of voters.
  • Approximation Guarantee: For specific "Candidate-Interval" profiles, they prove that any committee that manages to connect the whole graph is at least an $n$-approximation of the optimal CHGR score.
  • Computational Hardness: Unlike previous metrics which were easy to calculate for a fixed committee, evaluating the CHGR score of a single committee is itself NP-hard. This highlights that "robustness" is a deeper, more complex property than "reachability."
  • Tractability: They show that for small committees (fixed $k$), the problem becomes tractable, with even better performance (quasi-polynomial) in the Voter-Candidate-Interval (VCI) domain.
Schematic of the VCI domain where approval is determined by interval intersection on a 1D spectrum.

Limitations and Future Work

  • The "Zero" Problem: Like the CONS metric, CHGR assigns a score of zero to any committee that results in a disconnected graph. It cannot distinguish between a committee that almost connects everyone and one that connects no one. The authors suggest adding a damping factor (assigning small weights to absent edges) to refine this behavior.
  • Computational Weight: The high complexity of exact optimization suggests that future work should focus on spectral or flow-based heuristics, which are commonly used in the related field of community detection.
  • Weighted Graphs: The current model treats all shared approvals as equal. A natural extension would be to move to weighted graphs, where the strength of a connection depends on how many candidates two voters jointly approve.

Summary updated

Abstract

Approval-based committee selection has recently been studied through the lens of \emph{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 \emph{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.
BibTeX
@misc{bielous2026interlacing,
  author = {Gili Bielous and Reshef Meir},
  title = {{Interlacing Committees with Edge-Expansion}},
  year = {2026},
  eprint = {2611.25852},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.25852},
}
Figure