Electing Successive Committees: Complexity and Algorithms

Authors

  • Robert Bredereck Technische Universität Berlin
  • Andrzej Kaczmarczyk Technische Universität Berlin
  • Rolf Niedermeier Technische Universität Berlin

DOI:

https://doi.org/10.1609/aaai.v34i02.5552

Abstract

We introduce successive committees elections. The point is that our new model additionally takes into account that “committee members” shall have a short term of office possibly over a consecutive time period (e.g., to limit the influence of elitist power cartels or to keep the social costs of overloading committees as small as possible) but at the same time overly frequent elections are to be avoided (e.g., for the sake of long-term planning). Thus, given voter preferences over a set of candidates, a desired committee size, a number of committees to be elected, and an upper bound on the number of committees that each candidate can participate in, the goal is to find a “best possible” series of committees representing the electorate.

We show a sharp complexity dichotomy between computing series of committees of size at most two (mostly in polynomial time) and of committees of size at least three (mostly NP-hard). Depending on the voting rule, however, even for larger committee sizes we can spot some tractable cases.

Downloads

Published

2020-04-03

How to Cite

Bredereck, R., Kaczmarczyk, A., & Niedermeier, R. (2020). Electing Successive Committees: Complexity and Algorithms. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1846-1853. https://doi.org/10.1609/aaai.v34i02.5552

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms