Electing Successive Committees: Complexity and Algorithms

2020-06-02

Proceedings of the AAAI Conference on Artificial Intelligence, 34

Volume

Vol. 34 No. 02: AAAI-20 Technical Tracks 2

AAAI Technical Track: Game Theory and Economic Paradigms

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.

10.1609/aaai.v34i02.5552