arXiv cs.AI· Itai Zilberstein, Ruben Martins, Ratip Emin Berker·· 3 天前AI 评分23
MILP the Gap：用自动推理方法研究 Condorcet 悖论
MILP the Gap: An Automated Reasoning Approach to Condorcet's Paradox
AI 导读
研究者提出一个混合整数线性规划（MILP）框架，为固定参数 m 和 k 精确计算 Condorcet 获胜集下界，通过将选民建模为排序分布消除了对选民数 n 的依赖。该框架证明在 k ≥ 8m/9 的线性区间内，猜想中的 2/(k+1) 上界成立，首次给出与已知下界匹配的结果，并可刻画其他社会选择公理间的关系。
正文 · AI 翻译
摘要：计算社会选择研究如何将相互冲突的个人偏好聚合为集体决策，应用于选举、AI 评估/对齐以及推荐系统。我们关注这样的设定：$n$ 个投票者（例如人类评估者或算法基准）各自对 $m$ 个备选项（例如人类候选人或 AI 模型/输出）进行排序，目标是选出一个由 $k$ 个备选项组成的委员会。衡量结果（不）稳定性的一种指标是，偏好某个未被选中的备选项胜过委员会中所有备选项的投票者人数。如果该人数少于全体选民的一半，则该委员会是一个孔多塞获胜集，而当 $k \leq 2$ 时它可能不存在。更一般地，存在这样的情形：对于任意小的 $\epsilon$，任何规模为 $k$ 的委员会都至少有 $\frac{2}{(k+1)}-\epsilon$ 比例的选民偏好另一个备选项。尽管近期工作取得了显著进展缩小了这一差距，但目前尚不清楚该下界是否紧。我们开发了一个混合整数线性规划框架，用于计算固定参数值下的精确界。我们的方法仅依赖于 $m$ 和 $k$；通过将选民建模为排序上的分布，我们消除了对 $n$ 的任何依赖。我们的程序使我们能够排除任意选民规模下的反例，并获得固定 $m$ 和 $k$ 下的紧界。此外，我们的框架为证明一般上界提供了一条途径。特别地，我们展示了一个线性区间 $k \ge \frac{8m}{9}$，在该区间内，所猜想的 $\frac{2}{(k+1)}$ 上界确实成立，提供了首批与已知下界相匹配的结果。除稳定性之外，我们的框架还能刻画其他社会选择公理之间的关系，我们通过给出最小不可比性结果来加以展示。
| 评论： | 一篇题为“四个就够了吗？选举孔多塞维度的自动推理方法与对偶界”的早期版本发表于第 8 届博弈、智能体与激励研讨会（GAIW-26），该研讨会作为第 25 届国际自主智能体与多智能体系统会议研讨会的一部分举办 |
| 主题： | 计算机科学与博弈论（cs.GT）；人工智能（cs.AI） |
| 引用为： | arXiv:2604.19851 [cs.GT] |
| （或 arXiv:2604.19851v2 [cs.GT] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2604.19851 由 DataCite 颁发的 arXiv DOI |
提交历史
来自：Itai Zilberstein [查看电子邮件]
[v1]
2026 年 4 月 21 日星期二 15:25:12 UTC（59 KB）
[v2]
2026 年 10 月 10 日星期六 12:48:56 UTC（35 KB）
来源：arXiv cs.AI · arxiv.org