研究时间投票中比例代表制的效率代价，发现其损失随时间增长但增速放缓。
The Price of Proportional Representation in Temporal Voting
- 通过最大福利与比例约束下最大福利之比，量化比例代表的效率损失。
- 比例代表导致福利损失随选民数或轮次增加而上升，但增速小于线性。
- 弱比例公理（如JR）在长期可趋近无损失，强公理则始终存在冲突。
我们研究了在固定时间跨度内反复进行集体决策的时间投票模型中的比例代表问题。已有研究广泛探讨了多赢投票中的比例代表公理（如公正代表，JR及其变体）如何适应、满足与验证。然而，这些公理与社会福利之间的关系仍不清晰。本文通过最大可达效用福利与满足比例公理时的最大福利之比，形式化了福利与比例之间的权衡。我们证明，在时间设置中强制比例代表会导致福利损失随选民数量或轮次数增长而上升，但该增长为亚线性。进一步发现，不同公理间存在清晰分界：对于JR，福利损失随时间增长而减小，并在极限下消失；而对于更强的公理，这种冲突即使在大量轮次下仍持续存在。此外，我们证明在每种公理下的福利最大化问题在静态偏好和有界审批下仍为NP完全且APX难解，并在若干自然结构参数下提供了固定参数可解算法。
原文摘要 · Abstract (English)
We study proportional representation in the temporal voting model, where collective decisions are made repeatedly over time over a fixed horizon. Prior work has extensively investigated how proportional representation axioms from multiwinner voting (e.g., justified representation (JR) and its variants) can be adapted, satisfied, and verified in this setting. However, much less is understood about their interaction with social welfare. In this work, we quantify the efficiency cost of enforcing proportionality. We formalize the welfare-proportionality tension via the worst-case ratio between the maximum achievable utilitarian welfare and the maximum welfare attainable subject to a proportionality axiom. We show that imposing proportional representation in the temporal setting can incur a growing, yet sublinear, welfare loss as the number of voters or rounds increases. We further identify a clean separation among axioms: for JR, the welfare loss diminishes as the time horizon grows and vanishes asymptotically, whereas for stronger axioms this conflict persists even with many rounds. Moreover, we prove that welfare maximization under each axiom is NP-complete and APX-hard, even under static preferences and bounded-degree approvals, and provide fixed-parameter algorithms under several natural structural parameters.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。