|
 ABSTRACT
Much work has been devoted, during the past twenty years, to using complexity to protect elections from manipulation and control. Many results have been obtained showing NP-hardness shields, and recently there has been much focus on whether such worst-case hardness protections can be bypassed by frequently correct heuristics or by approximations. This paper takes a very different approach: We argue that when electorates follow the canonical political science model of societal preferences the complexity shield never existed in the first place. In particular, we show that for electorates having single-peaked preferences, many existing NP-hardness results on manipulation and control evaporate.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
{Austen-Smith and Banks, 2004} D. Austen-Smith and J. Banks. Positive Political Theory II: Strategy and Structure. University of Michigan Press, 2004.
|
| |
2
|
{Ballester and Haeringer, 2007} M. Ballester and G. Haeringer. A characterization of the single-peaked domain, 2007. Manuscript.
|
| |
3
|
{Bartholdi and Orlin, 1991} J. Bartholdi, III and J. Orlin. Single transferable vote resists strategic voting. Social Choice and Welfare, 8(4):341--354, 1991.
|
| |
4
|
{Bartholdi and Trick, 1986} J. Bartholdi, III and M. Trick. Stable matching with preferences derived from a psychological model. Operations Research Letters, 5(4):165--169, 1986.
|
| |
5
|
{Bartholdi et al., 1989} J. Bartholdi, III, C. Tovey, and M. Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6(3):227--241, 1989.
|
| |
6
|
{Bartholdi et al., 1992} J. Bartholdi, III, C. Tovey, and M. Trick. How hard is it to control an election? Mathematical and Computer Modeling, 16(8/9):27--40, 1992.
|
| |
7
|
{Baumeister et al., to appear} D. Baumeister, G. Erdélyi, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. Computational aspects of approval voting. In J. Laslier and R. Sanver, editors, Handbook of Approval Voting. Springer, to appear. Available as University of Rochester Computer Science Department Technical Report TR-2009-944, May 2009.
|
| |
8
|
{Black, 1948} D. Black. On the rationale of group decision-making. Journal of Political Economy, 56(1):23--34, 1948.
|
| |
9
|
{Black, 1958} D. Black. The Theory of Committees and Elections. Cambridge University Press, 1958.
|
| |
10
|
{Brelsford et al., 2008} E. Brelsford, P. Faliszewski, E. Hemaspaandra, H. Schnoor, and I. Schnoor. Approximability of manipulating elections. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence, pages 44--49. AAAI Press, July 2008.
|
| |
11
|
|
 |
12
|
|
| |
13
|
{Conitzer, to appear} V. Conitzer. Eliciting single-peaked preferences using comparison queries. Journal of Artificial Intelligence Research, to appear.
|
| |
14
|
{Davis et al., 1970} O. Davis, M. Hinich, and P. Ordeshook. An expository development of a mathematical model of the electoral process. American Political Science Review, 54(2):426--448, 1970.
|
| |
15
|
{Ephrati and Rosenschein, 1991} E. Ephrati and J. Rosenschein. The Clarke Tax as a consensus mechanism among automated agents. In Proceedings of the 9th National Conference on Artificial Intelligence, pages 173--178. AAAI Press, July 1991.
|
| |
16
|
|
| |
17
|
{Erdélyi et al., 2008} G. Erdélyi, M. Nowak, and J. Rothe. Sincere-strategy preference-based approval voting fully resists constructive control and broadly resists destructive control. Technical Report arXiv:0806.0535 {cs.GT}, arXiv.org, September 2008. To appear in Mathematical Logic Quarterly, 55(4):425--443, 2009.
|
| |
18
|
|
| |
19
|
|
| |
20
|
{Faliszewski et al., 2007} P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. Llull and Copeland voting broadly resist bribery and control. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence, pages 724--730. AAAI Press, July 2007.
|
| |
21
|
{Faliszewski et al., 2009} P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. A richer understanding of the complexity of election systems. In S. Ravi and S. Shukla, editors, Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz, pages 375--406. Springer, 2009.
|
| |
22
|
|
| |
23
|
{Gailmard et al., to appear} S. Gailmard, J. Patty, and E. Penn. Arrow's theorem on single-peaked domains. In E. Aragonés, C. Beviá, H. Llavador, and N. Schofield, editors, The Political Economy of Democracy. To appear.
|
| |
24
|
|
| |
25
|
|
| |
26
|
{Hemaspaandra et al., 2007b} E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. Hybrid elections broaden complexity-theoretic resistance to control. In Proceedings of the 20th International Joint Conference on Artificial Intelligence, pages 1308--1314. AAAI Press, January 2007. To appear in Mathematical Logic Quarterly, 55(4):397--424, 2009.
|
| |
27
|
{Krehbiel, 1998} K. Krehbiel. Pivotal Politics: A Theory of U.S. Lawmaking. University of Chicago Press, 1998.
|
| |
28
|
{Lepelley, 1996} D. Lepelley. Constant scoring rules, Condorcet criteria, and single-peaked preferences. Economic Theory, 7(3):491--500, 1996.
|
| |
29
|
{Niemi and Wright, 1987} R. Niemi and J. Wright. Voting cycles and the structure of individual preferences. Social Choice and Welfare, 4(3):173--183, 1987.
|
| |
30
|
{Peleg and Sudhölter, 1999} B. Peleg and P. Sudhölter. Single-peakedness and coalition-proofness. Review of Economic Design, 4(4):381--387, 1999.
|
| |
31
|
|
| |
32
|
{Poole and Rosenthal, 1997} K. Poole and H. Rosenthal. Congress: A Political-Economic History of Roll-Call Voting. Oxford University Press, 1997.
|
| |
33
|
{Procaccia and Rosenschein, 2007} A. Procaccia and J. Rosenschein. Junta distributions and the average-case complexity of manipulating elections. Journal of Artificial Intelligence Research, 28:157--181, 2007.
|
| |
34
|
{Trick, 1989} M. Trick. Recognizing single-peaked preferences on a tree. Mathematical Social Sciences, 17(3):329--334, 1989.
|
| |
35
|
{Walsh, 2007} T. Walsh. Uncertainty in preference elicitation and aggregation. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence, pages 3--8. AAAI Press, July 2007.
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
I.2