Existence of the Core in Approval-Based Committee Elections

Agent Multi-agent Collaboration AI Safety / AI Ethics AFBD
14
2026年09月10日
我们解决了基于认可投票的多胜者选举理论中的主要开放性问题：证明了核心（core）中始终存在一个委员会。核心是一个刻画稳定性与群体公平性的概念。该证明引入了一种全新的投票规则，该规则在所有委员会及对应的支付系统上优化一个类似熵的目标函数。该目标函数的所有局部最优解均位于核心之中，从而保证了核心委员会可在多项式时间内被找到。
We settle the main open question in the theory of approval-based multi-winner elections: we show that there always exists a committee in the core. The core is a stability and group fairness concept. The proof introduces a new voting rule that optimizes an entropy-like objective function over committees and payment systems. All local optima of this objective function lie in the core, which implies that a core committee can be found in polynomial time.
许愿