Multi-Winner Voting with Argumentative Ballots
2026-08-24 • Computer Science and Game Theory
Computer Science and Game TheoryArtificial Intelligence
AI summaryⓘ
The authors introduce a new voting system called multi-winner voting with argumentative ballots (MVArg), which lets voters give more detailed preferences about candidates instead of just approval or disapproval. They extend existing fairness ideas like voter cohesion and justified representation to fit this more expressive system. Their results show that MVArg can represent votes better than traditional approval voting, and some fairness conditions still hold while others don't always. They also prove it can be complex to check fairness but possible to find fair winners efficiently, with all their math formally verified by a computer.
multi-winner votingargumentative ballotsapproval ballotsvoter cohesionjustified representationJRPJREJRcoNP-hardLean 4
Authors
Ryuta Arisaka, Hirotaka Ono
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.