The Complexity of Sub election Isomorphism Problems

被引：0

作者：

Faliszewski, Piotr ^{[1
]}

Sornat, Krzysztof ^{[1
]}

Szufa, Stanislaw ^{[1
,2
]}

机构：

[1] AGH Univ Sci & Technol, Krakow, Poland

[2] Univ Paris 09, CNRS, LAMSADE, PSL, Paris, France

来源：

JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH | 2024年 / 80卷

基金：

欧洲研究理事会; 瑞士国家科学基金会;

关键词：

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We study extensions of the Election Isomorphism problem, focused on the existence of isomorphic sub elections. 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.

引用

页码：1343 / 1371

页数：29

共 45 条

[1] Ahuja R.K., 1993, Network Flows
[2] Arvind V, 2012, LECT NOTES COMPUT SC, V7464, P100, DOI 10.1007/978-3-642-32589-2_12
[3] Babai L., 2015, Dagstuhl Reports, V5, P1
[4] A characterization of the single-peaked domain
Ballester, Miguel A.
Haeringer, Guillaume
[J]. SOCIAL CHOICE AND WELFARE, 2011, 36 (02) : 305 - 322
[5] STABLE MATCHING WITH PREFERENCES DERIVED FROM A PSYCHOLOGICAL MODEL
BARTHOLDI, J
TRICK, MA
[J]. OPERATIONS RESEARCH LETTERS, 1986, 5 (04) : 165 - 169
[6] PARADOX OF VOTING UNDER AN URN MODEL - THE EFFECT OF HOMOGENEITY
BERG, S
[J]. PUBLIC CHOICE, 1985, 47 (02) : 377 - 387
[7] Black D., 1958, THEORY COMMITTEES EL
[8] Boehmer N., 2023, AAMAS, P1706
[9] Boehmer N, 2022, ADV NEUR IN
[10] Boehmer N, 2023, AAAI CONF ARTIF INTE, P5507

← 1 2 3 4 5 →