提出可高效验证的公平选举准则FJR+，解决传统方法难验证问题。
Strengthening Full Justified Representation: Efficient Verification and Computation
- 设计新公平准则FJR+，支持多项式时间验证与计算
- 证明RBG算法生成的委员会任一补全均满足FJR+
- 适用于预算分配、价格可计算场景，适合制度设计者参考
全公正代表（FJR）是批准型委员会选举中最强的可满足比例性公理之一。尽管已有研究证明可在多项式时间内找到满足FJR的委员会，但验证一个给定委员会是否满足FJR仍属于coNP完全问题。本文提出严格强化版FJR+，其验证与满足均可在多项式时间内完成。分析残余预算贪心算法（RBG），证明其生成的部分委员会，其任意大小为k的补全均满足FJR+。该自由度使我们可采用顺序Phragmén法获得价格可计算的补全结果。所提规则始终满足FJR+与子核心，并在至少有k个候选人获得支持时具备价格可计算性。此外，还构建了基于Droop配额的FJR+版本。最后，将FJR+扩展至具有任意项目成本的批准型参与式预算。项目特定的RBG算法可在多项式时间内实现此性质，并可继续生成满足成本型子核心的价格可计算结果。
原文摘要 · Abstract (English)
Full justified representation (FJR) is among the strongest known satisfiable proportionality axioms for approval-based committee elections. Recent work has shown that an FJR committee can be found in polynomial time, but verifying whether a given committee satisfies FJR remains coNP-complete. We introduce FJR+, a strict strengthening of FJR and EJR+ that can be verified and satisfied in polynomial time. We then analyze the Residual-Budget Greedy (RBG) algorithm and prove that it selects a partial committee such that every size-$k$ completion satisfies FJR+. This freedom allows us to use sequential Phragmén to obtain a priceable completion. The resulting rule always satisfies FJR+ and the sub-core, and it is priceable whenever at least $k$ candidates receive an approval. We also obtain a Droop-quota version of FJR+. Finally, we extend FJR+ to approval-based participatory budgeting with arbitrary project costs. A project-specific version of RBG computes this property in polynomial time and can be continued to a priceable outcome satisfying a cost-based version of the sub-core.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。