Multi-Winner Voting with Argumentative Ballots

[Submitted on 24 Aug 2026 (v1), last revised 28 Aug 2026 (this version, v2)]

View PDF HTML (experimental)

Abstract:We introduce multi-winner voting with argumentative ballots (MVArg) and investigate theoretical properties. As our conceptual contribution, we generalise approval ballots to argumentative ballots, thereby allowing voters to express defeasible preferences over candidates. We accordingly generalise voter cohesion and justified representation axioms JR, PJR and EJR. As our theoretical contribution, we establish several key results. First, MVArg is strictly more expressive than multi-winner voting with approval ballots (MV). Second, our notions of cohesion and justified representation are conservative generalisations of their counterparts in MV. Third, the MVArg counterpart of JR can always be satisfied, whereas the counterparts of PJR and EJR cannot always be. Fourth, although verifying whether a winner set satisfies the MVArg counterpart of JR is already coNP-hard, such a winner set can be constructed in polynomial time. All definitions, propositions, auxiliary lemmas and theorems have been formalised and mechanically checked in Lean 4.

Submission history

From: Ryuta Arisaka [view email]
[v1] Mon, 24 Aug 2026 13:39:05 UTC (714 KB)
[v2] Fri, 28 Aug 2026 10:05:50 UTC (527 KB)