基于候选者属性约束的委员会选举计算复杂性研究

《Displays》：Committee Elections with Candidate Attribute Constraints

本文系统研究了带候选者属性约束的委员会选举（CECAC）问题的计算复杂性。通过将混合专家（MoE）系统中的专家选择问题转化为选举模型，作者构建了基于命题逻辑表达式的属性约束框架，在经典复杂性和参数化复杂性层面获得了 dichotomy 结果，为多winner选举问题的算法设计提供了理论依据。

　　

章节精选

预备知识

带候选者属性约束的委员会选举可表示为一个五元组 E=(C,A,R,S,α)，其中 C 是候选者集合 C={c₁,c₂,…,c_m}，A 是属性集合 A={a₁,a₂,…,a_?}，R 是约束集合 R={r₁,…,r_d}，S 是收益函数 S:C→N，α 是属性函数，将候选者映射到属性的子集，即 α:C→2^A。令 α(c_i) 表示属于候选者 c_i的属性集合，每个候选者 c_i可表示为 c_i〈a_i1,…,a_i|α(ci)|〉。令 S(c_i) 表示候选者 c_i的收益，S(C) 表示总收益。

经典复杂性

本节我们研究了CECAC问题的经典计算复杂性，给出了一个 dichotomy 结果，该结果根据单个候选者关联的最大属性数 |α(c)| 和属性在所有约束中的最大出现次数 N(a) 对NP-困难情况和多项式时间可解情况进行了分类，其中 N(a) 是属性 a 或其否定形式 ā 在约束集合 R 中出现的次数。

参数化复杂性

接下来，我们研究以属性数量 ? 作为参数的CECAC问题的参数化复杂性，并获得了固定参数可解（FPT）的结果。

推论 4

CECAC问题对于委员会规模参数 k 和总收益阈值参数 p 是W[1]-困难的。

结论

本文研究了选举一个需要满足以候选者属性逻辑表达式给出的约束的委员会的问题。该问题的计算复杂性为混合专家（MoE）模型在所有专家中做出决策提供了更多方向，特别是在参数化复杂性方面。更具体地说，1）多项式时间算法有助于在MoE模型中做出有用的决策；2）困难性结果可用于指导实践。