×

Small one-dimensional Euclidean preference profiles. (English) Zbl 1479.91103

Summary: We characterize one-dimensional Euclidean preference profiles with a small number of alternatives and voters. We show that every single-peaked preference profile with two voters is one-dimensional Euclidean, and that every preference profile with up to five alternatives is one-dimensional Euclidean if and only if it is both single-peaked and single-crossing. By the work of J. Chen et al. [ibid. 48, No. 2, 409–432 (2017; Zbl 1392.91025)], we thus obtain that the smallest single-peaked and single-crossing preference profiles that are not one-dimensional Euclidean consist of three voters and six alternatives.

MSC:

91B08 Individual preferences
91B14 Social choice
91B86 Mathematical economics and fuzziness

Citations:

Zbl 1392.91025
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ballester, MÁ; Haeringer, G., A characterization of the single-peaked domain, Soc Choice Welfare, 36, 2, 305-322 (2011) · Zbl 1232.91150 · doi:10.1007/s00355-010-0476-3
[2] Black, D., On the rationale of group decision making, J Polit Econ, 56, 1, 23-34 (1948) · doi:10.1086/256633
[3] Black, D., The theory of committees and elections (1958), Cambridge: Cambridge University Press, Cambridge · Zbl 0091.15706
[4] Bogomolnaia, A.; Laslier, J-F, Euclidean preferences, J Math Econ, 43, 2, 87-98 (2007) · Zbl 1280.91052 · doi:10.1016/j.jmateco.2006.09.004
[5] Borg, I.; Groenen, PJ; Mair, P., Applied multidimensional scaling and unfolding (2018), Berlin: Springer, Berlin · Zbl 1409.62006 · doi:10.1007/978-3-319-73471-2
[6] Brams, SJ; Jones, MA; Kilgour, DM, Single-peakedness and disconnected coalitions, J Theor Polit, 14, 3, 359-383 (2002) · doi:10.1177/095169280201400304
[7] Bredereck, R.; Chen, J.; Woeginger, GJ, A characterization of the single-crossing domain, Soc Choice Welfare, 41, 4, 989-998 (2013) · Zbl 1288.91049 · doi:10.1007/s00355-012-0717-8
[8] Bredereck, R.; Chen, J.; Woeginger, GJ, Are there any nicely structured preference profiles nearby?, Math Soc Sci, 79, 61-73 (2016) · Zbl 1347.91128 · doi:10.1016/j.mathsocsci.2015.11.002
[9] Bulteau L, Chen J (2020) On the border between Euclidian and non-Euclidean preference profiles in \(d\)-dimension. working paper
[10] Chen J (2016) Exploiting structure in computationally hard voting problems. PhD thesis, Technical University of Berlin, Germany
[11] Chen, J.; Finnendahl, UP, On the number of single-peaked narcissistic or single-crossing narcissistic preferences, Discrete Math, 341, 5, 1225-1236 (2018) · Zbl 1410.91180 · doi:10.1016/j.disc.2018.01.008
[12] Chen, J.; Pruhs, K.; Woeginger, GJ, The one-dimensional Euclidean domain: finitely many obstructions are not enough, Soc Choice Welfare, 48, 2, 409-432 (2017) · Zbl 1392.91025 · doi:10.1007/s00355-016-1011-y
[13] Coombs, CH, A theory of data (1964), Hoboken: Wiley, Hoboken
[14] Doignon, J.; Falmagne, J., A polynomial time algorithm for unidimensional unfolding representations, J Algorithms, 16, 2, 218-233 (1994) · Zbl 0797.68081 · doi:10.1006/jagm.1994.1010
[15] Downs, A., An economic theory of democracy (1957), Manhattan: Harper and Row, Manhattan
[16] Elkind E, Faliszewski P (2014) Recognizing 1-Euclidean preferences: an alternative approach. In Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT ’14), volume 8768 of Lecture Notes in Computer Science, pp 146-157. Springer · Zbl 1403.91130
[17] Elkind E, Faliszewski P, Slinko A (2012) Clone structures in voters’ preferences. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC ’12), pp 496-513. ACM Press
[18] Elkind E, Lackner M, Peters D (2017) Structured preferences. In: Endriss U (ed) Trends in computational social choice. AI Access
[19] Escoffier B, Lang J, Öztürk M (2008) Single-peaked consistency and its complexity. In: Proceedings of the 18th European Conference on Artificial Intelligence (ECAI ’08), pp 366-370. IOS Press
[20] Gall FL (2014) Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC ’14), pp 296-303. ACM · Zbl 1325.65061
[21] Hotelling, H., Stability in competition, Econ J, 39, 153, 41-57 (1929) · doi:10.2307/2224214
[22] Knoblauch, V., Recognizing one-dimensional Euclidean preference profiles, J Math Econ, 46, 1, 1-5 (2010) · Zbl 1197.91077 · doi:10.1016/j.jmateco.2009.05.007
[23] Lackner, M-L; Lackner, M., On the likelihood of single-peaked preferences, Soc Choice Welfare, 48, 4, 717-745 (2017) · Zbl 1392.91026 · doi:10.1007/s00355-017-1033-0
[24] Lekkerkerker, CG; Boland, JC, Representation of finite graphs by a set of intervals on the real line, Fundamenta Mathematicae, 51, 45-64 (1962) · Zbl 0105.17501 · doi:10.4064/fm-51-1-45-64
[25] Mirrlees, JA, An exploration in the theory of optimal income taxation, Rev Econ Stud, 38, 175-208 (1971) · Zbl 0222.90028 · doi:10.2307/2296779
[26] Peters D (2017) Recognising multidimensional euclidean preferences. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI ’17), pp 642-648
[27] Roberts, KW, Voting over income tax schedules, J Public Econ, 8, 3, 329-340 (1977) · doi:10.1016/0047-2727(77)90005-6
[28] Schönhage, A.; Strassen, V., Schnelle multiplikation großer zahlen, Computing, 7, 3-4, 281-292 (1971) · Zbl 0223.68007 · doi:10.1007/BF02242355
[29] Stokes, DE, Spatial models of party competition, Am Polit Sci Rev, 57, 368-377 (1963) · doi:10.2307/1952828
[30] Tucker, A., A structure theorem for the consecutive \(1\)’s property, J Combin Theory Ser B, 12, 153-162 (1972) · Zbl 0208.52402 · doi:10.1016/0095-8956(72)90019-6
[31] van den Brand J (2020) A deterministic linear program solver in current matrix multiplication time. In: Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’20), pp 259-278 · Zbl 07304039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.