<p>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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10288_2025_583_Article_IEq1.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">\(n \le 15\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≤</mo> <mn>15</mn> </mrow> </math></EquationSource> </InlineEquation> alternatives until recent discoveries surpassed it for <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10288_2025_583_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(n = 8\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mn>8</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10288_2025_583_Article_IEq3.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">\(n \ge 13\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>13</mn> </mrow> </math></EquationSource> </InlineEquation>. For <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10288_2025_583_Article_IEq4.gif" Format="GIF" Height="13" Rendition="HTML" Resolution="72" Type="Linedraw" Width="81" /> </InlineMediaObject> <EquationSource Format="TEX">\(8&lt; n &lt; 13\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>8</mn> <mo>&lt;</mo> <mi>n</mi> <mo>&lt;</mo> <mn>13</mn> </mrow> </math></EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10288_2025_583_Article_IEq5.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">\(n \le 8\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≤</mo> <mn>8</mn> </mrow> </math></EquationSource> </InlineEquation>, found new large peak-pit CDs: size 1082 (previously 1069) for <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10288_2025_583_Article_IEq6.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">\(n = 10\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mn>10</mn> </mrow> </math></EquationSource> </InlineEquation>, and 2349 (previously 2324) for <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10288_2025_583_Article_IEq7.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">\(n = 11\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mn>11</mn> </mrow> </math></EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10288_2025_583_Article_IEq4.gif" Format="GIF" Height="13" Rendition="HTML" Resolution="72" Type="Linedraw" Width="81" /> </InlineMediaObject> <EquationSource Format="TEX">\(8&lt; n &lt; 13\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>8</mn> <mo>&lt;</mo> <mi>n</mi> <mo>&lt;</mo> <mn>13</mn> </mrow> </math></EquationSource> </InlineEquation> and offer new insights into the structure of large CDs.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An efficient heuristic search algorithm for discovering large Condorcet domains

  • Bei Zhou,
  • Søren Riis

摘要

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.