{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:43:52Z","timestamp":1740123832159,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2023,12,15]],"date-time":"2023-12-15T00:00:00Z","timestamp":1702598400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,12,15]],"date-time":"2023-12-15T00:00:00Z","timestamp":1702598400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In many settings, a collective decision has to be made over a set of alternatives that has a combinatorial structure: important examples are multi-winner elections, participatory budgeting, collective scheduling, and collective network design. A further common point of these settings is that agents generally submit preferences over issues (e.g., projects to be funded), each having a cost, and the goal is to find a feasible solution maximising the agents\u2019 satisfaction under problem-specific constraints. We propose the use of judgment aggregation as a unifying framework to model these situations, which we refer to as collective combinatorial optimisation problems. Despite their shared underlying structure, collective combinatorial optimisation problems have so far been studied independently. Our formulation into judgment aggregation connects them, and we identify their shared structure via five case studies of well-known collective combinatorial optimisation problems, proving how popular rules independently defined for each problem actually coincide. We also chart the computational complexity gap that may arise when using a general judgment aggregation framework instead of a specific problem-dependent model.<\/jats:p>","DOI":"10.1007\/s10472-023-09910-w","type":"journal-article","created":{"date-parts":[[2023,12,15]],"date-time":"2023-12-15T06:01:46Z","timestamp":1702620106000},"page":"1437-1465","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Collective combinatorial optimisation as judgment aggregation"],"prefix":"10.1007","volume":"92","author":[{"given":"Linus","family":"Boes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1164-4234","authenticated-orcid":false,"given":"Rachael","family":"Colley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Umberto","family":"Grandi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e9r\u00f4me","family":"Lang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arianna","family":"Novaro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,12,15]]},"reference":[{"issue":"10","key":"9910_CR1","doi-asserted-by":"publisher","first-page":"183","DOI":"10.3390\/math6100183","volume":"6","author":"TF Abdelmaguid","year":"2018","unstructured":"Abdelmaguid, T.F.: An efficient mixed integer linear programming model for the minimum spanning tree problem. Mathematics 6(10), 183 (2018)","journal-title":"Mathematics"},{"key":"9910_CR2","doi-asserted-by":"crossref","unstructured":"Aziz, H., Faliszewski, P., Grofman, B. et\u00a0al.: Egalitarian committee scoring rules. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI-2018) (2018)","DOI":"10.24963\/ijcai.2018\/8"},{"key":"9910_CR3","doi-asserted-by":"crossref","unstructured":"Baumeister, D., Boes, L., Hillebrand, J.: Complexity of manipulative interference in participatory budgeting. In: Proceedings of the 7th international conference on algorithmic decision theory (ADT-2021) (2021)","DOI":"10.1007\/978-3-030-87756-9_27"},{"key":"9910_CR4","unstructured":"Botan, S., de\u00a0Haan, R., Slavkovik, M. et\u00a0al.: Egalitarian judgment aggregation. In: Proceedings of the 20th international conference on autonomous agents and multiagent systems (AAMAS-2021) (2021)"},{"issue":"3\u20134","key":"9910_CR5","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s11127-007-9165-x","volume":"132","author":"SJ Brams","year":"2007","unstructured":"Brams, S.J., Kilgour, D.M., Sanver, M.R.: A minimax procedure for electing committees. Public Choice 132(3\u20134), 401\u2013420 (2007)","journal-title":"Public Choice"},{"key":"9910_CR6","doi-asserted-by":"crossref","unstructured":"Bredereck, R., Faliszewski, P., Kaczmarczyk, A. et\u00a0al.: An experimental view on committees providing justified representation. In: Proceedings of the 28th international joint conference on artificial intelligence (IJCAI-2019) (2019)","DOI":"10.24963\/ijcai.2019\/16"},{"key":"9910_CR7","doi-asserted-by":"crossref","unstructured":"Chamberlin, J.R., Courant, P.N.: Representative deliberations and representative decisions: proportional representation and the Borda rule. The American Political Science Review, pp. 718\u2013733 (1983)","DOI":"10.2307\/1957270"},{"key":"9910_CR8","unstructured":"Chingoma, J., Endriss, U., de\u00a0Haan, R.: Simulating multiwinner voting rules in judgment aggregation. In: Proceedings of the 21st international conference on autonomous agents and multiagent systems (AAMAS-2022) (2022)"},{"key":"9910_CR9","unstructured":"Conati, A., Niskanen, A., J\u00e4rvisalo, M.: Sat-based judgment aggregation. In: Proceedings of the 2023 international conference on autonomous agents and multiagent systems (AAMAS-2023) (2023)"},{"key":"9910_CR10","unstructured":"Darmann, A., Klamler, C., Pferschy, U.: Computing spanning trees in a social choice context. In: Proceedings of the 2nd international workshop on computational social choice (COMSOC-2008) (2008)"},{"issue":"2","key":"9910_CR11","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1016\/j.mathsocsci.2009.05.002","volume":"58","author":"A Darmann","year":"2009","unstructured":"Darmann, A., Klamler, C., Pferschy, U.: Maximizing the minimum voter satisfaction on spanning trees. Math. Soc. Sci. 58(2), 238\u2013250 (2009)","journal-title":"Math. Soc. Sci."},{"key":"9910_CR12","unstructured":"Eaton, J.W., Bateman, D., Hauberg, S. et\u00a0al.: GNU Octave version 5.2.0 manual: A high-level interactive language for numerical computations (2020). https:\/\/www.gnu.org\/software\/octave\/doc\/v5.2.0\/"},{"key":"9910_CR13","doi-asserted-by":"crossref","unstructured":"Endriss, U.: Judgment aggregation. In: Brandt, F., Conitzer, V., Endriss, U., et\u00a0al. (eds.) Handbook of Computational Social Choice. chap\u00a017 (2016)","DOI":"10.1017\/CBO9781107446984.018"},{"key":"9910_CR14","unstructured":"Endriss, U.: Judgment aggregation with rationality and feasibility constraints. In: Proceedings of the 17th international conference on autonomous agents and MultiAgent systems (AAMAS-2018) (2018)"},{"key":"9910_CR15","unstructured":"Endriss, U., de\u00a0Haan, R.: Complexity of the winner determination problem in judgment aggregation: Kemeny, Slater, Tideman, Young. In: Proceedings of 14th international conference on autonomous agents and multiagent systems (AAMAS-2015) (2015)"},{"key":"9910_CR16","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1613\/jair.1.11970","volume":"69","author":"U Endriss","year":"2020","unstructured":"Endriss, U., de Haan, R., Lang, J., et al.: The complexity landscape of outcome determination in judgment aggregation. Journal of Artificial Intelligence Research 69, 687\u2013731 (2020)","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"2","key":"9910_CR17","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/s10458-011-9188-z","volume":"26","author":"B Escoffier","year":"2013","unstructured":"Escoffier, B., Gourv\u00e8s, L., Monnot, J.: Fair solutions for some multiagent optimization problems. Auton. Agent. Multi-Agent Syst. 26(2), 184\u2013201 (2013)","journal-title":"Auton. Agent. Multi-Agent Syst."},{"key":"9910_CR18","unstructured":"Everaere, P., Konieczny, S., Marquis, P.: On egalitarian belief merging. In: Proceedings of the 14th international conference on the principles of knowledge representation and reasoning (KR-2014) (2014)"},{"key":"9910_CR19","unstructured":"Everaere, P., Konieczny, S., Marquis, P.: Belief merging versus judgment aggregation. In: Proceedings of the 14th international conference on autonomous agents and MultiAgent systems (AAMAS-2015) (2015)"},{"key":"9910_CR20","doi-asserted-by":"crossref","unstructured":"Fluschnik, T., Skowron, P., Triphaus, M., et\u00a0al.: Fair knapsack. In: Proceedings of the 33rd AAAI conference on artificial intelligence (AAAI-2019) (2019)","DOI":"10.1609\/aaai.v33i01.33011941"},{"key":"9910_CR21","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H, Freeman and Company (1979)"},{"key":"9910_CR22","unstructured":"Goel, A., Krishnaswamy, A.K., Sakshuwong, S. et\u00a0al.: Knapsack voting. Collective Intelligence 1 (2015)"},{"key":"9910_CR23","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.artint.2013.05.001","volume":"199\u2013200","author":"U Grandi","year":"2013","unstructured":"Grandi, U., Endriss, U.: Lifting integrity constraints in binary aggregation. Artif. Intell. 199\u2013200, 45\u201366 (2013)","journal-title":"Artif. Intell."},{"key":"9910_CR24","doi-asserted-by":"crossref","unstructured":"Grossi, D., Pigozzi, G.: Judgment Aggregation: A Primer. Synthesis Lectures on Artificial Intelligence and Machine Learning (2014)","DOI":"10.1007\/978-3-031-01568-7"},{"key":"9910_CR25","unstructured":"de\u00a0Haan, R.: Hunting for tractable languages for judgment aggregation. In: Proceedings of the 16th international conference on principles of knowledge representation and reasoning (KR-2018) (2018)"},{"key":"9910_CR26","doi-asserted-by":"crossref","unstructured":"de\u00a0Haan, R., Slavkovik, M.: Answer set programming for judgment aggregation. In: Proceedings of the 28th international joint conference on artificial intelligence (IJCAI-2019) (2019)","DOI":"10.24963\/ijcai.2019\/231"},{"issue":"1","key":"9910_CR27","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.mathsocsci.2011.11.006","volume":"64","author":"C Klamler","year":"2012","unstructured":"Klamler, C., Pferschy, U., Ruzika, S.: Committee selection under weight constraints. Math. Soc. Sci. 64(1), 48\u201356 (2012)","journal-title":"Math. Soc. Sci."},{"issue":"2","key":"9910_CR28","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s10992-011-9175-5","volume":"40","author":"S Konieczny","year":"2011","unstructured":"Konieczny, S., Pino P\u00e9rez, R.: Logic based merging. J. Philos. Log. 40(2), 239\u2013270 (2011)","journal-title":"J. Philos. Log."},{"key":"9910_CR29","doi-asserted-by":"crossref","unstructured":"Lackner, M., Skowron, P.: Multi-Winner Voting with Approval Preferences. Springer Briefs in Intelligent Systems, Springer (2023)","DOI":"10.1007\/978-3-031-09016-5"},{"key":"9910_CR30","doi-asserted-by":"crossref","unstructured":"Lang, J., Slavkovik, M.: Judgment aggregation rules and voting rules. In: Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT-2013) (2013)","DOI":"10.1007\/978-3-642-41575-3_18"},{"issue":"2","key":"9910_CR31","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s00355-016-1006-8","volume":"48","author":"L Lang","year":"2017","unstructured":"Lang, L., Pigozzi, P., Slavkovik, M., et al.: A partial taxonomy of judgment aggregation rules and their properties. Soc. Choice Welfare 48(2), 327\u2013356 (2017)","journal-title":"Soc. Choice Welfare"},{"issue":"4","key":"9910_CR32","doi-asserted-by":"publisher","first-page":"1051","DOI":"10.1007\/s00199-021-01348-7","volume":"73","author":"K Nehring","year":"2022","unstructured":"Nehring, K., Pivato, M.: The median rule in judgement aggregation. Econ. Theor. 73(4), 1051\u20131100 (2022)","journal-title":"Econ. Theor."},{"key":"9910_CR33","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1016\/j.jet.2013.12.013","volume":"151","author":"K Nehring","year":"2014","unstructured":"Nehring, K., Pivato, M., Puppe, C.: The Condorcet set: Majority voting over interconnected propositions. Journal of Economic Theory 151, 268\u2013303 (2014)","journal-title":"Journal of Economic Theory"},{"key":"9910_CR34","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The complexity of facets (and some facets of complexity). In: Proceedings of the 14th annual ACM symposium on theory of computing (1982)","DOI":"10.1145\/800070.802199"},{"key":"9910_CR35","unstructured":"Pascual, F., Rzadca, K., Skowron, P.: Collective schedules: Scheduling meets computational social choice. In: Proceedings of the 17th international conference on autonomous agents and MultiAgent systems (AAMAS-2018) (2018)"},{"key":"9910_CR36","doi-asserted-by":"crossref","unstructured":"Rey, S., Endriss, U., de\u00a0Haan, R.: Designing participatory budgeting mechanisms grounded in judgment aggregation. In: Proceedings of the 17th international conference on principles of knowledge representation and reasoning (KR-2020) (2020)","DOI":"10.24963\/kr.2020\/71"},{"key":"9910_CR37","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1613\/jair.5628","volume":"60","author":"P Skowron","year":"2017","unstructured":"Skowron, P., Faliszewski, P.: Chamberlin-Courant rule with approval ballots: Approximating the MaxCover problem with bounded frequencies in FPT time. Journal of Artificial Intelligence Research 60, 687\u2013716 (2017)","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9910_CR38","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.artint.2015.01.003","volume":"222","author":"P Skowron","year":"2015","unstructured":"Skowron, P., Faliszewski, P., Slinko, A.M.: Achieving fully proportional representation: Approximability results. Artif. Intell. 222, 67\u2013103 (2015)","journal-title":"Artif. Intell."},{"key":"9910_CR39","doi-asserted-by":"crossref","unstructured":"Sonar, C., Dey, P., Misra, N.: On the complexity of winner verification and candidate winner for multiwinner voting rules. In: Proceedings of the 29th international joint conference on artificial intelligence (IJCAI-2020) (2020)","DOI":"10.24963\/ijcai.2020\/13"},{"key":"9910_CR40","doi-asserted-by":"crossref","unstructured":"Sreedurga, G., Ratan\u00a0Bhardwaj, M., Narahari, Y.: Maxmin participatory budgeting. In: Proceedings of the 31st international joint conference on artificial intelligence (IJCAI-22) (2022)","DOI":"10.24963\/ijcai.2022\/70"},{"key":"9910_CR41","doi-asserted-by":"crossref","unstructured":"Talmon, N., Faliszewski, P.: A framework for approval-based budgeting methods. In: Proceedings of the 33th AAAI conference on artificial intelligence (2019)","DOI":"10.1609\/aaai.v33i01.33012181"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-023-09910-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10472-023-09910-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-023-09910-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T02:03:40Z","timestamp":1734919420000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10472-023-09910-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,15]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["9910"],"URL":"https:\/\/doi.org\/10.1007\/s10472-023-09910-w","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"type":"print","value":"1012-2443"},{"type":"electronic","value":"1573-7470"}],"subject":[],"published":{"date-parts":[[2023,12,15]]},"assertion":[{"value":"29 October 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 December 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}