References & Citations
Computer Science > Discrete Mathematics
Title: A heuristic search algorithm for discovering large Condorcet domains
(Submitted on 12 Mar 2023 (v1), last revised 26 Apr 2024 (this version, v4))
Abstract: The study of large Condorcet domains (CD) has been a significant area of interest in voting theory. In this paper, our goal is to search for large CDs that are hitherto unknown. With a straightforward combinatorial definition, searching for large CDs is naturally suited for algorithmic optimisations. For each value of n>2, one can ask for the size of the largest CD, thus finding the largest CDs provides an important benchmark for heuristic-based combinatorial optimisation algorithms. Despite extensive research over the past three decades, the CD sizes identified in 1996 remain the best known for many values of n. When n>8, conducting an exhaustive search becomes computationally unfeasible, thereby prompting the use of heuristic methods. To address this, we developed a novel heuristic search algorithm in which a specially designed heuristic function, backed by a lookup database, directs the search towards promising branches in the search tree. Our algorithm found new large CDs of size 1082 (surpassing the previous record of 1069) for n=10, and 2349 (improving the previous 2324) for n=11. Notably, these newly discovered CDs exhibit characteristics distinct from those of known CDs.
Submission history
From: Bei Zhou Mr [view email][v1] Sun, 12 Mar 2023 00:14:20 GMT (30kb)
[v2] Wed, 25 Oct 2023 07:33:41 GMT (61kb)
[v3] Sun, 14 Jan 2024 12:10:05 GMT (64kb)
[v4] Fri, 26 Apr 2024 09:00:52 GMT (62kb)
Link back to: arXiv, form interface, contact.