CS 287/487 Instructor Page
Algorithms and Elections
Fall 2012, Prof. Lane A. Hemaspaandra

Syllabus/Course Information Document

Focus Papers, by Day

9/5 The Syllabus/Course Information Document. Reading for Monday: (1) Using Complexity to Protect Elections, P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra, Communications of the ACM, V. 53, #11, pp. 74--82, November 2010, and (2) A Richer Understanding of the Complexity of Election Systems, P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe, in Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz, eds. S. Ravi and S. Shukla, Springer, Chapter 14, pp. 375-406, 2009.

9/10 Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe, Journal of the ACM, V. 44, #6, pp. 806-825, November 1997.

9/12 Llull and Copeland Voting Computationally Resist Bribery and Control, P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe, Journal of Artificial Intelligence Research, V. 35, pp. 275-341, June 2009. Reading for Monday: To get a better sense of the topic (which was covered a bit in this talk and will be covered a bit in the next talk) of "control" of voting systems, please look at the following paper (except you can skip section 4), which is available online through the UR library's eJournals system: Anyone but Him: The Complexity of Precluding an Alternative, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe, Artificial Intelligence, V. 171, #5-6, pp.255--285, April 2007.

9/17 The Shield that Never Was: Societies with Single-Peaked Preferences Are More Open to Manipulation and Control, P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe, Information and Computation, V. 209, #2, pp. 89-107, February 2011.

9/19 Universal Voting Protocol Tweaks to Make Manipulation Hard, V. Conitzer and T. Sandholm, Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03), pp. 781-788, Morgan Kaufmann, 2003.

9/24 Communication Complexity of Common Voting Rules, Vincent Conitzer and Tuomas Sandholm, Proceedings of the 6th ACM Conference on Electronic Commerce). pp. 78-87, ACM Press, 2005.

9/26 Online Voter Control in Sequential Elections, Edith Hemaspaandra, Lane A. Hemaspaandra, and Joerg Rothe, Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012), IOS Press, pp 396-401, 2012, and The Complexity of Online Manipulation of Sequential Elections, Edith Hemaspaandra, Lane A. Hemaspaandra, and Joerg Rothe, ACM Computing Research Repository Technical Report arXiv:1202.6655 [cs.GT], February 2012 (revised May 2012).

10/1 When Are Elections with Few Candidates Hard to Manipulate?, Vincent Conitzer, Tuomas Sandholm, and Jerome Lang, Journal of the ACM, Vol. 54, No. 3, Article 14, June 2007.

10/3 Hybrid Voting Protocols and Hardness of Manipulation, E. Elkind and H. Lipmaa, Proceedings of the 16th Annual International Symposium on Algorithms and Computation, pages 206-215. Springer-Verlag Lecture Notes in Computer Science #3872, December 2005.

10/8 UR's Fall Break, so no class session (sigh!).

10/10 Manipulation under Voting Rule Uncertainty, E. Elkind and G. Erdelyi, Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, pages 627-634, 2012.

10/15 Optimal Manipulation of Voting Rules, S. Obraztsova and E. Elkind, Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, pages 619-626, 2012.

10/17 Voting Procedures with Incomplete Preferences, K. Konczak and J. Lang, Proceedings of the Multidisciplinary IJCAI-05 Workshop on Advances in Preference Handling, pages 124-129, 2005.

10/22 Compiling the Votes of a Subelectorate. Y. Chevalerye, J. Lang, N. Maudet, and G. Ravilly-Abadie. Proceedings of the 21st International Joint Conference on Artificial Intelligence, pages 97-102, 2009.

10/24 Winner Determination in Sequential Majority Voting, J. Lang, M. S. Pini, F. Rossi, K. B. Venable, and T. Walsh, Proceedings of the 20th International Joint Conference on Artificial Intelligence, pages 1372-1377, 2007.

10/29 Dominating Manipulations in Voting with Partial Information, V. Conitzer, T. Walsh, and L. Xia, Proceedings of the 25th National Conference on Artificial Intelligence (AAAI-11), pages 638-643, 2011.

10/31 A Scheduling Approach to Coalitional Manipulation, L. Xia, V. Conitzer, and A. Procaccia, Proceedings of the Eleventh ACM Conference on Electronic Commerce (EC-10), pages 275-284, 2010.

11/5 Computing Slater Rankings Using Similarities Among Candidates, V. Conitzer, Proceedings of the 21st National Conference on Artificial Intelligence (AAAI-06)---Volume 1, pages 613-619, 2006.

11/7 Parameterized Computational Complexity of Dodgson and Young Elections, N. Betzler, J. Guo, and R. Niedermeier, Information and Computation, 208(2):165-177, 2010.

11/12 Fixed-Parameter Algorithms for Kemeny Rankings [note: this paper provides also a good intro to/treatment of kernelization], N. Betzler, M. Fellows, J. Guo, R. Niedermeier, and F. Rosamond, Theoretical Computer Science, 410(45):4554-4570, 2009.

11/14 Unweighted Coalitional Manipulation under the Borda Rule is NP-Hard, N. Betzler, R. Niedermeier, and G. Woeginger, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, pages 55-60, 2011.

11/19 An Empirical Study of Borda Manipulation, Jessica Davies, George Katsirelos, Nina Narodytska and Toby Walsh, Third International Workshop on Computational Social Choice, Workshop Notes, pages 91-102, 2010.

11/21 UR's Thanksgiving Break, so no class session.

11/26 An Empirical Study of the Manipulation of Single Transferable Voting, Toby Walsh, 19th European Conference on Artificial Intelligence, pages 257-262, 2010.

11/28 Hybrid Elections Broaden Complexity-Theoretic Resistance to Control, Edith Hemaspaandra, Lane A. Hemaspaandra, and Joerg Rothe, Mathematical Logic Quarterly 55(4):397-424, 2009.

12/3 Computational Complexity of Two Variants of the Possible Winner Problem, Dorothea Baumeister, Magnus Roos, and Joerg Rothe, 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), pages 853-860, May 2011.

12/5 Junta Distributions and the Average-Case Complexity of Manipulating Elections, A. Procaccia and J. Rosenschein, Journal of Artificial Intelligence Research, 28:157-181, 2007.

12/10 On the Approximability of Dodgson and Young Elections, I. Caragiannis, J. Covey, M. Feldman, C. Homan, C. Kaklamanis, N. Karanikolas, A. Procaccia, and J. Rosenschein, Artificial Intelligence, 187:31-51, 2012.

12/12 (last day of classes for the term) Approximating Power Indices: Theoretical and Empirical Analysis, Y. Bachrach, E. Markakis, E. Resnick, A. Procaccia, J. Rosenschein, and A. Saberi, Autonomous Agents and Multi-Agent Systems, 20(2):105-122, 2010.

Other Information/Resources


Misc.

Some of My Favorite Pieces of Wisdom for Understanding and Evaluating (or Doing) Research:

Other Odds and Ends (Mostly Quotations):