{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T21:31:35Z","timestamp":1773696695261,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T00:00:00Z","timestamp":1731024000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T00:00:00Z","timestamp":1731024000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["BR 4744\/2-1"],"award-info":[{"award-number":["BR 4744\/2-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Graduiertenkolleg \u201cFacets of Complexity\u201d","award":["GRK 2434"],"award-info":[{"award-number":["GRK 2434"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soc Choice Welf"],"published-print":{"date-parts":[[2025,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>When selecting multiple candidates based on approval preferences of voters, the proportional representation of voters\u2019 opinions is an important and well-studied desideratum. Existing criteria for evaluating the representativeness of outcomes focus on <jats:italic>groups<\/jats:italic> of voters and demand that sufficiently large and cohesive groups are \u201crepresented\u201d in the sense that candidates approved by <jats:italic>some<\/jats:italic> group members are selected. Crucially, these criteria say nothing about the representation of <jats:italic>individual<\/jats:italic> voters, even if these voters are members of groups that deserve representation. In this paper, we formalize the concept of <jats:italic>individual representation (IR)<\/jats:italic> and explore to which extent, and under which circumstances, it can be achieved. We show that checking whether an IR outcome exists is computationally intractable, and we verify that all common approval-based voting rules may fail to provide IR even in cases where this is possible. We then focus on domain restrictions and establish an interesting contrast between \u201cvoter interval\u201d and \u201ccandidate interval\u201d preferences. This contrast can also be observed in our experimental results, where we analyze the attainability of IR for realistic preference profiles.<\/jats:p>","DOI":"10.1007\/s00355-024-01563-w","type":"journal-article","created":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T11:22:00Z","timestamp":1731064920000},"page":"69-96","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Individual representation in approval-based committee voting"],"prefix":"10.1007","volume":"64","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9509-7017","authenticated-orcid":false,"given":"Markus","family":"Brill","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3992-3203","authenticated-orcid":false,"given":"Jonas","family":"Israel","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7373-5898","authenticated-orcid":false,"given":"Evi","family":"Micha","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9921-951X","authenticated-orcid":false,"given":"Jannik","family":"Peters","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,11,8]]},"reference":[{"issue":"2","key":"1563_CR1","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00355-016-1019-3","volume":"48","author":"H Aziz","year":"2017","unstructured":"Aziz H, Brill M, Conitzer V, Elkind E, Freeman R, Walsh T (2017) Justified representation in approval-based committee voting. Soc Choice Welf 48(2):461\u2013485","journal-title":"Soc Choice Welf"},{"key":"1563_CR2","volume-title":"Fair representation: meeting the ideal of one man","author":"ML Balinski","year":"1982","unstructured":"Balinski ML, Young HP (1982) Fair representation: meeting the ideal of one man. Yale University Press, One Vote"},{"key":"1563_CR3","doi-asserted-by":"crossref","unstructured":"Boehmer N, Brill M, Cevallos A, Gehrlein J, S\u00e1nchez-Fern\u00e1ndez L, Schmidt-Kraepelin U (2024) Approval-based committee voting in practice: A case study of (over-)representation in the Polkadot blockchain. In: Proceedings of the 38th AAAI conference on artificial intelligence (AAAI), pp 9519\u20139527","DOI":"10.1609\/aaai.v38i9.28807"},{"key":"1563_CR4","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s11127-007-9165-x","volume":"132","author":"SJ Brams","year":"2007","unstructured":"Brams SJ, Kilgour DM, Sanver MR (2007) A minimax procedure for electing committees. Public Choice 132:401\u2013420","journal-title":"Public Choice"},{"key":"1563_CR5","doi-asserted-by":"crossref","unstructured":"Bredereck R, Faliszewski P, Kaczmarczyk A, Niedermeier R (2019) An experimental view on committees providing justified representation. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pp 109\u2013115","DOI":"10.24963\/ijcai.2019\/16"},{"key":"1563_CR6","doi-asserted-by":"crossref","unstructured":"Brill M, Dindar H, Israel J, Lang J, Peters J, Schmidt-Kraepelin U (2023) Multiwinner voting with possibly unavailable candidates. In: Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pp 5532\u20135539","DOI":"10.1609\/aaai.v37i5.25687"},{"issue":"1\u20132","key":"1563_CR7","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s10107-023-01926-8","volume":"203","author":"M Brill","year":"2024","unstructured":"Brill M, Freeman R, Janson S, Lackner M (2024) Phragm\u00e9n\u2019s voting methods and justified representation. Math Program 203(1\u20132):47\u201376","journal-title":"Math Program"},{"issue":"1\u20132","key":"1563_CR8","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/s10107-022-01852-1","volume":"203","author":"M Brill","year":"2024","unstructured":"Brill M, G\u00f6lz P, Peters D, Schmidt-Kraepelin U, Wilker K (2024) Approval-based apportionment. Math. Program 203(1\u20132):77\u2013105","journal-title":"Program"},{"key":"1563_CR9","doi-asserted-by":"crossref","unstructured":"Brill M, Peters J (2023) Robust and verifiable proportionality axioms for multiwinner voting. In Proceedings of the 24th ACM Conference on Economics and Computation (ACM-EC), page 301. ACM, Full version arXiv:2302.01989 [cs.GT]","DOI":"10.1145\/3580507.3597785"},{"key":"1563_CR10","unstructured":"Elkind E, Lackner M (2015) Structure in dichotomous preferences. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pp. 2019\u20132025. AAAI Press"},{"key":"1563_CR11","unstructured":"Elkind E, Lackner M, Peters D (2017) Structured preferences. In: Endriss U (ed), Trends in Computational Social Choice, chapter\u00a010"},{"key":"1563_CR12","unstructured":"Gangl C, Maly J, Lackner M, Woltran S (2019) Aggregating expert opinions in support of medical diagnostic decision-making. In: Proceedings of the 11th International Workshop on Knowledge Representation for Health Care (KR4HC-2019)"},{"key":"1563_CR13","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman, New York"},{"key":"1563_CR14","unstructured":"Jung C, Kannan S, Lutz N (2020) A center in your neighborhood: Fairness in facility location. In: Proceedings of the Symposium on Foundations of Responsible Computing (FORC), pp. 5:1-5:15"},{"key":"1563_CR15","volume-title":"Multi-winner voting with approval preferences","author":"M Lackner","year":"2022","unstructured":"Lackner M, Skowron P (2022) Multi-winner voting with approval preferences. Springer, New York"},{"key":"1563_CR16","doi-asserted-by":"crossref","unstructured":"Peters D (2018) Single-peakedness and total unimodularity: new polynomial-time algorithms for multi-winner elections. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), pp. 1169\u20131176","DOI":"10.1609\/aaai.v32i1.11460"},{"key":"1563_CR17","doi-asserted-by":"crossref","unstructured":"Peters D, Pierczy\u0144ski G, Shah N, Skowron P (2021a) Market-based explanations of collective decisions. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pp 5656\u20135663","DOI":"10.1609\/aaai.v35i6.16710"},{"key":"1563_CR18","first-page":"12726","volume":"34","author":"D Peters","year":"2021","unstructured":"Peters D, Pierczy\u0144ski G, Skowron P (2021) Proportional participatory budgeting with additive utilities. Adv Neural Inf Process Syst 34:12726\u201312737","journal-title":"Adv Neural Inf Process Syst"},{"key":"1563_CR19","doi-asserted-by":"crossref","unstructured":"Peters D, Skowron P (2020) Proportionality and the limits of welfarism. In: Proceedings of the 21st ACM Conference on Economics and Computation (ACM-EC), pages 793\u2013794. ACM, Full version arXiv:1911.11747 [cs.GT]","DOI":"10.1145\/3391403.3399465"},{"key":"1563_CR20","doi-asserted-by":"crossref","unstructured":"Pierczy\u0144ski G, Skowron P (2022) Core-stable committees under restricted domains. In: Proceedings of the 18th International Workshop on Internet and Network Economics (WINE), pp 311\u2013329","DOI":"10.1007\/978-3-031-22832-2_18"},{"key":"1563_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03856-8","volume-title":"Proportional representation: apportionment methods and their applications","author":"F Pukelsheim","year":"2014","unstructured":"Pukelsheim F (2014) Proportional representation: apportionment methods and their applications. Springer, New York"},{"key":"1563_CR22","doi-asserted-by":"crossref","unstructured":"S\u00e1nchez-Fern\u00e1ndez L, Elkind E, Lackner M, Fern\u00e1ndez N, Fisteus JA, Basanta Val P, Skowron P (2017) Proportional justified representation. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pp 670\u2013676. AAAI Press","DOI":"10.1609\/aaai.v31i1.10611"},{"key":"1563_CR23","doi-asserted-by":"crossref","unstructured":"Skowron P (2021) Proportionality degree of multiwinner rules. In: Proceedings of the 22nd ACM Conference on Economics and Computation (ACM-EC), pp 820\u2013840. ACM","DOI":"10.1145\/3465456.3467641"},{"key":"1563_CR24","doi-asserted-by":"crossref","unstructured":"Skowron P, Lackner M, Brill M, Peters D, Elkind E (2017) Proportional rankings. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), pp 409\u2013415. IJCAI","DOI":"10.24963\/ijcai.2017\/58"},{"key":"1563_CR25","doi-asserted-by":"crossref","unstructured":"Szufa S, Faliszewski P, Janeczko \u0141, Lackner M, Slinko A, Sornat K, Talmon N (2022) How to sample approval elections? In: Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pp 496\u2013502","DOI":"10.24963\/ijcai.2022\/71"},{"key":"1563_CR26","doi-asserted-by":"crossref","unstructured":"Terzopoulou Z, Karpov A, Obraztsova S (2021) Restricted domains of dichotomous preferences with possibly incomplete information. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pp 5726\u20135733. AAAI Press","DOI":"10.1609\/aaai.v35i6.16718"},{"key":"1563_CR27","doi-asserted-by":"crossref","unstructured":"Yang Y (2019) On the tree representations of dichotomous preferences. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pp 644\u2013650. IJCAI","DOI":"10.24963\/ijcai.2019\/91"}],"container-title":["Social Choice and Welfare"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00355-024-01563-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00355-024-01563-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00355-024-01563-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,27]],"date-time":"2025-01-27T15:04:39Z","timestamp":1737990279000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00355-024-01563-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,8]]},"references-count":27,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["1563"],"URL":"https:\/\/doi.org\/10.1007\/s00355-024-01563-w","relation":{},"ISSN":["0176-1714","1432-217X"],"issn-type":[{"value":"0176-1714","type":"print"},{"value":"1432-217X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,8]]},"assertion":[{"value":"13 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}