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:
-
After solving a challenging problem, I solve it again from scratch,
retracing only the *insight* of the earlier solution. I repeat this
until the solution is as clear and direct as I can hope for. Then I
look for a general rule for attacking similar problems, that *would*
have led me to approach the given problem in the most efficient way
the first time. -- Robert Floyd
-
In computer science, elegance is not a dispensable luxury, but a
matter of life and death. -- Edsger Dijkstra
-
Imagination is more important than knowledge. -- Albert Einstein
-
They are ill discoverers that think there is no land, when they can see
nothing but sea. -- Francis Bacon
Other Odds and Ends (Mostly Quotations):
-
I don't believe it. Prove it, and I still won't believe it.
--Life, the Universe and Everything
-
It was mentioned on CNN that the new prime number discovered
recently is four times bigger then the previous record.
-
Sooner or later society will realize that certain kinds of hard work
are in fact admirable even though they are more fun than just about
anything else. -- Donald E. Knuth
-
Getting tenure doesn't really change anything.
However, not getting tenure changes everything.
-
My late friend Stan Ulam used to remark that his life was sharply
divided into two halves. In the first half, he was always the
youngest person in the group; in the second half, he was always the
oldest. There was no transitional period.
-- Gian-Carlo Rota, "Indiscrete Thoughts"
-
Fools ignore complexity. Pragmatists suffer it. Some
can avoid it. Geniuses remove it.
-- Alan Perlis, Epigrams in Programming
-
More Quotes from Dijkstra:
* None of the programs in this monograph, needless to say, has been tested on a machine. (From "A Discipline of Programming.")
* Computer science is not about computers, any more than astronomy is about telescopes.
* The question of whether computers can think is just like the question of whether submarines can swim.
-
"Supposing a tree fell down, Pooh, and we were underneath it?" [said Piglet.]
"Supposing it didn't," said Pooh after careful thought.