Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules

DOI10.1007/978-3-642-03816-7_12zbMath1250.91040OpenAlexW1690400894MaRDI QIDQ3182918

Nadja Betzler, Britta Dorn

Publication date: 16 October 2009

Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03816-7_12

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14)

Related Items (7)

On the parameterized complexity of some optimization problems related to multiple-interval graphs ⋮ Kernelization complexity of possible winner and coalitional manipulation problems in voting ⋮ On the exact amount of missing information that makes finding possible winners hard ⋮ New candidates welcome! Possible winners with respect to the addition of new candidates ⋮ Complexity of manipulation with partial information in voting ⋮ On the evaluation of election outcomes under uncertainty ⋮ On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard

Cites Work

• Incompleteness and incomparability in preference aggregation: complexity results
• Algorithms for the coalitional manipulation problem
• Dichotomy for voting systems
• On the parameterized complexity of multiple-interval graph problems
• When are elections with few candidates hard to manipulate?

This page was built for publication: Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules