CS Paper Radar

Sparse Disapproval Guarantees a Nonempty Hare Core

Jiarui Fang

cs.GT ·submitted 2026-09-03 22:49 UTC · v1
theorycode/data

Abstract

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.

Comment
4 pages, code and other materials are available at: https://github.com/Baymax-ray/approval-core-corank-two

Closest papers

Nearest neighbours by meaning across the whole index.

Veto Proportionality in Multiwinner Voting with Ranked Preferences

cs.GT ·2026-11-14 ·Haris Aziz, Yuhang Guo, Patrick Lederer
similarity 0.74
Abstract · Abstract shortened due to arXiv length restrictions

Proportional representation in committee voting with ranked preferences requires voter groups to influence the selected committee in proportion to their size. Existing axioms, such as proportionality for solid coalitions (PSC), demand that like-minded groups of voters are entitled to elect a fair number of candidates to the committee. However, in applications where voters are collectively affected by the entire committee, it may be equally important that no group is confronted with a disproportionate number of candidates that it regards as undesirable. Motivated by this, we initiate the study of veto proportionality in committee elections with ranked preferences. Our central notion, the proportional multiwinner veto core (PMVC), generalizes Moulin's proportional singlewinner veto core to multiwinner elections by allowing groups of voters to partially veto sets of candidates. We analyze how the PMVC relates to existing fairness notions and design rules that are guaranteed to select committees from the PMVC. Specifically, we first introduce a duality framework that connects inclusion- and exclusion-based fairness notions and show, e.g., that the dual axiom of the PMVC strengthens PSC. We further show that STV satisfies the dual axiom of the PMVC, which also implies the existence of committees in the PMVC. Subject to a strengthening of committee monotonicity, we characterize the rules that always return committees in the PMVC as sequential adaptations of singlewinner voting rules that always select from the proportional singlewinner veto core. By our duality framework, this also gives rise to a new class of rules that satisfy PSC. We further prove that the dual axiom of the PMVC and RankPJR+ are jointly satisfiable, thereby pushing the frontier of fairness guarantees that can always be attained. Finally, we show that deciding whether a given committee belongs to the PMVC is coNP-complete.

0.09

Best-of-Both Worlds Proportionality in Structured Committee Elections

cs.GT ·2026-10-20 ·Dimitris Avramidis, Mark de Berg, Ulrike Schmidt-Kraepelin
similarity 0.71
Abstract

We study randomized committee elections with additive preferences, where we seek best-of-both-worlds proportionality. That is, we strive for strong guarantees for the selection probabilities ex ante and each realized committee ex post. We focus on structured preferences and introduce antichain single-peakedness, a restricted domain generalizing single-peaked additive preferences as well as several well-studied approval domains. Our approach first computes a fractional committee and then decomposes it through a rounding rule called systematic rounding. Among profile-oblivious rounding rules, we characterize systematic rounding as the unique rule satisfying natural quota guarantees, and thereby the only promising rule for our two-step approach. We show that ex-ante core stability is incompatible with ex-post justified representation $JR$, even under single-peaked preferences. However, applying systematic rounding to certain fractional allocations that form so-called Lindahl equilibria yields ex-ante core stability and ex-post core stability up to one. Alternatively, we retain exact ex-post proportionality and approximate the ex-ante core using two parameters: $α$ raises the utility gain required for a deviation, while $β$ reduces the coalition's proportional share. We establish the tight threshold $αβ$=2. Below it, ex-post JR is incompatible even under single-peaked preferences; at and above it, adapting a fractional rule called BestRepresentative [Pierczyński and Skowron, 2022] and applying systematic rounding to its output yields ex-ante $α, β$-fractional core stability and ex-post PJR under antichain single-peaked preferences.

0.07

Nash Core in Multiwinner Election

cs.GT ·2026-08-31 ·Ashish Goel, Zhihao Jiang, Chenghan Zhou
theory similarity 0.71
Abstract

In the approval-based committee selection problem, a committee is said to be in the core if no subset of voters has an incentive to deviate by selecting a \emph{blocking} committee of proportional size, such that every voter in the deviating group strictly prefers the blocking committee. We consider the setting where candidates can be selected fractionally. Under a mild regularity assumption, we show that there always exists a weighting of candidates such that the fractional committee maximizing the candidate-weighted Nash Social Welfare is in the core. We refer to such a solution as being in the \emph{Nash core}. Additionally, we show that a Nash core solution admits a payment assignment between voters and candidates, where each voter pays a candidate they approve in proportion to the weight. For the discrete setting, where each candidate is either included or excluded from the committee, we prove that every approval-based committee election with at most eight equally weighted voters has a core committee by rounding the fractional Nash core solution. Although the non-emptiness of the core in this setting remains an open question and checking core membership is coNP-hard, we extend the notion of the Nash core to the discrete case, yielding a formulation that is efficiently verifiable and offers a promising path toward establishing core existence in discrete settings. Finally, we test our approach on real voting data using a payment-guided heuristic. We empirically show that the Nash core solution can be efficiently computed through an iterative algorithm in both the fractional and discrete settings.

0.38

Multi-Winner Elections: Justified Representation, Strategyproofness, and Risk-Avoiding Truthfulness

cs.GT ·2026-08-15 ·Yizhou Ai, Biaoshuai Tao
theory similarity 0.69
Abstract · 35 pages

We study approval-based multi-winner elections with Justified Representation (JR) when voters strategically report their ballots. We prove that there does not exist a strategy-proof mechanism that outputs JR committees, even when the mechanism can be randomized and only Ex-Ante strategyproofness is required. The impossibility already holds with three voters, four candidates, and target committee size three, even when the mechanism may select fewer than three candidates. It applies to every common strictly increasing cardinality-based utility function and scales to every target size $k\geq3$, every number of voters divisible by $k$, and every candidate-set size at least $k+1$. Motivated by our negative results, we then ask for weaker strategy-proof guarantees under voters' partial information. We use the notion of Risk-Avoiding Truthfulness and its RAT-Degree proposed by Hartman, Segal-Halevi, and Tao (EC'25), the number of other voters whose information a manipulator must know before a safe and profitable deviation is possible. Standard proportional rules, such as Greedy Approval Voting, Proportional Approval Voting, and the Method of Equal Shares, have poor performances under the RAT-Degree metric (with low RAT-Degrees). Finally, for $n$ voters, we construct a JR mechanism with RAT-Degree at least $n-5$, without a polynomial-time bound. We then use the same idea together with algebraic ballot encodings to obtain a polynomial-time JR mechanism with RAT-Degree at least $n-7$. When voters also have immutable private identifiers and both the identifiers and ballots of unknown voters are unobserved, we obtain a polynomial-time JR mechanism with RAT-Degree at least $n-1$ for $2\le k<m$. This degree is exactly $n-1$ when $k\ge3$ and $k$ divides $n$.

0.38

Approval-Based Apportionment: Like Portioning, Approximately like Committee Voting

cs.GT ·2026-08-27 ·Paul Gölz, Hannane Yaghoubizade
similarity 0.69
Abstract

We study approval-based apportionment, a variant of committee elections in which candidates ("parties") can be selected several times. We show that the proportionality axioms EJR, EJR+, and FJR coincide, and so do PJR, PJR+, and FPJR; that Lindahl priceability, an axiom implying core stability, is equivalent to a notion of approximate optimality with respect to the proportional approval voting (PAV) score; and that locally PAV-optimal committees are priceable. Approval-based apportionment (where a candidate receives an integer number of seats) lies between committee elections (zero or one seat) and portioning (a fractional number of seats). We formally connect portioning and apportionment by giving a construction that lifts axioms from apportionment to portioning and preserves implications between them. Several of our new implications between apportionment axioms are natural from a portioning perspective, leading us to believe that apportionment sits closer to portioning than to committee elections. None of them holds in committee elections, but several extend approximately, which makes apportionment a fruitful setting for conjecturing approximate relationships in approval-based committee elections.

0.44

Rules Before Oracles: Auditable, User-Configurable Argument Selection for Deliberative Polling

cs.AI cs.CRcs.CYcs.GT+1 ·2026-08-25 ·Muntaser Syed, Markus Zanker, Marius Silaghi
code/data similarity 0.68
Abstract

In a deliberative poll, once submissions outnumber what anyone will read, some mechanism chooses which arguments each voter sees, acquiring much of the decision; practice delegates it to opaque learned rankers, so a voter cannot recompute or contest the exposure that shaped their vote. We ask whether it can be a published rule over publicly recomputable evidence with parameters held by the voter, treating legibility as an admissibility condition on usable mechanisms, not an objective traded against accuracy. We formalise a poll over bipolar justification sets, judging a slate by reason coverage, the order it arrives in, and captured endorsement mass; we give seven checkable criteria for a civic recommender and a rule meeting them: a one-hop reversed endorsement flow parameterised by a relation-weight function. An agentic simulator records every slate at every vote, over about 17,000 seed-paired runs. Served slates fall 0.035 short of a label-reading ceiling upper-bounding every selection procedure, opaque ones included: any unconstrained ranker's advantage is bounded and small. On coverage alone, with non-degenerate authoring, the rule is indistinguishable from a random slate, a null due to an order-blind, charity-blind instrument; on the other two it leads at every prefix by a margin widening with adversarial pressure and dominates on mass by a factor of 3.3. Once a realistic fraction of submissions carries no reasons, the coverage margin returns and grows. Label-homogeneous flooding collapses completeness from 0.81 to 0.34 under a flat weight policy, only to 0.44 under author-count normalisation, making the weight function a security control worth 10% of completeness. The choice between ranking arms is a position on a coverage-versus-mass frontier, not a fact, the kind of choice only a legible rule can hand to the person it affects. It maps onto an open-source peer-to-peer platform.

0.25

Exact Sizewise Least Cores for Candidate-Disjoint Approval Chains

cs.GT ·2026-09-03 ·Jiarui Fang
code/data similarity 0.68
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

Sequential Phragmén Guarantees 2-Approximate Core Stability

cs.GT ·2026-09-11 ·Jianan Lin, Chenhao Wang
similarity 0.68
Abstract

We study approximately stable committee selection under approval preferences, following Cheng et al.~[EC~2019] and Jiang, Munagala, and Wang~[STOC~2020]. In an approval-based committee election, $n$ voters each approve a subset of the candidates, and a committee of size $k$ is selected. A size-$k$ committee is $λ$-stable if, for every nonempty subset $T$ of candidates, the number of voters who strictly prefer $T$ is less than $λ$ times the proportional share $\frac{n|T|}{k}$. We consider sequential Phragmén, a classical polynomial-time voting rule, and prove that it always returns a $2$-stable committee. This implies that the $2$-core is always nonempty and improves upon the $3.651$-stability guarantee of Gao, Sun, and Vondrák~[EC~2026]. The guarantee also extends to weighted voters and is tight even for unweighted elections: for every $1\leλ<2$, sequential Phragmén can return a committee that is not $λ$-stable. Compared with the exact-core algorithm developed in concurrent work by Becker, Greger, and Peters~[arXiv~2026], sequential Phragmén is simpler to implement, and our proof of its $2$-stability is elementary.

0.39