Digitala Vetenskapliga Arkivet

Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Coherent domains and improved lower bounds for the maximum size of Condorcet domains
HSE University, Russian Federation; Institute of Control Sciences, Russian Academy of Sciences, Russian Federation.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Queen Mary University of London, United Kingdom.
Imperial College London, United Kingdom.
2025 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 370, p. 57-70Article in journal (Refereed) Published
Abstract [en]

In this paper, we study Condorcet domains, sets of linear orders from which majority ranking produces a linear order. We introduce a new class of Condorcet domains, called coherent domains, which is natural from both a voting theoretic and combinatorial perspective. After studying the properties of these domains we introduce set-alternating schemes. This is a method for constructing well-behaved coherent domains. Using this we show that, for sufficiently large numbers of alternatives n, there are coherent domains of size more than 2.1973n. This improves the best existing asymptotic lower bounds for the size of the largest general Condorcet domains.

Place, publisher, year, edition, pages
2025. Vol. 370, p. 57-70
Keywords [en]
Catalan numbers, Condorcet domains, Majority voting, Preference orders
National Category
Computer Sciences Mathematical sciences
Identifiers
URN: urn:nbn:se:umu:diva-237656DOI: 10.1016/j.dam.2025.03.007ISI: 001448430900001Scopus ID: 2-s2.0-86000769047OAI: oai:DiVA.org:umu-237656DiVA, id: diva2:1954086
Available from: 2025-04-23 Created: 2025-04-23 Last updated: 2025-04-23Bibliographically approved

Open Access in DiVA

fulltext(598 kB)24 downloads
File information
File name FULLTEXT01.pdfFile size 598 kBChecksum SHA-512
9d230ddce8a154ad22290bd00cd137f2d9b6d3b2dda2a81654a3faf0b43520cdb1ae654fef65c6f1e135f9e0f40ea5ed83ce8eb401953584a5b5b7bcaad62bce
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Markström, Klas
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Discrete Applied Mathematics
Computer SciencesMathematical sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 24 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 237 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf