{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T01:47:33Z","timestamp":1770688053536,"version":"3.49.0"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,4,5]],"date-time":"2023-04-05T00:00:00Z","timestamp":1680652800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,5]],"date-time":"2023-04-05T00:00:00Z","timestamp":1680652800000},"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":"crossref","award":["NI 369\/19"],"award-info":[{"award-number":["NI 369\/19"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["NI 369\/22"],"award-info":[{"award-number":["NI 369\/22"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"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"}]},{"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"}]},{"DOI":"10.13039\/501100006764","name":"Technische Universit\u00e4t Berlin","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006764","id-type":"DOI","asserted-by":"crossref"}]}],"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>Given a set of agents with approval preferences over each other, we study the task of finding <jats:italic>k<\/jats:italic> matchings fairly representing everyone\u2019s preferences. To formalize fairness, we apply the concept of proportional representation as studied in approval-based multiwinner elections. To this end, we model the problem as a multiwinner election where the set of candidates consists of matchings of the agents, and agents\u2019 preferences over each other are lifted to preferences over matchings. Due to the exponential number of candidates in such elections, standard algorithms for classical sequential voting rules (such as those proposed by Thiele and Phragm\u00e9n) are rendered inefficient. We show that the computational tractability of these rules can be regained by exploiting the structure of the approval preferences. Moreover, we establish algorithmic results and axiomatic guarantees that go beyond those obtainable in the classical approval-based multiwinner setting: Assuming that approvals are symmetric, we show that Proportional Approval Voting (PAV), a well-established but computationally intractable voting rule, becomes polynomial-time computable, and that its sequential variant, which does not provide any proportionality guarantees in general, fulfills a rather strong guarantee known as extended justified representation. Some of our algorithmic results extend to other types of compactly representable elections with an exponential candidate space.<\/jats:p>","DOI":"10.1007\/s00355-023-01453-7","type":"journal-article","created":{"date-parts":[[2023,4,5]],"date-time":"2023-04-05T17:02:06Z","timestamp":1680714126000},"page":"179-220","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Proportional representation in matching markets: selecting multiple matchings under dichotomous preferences"],"prefix":"10.1007","volume":"64","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5102-449X","authenticated-orcid":false,"given":"Niclas","family":"Boehmer","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9509-7017","authenticated-orcid":false,"given":"Markus","family":"Brill","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9213-7746","authenticated-orcid":false,"given":"Ulrike","family":"Schmidt-Kraepelin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,5]]},"reference":[{"key":"1453_CR5","unstructured":"Aziz H, Gaspers S, Gudmundsson J, Mackenzie S, Mattei N, Walsh T (2015a) Computational aspects of multi-winner approval voting. In: Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), IFAAMAS, pp 107\u2013115"},{"issue":"2857","key":"1453_CR1","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.artint.2015.06.002","volume":"227","author":"H Aziz","year":"2015","unstructured":"Aziz H, Gaspers S, Mackenzie S, Walsh T (2015b) Fair assignment of indivisible objects under ordinal preferences. Artif Intell 227(2857):71\u201392","journal-title":"Artif Intell"},{"issue":"2","key":"1453_CR2","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":"1453_CR3","doi-asserted-by":"crossref","unstructured":"Aziz H, Elkind E, Huang S, Lackner M, S\u00e1nchez-Fern\u00e1ndez S, Skowron P (2018) On the complexity of extended and proportional justified representation. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, pp 902\u2013909","DOI":"10.1609\/aaai.v32i1.11478"},{"issue":"2","key":"1453_CR4","doi-asserted-by":"publisher","first-page":"6:1","DOI":"10.1145\/3327970","volume":"7","author":"H Aziz","year":"2019","unstructured":"Aziz H, Brandl F, Brandt F, Harrenstein P, Olsen M, Peters D (2019) Fractional hedonic games. ACM Trans Econ Comput 7(2):6:1-6:29","journal-title":"ACM Trans Econ Comput"},{"key":"1453_CR6","unstructured":"Berman P, Karpinski M, Scott AD (2003) Approximation hardness of short symmetric instances of MAX-3SAT. Electronic Colloquium on Computational Complexity (049)"},{"key":"1453_CR8","doi-asserted-by":"crossref","unstructured":"Boehmer N, Elkind E (2020) Stable roommate problem with diversity preferences. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pp 96\u2013102. https:\/\/ijcai.org","DOI":"10.24963\/ijcai.2020\/14"},{"key":"1453_CR7","doi-asserted-by":"crossref","unstructured":"Boehmer N, Brill M, Schmidt-Kraepelin U (2022) Proportional representation in matching markets: selecting multiple matchings under dichotomous preferences. In: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS). IFAAMAS, pp 136\u2013144","DOI":"10.1007\/s00355-023-01453-7"},{"issue":"2","key":"1453_CR9","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1006\/game.2001.0877","volume":"38","author":"A Bogomolnaia","year":"2002","unstructured":"Bogomolnaia A, Jackson MO (2002) The stability of hedonic coalition structures. Games Econom Behav 38(2):201\u2013230","journal-title":"Games Econom Behav"},{"issue":"1","key":"1453_CR10","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1111\/j.1468-0262.2004.00483.x","volume":"72","author":"A Bogomolnaia","year":"2004","unstructured":"Bogomolnaia A, Moulin H (2004) Random matching under dichotomous preferences. Econometrica 72(1):257\u2013279","journal-title":"Econometrica"},{"key":"1453_CR11","unstructured":"Bouveret S, Endriss U, Lang J (2010) Fair division under ordinal preferences: computing envy-free allocations of indivisible goods. In: Proceedings of the 19th European Conference on Artificial Intelligence (ECAI). IOS Press, pp 387\u2013392"},{"key":"1453_CR12","first-page":"406","volume-title":"Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI)","author":"M Brill","year":"2017","unstructured":"Brill M, Freeman R, Janson S, Lackner M (2017) Phragm\u00e9n\u2019s voting methods and justified representation. Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), AAAI Press, pp 406\u2013413"},{"issue":"3","key":"1453_CR13","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1177\/0951629818775518","volume":"30","author":"M Brill","year":"2018","unstructured":"Brill M, Laslier J-F, Skowron P (2018) Multiwinner approval rules as apportionment methods. J Theor Polit 30(3):358\u2013382","journal-title":"J Theor Polit"},{"key":"1453_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01852-1","author":"M Brill","year":"2022","unstructured":"Brill M, G\u00f6lz P, Peters D, Schmidt-Kraepelin U, Wilker K (2022a) Approval-based apportionment. Math Program. https:\/\/doi.org\/10.1007\/s10107-022-01852-1","journal-title":"Math Program"},{"key":"1453_CR14","first-page":"4892","volume-title":"Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI)","author":"M Brill","year":"2022","unstructured":"Brill M, Israel J, Micha E, Peters J (2022b) Individual representation in approval-based committee voting. Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), AAAI Press, pp 4892\u20134899"},{"issue":"3","key":"1453_CR16","doi-asserted-by":"publisher","first-page":"718","DOI":"10.2307\/1957270","volume":"77","author":"JR Chamberlin","year":"1983","unstructured":"Chamberlin JR, Courant PN (1983) Representative deliberations and representative decisions: proportional representation and the Borda rule. Am Polit Sci Rev 77(3):718\u2013733","journal-title":"Am Polit Sci Rev"},{"key":"1453_CR17","doi-asserted-by":"crossref","unstructured":"Cheng Y, Jiang Z, Munagala K, Wang K (2019) Group fairness in committee selection. Proceedings of the 20th ACM Conference on Economics and Computation (ACM-EC). ACM, pp 263\u2013279","DOI":"10.1145\/3328526.3329577"},{"issue":"4","key":"1453_CR18","first-page":"37","volume":"29","author":"Y Chevaleyre","year":"2008","unstructured":"Chevaleyre Y, Endriss U, Lang J, Maudet N (2008) Preference handling in combinatorial domains: from AI to social choice. AI Mag 29(4):37\u201346","journal-title":"AI Mag"},{"key":"1453_CR19","unstructured":"Cseh \u00c1 (2017) Popular matchings. In: Endriss U (ed) Trends in computational social choice, chapter 6. AI Access, pp 105\u2013122"},{"key":"1453_CR20","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds J (1965) Paths, trees and flowers. Can J Math 17:449\u2013467","journal-title":"Can J Math"},{"issue":"4","key":"1453_CR21","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1145\/321978.321982","volume":"23","author":"MJ Eisner","year":"1976","unstructured":"Eisner MJ, Severance DG (1976) Mathematical techniques for efficient record segmentation in large shared databases. J Assoc Comput Mach 23(4):619\u2013635","journal-title":"J Assoc Comput Mach"},{"key":"1453_CR22","unstructured":"Faliszewski P, Skowron P, Slinko A, Talmon N (2017) Multiwinner voting: a new challenge for social choice theory. In: Endriss U (ed) Trends in computational social choice, chap 2. AI Access, pp 27\u201347"},{"issue":"1","key":"1453_CR23","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale D, Shapley LS (1962) College admissions and the stability of marriage. Am Math Mon 69(1):9\u201315","journal-title":"Am Math Mon"},{"key":"1453_CR24","first-page":"401","volume":"9","author":"T Gallai","year":"1964","unstructured":"Gallai T (1964) Maximale systeme unabh\u00e4ngiger kanten. Publ Math Instit Hung Acad Sci Ser A 9:401\u2013413","journal-title":"Publ Math Instit Hung Acad Sci Ser A"},{"key":"1453_CR25","doi-asserted-by":"publisher","first-page":"1291","DOI":"10.1007\/s10618-020-00675-y","volume":"34","author":"D Garc\u00eda-Soriano","year":"2020","unstructured":"Garc\u00eda-Soriano D, Bonchi F (2020) Fair-by-design matching. Data Min Knowl Disc 34:1291\u20131335","journal-title":"Data Min Knowl Disc"},{"issue":"3","key":"1453_CR26","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1002\/bs.3830200304","volume":"20","author":"P G\u00e4rdenfors","year":"1975","unstructured":"G\u00e4rdenfors P (1975) Match making: assignments based on bilateral preferences. Behav Sci 20(3):166\u2013173","journal-title":"Behav Sci"},{"key":"1453_CR27","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M Garey","year":"1979","unstructured":"Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, New York"},{"key":"1453_CR28","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1112\/jlms\/s1-10.37.26","volume":"10","author":"P Hall","year":"1935","unstructured":"Hall P (1935) On representatives of subsets. J Lond Math Soc 10:26\u201330","journal-title":"J Lond Math Soc"},{"issue":"4","key":"1453_CR29","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer I (1981) The NP-completeness of edge-colouring. SIAM J Comput 10(4):718\u2013720","journal-title":"SIAM J Comput"},{"key":"1453_CR30","unstructured":"Janson S (2016) Phragm\u00e9n\u2019s and Thiele\u2019s election methods. Technical report, arXiv:1611.08826 [math.HO]"},{"key":"1453_CR31","doi-asserted-by":"crossref","unstructured":"Jiang Z, Munagala K, Wang K (2020) Approximately stable committee selection. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC). ACM, pp 463\u2013472","DOI":"10.1145\/3357713.3384238"},{"issue":"24","key":"1453_CR32","doi-asserted-by":"publisher","first-page":"2679","DOI":"10.1016\/j.tcs.2010.03.028","volume":"412","author":"T Kavitha","year":"2011","unstructured":"Kavitha T, Mestre J, Nasre M (2011) Popular mixed matchings. Theoret Comput Sci 412(24):2679\u20132690","journal-title":"Theoret Comput Sci"},{"key":"1453_CR33","doi-asserted-by":"crossref","unstructured":"Korte B, Vygen J (2012) Combinatorial optimization: theory and algorithms, 5th edn. Springer","DOI":"10.1007\/978-3-642-24488-9"},{"key":"1453_CR34","doi-asserted-by":"crossref","unstructured":"Lackner M (2020) Perpetual voting: fairness in long-term decision making. Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, pp 2103\u20132110","DOI":"10.1609\/aaai.v34i02.5584"},{"key":"1453_CR35","doi-asserted-by":"crossref","unstructured":"Lackner M, Skowron P (2022) Multi-winner voting with approval preferences. Technical report, arXiv:2007.01795 [cs.GT]","DOI":"10.1007\/978-3-031-09016-5"},{"key":"1453_CR36","doi-asserted-by":"crossref","unstructured":"Lang J, Xia L (2016) Voting in combinatorial domains. In: Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD (eds) Handbook of computational social choice, chap 9. Cambridge University Press, pp 197\u2013222","DOI":"10.1017\/CBO9781107446984.010"},{"key":"1453_CR38","doi-asserted-by":"publisher","DOI":"10.1142\/8591","volume-title":"Algorithmics of matching under preferences","author":"DF Manlove","year":"2013","unstructured":"Manlove DF (2013) Algorithmics of matching under preferences. World Scientific Publishing Company"},{"issue":"4","key":"1453_CR39","doi-asserted-by":"publisher","first-page":"925","DOI":"10.2307\/2082518","volume":"89","author":"BL Monroe","year":"1995","unstructured":"Monroe BL (1995) Fully proportional representation. Am Polit Sci Rev 89(4):925\u2013940","journal-title":"Am Polit Sci Rev"},{"key":"1453_CR40","doi-asserted-by":"crossref","unstructured":"Peters D, Skowron P (2020) Proportionality and the limits of welfarism. Proceedings of the 21st ACM Conference on Economics and Computation (ACM-EC). ACM Press, pp 793\u2013794","DOI":"10.1145\/3391403.3399465"},{"key":"1453_CR41","doi-asserted-by":"crossref","unstructured":"Peters D, Pierczyski G, Shah N, Skowron P (2021) Market-based explanations of collective decisions. AAAI Press, pp 5656\u20135663","DOI":"10.1609\/aaai.v35i6.16710"},{"issue":"3","key":"1453_CR42","first-page":"133","volume":"51","author":"E Phragm\u00e9n","year":"1894","unstructured":"Phragm\u00e9n E (1894) Sur une m\u00e9thode nouvelle pour r\u00e9aliser, dans les \u00e9lections, la repr\u00e9sentation proportionnelle des partis. \u00d6fversigt af Kongliga Vetenskaps-Akademiens F\u00f6rhandlingar 51(3):133\u2013137","journal-title":"\u00d6fversigt af Kongliga Vetenskaps-Akademiens F\u00f6rhandlingar"},{"issue":"4","key":"1453_CR43","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1287\/moor.18.4.803","volume":"18","author":"AE Roth","year":"1993","unstructured":"Roth AE, Rothblum UG, Vande Vate JH (1993) Stable matchings, optimal assignments, and linear programming. Math Oper Res 18(4):803\u2013828","journal-title":"Math Oper Res"},{"key":"1453_CR44","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). AAAI Press, pp 670\u2013676","DOI":"10.1609\/aaai.v31i1.10611"},{"key":"1453_CR45","unstructured":"Thiele TN (1895) Om flerfold valg. Oversigt over det Kongelige Danske Videnskabernes Selskabs Fordhandlinger"},{"key":"1453_CR46","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"Leslie G Valiant","year":"1979","unstructured":"Valiant Leslie G (1979) The complexity of computing the permanent. Theoret Comput Sci 8:189\u2013201","journal-title":"Theoret Comput Sci"}],"container-title":["Social Choice and Welfare"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00355-023-01453-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00355-023-01453-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00355-023-01453-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,27]],"date-time":"2025-01-27T15:04:04Z","timestamp":1737990244000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00355-023-01453-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,5]]},"references-count":45,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["1453"],"URL":"https:\/\/doi.org\/10.1007\/s00355-023-01453-7","relation":{},"ISSN":["0176-1714","1432-217X"],"issn-type":[{"value":"0176-1714","type":"print"},{"value":"1432-217X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,5]]},"assertion":[{"value":"23 April 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 April 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}