On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard

DOI10.4230/LIPIcs.MFCS.2017.57zbMath1447.91053arXiv1610.08407OpenAlexW2964079196MaRDI QIDQ5111273

Palash Dey, Neeldhara Misra

Publication date: 26 May 2020

Full work available at URL: https://arxiv.org/abs/1610.08407

zbMATH Keywords

NP-completenessvotingdichotomycomputational social choicepossible winnermaxflow

Mathematics Subject Classification ID

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

Related Items (6)

Manipulative elicitation -- a new attack on elections with incomplete preferences ⋮ On the exact amount of missing information that makes finding possible winners hard ⋮ Complexity of manipulation with partial information in voting ⋮ A parameterized perspective on protecting elections ⋮ Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers ⋮ On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard

Cites Work

• Unnamed Item
• Unnamed Item
• Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules
• New candidates welcome! Possible winners with respect to the addition of new candidates
• Frugal bribery in voting
• Kernelization complexity of possible winner and coalitional manipulation problems in voting
• Determining Possible and Necessary Winners Given Partial Orders
• Partial Kernelization for Rank Aggregation: Theory and Experiments
• Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
• On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard
• Handbook of Computational Social Choice
• Parameterized Algorithms

This page was built for publication: On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard