Publications

Sort by  |  Author

2018

Bounds on the Cost of Stabilizing a Cooperative Game.
Y. Bachrach, E. Elkind, E. Malizia, R. Meir, D. Pasechnik, J. Rosenschein, J. Rothe, and M. Zuckerman.
Journal of Artificial Intelligence Research, vol. 63, pp. 987-1023, December 2018.

2015

Control Complexity in Bucklin and Fallback Voting: A Theoretical Analysis.
G. Erdélyi, M. Fellows, J. Rothe, and L. Schend.
Journal of Computer and System Sciences, vol. 81, no. 4, pp. 632-660, June 2015.

2014

Computational Complexity and Approximability of Social Welfare Optimization in Multiagent Resource Allocation.
N. Nguyen, T. Nguyen, M. Roos, and J. Rothe.
Journal of Autonomous Agents and Multi-Agent Systems, vol. 28, no. 2, pp. 256-289, March 2014.

The Complexity of Probabilistic Lobbying.
D. Binkele-Raible, G. Erdélyi, H. Fernau, J. Goldsmith, N. Mattei, and J. Rothe.
Discrete Optimization, vol. 11, no. 1, pp. 1-21, February 2014.

False-Name Manipulation in Weighted Voting Games is Hard for Probabilistic Polynomial Time.
A. Rey and J. Rothe.
Journal of Artificial Intelligence Research, vol. 50, pp. 573-601, July 2014.

2013

The Complexity of Computing Minimal Unidirectional Covering Sets.
D. Baumeister, F. Brandt, F. Fischer, J. Hoffmann, and J. Rothe.
Theory of Computing Systems, vol. 53, no. 3, pp. 467-502, October 2013.

2012

Taking the Final Step to a Full Dichotomy of the Possible Winner Problem in Pure Scoring Rules.
D. Baumeister and J. Rothe.
Information Processing Letters, vol. 112, no. 5, pp. 186-190, February 2012.

Control Complexity in Bucklin, Fallback, and Plurality Voting: An Experimental Approach.
J. Rothe and L. Schend.
Proceedings of the 11th International Symposium on Experimental Algorithms (SEA 2012), Bordeaux, France. Springer-Verlag Lecture Notes in Computer Science 7276, pages 356-368, June 2012.

A Statistical Approach to Calibrating the Scores of Biased Reviewers: The Linear vs. the Nonlinear Model.
M. Roos, J. Rothe, J. Rudolph, B. Scheuermann, and D. Stoyan.
Website proceedings of the 6th Multidisciplinary Workshop on Advances in Preference Handling (M-PREF 2012), Montpellier, France, August 2012.

Control Complexity in Bucklin, Fallback, and Plurality Voting: An Experimental Approach.
J. Rothe and L. Schend.
Technical Report arXiv:1203.3967v2 [cs.GT], ACM Computing Research Repository (CoRR), 370 pages, March 2012. Revised, August 2012.

Control Complexity in Bucklin and Fallback Voting.
G. Erdélyi, M. Fellows, J. Rothe, and L. Schend.
Technical Report arXiv:1103.2230v2 [cs.CC], ACM Computing Research Repository (CoRR), 50 pages, March 2011. Revised, August 2012.

Computational Complexity in Three Areas of Computational Social Choice: Possible Winners, Unidirectional Covering Sets, and Judgment Aggregation
D. Baumeister.
PhD Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 130 pages, September 2012.

2011

Einführung in Computational Social Choice: Individuelle Strategien und kollektive Entscheidungen beim Spielen, Wählen und Teilen.
J. Rothe, D. Baumeister, C. Lindner, and I. Rothe.
Springer (Spektrum Akademischer Verlag), Heidelberg, xii+375 pp., 2011.

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

Computational Complexity of Two Variants of the Possible Winner Problem.
D. Baumeister, M. Roos, and J. Rothe.
Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), Taipei, Taiwan. IFAAMAS, pages 853-860, May 2011.

The Complexity of Voter Partition in Bucklin and Fallback Voting: Solving Three Open Problems.
G. Erdélyi, L. Piras, and J. Rothe.
Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), Taipei, Taiwan. IFAAMAS, pages 837-844, May 2011.

How to Calibrate the Scores of Biased Reviewers by Quadratic Programming.
M. Roos, J. Rothe, and B. Scheuermann.
Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI 2011), San Francisco, CA, USA. AAAI Press, pages 255-260, August 2011.

How Hard is it to Bribe the Judges? A Study of the Complexity of Bribery in Judgment Aggregation.
D. Baumeister, G. Erdélyi, and J. Rothe.
Proceedings of the 2nd International Conference on Algorithmic Decision Theory (ADT 2011), DIMACS Center, Rutgers University, Piscataway, NJ, USA. Springer-Verlag Lecture Notes in Artificial Intelligence 6992, pages 1-15, October 2011.

Bribery in Path-Disruption Games.
A. Rey and J. Rothe.
Proceedings of the 2nd International Conference on Algorithmic Decision Theory (ADT 2011), DIMACS Center, Rutgers University, Piscataway, NJ, USA. Springer-Verlag Lecture Notes in Artificial Intelligence 6992, pages 247-261, October 2011.

The Complexity of Probabilistic Lobbying.
D. Binkele-Raible, G. Erdélyi, H. Fernau, J. Goldsmith, N. Mattei, and J. Rothe.
Technical Report arXiv:0906.4431v4 [cs.CC], ACM Computing Research Repository (CoRR), 35 pages, June 2009. Revised, February 2011.

Taking the Final Step to a Full Dichotomy of the Possible Winner Problem in Pure Scoring Rules.
D. Baumeister and J. Rothe.
Technical Report arXiv:1108.4436v2 [cs.CC], ACM Computing Research Repository (CoRR), 9 pages, August 2011. Revised, November 2011.

Bribery in Path-Disruption Games.
A. Rey.
Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 58 pages, August 2011.

2010

Exakte Algorithmen für schwere Graphenprobleme.
F. Gurski, I. Rothe, J. Rothe, and E. Wanke.
eXamen.press, Springer-Verlag, Berlin, Heidelberg, xii+331 pages, 2010.

Computational Aspects of Approval Voting.
D. Baumeister, G. Erdélyi, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Chapter 10 in "Handbook on Approval Voting," J. Laslier and R. Sanver (editors), pp. 199-251. Springer-Verlag, Berlin, Heidelberg, 2010.

Control Complexity in Fallback Voting.
G. Erdélyi and J. Rothe.
Proceedings of Computing: the 16th Australasian Theory Symposium (CATS 2010), Brisbane, Australia. Australian Computer Society, Conferences in Research and Practice in Information Technology Series, pages 39-48, January 2010.

Complexity of Social Welfare Optimization in Multiagent Resource Allocation.
M. Roos and J. Rothe.
Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), Toronto, Canada. IFAAMAS, pages 641-648, May 2010.

The Complexity of Computing Minimal Unidirectional Covering Sets.
D. Baumeister, F. Brandt, F. Fischer, J. Hoffmann, and J. Rothe.
Proceedings of the 7th International Conference on Algorithms and Complexity (CIAC 2010), Rome, Italy. Springer-Verlag Lecture Notes in Computer Science 6078, pages 299-310, May 2010.

A Market-Affected Sealed-Bid Auction Protocol.
C. Lindner.
Proceedings of the 6th Hellenic Conference on Artificial Intelligence (SETN 2010), Athens, Greece. Springer-Verlag Lecture Notes in Artificial Intelligence 6040, pages 193-202, May 2010.

Complexity of Merging and Splitting for the Probabilistic Banzhaf Power Index in Weighted Voting Games.
A. Rey and J. Rothe.
Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), Lisbon, Portugal. IOS Press, pages 1021-1022 (short paper), August 2010.

Taking the Final Step to a Full Dichotomy of the Possible Winner Problem in Pure Scoring Rules.
D. Baumeister and J. Rothe.
Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), Lisbon, Portugal. IOS Press, pages 1019-1020 (short paper), August 2010.

Merging and Splitting for Power Indices in Weighted Voting Games and Network Flow Games on Hypergraphs.
A. Rey and J. Rothe.
Proceedings of the 5th European Starting AI Researcher Symposium (STAIRS 2010), Lisbon, Portugal. IOS Press, pages 277-289, August 2010.

Introduction to Computational Complexity.
M. Roos and J. Rothe.
Supplement in the Mathematical Programming Glossary, A. Holder, editor. INFORMS Computing Society, March 2010.

Parameterized Control Complexity in Fallback Voting.
G. Erdélyi and M. Fellows.
Technical Report arXiv:1004.3659v1 [cs.CC], ACM Computing Research Repository (CoRR), 13 pages, April 2010.

Control Complexity in Fallback Voting.
G. Erdélyi, L. Piras, and J. Rothe.
Technical Report arXiv:1004.3398v1 [cs.GT], ACM Computing Research Repository (CoRR), 30 pages, April 2010.

Bucklin Voting is Broadly Resistant to Control.
G. Erdélyi, L. Piras, and J. Rothe.
Technical Report arXiv:1005.4115v1 [cs.GT], ACM Computing Research Repository (CoRR), 20 pages, May 2010.

Proceedings of the Third International Workshop on Computational Social Choice.
V. Conitzer and J. Rothe (editors).
Printed by Düsseldorf University Press. University of Düsseldorf, Germany, viii+495 pages, September 2010.

2009

A Richer Understanding of the Complexity of Election Systems.
P. Faliszewski, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Chapter 14 in "Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz," S. Ravi and S. Shukla (editors), pp. 375-406. Springer, Berlin, Heidelberg, New York, 2009.

Satisfiability Parsimoniously Reduces to the Tantrix(TM) Rotation Puzzle Problem.
D. Baumeister and J. Rothe.
Fundamenta Informaticae, vol. 91, no. 1, pp. 35-51, 2009.

Hybrid Elections Broaden Complexity-Theoretic Resistance to Control.
L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Mathematical Logic Quarterly, vol. 55, no. 4, pp. 397-424, August 2009.

Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control.
G. Erdélyi, M. Nowak, and J. Rothe.
Mathematical Logic Quarterly, vol. 55, no. 4, pp. 425-443, August 2009.

Llull and Copeland Voting Computationally Resist Bribery and Constructive Control.
P. Faliszewski, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Journal of Artificial Intelligence Research, vol. 35, pp. 275-341, June 2009.

The Three-Color and Two-Color Tantrix(TM) Rotation Puzzle Problems are NP-Complete via Parsimonious Reductions.
D. Baumeister and J. Rothe.
Information and Computation, vol. 207, no. 11, pp. 1119-1139, November 2009.

Frequency of Correctness versus Average Polynomial Time.
G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
Information Processing Letters, vol. 109, no. 16, pp. 946-949, July 2009.

Generalized Juntas and NP-Hard Sets.
G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
Theoretical Computer Science, vol. 410, no. 38-40, pp. 3995-4000, September 2009.

The Cost of Stability in Weighted Voting Games (Extended Abstract).
Y. Bachrach, R. Meir, M. Zuckerman, J. Rothe, and J. Rosenschein.
Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009), Budapest, Hungary. IFAAMAS, pages 1289-1290, May 2009.

The Shield that Never Was: Societies with Single-Peaked Preferences are More Open to Manipulation and Control.
P. Faliszewski, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Proceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2009), Stanford University, Palo Alto, CA, USA. ACM Digital Library, pages 118-127, July 2009.

The Complexity of Probabilistic Lobbying.
G. Erdélyi, H. Fernau, J. Goldsmith, N. Mattei, D. Raible, and J. Rothe.
Proceedings of the 1st International Conference on Algorithmic Decision Theory (ADT 2009), Venice, Italy. Springer-Verlag Lecture Notes in Artificial Intelligence 5783, pages 86-97, October 2009.

The Cost of Stability in Coalitional Games.
Y. Bachrach, E. Elkind, R. Meir, D. Pasechnik, M. Zuckerman, J. Rothe, and J. Rosenschein.
Proceedings of the 2nd International Symposium on Algorithmic Game Theory (SAGT 2009), Paphos, Cyprus. Springer-Verlag Lecture Notes in Computer Science 5814, pages 122-134, October 2009.

Degrees of Guaranteed Envy-Freeness in Finite Bounded Cake-Cutting Protocols.
C. Lindner and J. Rothe.
Proceedings of the 5th Workshop on Internet & Network Economics (WINE 2009), Rome, Italy. Springer-Verlag Lecture Notes in Computer Science 5929, pages 149-159, December 2009.

Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control.
G. Erdélyi, M. Nowak, and J. Rothe.
Technical Report arXiv:0806.0535v5 [cs.GT], ACM Computing Research Repository (CoRR), 26 pages, June 2008. Revised, September 2008 and June 2009.

Computational Aspects of Approval Voting.
D. Baumeister, G. Erdélyi, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Technical Report 944, University of Rochester, Computer Science Department, Rochester, NY, 61 pages, May 2009.

The Cost of Stability in Coalitional Games.
Y. Bachrach, E. Elkind, R. Meir, D. Pasechnik, M. Zuckerman, J. Rothe, and J. Rosenschein.
Technical Report arXiv:0907.4385 [cs.GT], ACM Computing Research Repository (CoRR), 20 pages, July 2009.

The Complexity of Computing Minimal Unidirectional Covering Sets.
D. Baumeister, F. Brandt, F. Fischer, J. Hoffmann, and J. Rothe.
Technical Report arXiv:0901.3692v3 [cs.CC], ACM Computing Research Repository (CoRR), 27 pages, July 2009.
Supersedes the Technical Report "Deciding Membership in Minimal Upward Covering Sets is Hard for Parallel Access to NP" coauthored by D. Baumeister, F. Brandt, F. Fischer, and J. Rothe, arXiv:0901.3692v2 [cs.CC], ACM Computing Research Repository (CoRR), 14 pages, April 2009.

The Shield that Never Was: Societies with Single-Peaked Preferences are More Open to Manipulation and Control.
P. Faliszewski, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Technical Report arXiv:0909.3257v2 [cs.GT], ACM Computing Research Repository (CoRR), 38 pages, September 2009. Revised, June 2010.
Also appears as University of Rochester Computer Science Department Technical Report TR 950, Rochester, NY, 38 pages, September 2009.

The Control Complexity of Sincere-Strategy Preference-Based Approval Voting and of Fallback Voting, and a Study of Optimal Lobbying and Junta Distributions for SAT.
G. Erdélyi.
PhD Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 103 pages, March 2009.

2008

Komplexitätstheorie und Kryptologie. Eine Einführung in Kryptokomplexität.
J. Rothe.
eXamen.press, Springer-Verlag, Berlin, Heidelberg, xii+535 pages, 2008.

Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control.
G. Erdélyi, M. Nowak, and J. Rothe.
Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), Torun, Poland. Springer-Verlag Lecture Notes in Computer Science 5162, pages 311-322, August 2008.
An extended version appeared under the title "Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control" in the proceedings of the 2nd International Workshop on Computational Social Choice (COMSOC 2008), U. Endriss and P. Goldberg, editors, pages 229-240. University of Liverpool, UK, September 2008.

Computational Complexity for Social Choice Theorists.
J. Rothe.
Invited tutorial at the 2nd International Workshop on Computational Social Choice (COMSOC'08), Liverpool, United Kingdom, September 2008.

Computational Foundations of Social Choice: A Complexity-Theoretic Perspective.
J. Rothe.
Invited talk at the ESF LogICCC Launch Conference, Prague, Czech Republic, October 2008.

Fixed-Parameter Tractability and Parameterized Complexity Applied to Problems From Computational Social Choice.
C. Lindner and J. Rothe.
Supplement in the Mathematical Programming Glossary, A. Holder, editor. INFORMS Computing Society, October 2008.

Hybrid Elections Broaden Complexity-Theoretic Resistance to Control.
L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Technical Report cs.GT/0608057, ACM Computing Research Repository (CoRR), 53 pages, August 2006. Revised, September 2008.
Also appears as University of Rochester Computer Science Department Technical Report TR 900, Rochester, NY, 53 pages, June 2006. Revised, August 2006 and September 2008.

Llull and Copeland Voting Computationally Resist Bribery and Control.
P. Faliszewski, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Technical Report arXiV:0809.4484v2 [cs.GT], ACM Computing Research Repository (CoRR), 77 pages, September 2008.
Also appears as University of Rochester Computer Science Department Technical Report TR 933, Rochester, NY, 77 pages, April 2008. Revised, September 2008.

Frequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas.
G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
Technical Report arXiv:0806.2555v1 [cs.CC], ACM Computing Research Repository (CoRR), 20 pages, June 2008.
Also appears as University of Rochester Computer Science Department Technical Report TR 934, Rochester, NY, 20 pages, June 2008.