On the Tractability Landscape of the Conditional Minisum Approval Voting Rule

Georgios Amanatidis, Michael Lampis, Evangelos Markakis, Georgios Papasotiropoulos · 2024

Read On the Tractability Landscape of the Conditional Minisum Approval Voting Rule by Georgios Amanatidis, Michael Lampis, Evangelos Markakis, Georgios Papasotiropoulos (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-09005.txt.

Description

Elections on linked issues let voters approve packages, but a fairness rule for picking winners may be hopeless to compute. Georgios Amanatidis, Michael Lampis, Evangelos Markakis, and Georgios Papasotiropoulos map that hardness in a 2024 paper. Their rule sums each voter's unmet wishes across issues and seeks the smallest total. Brute force, they show, is nearly impossible to beat under standard assumptions.

Two practical limits on inputs do make the problem solvable. Both limits are shown to sit right at the edge of hardness. The paper names where conditional voting can work in practice. Ballots that tie choices across issues are the root complication.

Catalog record

CREATORGeorgios Amanatidis, Michael Lampis, Evangelos Markakis, Georgios Papasotiropoulos
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE54 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-09005

Browse the full library · About the Tower of Babel