direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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.


Andrzej Kaczmarczyk
TEL 512

Back to the research colloquium site.

To top

Zusatzinformationen / Extras