检验时间投票中比例代表制是否成立，发现比多候选人选举更难但有特例可高效解决。
Verifying Proportionality in Temporal Voting
- 提出在时间投票模型中验证比例代表性的方法
- 证明该问题比多候选人选举更难，复杂度更高
- 发现特定情况下可用高效算法，适合关注公平性验证的研究者
我们研究一种固定时间范围内的时序投票模型：每轮投票者对可用候选人表达偏好，并选出单一候选人。先前工作将多候选人选举中的合理代表性概念及强代表性保障的投票规则引入此模型。本文聚焦于验证给定结果是否提供比例代表性，发现时序设置下验证问题严格比多候选人选举更难，但识别出若干自然特殊情形，可在这些情形下设计出高效算法。
原文摘要 · Abstract (English)
We study a model of temporal voting where there is a fixed time horizon, and at each round the voters report their preferences over the available candidates and a single candidate is selected. Prior work has adapted popular notions of justified representation as well as voting rules that provide strong representation guarantees from the multiwinner election setting to this model. In our work, we focus on the complexity of verifying whether a given outcome offers proportional representation. We show that in the temporal setting verification is strictly harder than in multiwinner voting, but identify natural special cases that enable efficient algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。