Doklady MathematicsDoklady MathematicsДоклады Российской академии наук. Математика, информатика, процессы управления2686-95433034-5049The Russian Academy of Sciences69843910.7868/S3034504925050154MATHEMATICSМАТЕМАТИКАResearch ArticleARROW’S SINGLE-PEAKED DOMAINSОДНОПИКОВЫЕ ПО ЭРРОУ ДОМЕНЫ ПРЕДПОЧТЕНИЙKarpovA. VКарповА. Вakarpov@hse.ruHSE UniversityНациональный Исследовательский Университет Высшая Школа ЭкономикиV.A. Trapeznikov Institute of Control Sciences of Russian Academy of SciencesИнститут проблем управления имени В.А. Трапезникова Российской академии наук150920255251VOL 525, NO1 (2025)ТОМ 525, №1 (2025)10210810122025Copyright ©; 2025, Russian Academy of SciencesCopyright ©; 2025, Российская академия наук2025Russian Academy of SciencesРоссийская академия наукhttps://journals.eco-vector.com/2686-9543/article/view/698439

The paper studies structured preferences domains that avoid configuration with three different third elements in three elements restrictions (Arrow’s single-peaked domains). The number of Arrow’s single-peaked domains and the number of non-isomorphic classes of Arrow’s single-peaked domains are found. We present a forbidden submatrix characterization for matrix representation of Arrow’s single-peaked preferences.

Исследуются множества линейных порядков (домены), которые в сужении на каждую тройку альтернатив являются однопиковыми, т. е. в каждой тройке существует альтернатива никогда не стоящая на последнем месте в сужениях линейных порядков на эту тройку. Данные множества линейных порядков называются однопиковыми по Эрроу. Найдено количество однопиковых по Эрроу доменов и количество неизоморфных классов однопиковых по Эрроу доменов. Показано, что однопиковые по Эрроу домены однозначно соответствуют бинарным матрицам, не содержащих подматрицу специального вида.

binary matricessingle-peakednessdichotomous preferencesбинарные матрицыоднопиковостьдихотомические предпочтенияИсследование осуществлено в рамках Программы фундаментальных исследований НИУ ВШЭ.Akello-Egwel D., Leedham-Green C., Litterick A., Markstrom K., Riis S. Condorcet domains on at most seven alternatives // Math. Soc. Sci. 2025. V. 133. P. 23–33.Anstee R.P. Properties of (0,1)-matrices without triangles // J. Comb. Theory Ser. A. 1980. V. 29. P. 186–198.Anstee R.P. A survey of forbidden configuration results. Electron // J. Comb. 2013. V. 20(1). DS20.Durand S. Finding sharper distinctions for conditions of transitivity of the majority method // Discret. Appl. Math. 2003. V. 131. P. 577–595.Elkind E., Lackner M. Structure in dichotomous preferences // Proc. IJCAI-2015. 2015. P. 2019–2025.Karpov A.V. Structured preferences: A literature survey // Autom. Remote Control. 2022. V. 83. P. 1329–1354.Karpov A. Structure of single-peaked preferences // J. Math. Psychol. 2023. V. 117. 102817.Karpov A., Slinko A. Constructing large peak-pit Condorcet domains // Theory Decis. 2023. V. 94(1). P. 97–120.Liversidge G. Counting Condorcet domains / Arxiv preprint, math.CO. 2020. arXiv:2004.00751.Markstrom K., Riis S., Zhou B. Arrow’s single peaked domains, richness, and domains for plurality and the Borda count / Arxiv preprint, econ.TH. 2024. arXiv:2401.12547.Puppe C., Slinko A. Maximal Condorcet domains. A further progress report // Games Econ. Behav. 2024. V. 145. P. 426–450.Slinko A. Condorcet domains satisfying Arrow’s single-peakedness // J. Math. Econ. 2019. V. 84. P. 166–170.Slinko A. A combinatorial representation of Arrow’s single-peaked domains / Arxiv preprint, math.CO. 2024. arXiv:2412.05406.Terzopoulou Z., Karpov A., Obraztsova S. Restricted domains of dichotomous preferences with possibly incomplete information // Proc. AAAI-21. 2021. V. 35(6) P. 5726–5733.