arXiv:2512.00616cs.GTcs.AI2025-12AAAI被引 2

证明了稳定投票在6个以下选项时是分裂循环的精化,超过6个则不成立。

Stable Voting and the Splitting of Cycles

  • 通过逻辑推理与SAT求解验证,分析投票方法中胜差排序的影响
  • 在5个及以下选项时证实猜想成立,在7个以上时给出反例
  • 该方法适用于所有基于胜差大小排序的投票机制测试

在偏好聚合中解决多数循环的算法在计算社会选择领域被广泛研究。诸如Tideman的排序对、Schulze的路径优势和Heitzig的河流等方法,都是分裂循环(SC)方法的改进,而后者通过剔除每个循环中最弱的多数胜利来解决多数循环问题。最近,Holliday和Pacuit提出了一种分裂循环的新改进方法——稳定投票(Stable Voting),以及其简化版本简单稳定投票(SSV)。他们推测:当任意两个多数胜利的规模不同时,SSV总是比SC更精细。本文在最多6个备选项下证明了该猜想,并在超过6个选项时给出了反例。5个及以下选项的证明采用传统数学推导,6个选项的证明和7个选项的反例则借助了SAT求解。支撑该证明与反例的SAT编码具有普适性,可应用于任何仅依赖于胜差大小排序的投票方法的性质检验。

原文摘要 · Abstract (English)

Algorithms for resolving majority cycles in preference aggregation have been studied extensively in computational social choice. Several sophisticated cycle-resolving methods, including Tideman's Ranked Pairs, Schulze's Beat Path, and Heitzig's River, are refinements of the Split Cycle (SC) method that resolves majority cycles by discarding the weakest majority victories in each cycle. Recently, Holliday and Pacuit proposed a new refinement of Split Cycle, dubbed Stable Voting, and a simplification thereof, called Simple Stable Voting (SSV). They conjectured that SSV is a refinement of SC whenever no two majority victories are of the same size. In this paper, we prove the conjecture up to 6 alternatives and refute it for more than 6 alternatives. While our proof of the conjecture for up to 5 alternatives uses traditional mathematical reasoning, our 6-alternative proof and 7-alternative counterexample were obtained with the use of SAT solving. The SAT encoding underlying this proof and counterexample is applicable far beyond SC and SSV: it can be used to test properties of any voting method whose choice of winners depends only on the ordering of margins of victory by size.

投票机制逻辑推理形式化验证组合优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。