4OR Управленческие информационные системы
An efficient heuristic search algorithm for discovering large Condorcet domains
Аннотация
Abstract 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’s alternating scheme produced the largest known CDs for $$n \le 15$$ n ≤ 15 alternatives until recent discoveries surpassed it for $$n = 8$$ n = 8 and $$n \ge 13$$ n ≥ 13 . For $$8< n < 13$$ 8 < n < 13 , 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 \le 8$$ n ≤ 8 , found new large peak-pit CDs: size 1082 (previously 1069) for $$n = 10$$ n = 10 , and 2349 (previously 2324) for $$n = 11$$ n = 11 , 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 $$8< n < 13$$ 8 < n < 13 and offer new insights into the structure of large CDs.