Recognizing distributed approval voting forms and correspondences

2020/10/29 by Endre Boros, Ondrej Cepek, Boros, Endre +5
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.2010.15730

16 pages

arxiv created 2020/10/29 · arxiv updated 2020/10/30

Abstract

Each voter i ∈ I has α_i cards that (s)he distributes among the candidates a ∈ A as a measure of approval. One (or several) candidate(s) who received the maximum number of cards is (are) elected. We provide polynomial algorithms to recognize voting forms and voting correspondences generated by such voting schemes in cases when either the number of candidates or the number of voters is equal to 2. We prove that for two voters, if α₂ ≥ α₁-2≥ 0 then the unique voting correspondence has distinct rows. We also characterize voting forms with distinct rows.

Related

• Selecting Matchings via Multiwinner Voting: How Structure Defeats a Large Candidate Space
• Computational Aspects of Multi-Winner Approval Voting
• Algorithms for two variants of Satisfaction Approval Voting
• Approval Voting with Intransitive Preferences
• A Polynomial-time Algorithm to Achieve Extended Justified Representation