研究动态投票下公共事务决策的公平性与计算复杂性。
Not in My Backyard! Temporal Voting Over Public Chores
- 构建时间动态投票模型，分析公众对公共事务的偏好变化
- 证明最小化平等福利在多数情况下计算困难，但特定场景可解
- 揭示时间公平性对社会总福利的影响，适合政策设计者参考
我们研究一种时间动态投票模型，其中选民对一系列公共事务（即惠及社会但对个体造成成本的项目）具有随时间变化的偏好。本文探讨了优化功利主义与平等主义福利的计算复杂性。结果表明，功利主义最优在计算上是简单的，而最小化平等主义福利即使在极受限的情况下也属于计算难问题。然而，我们识别出若干能高效求解该问题的场景，包括精确解法与近似算法。此外，我们考察了强制时间公平性的效果及其对社会福利的影响，并分析了在线算法的竞争比。最后，我们研究了代理人的策略行为，揭示了此类决策环境中潜在的操纵风险，并讨论了多种公平性度量在此场景下的适用性。
原文摘要 · Abstract (English)
We study a temporal voting model where voters have dynamic preferences over a set of public chores -- projects that benefit society, but impose individual costs on those affected by their implementation. We investigate the computational complexity of optimizing utilitarian and egalitarian welfare. Our results show that while optimizing the former is computationally straightforward, minimizing the latter is computationally intractable, even in very restricted cases. Nevertheless, we identify several settings where this problem can be solved efficiently, either exactly or by an approximation algorithm. We also examine the effects of enforcing temporal fairness and its impact on social welfare, and analyze the competitive ratio of online algorithms. We then explore the strategic behavior of agents, providing insights into potential malfeasance in such decision-making environments. Finally, we discuss a range of fairness measures and their suitability for our setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。