CS Paper Radar

Interlacing Committees with Edge-Expansion

Gili Bielous, Reshef Meir

cs.MA ·submitted 2026-11-19 10:05 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Improved Metric Distortion Bounds for Deterministic Weighted-Tournament Voting Rules

cs.GT ·2026-08-15 ·Hau Chan, Jianan Lin, Chenhao Wang
theory similarity 0.66
Abstract

In metric social choice, voters and candidates lie in a common but unknown metric space, voters rank candidates by distance, and a voting rule seeks to minimize total distance to the voters. Its distortion is the worst-case approximation ratio relative to the minimum possible total distance. We study weighted-tournament rules (also known as C2 rules), which observe only the fraction of voters who prefer $a$ to $b$ for each pair of candidates $a,b$. These frequencies form a weighted tournament on candidates, a compressed representation that omits voter identities and the association of comparisons with individual voters. Prior work placed the optimal distortion of deterministic C2 rules between $3.1128$ and $3.9312$ [Charikar et al., EC 2025]. We introduce the Path-Unblanketed Set rule, a polynomial-time deterministic C2 rule with distortion at most $1+2\sqrt{2}\approx3.8284$ for every finite number of candidates. For elections with no more than six candidates, we prove with computer assistance that the distortion is at most $3.3346$. Furthermore, using an exact computer-assisted certificate, we provide a lower bound of $3.1828$ for deterministic C2 rules as a byproduct.

0.32

Influence Enhancement in Opinion Dynamics Using Edge Modification: A Kron Reduction-Based Approach

eess.SY ·2026-09-12 ·Aashi Shrinate, Aravind Seshadri, Twinkle Tripathy, Laxmidhar Behera, Lingfei Wang +1 more
similarity 0.64
Abstract

With the emergence of online social networks as a primary platform for advertising and advocacy, enhancing a user's influence has become of significant interest. In this paper, we investigate this problem under the Friedkin Johnsen opinion dynamics model, wherein stubborn agents influence the opinions of other agents in the network. Unlike most of the existing works, we leverage topological properties of the network to increase the influence of a desired stubborn agent. Specifically, we introduce the notion of edge modification, which mimics the mechanism of recommendations in social networks. First, we present a topology-based condition that identifies edge modifications that always increase the influence of a desired stubborn agent. It is shown that the impact of the chosen edge modifications remains robust to changes in parameters such as stubbornness and the interaction weights. Thereafter, we formulate a discrete optimisation problem to identify a set of edge modifications that maximise the agent's influence centrality. We present a computationally efficient approximate solution to the optimisation problem. Finally, we demonstrate the effectiveness of our approach on the Friedkin-Johnsen opinion dynamics over the Erdos Renyi random graph.

0.31

The Voter Model with Opinion Graph

cs.GT cs.DC ·2026-10-12 ·Petra Berenbrink, Thorsten Götte, Martin Hoefer, Tim Koglin
similarity 0.64
Abstract · Abstract shortened to comply Arxiv requirements

We study the \emph{voter model with opinion graph}, a generalization of the standard (pull) voter model that adds a notion of bounded confidence. In this process, we consider a finite set $A$ of $n$ agents. Each agent $u \in A$ has an opinion $x_u \in O$, where we model opinions as vertices in an undirected opinion graph $G = (O,E)$ with $|O|=q$. In each step, an agent $u$ interacts with another agent $v \in A$. In contrast to classical voting, $u$ adopts the opinion $x_v$ if and only if $x_v$ and $x_u$ are neighbors in $G$. The process is stable once all remaining opinions are an independent set in $G$. We analyze two variants of the process: the ordinary EdgeVOG process, which samples a pair of interacting agents uniformly at random from all possible pairs, and the productive EdgeVOG process, which samples only pairs with neighboring opinions in $G$. We show the following: - For every opinion graph and every initial configuration, ordinary EdgeVOG stabilizes within $O(n^2\log n)$ steps in expectation and with high probability. The expectation bound is asymptotically tight. For the productive EdgeVOG process, the expected stabilization time is exactly the initial number of compatible agent pairs, while $O(n^2\log n)$ steps suffice with high probability. - An opinion $i$ with initial support $s_i$ survives with probability at least $p_i:=s_i/(s_i+\sum_{j\in N(i)}s_j)$. Further, let $μ= \sum_{i \in O} p_i$, then we show the probability that less than $(1-δ)μ$ opinions survive is at most $\exp(-δ^2μ/(2(Δ^2+1)))$ for every $0\leqδ\leq1$. -If $G$ has maximum degree $Δ$ and every opinion initially has support at most $\hat{s}$, then no opinion ever acquires more than $\tilde{O}(\min\{n,Δ^6\hat{s}\})$ agents with high probability. This yields near-linear stabilization bounds for productive EdgeVOG for a large class of configurations.

0.21

Nearly Group-Separable Elections

cs.GT cs.MA ·2026-09-27 ·Piotr Faliszewski, Jan Jabrocki, Stanisław Kaźmierowski, Kristýna Pekárková, Šimon Schierreich +1 more
similarity 0.64
Abstract

We study the problem of computing how close a given election is to being group-separable, measuring proximity by swaps of adjacent candidates in the votes. We also consider several other domains, including caterpillar group-separable, balanced group-separable, single-peaked, and single-crossing ones. Our problem is generally intractable, but we find practical FPT algorithms parameterized by the number of candidates or swaps. For the latter case, our algorithm applies to all domains characterized by finite forbidden subelections, resolving a well-established open problem. We supplement our theoretical findings with experimental analysis.

0.14

A Constant Metric Distortion Protocol for Approval Voting Given Plurality Polls

cs.GT ·2026-08-28 ·Fabian Frank, Jannik Peters
similarity 0.62
Abstract

Approval voting is a simple and well-regarded voting rule: voters submit approval ballots (subsets of the candidates) and the candidate receiving the most approvals wins. One major limitation of approval voting is that it is not clear which candidates voters should approve if they have an underlying strict order over the candidates. In this paper, we initiate the study of approval voting under a simple kind of information: plurality polls. That is, we assume that for each candidate we know the share of voters who rank this candidate as their top choice. Using these plurality polls, we suggest a simple protocol parameterized by a fraction $k \in (0,1)$: every voter should approve the smallest prefix of their preference list containing the first choices of at least a fraction $k$ of the voters. We evaluate this protocol via the framework of metric distortion and show that for the optimal choice of $k$, this rule achieves a metric distortion of $2 + \sqrt{5} \simeq 4.236$. The proof techniques we use for this statement also show that the Bucklin voting rule has a metric distortion of at most $5$. Finally, we evaluate the robustness of our protocol to noise and show that the upper bounds obtained for our protocol are tight.

0.40

Exact Sizewise Least Cores for Candidate-Disjoint Approval Chains

cs.GT ·2026-09-03 ·Jiarui Fang
code/data similarity 0.61
Abstract · 14 pages, code and other materials are available at: https://github.com/Baymax-ray/sizewise-least-core

For approval-based committee elections, the sizewise least-core value $Γ(P)$ minimizes the maximum excess support of a deviation over size-$k$ committees. Deviations are nonempty and contain at most $k$ candidates, with support measured relative to their Hare quota. A negative value certifies core nonemptiness, while $-Γ(P)$ is the largest worst-case quota shortfall secured by any committee. We quantify this margin on candidate-disjoint approval chains, a domain whose qualitative core nonemptiness is already known. We first factor each committee's deviation score over disjoint components. For chains, a closed local table yields the exact value and an attaining committee in polynomial time for rational weights. For nonnegative normalized real weights, let $q_{\mathrm{act}}\ge1$ count the connected components of the positive-support incidence graph. Then \[ Γ(P)\le-\frac{1}{k\min\{q_{\mathrm{act}},k+1\}}. \] Explicit extremal profiles show that this dependence on the active-component count is sharp. The margin is $1$-Lipschitz in total variation on the full ballot space. Each negative margin therefore certifies a neighborhood with nonempty core, even when perturbations leave the chain domain.

0.41

Hidden Distances: How Likert-Scale Spacing Shapes Algorithmic Voting Advice

cs.CY cs.IRphysics.soc-ph ·2026-11-09 ·Thomas Broholt Knudsen, Christian Høst-Madsen, Vedran Sekara, Jonas L. Juul
similarity 0.61
Abstract · 18 pages, 6 figures

Voting Advice Applications (VAAs) are algorithmic recommenders that match voters with political candidates on policy preferences. They are widely adopted across many multi-party democracies; in Denmark, 62\% of eligible voters used a VAA ahead of the 2022 general election, and 45\% of VAA users reported following its advice. VAAs typically ask voters and candidates to respond to policy statements on a Likert scale, from ``strongly disagree'' to ``strongly agree'', and recommend candidates whose responses are closest to the voter's. Computing these distances requires assigning numbers to response options, a design choice without an empirical basis, since it is unknown how people perceive the distances between options. Here we show that this seemingly technical choice substantially changes whom voters are matched with. We parameterize the distance between ``(dis)agree'' and ``strongly (dis)agree'' relative to the distance between ``neutral'' and ``(dis)agree'' as $α$, and quantify how it changes recommendations for a popular Danish VAA. We find that moving from equidistant options to doubling this distance can change $37.7\%$ of top candidate matches and $21.9\%$ of top party matches, although no answers change. Low $α$-values favor candidates with strong positions, with some parties receiving up to $ 19.6\%$ more recommendations, while high $α$-values favor moderates. Similarly, female candidates receive fewer recommendations at low $α$ and more at high $α$-values. Our findings demonstrate that undisclosed quantification choices in algorithmic recommenders can carry considerable electoral consequences, and they call for transparency and sensitivity analysis in VAA design. As Likert-based matching also underpins dating platforms and roommate allocation systems, these implications extend well beyond elections.

0.39

Metric Distortion of Social Welfare Functions

cs.GT cs.MA ·2026-08-22 ·Fatih Erdem Kizilkaya, Aaryaman Aggarwal, Evi Micha
similarity 0.61
Abstract · 11 pages, 1 table

Metric distortion has primarily been studied for social choice functions, which select a single winner from ordinal preferences. We extend this framework to social welfare functions, which output a ranking of $m$ candidates. We associate each voter $v$ with a monotone weight vector $\mathbf{w}_v = (w_{v1},\ldots,w_{vm})$, specifying the importance of the $i$-th position for voter $v$, and define the cost of a ranking as the position-weighted sum of their distances to the ranked candidates. This model generalizes both single-winner voting and committee selection. We consider three information regimes. First, we study the setting where the positional weight vectors are known. A natural approach recursively applies a single-winner rule with distortion $β$ to construct the ranking one position at a time. We show that this yields distortion at most $3β$ in general. This gap is not merely an artifact of the analysis: we show that no analysis based solely on per-round guarantees can certify a bound better than $2β$. By exploiting structural properties specific to Fractional Veto of Kizilkaya and Kempe, we show that its recursive extension achieves the optimal distortion of 3. Second, when all voters share the same unknown weight vector, recursively applying any social choice function with distortion $β$ achieves distortion at most $1+(β-1)\text{range}(\mathbf{w})$, where $\text{range}(\mathbf{w})=(w_1-w_m)/w_1$ denotes the normalized range of the common weight vector $\mathbf{w}$. Finally, we study unknown heterogeneous weights. Without further assumptions, every rule has unbounded distortion. We therefore consider two natural normalizations: unit-sum, where each voter distributes one unit of value across the ranking, and unit-top, where every voter assigns unit value to the first position. Under both models, we show that the optimal distortion is $Θ(m)$.

0.40