as a shield and seeking holes in and paths around that shield is a natural, exciting part of the drama of science, and is likely to continue for decades to come as new models, techniques, and attacks are formulated and studied. This study will clearly benefit from the broadest possible participation, and we urge any interested readers—and most especially those early in their careers—to bring their own time and skills to bear on the many problems that glimmer in the young, important, challenging study of the complexity of elections.

acknowledgments

We are deeply grateful to Preetjot Singh, Communications editors Georg Gottlob, Moshe Vardi, and Andrew Yao, and the anonymous referees for helpful suggestions and encouragement.

Piotr Faliszewski was supported in part by Polish Ministry of Science and Higher Education grant N-N206- 378637, AGH-UST grant 11. 11.120.865, and by the Foundation for Polish Sci-ence's Homing Program. Edith Hemaspaandra was supported in part by NSF grant IIS-0713061 and a Friedrich Wilhelm Bessel Research Award from the Alexander von Humboldt Foundation. Lane A. Hemaspaandra was supported in part by NSF grants CCF-0426761 and CCF-0915792 and a Friedrich Wilhelm Bessel Research Award from the Alexander von Humboldt Foundation.

 

References

1. ajtai, m. Worst-case complexity, average-case complexity and lattice problems. Documenta Mathematica, extra Volume Icm III (1998), 421–428.

2. Bartholdi, III, J. and orlin, J. single transferable vote resists strategic voting. Social Choice and Welfare 8, 4 (1991) 341–354.

3. Bartholdi, III, J., tovey, c. and trick, m. the computational difficulty of manipulating an election. Social Choice and Welfare 6, 3 (1989) 227–241.

4. Bartholdi, III, J., tovey, c. and trick, m. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare 6, 2 (1989), 157–165.

5. Bartholdi, III, J., tovey, c. and trick, m. How hard is it to control an election? Mathematical and Computer Modeling 16, 8/9 (1992), 27–40.

6. Betzler, n., fellows, m., guo, J., niedermeier, r. and rosamond, f. fixed-parameter algorithms for Kemeny scores. In Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management. Lecture notes in computer science #5034 (June 2008). springer-Verlag, 60–71.

7. Betzler, n., guo, J., niedermeier, r. parameterized computational complexity of Dodgson and young elections. In Proceedings of the 11th Scandinavian Workshop on Algorithm Theory. Lecture notes in computer science #5124 (July 2008). springer-Verlag, 402–413.

8. Brelsford, e., faliszewski, p., Hemaspaandra, e.,
schnoor, H., and schnoor, I. approximability of
manipulating elections. In Proceedings of the 23rd
AAAI Conference on Artificial Intelligence (July
2008). aaaI press, 44–49.

 

Piotr Faliszewski ( [e-mail]) is an assistant professor at the agH university of science and technology, Kraków, poland.

Edith hemaspaandra ( [e-mail]) is a professor at the rochester Institute of technology, rochester, ny.

Lane A. hemaspaandra ( [e-mail]) is a professor at the university of rochester, rochester, ny.

© 2010 acm 0001-0782/10/1100 $10.00