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.

 

Date
Speaker
Location
Language
09.05.2019
16:15
Andrzej Kaczmarczyk
TEL 512
English

Back to the research colloquium site.

To top

Zusatzinformationen / Extras