提出高效算法解决连续委员会选举的计算难题。
Efficient Algorithms for Electing Successive Committees
- 设计参数化算法，应对委员会选举的NP难问题。
- 在候选人数或时间范围适中时可有效求解。
- 适合关注长期公平决策的制度设计者。
在最近提出的连续委员会选举模型（Bredereck et al., AAAI-20）中，给定序数或批准偏好，目标是生成指定长度的同规模“最优”委员会序列，且每位候选人仅能出现在有限个连续委员会中。然而，该任务对多数选择标准而言，即使委员会规模为三，也已属于NP难问题，且缺乏非平凡或高效的算法。为释放该时间模型的全部潜力，本文提出参数化算法，可在候选人数适中或时间跨度有限的实际场景中高效求解这些难题。
原文摘要 · Abstract (English)
In a recently introduced model of successive committee elections (Bredereck et al., AAAI-20) for a given set of ordinal or approval preferences one aims to find a sequence of a given length of "best" same-size committees such that each candidate is a member of a limited number of consecutive committees. However, the practical usability of this model remains limited, as the described task turns out to be NP-hard for most selection criteria already for seeking committees of size three. Non-trivial or somewhat efficient algorithms for these cases are lacking too. Motivated by a desire to unlock the full potential of the described temporal model of committee elections, we devise (parameterized) algorithms that effectively solve the mentioned hard cases in realistic scenarios of a moderate number of candidates or of a limited time horizon.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。