{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,5]],"date-time":"2025-06-05T04:15:46Z","timestamp":1749096946746,"version":"3.41.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T00:00:00Z","timestamp":1737676800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T00:00:00Z","timestamp":1737676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["4OR-Q J Oper Res"],"published-print":{"date-parts":[[2025,6]]},"abstract":"Abstract<\/jats:title>\n We explore large peak-pit Condorcet domains (CD), an active research area in voting theory. The search for large CDs, defined combinatorially, serves as a benchmark for heuristic-based optimisation algorithms. Since 1996, Fishburn\u2019s alternating scheme produced the largest known CDs for \n \n $$n \\le 15$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n \u2264<\/mml:mo>\n 15<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> alternatives until recent discoveries surpassed it for \n \n $$n = 8$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n =<\/mml:mo>\n 8<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and \n \n $$n \\ge 13$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n \u2265<\/mml:mo>\n 13<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. For \n \n $$8< n < 13$$<\/jats:tex-math>\n \n \n 8<\/mml:mn>\n <<\/mml:mo>\n n<\/mml:mi>\n <<\/mml:mo>\n 13<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, exhaustive searches are infeasible, necessitating the design of heuristic methods. We developed a novel algorithm using a specially designed heuristic function and a 5-alternative subset lookup database to obtain new record-size CDs in this critical range. This approach, distinct from existing methods used for \n \n $$n \\le 8$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n \u2264<\/mml:mo>\n 8<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, found new large peak-pit CDs: size 1082 (previously 1069) for \n \n $$n = 10$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n =<\/mml:mo>\n 10<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, and 2349 (previously 2324) for \n \n $$n = 11$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n =<\/mml:mo>\n 11<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, establishing new lower bounds for these cases. Notably, these new CDs hold restrictions of remarkably small size. These findings fill a significant gap in our knowledge of CDs on \n \n $$8< n < 13$$<\/jats:tex-math>\n \n \n 8<\/mml:mn>\n <<\/mml:mo>\n n<\/mml:mi>\n <<\/mml:mo>\n 13<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and offer new insights into the structure of large CDs.<\/jats:p>","DOI":"10.1007\/s10288-025-00583-1","type":"journal-article","created":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T20:18:26Z","timestamp":1737749906000},"page":"193-216","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An efficient heuristic search algorithm for discovering large Condorcet domains"],"prefix":"10.1007","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-8365-3629","authenticated-orcid":false,"given":"Bei","family":"Zhou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S\u00f8ren","family":"Riis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,24]]},"reference":[{"issue":"4","key":"583_CR1","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1137\/0605057","volume":"5","author":"JM Abello","year":"1984","unstructured":"Abello JM, Johnson CR (1984) How large are transitive simple majority domains? SIAM J Algebr Discrete Methods 5(4):603\u2013618","journal-title":"SIAM J Algebr Discrete Methods"},{"key":"583_CR2","doi-asserted-by":"crossref","unstructured":"Akello-Egwel D, Leedham-Green C, Litterick A, Markstr\u00f6m K, Riis S (2024) Condorcet domains on at most seven alternatives. Math Soc Sci","DOI":"10.1016\/j.mathsocsci.2024.12.002"},{"key":"583_CR3","volume-title":"Social choice and individual values","author":"KJ Arrow","year":"1963","unstructured":"Arrow KJ (1963) Social choice and individual values, vol 12, 2nd edn. Yale University Press","edition":"2"},{"key":"583_CR4","doi-asserted-by":"crossref","unstructured":"Barrett T, Clements W, Foerster J, Lvovsky A (2020) Exploratory combinatorial optimization with reinforcement learning. In: Proceedings of the AAAI conference on artificial intelligence, vol\u00a034, pp 3243\u20133250","DOI":"10.1609\/aaai.v34i04.5723"},{"issue":"3731","key":"583_CR5","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1126\/science.153.3731.34","volume":"153","author":"R Bellman","year":"1966","unstructured":"Bellman R (1966) Dynamic programming. Science 153(3731):34\u201337","journal-title":"Science"},{"issue":"7\u20138","key":"583_CR6","doi-asserted-by":"publisher","first-page":"933","DOI":"10.1016\/j.dam.2011.08.001","volume":"160","author":"VI Danilov","year":"2012","unstructured":"Danilov VI, Karzanov AV, Koshevoy G (2012) Condorcet domains of tiling type. Discrete Appl Math 160(7\u20138):933\u2013940","journal-title":"Discrete Appl Math"},{"key":"583_CR7","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s11083-011-9235-z","volume":"30","author":"VI Danilov","year":"2013","unstructured":"Danilov VI, Koshevoy GA (2013) Maximal Condorcet domains. Order 30:181\u2013194","journal-title":"Order"},{"key":"583_CR8","unstructured":"Dittrich T (2018) Eine vollst\u00e4ndige klassifikation von condorcet domains f\u00fcr kleine alternativenmengen (Unpublished doctoral dissertation). KIT-Bibliothek"},{"issue":"2","key":"583_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4018\/IJRSDA.2018040101","volume":"5","author":"MA El-Shorbagy","year":"2018","unstructured":"El-Shorbagy MA, Hassanien AE (2018) Particle swarm optimization from theory to applications. Int J Rough Sets Data Anal (IJRSDA) 5(2):1\u201324","journal-title":"Int J Rough Sets Data Anal (IJRSDA)"},{"issue":"7930","key":"583_CR10","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1038\/s41586-022-05172-4","volume":"610","author":"A Fawzi","year":"2022","unstructured":"Fawzi A, Balog M, Huang A, Hubert T, Romera-Paredes B, Barekatain M et al (2022) Discovering faster matrix multiplication algorithms with reinforcement learning. Nature 610(7930):47\u201353","journal-title":"Nature"},{"issue":"1","key":"583_CR11","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s003550050055","volume":"14","author":"P Fishburn","year":"1996","unstructured":"Fishburn P (1996) Acyclic sets of linear orders. Soc Choice Welfare 14(1):113\u2013124","journal-title":"Soc Choice Welfare"},{"key":"583_CR12","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/s003550100120","volume":"19","author":"PC Fishburn","year":"2002","unstructured":"Fishburn PC (2002) Acyclic sets of linear orders: a progress report. Soc Choice Welfare 19:431\u2013447","journal-title":"Soc Choice Welfare"},{"issue":"2","key":"583_CR13","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00355-007-0228-1","volume":"30","author":"A Galambos","year":"2008","unstructured":"Galambos A, Reiner V (2008) Acyclic sets of linear orders via the Bruhat orders. Soc Choice Welfare 30(2):245\u2013264","journal-title":"Soc Choice Welfare"},{"issue":"9","key":"583_CR14","doi-asserted-by":"publisher","first-page":"1329","DOI":"10.1134\/S0005117922090016","volume":"83","author":"A Karpov","year":"2022","unstructured":"Karpov A (2022) Structured preferences: a literature survey. Autom Remote Control 83(9):1329\u20131354","journal-title":"Autom Remote Control"},{"key":"583_CR15","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s11083-022-09612-8","volume":"40","author":"A Karpov","year":"2022","unstructured":"Karpov A, Slinko A (2022) Symmetric maximal Condorcet domains. Order 40:289\u2013309","journal-title":"Order"},{"issue":"1","key":"583_CR16","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s11238-022-09878-9","volume":"94","author":"A Karpov","year":"2023","unstructured":"Karpov A, Slinko A (2023) Constructing large peak-pit Condorcet domains. Theor Decis 94(1):97\u2013120","journal-title":"Theor Decis"},{"key":"583_CR17","unstructured":"Karpov A, Markstr\u00f6m K, Riis S, Zhou B (2023) Set-alternating schemes: a new class of large Condorcet domains. arXiv preprint arXiv:2308.02817"},{"key":"583_CR18","unstructured":"Karpov A, Markstr\u00f6m K, Riis S, Zhou B (2024) Local diversity of Condorcet domains. arXiv preprint arXiv:2401.11912"},{"key":"583_CR19","unstructured":"King T, Butcher S, Zalewski L (2021) Apocrita\u2014high performance computing cluster for queen Mary university of London (2017). Accessed 5 Feb"},{"key":"583_CR20","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s00355-017-1033-0","volume":"48","author":"M-L Lackner","year":"2017","unstructured":"Lackner M-L, Lackner M (2017) On the likelihood of single-peaked preferences. Soc Choice Welfare 48:717\u2013745","journal-title":"Soc Choice Welfare"},{"key":"583_CR21","unstructured":"Laterre A, Fu Y, Jabri MK, Cohen A-S, Kas D, Hajjar K, Beguir K (2018) Ranked reward: Enabling self-play reinforcement learning for combinatorial optimization. arXiv preprint arXiv:1807.01672"},{"key":"583_CR22","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/s10732-023-09512-z","volume":"29","author":"J Lauri","year":"2023","unstructured":"Lauri J, Dutta S, Grassia M, Ajwani D (2023) Learning fine-grained search space pruning and heuristics for combinatorial optimization. J Heuristics 29:313\u2013347","journal-title":"J Heuristics"},{"issue":"1","key":"583_CR23","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s00355-023-01481-3","volume":"62","author":"C Leedham-Green","year":"2024","unstructured":"Leedham-Green C, Markstr\u00f6m K, Riis S (2024) The largest Condorcet domain on 8 alternatives. Soc Choice Welfare 62(1):109\u2013116","journal-title":"Soc Choice Welfare"},{"issue":"7964","key":"583_CR24","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1038\/s41586-023-06004-9","volume":"618","author":"DJ Mankowitz","year":"2023","unstructured":"Mankowitz DJ, Michi A, Zhernov A, Gelmi M, Selvi M, Paduraru C et al (2023) Faster sorting algorithms discovered using deep reinforcement learning. Nature 618(7964):257\u2013263","journal-title":"Nature"},{"key":"583_CR25","unstructured":"Markstr\u00f6m K, Riis S, Zhou B (2024) Arrow\u2019s single peaked domains, richness, and domains for plurality and the Borda count. arXiv preprint arXiv:2401.12547"},{"key":"583_CR26","doi-asserted-by":"publisher","first-page":"105400","DOI":"10.1016\/j.cor.2021.105400","volume":"134","author":"N Mazyavkina","year":"2021","unstructured":"Mazyavkina N, Sviridov S, Ivanov S, Burnaev E (2021) Reinforcement learning for combinatorial optimization: a survey. Comput Oper Res 134:105400","journal-title":"Comput Oper Res"},{"issue":"7540","key":"583_CR27","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1038\/nature14236","volume":"518","author":"V Mnih","year":"2015","unstructured":"Mnih V, Kavukcuoglu K, Silver D, Rusu AA, Veness J, Bellemare MG et al (2015) Human-level control through deep reinforcement learning. Nature 518(7540):529\u2013533","journal-title":"Nature"},{"key":"583_CR28","unstructured":"Mnih V, Badia AP, Mirza M, Graves A, Lillicrap T, Harley T, Kavukcuoglu K (2016) Asynchronous methods for deep reinforcement learning. In: International conference on machine learning, pp 1928\u20131937"},{"key":"583_CR29","doi-asserted-by":"crossref","unstructured":"Monjardet B (2009) Acyclic domains of linear orders: a survey. In: The mathematics of preference, choice and order: essays in honor of Peter C. Fishburn, pp 139\u2013160","DOI":"10.1007\/978-3-540-79128-7_8"},{"key":"583_CR30","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1016\/j.geb.2024.04.001","volume":"145","author":"C Puppe","year":"2024","unstructured":"Puppe C, Slinko A (2024) Maximal Condorcet domains a further progress report. Games Econ Behav 145:426\u2013450","journal-title":"Games Econ Behav"},{"key":"583_CR31","doi-asserted-by":"crossref","unstructured":"Radhakrishnan A, Jeyakumar G (2021) Evolutionary algorithm for solving combinatorial optimization\u2014a review. In: Innovations in computer science and engineering: proceedings of 8th ICICSE, pp 539\u2013545","DOI":"10.1007\/978-981-33-4543-0_57"},{"key":"583_CR32","volume-title":"Paradoxical results from Inada\u2019s conditions for majority rule","author":"H Raynaud","year":"1981","unstructured":"Raynaud H (1981) Paradoxical results from Inada\u2019s conditions for majority rule. Institute for Mathematical Studies in the Social Sciences, Stanford University"},{"key":"583_CR33","volume-title":"The individual freedom allowed by the value restriction condition","author":"H Raynaud","year":"1982","unstructured":"Raynaud H (1982) The individual freedom allowed by the value restriction condition. Institute for Mathematical Studies in the Social Sciences"},{"key":"583_CR34","unstructured":"Schulman J, Wolski F, Dhariwal P, Radford A, Klimov O (2017) Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347"},{"issue":"2","key":"583_CR35","doi-asserted-by":"publisher","first-page":"491","DOI":"10.2307\/1909947","volume":"34","author":"AK Sen","year":"1966","unstructured":"Sen AK (1966) A Possibility theorem on majority decisions. Econometrica 34(2):491\u2013499","journal-title":"Econometrica"},{"issue":"6419","key":"583_CR36","doi-asserted-by":"publisher","first-page":"1140","DOI":"10.1126\/science.aar6404","volume":"362","author":"D Silver","year":"2018","unstructured":"Silver D, Hubert T, Schrittwieser J, Antonoglou I, Lai M, Guez A et al (2018) A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science 362(6419):1140\u20131144","journal-title":"Science"},{"key":"583_CR37","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.jmateco.2019.08.001","volume":"84","author":"A Slinko","year":"2019","unstructured":"Slinko A (2019) Condorcet domains satisfying arrow\u2019s single-peakedness. J Math Econ 84:166\u2013175","journal-title":"J Math Econ"},{"key":"583_CR38","doi-asserted-by":"crossref","unstructured":"Slinko A (2024) A family of condorcet domains that are single-peaked on a circle. Soc Choice Welfare 1\u201311","DOI":"10.1007\/s00355-024-01520-7"},{"key":"583_CR39","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00992698","volume":"8","author":"CJ Watkins","year":"1992","unstructured":"Watkins CJ, Dayan P (1992) Q-learning. Mach Learn 8:279\u2013292","journal-title":"Mach Learn"},{"key":"583_CR40","unstructured":"Zhou B, Riis S (2022) Impartial games: a challenge for reinforcement learning. arXiv preprint arXiv:2205.12787"},{"key":"583_CR41","doi-asserted-by":"publisher","first-page":"101951","DOI":"10.1016\/j.softx.2024.101951","volume":"28","author":"B Zhou","year":"2024","unstructured":"Zhou B, Markstr\u00f6m K, Riis S (2024) CDL: a fast and flexible library for the study of permutation sets with structural restrictions. SoftwareX 28:101951","journal-title":"SoftwareX"}],"container-title":["4OR"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-025-00583-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10288-025-00583-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-025-00583-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T18:08:48Z","timestamp":1749060528000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10288-025-00583-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,24]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["583"],"URL":"https:\/\/doi.org\/10.1007\/s10288-025-00583-1","relation":{},"ISSN":["1619-4500","1614-2411"],"issn-type":[{"type":"print","value":"1619-4500"},{"type":"electronic","value":"1614-2411"}],"subject":[],"published":{"date-parts":[[2025,1,24]]},"assertion":[{"value":"13 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 December 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 December 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 January 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}