direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

On Serial Committee Elections: Complexity and Algorithms

Andrzej Kaczmarczyk (TU Berlin)


We introduce serial committee elections. The point is that our new model additionally takes into account that committee members shall have a short term of office (e.g., to limit the influence of elitist power cartels) but at the same time (too) frequent elections are to be avoided. 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 committee sizes greater than two we can spot few islands of tractability.


Andrzej Kaczmarczyk
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras