← 返回论文列表

在线时序投票：策略抗性、比例性与渐近分析
Online Temporal Voting: Strategyproofness, Proportionality and Asymptotic Analysis

作者: Allan Borodin, Tristan Lueger
arXiv: 2603.26504v1
分类: cs.GT
📝 论文摘要
我们研究在线时序投票，其中一组选民在多轮在线到达的备选方案集合上提交0/1批准票，每轮选择一个备选方案。我们引入了两种著名博弈论性质的在线变体：策略证明性（SP）和无关备选独立性。我们证明在线无关备选独立性（OIIA）是在线策略证明性（OSP）的充分条件，并且几种已知的在线投票规则满足OIIA，从而满足OSP，但它们不满足SP。特别地，我们展示了唯一已知满足PJR的在线投票规则——永久法格曼规则，满足OSP。而半在线投票规则——平等份额法（MES），已知满足wEJR，同样满足OSP。接着，我们引入了可操纵性代价，以量化策略行为对比例代表制保证的影响。最后，我们引入了比例代表制的渐近满足性，并证明了一种在线投票规则——序列独裁者规则，是完全策略证明的，并且满足比例合理代表制（PJR）至一个加法常数。

📊 核心分析

🎯 研究动机
研究在线时序投票(online temporal voting)场景下的策略操纵问题。背景是：在多轮投票中，选民对按序到达的候选集进行0/1批准投票，每轮需选择一个候选。现有在线投票规则可能面临策略性投票行为，但缺乏对在线环境下策略防护性(strategyproofness)和比例代表性(proportional representation)的系统分析。
🔧 核心方法
• 提出在线独立性无关备选(online independence of irrelevant alternatives, OIIA)作为在线策略防护性(online strategyproofness, OSP)的充分条件 • 分析多种已知在线投票规则（如Perpetual Phragmén、Method of Equal Shares）的OIIA/OSP性质 • 引入可操纵性代价(price of manipulability)量化策略行为对比例代表性的影响 • 提出比例代表性的渐近满足(asymptotic satisfaction)概念，并分析序列独裁(Serial Dictator)规则的渐近性质
💡 核心创新
• 首次系统定义在线投票环境下的策略防护性框架，提出OIIA→OSP的理论连接 • 发现关键理论突破：Perpetual Phragmén（已知唯一满足PJR的在线规则）满足OSP，而Method of Equal Shares（半在线规则）也满足OSP，但这些规则不满足完全策略防护性(SP) • 提出可操纵性代价新度量，首次量化策略行为对比例保证的侵蚀程度 • 证明序列独裁规则具有完全策略防护性，且能以加性常数误差满足比例合理性代表(proportional justified representation, PJR)，建立了在线规则渐近理论的新基准
🏆 总体贡献
• 建立了在线时序投票的策略防护性理论框架，为在线集体决策系统设计提供理论基础 • 揭示了在线与离线投票规则在策略防护性上的本质差异，证明OIIA是OSP的有效充分条件 • 提供了多个实用在线投票规则（Perpetual Phragmén、MES）的策略防护性保证 • 开创了比例代表性渐近分析的新研究方向，为平衡策略防护性与比例性提供了量化工具