The Complexity of Subelection Isomorphism Problems

被引：0
作者：
Faliszewski, Piotr [1 ]
Sornat, Krzysztof [1 ]
Szufa, Stanislaw [1 ,2 ]
机构：
[1] AGH University, Kraków
[2] CNRS, LAMSADE, Université Paris Dauphine-PSL
来源：
Journal of Artificial Intelligence Research | 2024年 / 80卷
基金：
欧盟地平线“2020”; 欧洲研究理事会;
关键词：
D O I：
10.1613/jair.1.15550
中图分类号：
学科分类号：
摘要：
We study extensions of the Election Isomorphism problem, focused on the existence of isomorphic subelections. Specifically, we propose the Subelection Isomorphism and the Maximum Common Subelection problems and study their computational complexity and approximability. Using our problems in experiments, we provide some insights into the nature of several statistical models of elections. ©2024 The Authors.
引用
收藏
页码：1343 / 1371
页数：28
相关论文
共 45 条
[1]  
Ahuja R., Magnanti T., Orlin J., Network Flows: Theory, Algorithms, and Applications, (1993)
[2]  
Arvind V., Kobler J., Kuhnert S., Vasudev Y., Approximate graph isomorphism, Proceedings of MFCS-12, pp. 100-111, (2012)
[3]  
Babai L., Dawar A., Schweitzer P., Toran J., The graph isomorphism problem (Dagstuhl Seminar 15511), Dagstuhl Reports, 5, 12, pp. 1-17, (2015)
[4]  
Ballester M., Haeringer G., A characterization of the single-peaked domain, Social Choice and Welfare, 36, 2, pp. 305-322, (2011)
[5]  
Bartholdi J., Trick M., Stable matching with preferences derived from a psychological model, Operations Research Letters, 5, 4, pp. 165-169, (1986)
[6]  
Berg S., Paradox of voting under an urn model: The effect of homogeneity, Public Choice, 47, 2, pp. 377-387, (1985)
[7]  
Black D., The Theory of Committees and Elections, (1958)
[8]  
Boehmer N., Bredereck R., Elkind E., Faliszewski P., Szufa S., Expected frequency matrices of elections: Computation, geometry, and preference learning, Proceedings of NeurIPS-2022, (2022)
[9]  
Boehmer N., Bredereck R., Faliszewski P., Niedermeier R., Szufa S., Putting a compass on the map of elections, Proceedings of IJCAI-21, pp. 59-65, (2021)
[10]  
Boehmer N., Cai J., Faliszewski P., Fan A., Janeczko L., Kaczmarczyk A., Was T., Properties of position matrices and their elections, Proceedings of AAAI-23, pp. 5507-5514, (2023)
12345