Inhalt des Dokuments
Committees Providing Justified Representation: Theory and Experiments
Andrzej Kaczmarczyk (TU Berlin)
We explore the landscape of committees that provide (proportional/extended) justified representation. We address the following three computational problems:
(1) How many committees provide justified representation?
(2) How many candidates are needed to provide justified representation?
(3) How good are committees providing justified representation with respect to standard quality measures?
On the theoretical side, we show that answering these questions is computationally intractable even for the basic variant of justified representation. This contrasts with the fact that one can easily find some committee providing justified representation. On the experimental side, motivated by the theoretical hardness results we employ integer linear programming formulations to address our questions. We empirically reveal that for a truly representative committee, justified representation is only a minimal requirement and we should analyze this committee more carefully. To this end, we perform experiments using several natural distributions (including variants of the impartial culture assumption and Euclidean elections) and real-world data from the Preflib library.
This is joint work with Robert Bredereck, Piotr Faliszewski, and Rolf Niedermeier.
Back to the research colloquium site.