CS Paper Radar

Binary $k$-Center under a Hard Threshold with Applications to Delegated Voting

Jakub Dargaj, Aris Filos-Ratsikas, Paul W. Goldberg

cs.GT ·submitted 2026-09-28 15:19 UTC · v1

Abstract

We study the problem of covering binary strings of the same length, possibly with missing entries, by a fixed number of center strings, such that each input string is within a given relative distance of the closest center. The problem has applications in binary $k$-center clustering and bioinformatics, but our main motivation comes from computational social choice. In the setting of multi-issue approval voting, we consider an algorithmic question that precedes any election: how should representatives be designed so that as many voters as possible are willing to delegate? We study the problem in two dimensions, namely the number of centers and the agreement threshold, parameters that are application-specific, and provide a complete picture of its computational complexity when entries may be missing. For the special case without missing entries, we extend our hardness results to any number of centers and large values of threshold, leaving a narrow range of thresholds unresolved.

Closest papers

Nearest neighbours by meaning across the whole index.

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

Sparse Disapproval Guarantees a Nonempty Hare Core

cs.GT ·2026-09-03 ·Jiarui Fang
theorycode/data similarity 0.63
Abstract · 4 pages, code and other materials are available at: https://github.com/Baymax-ray/approval-core-corank-two

An approval committee is Hare-core stable if no coalition meeting the Hare quota can strictly improve by moving to another candidate set. Whether every approval election has such a committee remains open. We prove nonemptiness when each voter disapproves at most two candidates, with no bounds on the numbers of candidates, seats, or voter types. The result also permits arbitrary positive rational voter weights. Our deterministic rule represents a committee by its missing set. It first maximizes weighted coverage of two-candidate disapproval sets and then maximizes total disapproval incidence. An exact coverage inequality excludes targets one seat below the committee. The incidence objective excludes unanimous equal-size targets, while targets of size at most $k-2$ cannot improve any voter. Two implementation-level independent verifiers audit overlapping finite grids. The symbolic proof, not this bounded enumeration, establishes the theorem's unbounded quantifiers. The argument identifies complement-side coverage as a tractable mechanism for a broad parameter range within a sharply defined preference domain.

0.31

Improved Metric Distortion Bounds for Deterministic Weighted-Tournament Voting Rules

cs.GT ·2026-08-15 ·Hau Chan, Jianan Lin, Chenhao Wang
theory similarity 0.62
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

Interlacing Committees with Edge-Expansion

cs.MA ·2026-11-19 ·Gili Bielous, Reshef Meir
similarity 0.60
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.

0.23

Tree Plurality Veto: Voting in Few Rounds with Efficient Communication and Low Metric Distortion

cs.GT cs.AIcs.DMcs.DS ·2026-10-17 ·Gabriel Chen, Yu Cheng, Alice Wang
similarity 0.60
Abstract · SOSA'27

We consider the metric distortion framework for voting, where $n$ voters and $m$ candidates are embedded in an unknown metric space. A voting rule selects a candidate using only voters' ordinal preferences, and its distortion is the worst-case ratio between the social cost of the selected candidate and the minimum social cost. We study how round complexity trades off against total communication in deterministic voting protocols with low distortion. Deterministic rules can achieve the optimal distortion of $3$ in one round by eliciting complete rankings using $Θ(nm\log m)$ bits, while a direct sequential implementation of PluralityVeto achieves the same distortion using only $O(n\log m)$ bits but requires $Θ(n)$ rounds. Our main result is TreePluralityVeto, a deterministic voting protocol that, for every $r\ge 2$, achieves distortion at most $2r-1$ using at most $r$ rounds and $O(n\log m+n s^{1/(r-1)}\log s)$ bits of total communication, where $s = \min\{n, m\}$. The protocol runs PluralityVeto on a hierarchical partition of the voters, collecting restricted rankings in parallel at each level. The branching factor controls the tradeoff between rounds and communication, and a matching-based analysis shows that each level increases the distortion bound by at most $2$.

0.19

Approval-Based Multiwinner Voting with Candidate Qualities

cs.GT ·2026-09-08 ·Niclas Boehmer, Chris Dong, Luca Kreisel, Markus Utke
similarity 0.59
Abstract · 47 pages

We initiate the study of a new model of approval-based multiwinner voting in which each candidate carries an exogenous quality score, capturing, for instance, the reliability of the candidate or their relevance to the context of the selection. Quality scores break with the standard assumption of approval-based multiwinner voting that candidates are fully defined by the set of their supporters. We rethink what proportional representation means in the presence of quality scores. For this, we introduce a threshold-based and a value-based family of axioms, analyze their relationships, satisfiability, and computational complexity, and present rules that achieve the strongest jointly satisfiable combinations of our proportionality axioms. We then analyze the compatibility of proportionality with the natural goal of maximizing the summed quality of the selected candidates. While imposing standard proportionality notions can lead to an almost complete loss of quality, we show that under a new class of reciprocal axioms, which scale a group's entitlement by the quality of its commonly approved candidate(s), there always exist proportional committees retaining at least 3/4 of the optimal summed quality, and such committees can be computed by our voting rules at no additional computational cost.

0.25

Diverse Representation in Approval-Based Committee Voting

cs.GT ·2026-09-24 ·Julian Chingoma, Davide Grossi, Feline Lindeboom, Jan Maly
similarity 0.59
Abstract

The study of approval-based committee voting has so far focused predominantly on proportional representation. The canonical notion of diverse representation, based on the Chamberlin-Courant score, counts the number of voters with at least one representative in the committee, making it an individualistic notion. We develop a more comprehensive theory that instead requires the representation of many groups of voters, grounding it in the justified representation (JR) axiom, which we strengthen in two directions. First, we study the existing axioms of Strong JR (SJR) and Semi-Strong JR (SSJR), which consider the same cohesive groups as JR but demand stricter representation. We show that neither can be optimized efficiently on general domains (unless P = NP), but both can be on the Candidate Interval and Voter Interval domain. Second, to capture the unique and defining opinions of a group, we introduce Distinctive Representation (DR) and its local optimization variant, Local DR. We address satisfiability and computation time, and show (Local) DR to be distinct from known proportionality and diversity axioms. Experiments on real-world and synthetic data show that Local DR performs well on multiple empirical measures of diversity.

0.05

Proportionality in Elections under Feasibility Constraints and Ranked Ballots: The Solid Coalition Refinement Rule

cs.GT ·2026-11-06 ·Grzegorz Kwacz, Georgios Papasotiropoulos, Piotr Skowron
similarity 0.59
Abstract

We study elections with ranked ballots and general feasibility constraints, which indicate which sets of candidates are allowed as outcomes. We introduce the first proportionality axiom for this general setting and show that it extends the established notions from specific models that fit our general framework. We extend the Solid Coalition Refinement (SCR) rule to general constraints and prove that it satisfies our axiom exactly for matroid constraints. Although the naive implementation of SCR involves a step that is computationally intractable for weak orders, we show that in practical cases it can be implemented in polynomial time or efficiently in FPT time. We also illustrate limitations of this rule for approval ballots and provide its first empirical evaluation.

0.08