标题： 基于批准的选举中近似稳定委员会的计算 显示英文标题

标题： Computation of Approximately Stable Committees in Approval-based Elections

摘要： 基于批准的委员会选择是社会选择理论中一个备受关注的模型。 在这个模型中，我们有一个选民集合$\mathcal{V}$，一个候选人集合$\mathcal{C}$，每个选民有一个批准的候选人集合$A_v \subset \mathcal{C}$。 对于任何委员会规模$K$，目标是选择$K$个候选人来代表选民的偏好。 我们研究一个称为\emph{近似稳定性}的准则，其中如果不存在另一个由至少$\frac{\lambda|T|}{k} |\mathcal{V}| $名选民偏好的委员会$T$，则委员会$\lambda$是近似稳定的。 我们证明，在这种情况下，一个$3.65$近似稳定的委员会总是存在，并且可以算法地计算出来。 我们的方法是基于寻找一个 Lindahl 均衡，并从与之相关的强 Rayleigh 分布中进行抽样。 显示英文摘要

摘要： Approval-based committee selection is a model of significant interest in social choice theory. In this model, we have a set of voters $\mathcal{V}$, a set of candidates $\mathcal{C}$, and each voter has a set $A_v \subset \mathcal{C}$ of approved candidates. For any committee size $K$, the goal is to choose $K$ candidates to represent the voters' preferences. We study a criterion known as \emph{approximate stability}, where a committee is $\lambda$-approximately-stable if there is no other committee $T$ preferred by at least $\frac{\lambda|T|}{k} |\mathcal{V}| $ voters. We prove that a $3.65$-approximately stable committee always exists and can be computed algorithmically in this setting. Our approach is based on finding a Lindahl equilibrium and sampling from a strongly Rayleigh distribution associated with it.