Junta Distributions and the Average-Case Complexity of Manipulating Elections

Ariel D. Procaccia · Jeffrey S. Rosenschein

148 citations0/0 files storedJournal of Artificial Intelligence Research

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Game Theory and Voting Systems Complexity and Algorithms in Graphs Internet Traffic Analysis and Secure E-voting

Abstract

Encouraging voters to truthfully reveal their preferences in an election has long been an important issue. Recently, computational complexity has been suggested as a means of precluding strategic behavior. Previous studies have shown that some voting protocols are hard to manipulate, but used NP-hardness as the complexity measure. Such a worst-case analysis may be an insufficient guarantee of resistance to manipulation. Indeed, we demonstrate that NP-hard manipulations may be tractable in the average case. For this purpose, we augment the existing theory of average-case complexity with some new concepts. In particular, we consider elections distributed with respect to junta distributions, which concentrate on hard instances. We use our techniques to prove that scoring protocols are susceptible to manipulation by coalitions, when the number of candidates is constant.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 148 citations exist upstream.

References

1975Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions 1989Voting schemes for which it can be difficult to tell who won the election 1989The computational difficulty of manipulating an election 1991Single transferable vote resists strategic voting 1992How hard is it to control an election?

Cited by

2006Dichotomy for voting systems 2008Algorithms for the coalitional manipulation problem 2009Eliciting Single-Peaked Preferences Using Comparison Queries 2011Multimode Control Attacks on Elections 2008Complexity of Strategic Behavior in Multi-Winner Elections 2009Complexity of unweighted coalitional manipulation under some common voting rules 2008Copeland voting: ties matter 2013Better Human Computation Through Principled Voting

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.