提出可控制选民不满次数增长的永续投票方法
Optimal bounds for dissatisfaction in perpetual voting
- 引入'有限冲突'条件，确保不满度亚线性增长
- 证明不满度增长上限为次线性，理论严格
- 基于专家建议学习框架，适合关注公平性的研究者
在永续投票中，多个决策随时间陆续作出。考虑历史决策有助于实现时间上的比例公平。本文探讨是否存在一种永续批准投票方法，能保证无选民长期频繁不满。我们识别出一个关键条件——'有限冲突'，在此条件下，不满度的亚线性增长成为可能。通过柯尔莫哥洛夫复杂性技术，我们给出了不满度增长的紧致上界。此外，发现二元选择的批准投票机制类似于预测中专家建议的学习场景，由此设计出一种在有限冲突下具有次线性不满保证的投票方法，其核心基于专家建议的标准技术。
原文摘要 · Abstract (English)
In perpetual voting, multiple decisions are made at different moments in time. Taking the history of previous decisions into account allows us to satisfy properties such as proportionality over periods of time. In this paper, we consider the following question: is there a perpetual approval voting method that guarantees that no voter is dissatisfied too many times? We identify a sufficient condition on voter behavior -- which we call 'bounded conflicts' condition -- under which a sublinear growth of dissatisfaction is possible. We provide a tight upper bound on the growth of dissatisfaction under bounded conflicts, using techniques from Kolmogorov complexity. We also observe that the approval voting with binary choices mimics the machine learning setting of prediction with expert advice. This allows us to present a voting method with sublinear guarantees on dissatisfaction under bounded conflicts, based on the standard techniques from prediction with expert advice.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。