{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T15:32:16Z","timestamp":1758814336941,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T00:00:00Z","timestamp":1725580800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Union\u2019s Horizon 2020 research and innovation programme","award":["101002854"],"award-info":[{"award-number":["101002854"]}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["BR 4744\/2-1"],"award-info":[{"award-number":["BR 4744\/2-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"name":"JST PRESTO","award":["JPMJPR20C1"],"award-info":[{"award-number":["JPMJPR20C1"]}]},{"DOI":"10.13039\/501100001459","name":"Singapore Ministry of Education","doi-asserted-by":"crossref","award":["MOE-T2EP20221-0001"],"award-info":[{"award-number":["MOE-T2EP20221-0001"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>\n            In multiwinner approval voting, the goal is to select a\n            <jats:italic>k<\/jats:italic>\n            -member committee based on voters\u2019 approval ballots. A well-studied concept of proportionality in this context is the\n            <jats:italic>justified representation<\/jats:italic>\n            (JR) axiom, which demands that no large cohesive group of voters remains unrepresented. However, the JR axiom may conflict with other desiderata, such as\n            <jats:italic>social welfare<\/jats:italic>\n            (the number of approvals obtained by committee members) or\n            <jats:italic>coverage<\/jats:italic>\n            (the number of voters who approve at least one committee member). In this article, we investigate the price of imposing the JR axiom (as well as the more demanding\n            <jats:italic>extended justified representation<\/jats:italic>\n            axiom) on social welfare and coverage. Our approach is twofold: We derive worst-case bounds on the loss of welfare\/coverage caused by imposing JR and study the computational complexity of finding committees with high welfare that provide JR (obtaining hardness results, approximation algorithms, and an exact algorithm for one-dimensional preferences).\n          <\/jats:p>","DOI":"10.1145\/3676953","type":"journal-article","created":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T11:12:41Z","timestamp":1722942761000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["The Price of Justified Representation"],"prefix":"10.1145","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6718-3436","authenticated-orcid":false,"given":"Edith","family":"Elkind","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom and Alan Turing Institute, London, United Kingdom"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0332-4364","authenticated-orcid":false,"given":"Piotr","family":"Faliszewski","sequence":"additional","affiliation":[{"name":"AGH University of Science and Technology, Krak\u00f3w Poland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5304-577X","authenticated-orcid":false,"given":"Ayumi","family":"Igarashi","sequence":"additional","affiliation":[{"name":"University of Tokyo, Tokyo, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1052-2801","authenticated-orcid":false,"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[{"name":"Google Research, Bangkok, Thailand"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9213-7746","authenticated-orcid":false,"given":"Ulrike","family":"Schmidt-Kraepelin","sequence":"additional","affiliation":[{"name":"TU Eindhoven, Eindhoven, Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8973-2539","authenticated-orcid":false,"given":"Warut","family":"Suksompong","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore Singapore"}]}],"member":"320","published-online":{"date-parts":[[2024,9,6]]},"reference":[{"key":"e_1_3_4_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/070680096"},{"key":"e_1_3_4_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-016-1019-3"},{"key":"e_1_3_4_4_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11478"},{"key":"e_1_3_4_5_1","first-page":"107","volume-title":"Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201915)","author":"Aziz Haris","year":"2015","unstructured":"Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, and Toby Walsh. 2015. Computational aspects of multi-winner approval voting. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201915). 107\u2013115."},{"key":"e_1_3_4_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1388310"},{"key":"e_1_3_4_7_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0865"},{"key":"e_1_3_4_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2566972.2566985"},{"key":"e_1_3_4_9_1","volume-title":"The Theory of Committees and Elections","author":"Black Duncan","year":"1958","unstructured":"Duncan Black. 1958. The Theory of Committees and Elections. Cambridge University Press."},{"key":"e_1_3_4_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3367032.3367049"},{"key":"e_1_3_4_11_1","first-page":"406","volume-title":"Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI\u201917)","author":"Brill Markus","year":"2017","unstructured":"Markus Brill, Rupert Freeman, Svante Janson, and Martin Lackner. 2017. Phragm\u00e9n\u2019s voting methods and justified representation. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI\u201917). 406\u2013413."},{"key":"e_1_3_4_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580507.3597785"},{"key":"e_1_3_4_13_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v38i9.28808"},{"key":"e_1_3_4_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9359-y"},{"key":"e_1_3_4_15_1","doi-asserted-by":"publisher","DOI":"10.2307\/1957270"},{"key":"e_1_3_4_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-006-7908-0"},{"key":"e_1_3_4_17_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i5.20429"},{"key":"e_1_3_4_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.114039"},{"key":"e_1_3_4_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103357"},{"key":"e_1_3_4_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2832415.2832529"},{"key":"e_1_3_4_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/3535850.3535897"},{"key":"e_1_3_4_22_1","first-page":"27","volume-title":"Trends in Computational Social Choice","author":"Faliszewski Piotr","year":"2017","unstructured":"Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. 2017. Multiwinner voting: A new challenge for social choice theory. In Trends in Computational Social Choice, Ulle Endriss (Ed.). AI Access, Chapter 2, 27\u201347."},{"key":"e_1_3_4_23_1","first-page":"670","volume-title":"Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI\u201917)","author":"Fern\u00e1ndez Luis S\u00e1nchez","year":"2017","unstructured":"Luis S\u00e1nchez Fern\u00e1ndez, Edith Elkind, Martin Lackner, Norberto Fern\u00e1ndez Garc\u00eda, Jes\u00fas Arias-Fisteus, Pablo Basanta-Val, and Piotr Skowron. 2017. Proportional justified representation. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI\u201917). 670\u2013676."},{"key":"e_1_3_4_24_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i6.16686"},{"key":"e_1_3_4_25_1","first-page":"627","volume-title":"Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS\u201996)","author":"H\u00e5stad Johan","year":"1996","unstructured":"Johan H\u00e5stad. 1996. Clique is hard to approximate within \\(n^{1 - \\varepsilon }\\) . In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS\u201996). 627\u2013636."},{"key":"e_1_3_4_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02839-7_6"},{"key":"e_1_3_4_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/3367032.3367088"},{"key":"e_1_3_4_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1764891.1764944"},{"key":"e_1_3_4_29_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139177801.004"},{"key":"e_1_3_4_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103366"},{"key":"e_1_3_4_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-09016-5"},{"key":"e_1_3_4_32_1","first-page":"280","volume-title":"Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI\u201911)","author":"Lu Tyler","year":"2011","unstructured":"Tyler Lu and Craig Boutilier. 2011. Budgeted social choice: From consensus to personalized decision making. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI\u201911). 280\u2013286."},{"key":"e_1_3_4_33_1","doi-asserted-by":"publisher","DOI":"10.2307\/2296779"},{"key":"e_1_3_4_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00027-9"},{"key":"e_1_3_4_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_3_4_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/3540261.3541235"},{"key":"e_1_3_4_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-007-0235-2"},{"key":"e_1_3_4_38_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22792"},{"key":"e_1_3_4_39_1","volume-title":"The (Computational) Social Choice Take on Indivisible Participatory Budgeting","author":"Rey Simon","year":"2023","unstructured":"Simon Rey and Jan Maly. 2023. The (Computational) Social Choice Take on Indivisible Participatory Budgeting. Technical Report. arXiv.2303.00621 [cs.GT]. Retrieved from https:\/\/arxiv.org\/abs\/2303.00621"},{"key":"e_1_3_4_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0047-2727(77)90005-6"},{"key":"e_1_3_4_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/3207692.3207708"},{"key":"e_1_3_4_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2016.09.003"},{"key":"e_1_3_4_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.12.012"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3676953","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3676953","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:19:12Z","timestamp":1750295952000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3676953"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,6]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1145\/3676953"],"URL":"https:\/\/doi.org\/10.1145\/3676953","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2024,9,6]]},"assertion":[{"value":"2022-11-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-28","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}