arXiv:2604.19851cs.GTcs.AI2026-04被引 1

证明4人委员会在多数投票中总存在,缩小了理论差距。

Is Four Enough? Automated Reasoning Approaches and Dual Bounds for Condorcet Dimensions of Elections

  • 用混合整数规划自动搜索反例,优化对称性和无限选民建模。
  • 实验未找到需超过3人委员会的选举,暗示4人足够。
  • 通过对偶分析提出新猜想,或可证明4人必存胜出集。

在有n位选民、m名候选人的选举中,一个柯尔特塞特胜出集是大小为k的候选人组合,使得任何外部候选人均被多数选民偏好于该组合中的某成员。柯尔特塞特悖论表明,某些选举不存在单人胜出集(k=1),甚至两人也未必存在。然而,近期研究证明任意选举中都存在大小为k=5的胜出集。这留下了一个重要的理论空白:已知下界为k≥3,上界为k≤5。本文旨在缩小存在性保证与不可能性结果之间的差距。我们采用自动化推理方法,设计混合整数线性规划(MILP)以搜索可能作为反例的选举。通过对称性破除、子采样和约束生成等优化策略,有效模拟无限选民群体。同时,分析线性规划松弛的对偶问题,探索新的上界证明路径。尽管在中等规模选举上进行了广泛搜索,仍未发现需要超过3人委员会的实例。基于这些实验结果,我们简化对偶问题并提出一个猜想:若成立,则表明大小为4的胜出集始终存在。自动化推理提供了强有力的经验证据,表明多数选举的柯尔特塞特维度可能小于现有上界,至少在小规模情况下如此。本文提供了一个通用框架用于搜索排名投票中的选举,并通过对偶性开辟了一条清晰的分析路径,以证明更小委员会即可满足需求。

原文摘要 · Abstract (English)

In an election where $n$ voters rank $m$ candidates, a Condorcet winning set is a committee of $k$ candidates such that for any outside candidate, a majority of voters prefer some committee member. Condorcet's paradox shows that some elections admit no Condorcet winning sets with a single candidate (i.e., $k=1$), and the same can be shown for $k=2$. On the other hand, recent work proves that a set of size $k=5$ exists for every election. This leaves an important theoretical gap between the best known lower bound $(k\geq 3)$ and upper bound $(k \leq 5)$ for the number of candidates needed to guarantee existence. We aim to close the gap between the existence guarantees and impossibility results for Condorcet winning sets. We explore an automated reasoning approach to tighten these bounds. We design a mixed-integer linear program (MILP) to search for elections that would serve as counter-examples to conjectured bounds. We employ a number of optimizations, such as symmetry breaking, subsampling, and constraint generation, to enhance the search and model effectively infinite electorates. Furthermore, we analyze the dual of the linear programming relaxation as a path towards obtaining a new upper bound. Despite extensive search on moderate-sized elections, we fail to find any election requiring a committee larger than size 3. Motivated by our experimental results in this direction, we simplify the dual linear program and formulate a conjecture which, if true, implies that a winning set of size 4 always exists. Our automated reasoning results provide strong empirical evidence that the Condorcet dimension of any election may be smaller than currently known upper bounds, at least for small instances. We offer a general-purpose framework for searching elections in ranked voting and a new, concrete analytical path via duality toward proving that smaller committees suffice.

投票机制组合优化形式推理

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