Vote trading and subset sums

S. Bervoets; V. Merlin; G. Woeginger

doi:10.1016/j.orl.2014.12.007

Vote trading and subset sums

S. Bervoets, V. Merlin, G. Woeginger

Research output: Contribution to journal › Article › Academic › peer-review

3 Citations (Scopus)

201 Downloads (Pure)

Abstract

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. Keywords: Vote swapping; Vote trading; Manipulation; Subset sum problem

Original language	English
Pages (from-to)	99-102
Number of pages	4
Journal	Operations Research Letters
Volume	43
Issue number	1
DOIs	https://doi.org/10.1016/j.orl.2014.12.007
Publication status	Published - 2015

Access to Document

10.1016/j.orl.2014.12.007

publishers versionFinal published version, 342 KB

Cite this

@article{4d02280ef3404416a88c0be4caa5b3dd,

title = "Vote trading and subset sums",

abstract = "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. Keywords: Vote swapping; Vote trading; Manipulation; Subset sum problem",

author = "S. Bervoets and V. Merlin and G. Woeginger",

year = "2015",

doi = "10.1016/j.orl.2014.12.007",

language = "English",

volume = "43",

pages = "99--102",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Vote trading and subset sums

AU - Bervoets, S.

AU - Merlin, V.

AU - Woeginger, G.

PY - 2015

Y1 - 2015

N2 - 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. Keywords: Vote swapping; Vote trading; Manipulation; Subset sum problem

AB - 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. Keywords: Vote swapping; Vote trading; Manipulation; Subset sum problem

U2 - 10.1016/j.orl.2014.12.007

DO - 10.1016/j.orl.2014.12.007

M3 - Article

SN - 0167-6377

VL - 43

SP - 99

EP - 102

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

Vote trading and subset sums

Abstract

Access to Document

Fingerprint

Cite this