Computing Thiele Rules on Interval Elections and Their Generalizations¶

会议: NeurIPS 2026
arXiv: 2605.03067
领域: 其他
关键词: 计算社会选择, Thiele规则, 赞同式委员会选举, 结构化偏好, 线性规划松弛

一句话总结¶

本文证明了在选民-候选人区间（VCI）域和线性一致（LC）域上，计算所有广义 Thiele 规则的 LP 松弛均存在多项式时间可求的整数最优解，并在 PAV 等递减正权重规则下证明所有最优极值点均为整数，同时证明了树表示域下的 NP-完全性。

研究背景与动机¶

在基于赞同的多胜者委员会投票（approval-based committee voting）中，选民提交对候选人子集的赞同选票，投票规则需选出固定规模 $k$ 的委员会以最大化整体代表性与社会福利。在众多规则中，由 Thiele 于 1895 年提出的 Thiele 规则族（尤其是比例赞同投票 PAV）占据核心地位，具有拓展合理代表性（EJR）、最优比例度以及核心稳定性（core stability）等极佳公理化性质。然而，Thiele 规则在实际应用中面临一道难以逾越的计算障碍：除简单赞同投票（AV）外，包括 PAV 和 Chamberlin-Courant（CC）在内的几乎所有 Thiele 规则在一般偏好下均为 NP-难问题。

为绕过这一复杂度下界，社会选择理论学者通常寄希望于受限偏好域（restricted domains）。Peters (2018) 曾证明，在候选人区间（Candidate Interval, CI）域上，Thiele 规则的整数规划松弛具有全单模（totally unimodular, TUM）约束矩阵，从而可在多项式时间内精确求解；然而令人意外的是，这一全单模性在对称的选民区间（Voter Interval, VI）域上完全失效，其约束矩阵甚至会出现行列式绝对值大于 1 的子矩阵。自 2015 年起，VI 域及其超类——选民-候选人区间（VCI）域上 Thiele 规则的计算复杂度一直被反复提出并悬而未决，成为计算社会选择领域的著名公开难题。

本文的切入角度是：约束矩阵不具备全单模性，并不意味着线性规划松弛的最优解集合中不存在整数解。只要能在松弛解中识别出“非全单模性”的根源并加以消除，就能重新回归多项式可解子空间。本文的核心 idea 是：虽然 VCI 矩阵的 LP 松弛非全单模，但其非全单模结构完全由支配候选人引发；通过多项式步权重转移消除支配候选人后，残差实例必然落在无支配的 CI 域上，从而诱导出 LP 的最优整数解，并将该多项式时间算法进一步推广至严格包含 VCI 的线性一致（LC）域。

方法详解¶

整体框架¶

算法的核心目标是求解给定赞同矩阵 $A \in \mathcal{A}^{\text{VCI}}$（或 $\mathcal{A}^{\text{LC}}$）、委员会规模 $k$ 与选民个性化非递增非负权重 $w=(w^i)_{i \in [n]}$ 下的 Thiele 胜者确定问题。整体流水线分为三步：首先求解 Peters (2018) 建立的标准 LP 松弛，获得可能包含分数的初始最优解；随后执行贪心权重转移，将支配候选人之间的分数权重由被支配者单向推给支配者，直至残差候选人诱导的子矩阵无支配关系；最后利用“无支配 VCI/LC 矩阵必为 CI 矩阵”的关键图论结构引理，将残差问题转化为全单模 CI 实例并通过多项式时间求解得到最优整数委员会。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：赞同矩阵 A、委员会规模 k、权重向量 w"] --> B["阶段 1：求解标准 LP 松弛<br/>解线性规划得到最优解 (x, y)"]
    B --> C["阶段 2：支配候选人权重转移<br/>贪心将 donor 权重转移给 recipient"]
    C --> D["阶段 3：残差无支配实例规约<br/>固定整数解并构造无支配子实例 (A', k', w')"]
    D --> E["阶段 4：CI 域全单模求解<br/>利用全单模性多项式求解残差整数解 W'"]
    E --> F["输出：合并最优整数委员会 W1 ∪ W'"]

关键设计¶

1. 标准线性规划松弛与结构规范化：消除辅助变量的分数割裂 论文基于 Peters (2018) 的 ILP 构建连续松弛 $\text{LP}_{(A,k,w)}$。设决策变量 $x_j \in [0, 1]$ 表示候选人 $j$ 是否入选，辅助变量 $y_\ell^i \in [0, 1]$ 表示选民 $i$ 是否获得至少 $\ell$ 名被赞同的候选人。其约束系统为 $\sum_{j=1}^m x_j = k$ 且对每个选民满足 $\sum_{j \in C_i} x_j = \sum_{\ell=1}^k y_\ell^i$。由于目标函数为 $\sum_{i=1}^n \sum_{\ell=1}^k w_\ell^i y_\ell^i$，且各选民的权重序列 $w_1^i \ge w_2^i \ge \dots \ge w_k^i \ge 0$ 单调非递增，任意可行解 $(x, y)$ 中的辅助变量 $y$ 均可被规范化为阶梯型极值向量 $y^*$： $$y_\ell^{*i} = \begin{cases} 1 & \text{若 } \ell \le \lfloor \sum_{j \in C_i} x_j \rfloor \\ \sum_{j \in C_i} x_j - \lfloor \sum_{j \in C_i} x_j \rfloor & \text{若 } \ell = \lfloor \sum_{j \in C_i} x_j \rfloor + 1 \\ 0 & \text{若 } \ell > \lfloor \sum_{j \in C_i} x_j \rfloor + 1 \end{cases}$$ 该规范化保证了目标函数值完全由选民的表现值 $r_i(x) = \sum_{j \in C_i} x_j$ 唯一下凸决定，且在严格递减权重下保证了最优 $y$ 与 $x$ 的强对应关系。

2. 支配候选人权重转移机制：多项式收敛至无支配子实例 在 VCI 域中，约束矩阵失去全单模性的根本诱因在于候选人之间的包含与支配结构（即存在赞同选民集合满足 $N_{j'} \subset N_j$）。若候选人 $j$ 支配 $j'$ 且在分数解中 $x_j < 1$ 且 $x_{j'} > 0$，算法将权重由被支配候选人 $j'$ 转移给支配候选人 $j$，即 $x_j \leftarrow \min(1, x_j + x_{j'})$，$x_{j'} \leftarrow x_{j'} - \Delta$。由于 $N_{j'} \subset N_j$，该操作绝不会降低任何选民的赞同覆盖度 $r_i(x)$，因此目标函数值单调非减。为确保多项式步数收敛，算法在每次迭代中严格选取使超额支持者差值 $|N_j \setminus N_{j'}|$ 最大的可行对 $(j, j')$。每次转移必然使某个 $x_j$ 变为 1 或某个 $x_{j'}$ 变为 0，且新生成的固定变量绝不会催生出差值更大的潜在支配对，从而保证 while 循环在多项式步内必然终止，输出一个残差无支配候选人集合 $C' = \{j \in [m] \mid 0 < x_j < 1\}$。

3. 结构引理驱动的 CI 规约与极值点整数性保证：无支配到全单模的跨域桥接 算法将已确定取值为 1 的候选人集合设为 $W_1$，并在残差实例中将委员会需求缩减为 $k' = k - |W_1|$，选民权重位移为 $w_\ell^{\prime i} = w_{\ell + \ell_i}^i$（其中 $\ell_i = |C_i \cap W_1|$）。关键数学支撑在于结构引理：任何属于 VCI 域（以及更宽广的 LC 域）且无支配的赞同矩阵，其行经过适当排序后必属于候选人区间域 $\mathcal{A}^{\text{CI}}$。因此，残差实例 $(A', k', w')$ 对应的约束矩阵严格全单模，其 LP 松弛的任意极值点均自动为整数向量 $x'$。将已选出的 $W_1$ 与残差整数解 $W' = \{j \in C' \mid x'_j = 1\}$ 合并，严格满足 $f(W_1 \cup W') = f(x)$，即为全局最优整数委员会。针对 PAV 等权重严格递减且为正的规则，论文进一步证明：松弛多面体的任意分数解均可沿残差 CI 矩阵的零空间非零扰动方向 $\Delta x$ 构造对称可行解，从而反证出其所有最优极值点（extreme points）必须直接为整数。

一个完整示例¶

考虑包含 3 位选民与 4 位候选人的实例，赞同矩阵为 $A = \begin{pmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix}$，需求规模 $k=2$。 1. 候选人 1 的支持者为 $\{1, 2, 3\}$，分别严格支配候选人 2（支持者 $\{1\}$）、候选人 3（支持者 $\{2\}$）和候选人 4（支持者 $\{3\}$）。 2. 若求解器最初给出一个极端分数解 $x_1 = x_2 = x_3 = x_4 = 0.5$（此时每个选民覆盖度均为 1.0）； 3. 算法检测到候选人 1 支配候选人 2，且 $|N_1 \setminus N_2| = 2$。执行权重转移：将 $x_2$ 的 0.5 转移给 $x_1$，更新后 $x_1 = 1.0, x_2 = 0.0$； 4. 此时已选定 $W_1 = \{1\}$，排除 $W_0 = \{2\}$。剩余候选人 $C' = \{3, 4\}$ 且 $x_3 = x_4 = 0.5$，剩余需求 $k' = 2 - 1 = 1$； 5. 子矩阵 $A' = \begin{pmatrix} 0 & 0 \\ 1 & 0 \\ 0 & 1 \end{pmatrix}$ 完全无支配关系，天然满足 CI 结构且全单模； 6. 求解残差实例，在候选人 3 与 4 中任选其一（例如选出 $W' = \{3\}$），最终得到整数委员会 $W_1 \cup W' = \{1, 3\}$，目标福利达到理论最优。

实验关键数据¶

主实验¶

论文聚焦于理论计算复杂度的突破与受限域之间的包含界限确立，给出了各类经典偏好域上广义 Thiele 规则的复杂度划分与极值点性质对比。

偏好域 / 矩阵类别	包含关系定位	TUM 全单模矩阵	最优极值点整数性（PAV）	算法复杂度
候选人区间域（CI）	基准单调域	是 (Peters, 2018)	必然为整数	多项式时间 $O(\text{poly})$
选民区间域（VI）	经典未解域	否（存在 det = -2）	必然为整数 (本文 Theorem 3)	多项式时间 $O(\text{poly})$
选民-候选人区间域（VCI）	$\text{CI} \cup \text{VI} \subseteq \text{VCI}$	否（存在 det = -2）	必然为整数 (本文 Theorem 3)	多项式时间 $O(\text{poly})$
线性一致域（LC / VCCI）	$\text{VCI} \subsetneq \text{LC}$ (本文严格真包含)	否	必然为整数 (本文 Theorem 4)	多项式时间 $O(\text{poly})$
树表示域（Tree Rep., TR）	VCI 的正交树图泛化	否	存在分数极值点	NP-完全 (本文 Theorem 8)

消融实验¶

论文针对支配结构消除、权重单调性与拓扑图结构对计算可解性的边界影响进行了理论消融与反例构造分析：

结构配置 / 假设变体	约束矩阵特性	极值点解状态	理论状态与反例依据
保留全部支配候选人（全图）	非全单模 (det = -2)	存在非整数极值点	Example 2 反例：全 0 权重或 CC 规则下 $x_j=0.5$ 构成极值点
贪心权重转移去除支配候选人	残差子矩阵全单模	必存在整数最优解	Lemma 1 / 2：无支配 VCI/LC 诱导矩阵严格为 CI 矩阵
权重严格递减且为正（如 PAV）	非全单模	所有极值点均为整数	Theorem 3 / 4：分数扰动必然在 CI 残差零空间可行，矛盾于极值点
树表示域（星型树中心+叶子节点）	非全单模且拓扑分支	无法多项式化规约	Theorem 8：从 Set Cover 归约，即便选民或候选人仅为单叶子节点仍硬
树表示域且全节点均为候选人	树拓扑约束系统	无法多项式化规约	Corollary 1：引入 $L \ge n$ 虚拟哑选民后 CC 规则仍然 NP-完全

关键发现¶

算法的瓶颈与突破口完全落在“支配候选人”上：非全单模性仅仅发生在跨越包含关系的列之间；一旦将支配候选人的分数解饱和处理，几何空间立即退化为全单模的多面体面。
偏好域的理论边界在图论层面上被清晰阐明：论文通过区间二部图与链图交集的深层性质，首次证明了线性一致域（LC）与选民包含候选人区间域（VCCI）完全等价（$\mathcal{A}^{\text{LC}} = \mathcal{A}^{\text{VCCI}}$），且 VCI 是 LC 的严格真子集（通过构造 $7 \times 7$ 阶不可 VCI 表达的 LC 赞同矩阵并运用 L/R 标签矛盾反证）。
维度的提升立即摧毁可解性：将实数线区间（一维拓扑）拓展至树结构（哪怕仅为度数任意的简单星型树），即使退化到最基础的 Chamberlin-Courant 规则，问题也会立刻坠入 NP-完全深渊。

亮点与洞察¶

巧妙绕过全单模性直接证明整数极值解的存在：传统离散优化在失去 TUM 后往往束手无策，本文跳出“试图证明全单模”的思维定势，巧妙借助贪心权重推导和维数衰减，将一般 VCI/LC 问题降解至无支配 CI 子空间。
彻底理清计算社会选择中长期混淆的受限偏好域层级结构：首次给出了 VCI 与 LC 之间的严格真包含证明，并提出了选民包含候选人（VCCI）这一直观且符合社会选择投票场景的几何定义。
证明技巧具备广泛迁移潜力：通过识别“非单模诱导子结构”并利用贪心权重调整进行安全消除的模式，可以直接迁移至 max-Phragmén 等其他具有类似组合代表性结构的 NP-难投票规则。

局限与展望¶

论文提出的多项式算法依赖通用的通用线性规划求解器（如内点法或椭圆体法）和后处理权重转移，时间复杂度受限于 LP 解的编码长度，尚未给出如纯组合贪心或动态规划那样的强多项式超高速组合算法。
树表示域（TR）被证明在一般星型拓扑下即为 NP-难，但对于最大度受限的树、有界路径宽度的树或特定参数化下的算法复杂度边界仍未完全厘清。
仅处理了一维轴上的区间相交/包含，对于二维平面欧氏距离（2D-Euclidean）或高维超矩形赞同选举，多项式求解的边界依然悬而未决。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 彻底解决了计算社会选择领域关于 VI/VCI 域 Thiele 规则复杂度的标志性公开问题，并确立了 LC 域的等价几何刻画。
实验充分度: ⭐⭐⭐⭐ 理论推导完备闭环，反例构造与不可表示性证明精巧，但缺少大规模实际投票数据上的求解器运行耗时仿真。
写作质量: ⭐⭐⭐⭐⭐ 数学符号清晰规范，几何与图论直觉阐述极其透彻，引理衔接层层递进。
价值: ⭐⭐⭐⭐⭐ 为赞同式委员会投票在受限域上的多项式时间算法提供了里程碑式的理论基础。