技术摘要：具有加性效用的比例性一般理论

1. 问题陈述

本文研究了基于选民偏好，在由候选人集合 $C$ 的子集族 $\mathcal{F} \subseteq 2^C$ 定义的一般可行性约束下，选择候选人可行子集的问题。该框架推广了社会选择理论中已建立的几种模型，包括：

• 委员会选举： 选择固定数量的候选人。
• 参与式预算 (PB)： 在总预算范围内选择项目。
• 公共决策与判断聚合： 对多个独立议题进行决策。
• 多样性约束： 确保所选集合具有特定的结构属性（例如性别平衡）。

虽然针对这一一般模型已经定义了比例性公理（如正当代表性），但现有的规则主要针对赞成票 (approval ballots)（即选民分配效用 0 或 1）设计。本文的研究重点是更复杂的加性效用 (additive utilities) 情境，即每位选民 $i$ 为每个候选人 $c$ 分配一个数值化的效用 $u_i(c) \geq 0$。其目标是设计能够在这些一般约束和基数效用下，确保凝聚性群体（cohesive groups）获得公平代表性的规则。

2. 方法论

作者提出了两种受“选民使用虚拟货币‘购买’候选人”概念启发的算法方法。

2.1 PropRank 规则

PropRank 是一种受 Phragmén 序列规则启发并针对加性效用进行改进的顺序规则。

• 机制： 选民随时间以恒定速率赚取虚拟货币。该规则模拟了一个购买过程，其中选民决定在候选人身上花费多少钱。
• 预见机制 (Foresight Mechanism)： 与标准的贪婪方法不同，PropRank 中的选民会预见未来的机会。他们计算一个“缩放因子” $\lambda_i$，该因子基于如果他们等待一个更理想的候选人变得可负担时，所能实现的最佳“支付-效用比”。
• 支出函数： 选民 $i$ 同意在第 $r$ 轮对候选人 $c$ 最多支付 $x_i(c, r)$，该函数涉及其当前预算、候选人的效用以及缩放因子。这确保了支付-效用比不会超过可获得的最佳分数支付。
• 排序： 算法通过购买时间戳构建完整的候选人排名。由于在排名构建过程中（针对特定委员会规模）并不会移除不可行的候选人，因此排名的每一个前缀都满足比例性。

2.2 广义等份额法 (Generalized Method of Equal Shares, MES)

作者将最初用于参与式预算 (PB) 的等份额法 (Method of Equal Shares) 扩展到了一般约束下。

• 结构： 算法按轮运行。在每一轮中，算法确定分配给选民的最大金额，使得“等份额”子程序可以在不违反可行性约束的情况下购买一组候选人。
• MES 中的预见性： 与 PropRank 类似，广义 MES 引入了预见机制。它计算支出的上限 ($capi$)，以防止选民过早地在那些在未来迭代中可能效率较低的候选人身上进行消费。
• 回溯启发式算法： 文中引入了启发式变体（PropRankRem, PropRankBacktrack），当候选人被移除时，它们会重启程序或进行回溯，旨在减少未使用的预算并提高实际性能，尽管这些变体缺乏与基础规则相同的理论保证。
• 有界超支 (Bounded Overspending, BOS)： 针对一般约束提出了 BOS 方法的适配版本，其中算法识别在违反可行性之前进行购买的最大有效时间戳。

3. 核心贡献

3.1 理论框架

• 加性效用的比例性公理： 本文将诸如扩展正当代表性 (EJR) 和比例正当代表性 (PJR) 等公理推广到了具有一般约束的加性效用设定。
• 比例度 (Proportionality Degree)： 作者定义并分析了“比例度”，用于量化凝聚性群体的平均满意度。他们建立了 EJR 与比例度之间的关系，表明对于一般约束，该保证取决于凝聚性群体的规模 ($\gamma = |S|/n$)。

3.2 理论保证

• PropRank 保证：
  • 对于参与式预算约束，PropRank 满足比例度 $d(\alpha) = (\alpha - u_{max})/2$。
  • 对于一般约束，它满足程度 $d(\alpha) \geq \alpha \cdot \frac{1-\gamma}{2} - \frac{u_{max}}{2}$。
  • 对于拟阵 (Matroid) 约束，它满足弱比例度 $(\alpha - u_{max})/2$。
• PJR 保证： 这些规则满足 PJR 程度保证 $d(\alpha) = (\alpha - u_{max})/(\kappa + 1)$，其中 $\kappa$ 是一个控制支出灵活性的参数。

3.3 算法扩展

• 本文提供了将等份额法推广到具有加性效用的任意可行性约束的首次尝试。
• 引入了启发式工具（PropRankRem, PropRankBacktrack）来解决实际场景中未使用预算的问题。

4. 实验结果

作者在来自 Pabulib 数据集的 1,300 多个真实世界参与式预算实例上评估了其规则。

• 指标： 评估基于 EJR+ 违规（比例性）、排除率（效用为零的选民比例）以及平均成本-满意度（功利效率）。
• 发现：
  • $\kappa$ 参数： 实验表明，当 $\kappa = 1$（允许更灵活的支出）时，PropRank 在比例性方面（更少的 EJR+ 违规）表现显著优于 $\kappa = 0$。
  • 启发式算法： 结合 $\kappa = 0$ 的启发式变体（PropRankRem, PropRankBacktrack）表现出极少的 EJR+ 违规和良好的排除率，在实际指标上通常优于基础 PropRank，尽管它们缺乏针对这些特定启发式的形式化证明。
  • BOS 适配： 适配了有界超支的等份额法表现异常出色，在 EJR+ 违规方面优于原始的 BOS-PB，并在排除率和效用方面与之持平。它也被指出是所提出的技术中最具计算效率的方法。
  • 对比： 所提出的规则在处理一般约束的同时，通常能达到与现有 PB 特定规则（MES-PB, BOS-PB）相当甚至更好的成本-满意度。

5. 重要性与主张

本文声称提供了一个比例性的通用理论，弥合了特定模型（如委员会选举和 PB）与更广泛的受限选择问题领域之间的鸿ர。

• 泛化性： 它证明了已建立的方法（Phragmén 和 Equal Shares）可以在不丢失其核心比例属性的情况下，扩展到任意可行性约束和加性效用。
• 排序： 一个重要的贡献是能够在加性效用设定下生成比例排名（即每个前缀都是一个比例委员会），填补了文献中的空白。
• 实用性： 虽然理论保证很强，但作者谦虚地指出，牺牲了一定理论可处理性以换取更好实际性能（减少未使用预算）的启发式变体在现实世界实例中非常有效。
• 局限性： 本文承认，基础算法的证明技术并不直接适用于启发式变体，且回溯启发式的计算复杂度可能是指数级的（通过参数 $\sigma$ 予以缓解）。

总之，这项工作为一般约束和加性效用下的比例代表制建立了稳健的理论基础，既提供了可证明公平的算法，也提供了在真实数据上表现良好的实用启发式方法。