Vote trading and subset sums

Sebastian Bervoets (1) , Vincent Merlin (2) , Gerhard J. Woeginger (3)

1 GREQAM - Groupement de Recherche en Économie Quantitative d'Aix-Marseille
2 CREM - Centre de recherche en économie et management
3 Department of mathematics and computing science [Eindhoven]

We analyze the complexity of vote trading problems with equal-sized voting districts.For two allied vote-swapping parties, the problem is polynomially solvable.For three parties, the problem is NP-complete.

Mots clés: Vote swapping; vote trading; manipulation; subset sum problem

Domaines: Economies et finances

Sebastian Bervoets, Vincent Merlin, Gerhard J. Woeginger. Vote trading and subset sums. Operations Research Letters, 2015, 43 (1), pp.99-102. ⟨10.1016/j.orl.2014.12.007⟩. ⟨halshs-01102568⟩