The Price of Justified Representation
Authors: Edith Elkind, Piotr Faliszewski, Ayumi Igarashi, Pasin Manurangsi, Ulrike Schmidt-Kraepelin, Warut Suksompong4983-4990
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our approach is threefold: we derive worst-case bounds on the loss of welfare/coverage that is caused by imposing JR, study the computational complexity of finding good committees that provide JR (obtaining a hardness result, an approximation algorithm, and an exact algorithm for one-dimensional preferences), and examine this setting empirically on several synthetic datasets. |
| Researcher Affiliation | Collaboration | Edith Elkind,1 Piotr Faliszewski,2 Ayumi Igarashi,3 Pasin Manurangsi,4 Ulrike Schmidt-Kraepelin,5 Warut Suksompong6 1 University of Oxford, 2 AGH University of Science and Technology, 3 National Institute of Informatics 4 Google Research 5 TU Berlin 6 National University of Singapore |
| Pseudocode | No | The paper describes algorithms such as 'Greedy CC' in paragraph text, but does not include structured pseudocode or algorithm blocks. |
| Open Source Code | Yes | Our code can be found at https://github.com/ProjectPRAGMA/PriceOfJR-AAAI-2022. |
| Open Datasets | Yes | We consider three different models for generating random elections. All take as input the number of voters n, the number of candidates m, and one additional parameter. The impartial culture (IC) model is parameterized by p [0, 1]... The n-dimensional Euclidean model takes as input a parameter r [0, n]... All three models are frequently used in the literature (see, e.g., Bredereck et al. 2019; Godziszewski et al. 2021). |
| Dataset Splits | No | For each of the three models we sample 100 instances. For a given instance I, we iterate over α [0, 1] (in 0.01 increments) and compute a size-k committee WI,α so as to maximize the social welfare subject to the constraint that at least α cvr(I) coverage is achieved and JR is satisfied. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., GPU/CPU models, memory) used for running its experiments. |
| Software Dependencies | No | The paper states 'Part of our implementation builds upon code contributed by Andrzej Kaczmarczyk (Bredereck et al. 2019),' and provides a GitHub link, but it does not specify software names with version numbers. |
| Experiment Setup | Yes | We focus on elections with parameters n = m = 100 and k = 10. To make the results for the three models comparable, we chose the parameters p and r so that on average each voter approves n/k = 10 candidates. This leads to parameters p = 0.1 (for IC), r = 0.054 (for 1D) and r = 0.195 (for 2D). |