Junta distributions and the average-case complexity of manipulating elections

Abstract

Encouraging voters to truthfully reveal their preferences in an election has long been an important issue. Previous studies have shown that some voting protocols are hard to manipulate, but predictably 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 new concepts; we consider elections distributed with respect to junta distributions, which concentrate on hard instances, and introduce a notion of heuristic polynomial time. We use our techniques to prove that a family of important voting protocols is susceptible to manipulation by coalitions, when the number of candidates is constant.

Cite this work

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

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

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