平等主义协议的计算困难性：EAP-0的NP完全性、4/5不可近似性与LEAP-0的Σ2p完全性及遗传算法研究

《Journal of Computational Science》：Egalitarian agreements are (computationally) hard

　　

在本文中，研究人员分析了在平等主义社会福利（egalitarian social welfare）下确定最佳可能协议（covenant）问题的计算复杂性。特别地，研究人员考虑了如下场景：存在若干可能被批准或拒绝的措施，并且对于每个措施，每个代理（agent）都有一个若其被批准将获得的值（如果该代理反对该措施，则该值为负）。如果该措施未被批准，则它不会向任何代理贡献任何正值或负值。在这些假设下，并假设平等主义社会福利，研究人员表明，确定最佳可能协议的问题不仅是NP完全（NP-complete）的，而且不可能在多项式时间（polynomial time）内保证良好的近似。研究人员还表明，当某个代理为了从系统中获益而想要撒谎时，寻找一个为该代理提供某个目标收益的谎言的问题是Σ₂^p完全（Σ₂^p-complete）的。此外，研究人员考虑了一个现实案例研究，其中八个政党必须就25项法律达成协议。一方面，研究人员提供遗传算法（genetic algorithms）来求解该问题。另一方面，研究人员分析如何阻止政党就其偏好撒谎以便在立法协议中获益。事实上，研究人员表明，通过使用一个简单限制，可以在实际意义上阻止撒谎。

研究背景与问题：政治博弈和联盟形成中，代理人需就一系列必须全局采纳的选择达成协议。一个目标是功利主义社会福利（utilitarian social welfare），最大化总体满意度，但可能造成不平等；另一个是平等主义社会福利（egalitarian social welfare，目标为最大化最不满意代理人的满意度），以保证公平。论文选择后者作为目标。问题在于，随着政党和法律数量增长，确定哪些法律应通过以满足平等主义目标变得复杂；若代理人可撒谎，难度更高。因此有必要形式化计算复杂性，分析最佳协议与最佳谎言问题，提出启发式算法，并研究阻止撒谎机制。

研究开展与主要结论：研究人员定义 EAP-0（Egalitarian Agreement Problem with 0 profit from rejection），其中 n 个政党、m 项法律，f_ij∈? 表示政党 i 在法律 j 通过时的收益，未通过为0，且 ∑|f_ij|=1；解为 t_j∈{0,1}，目标最大化 min_i{1+∑ t_jf_ij}。研究人员证明 EAP-0 是 NP完全（NP-complete），并证明其属于 APX（近似类），性能比为1/2；若多项式时间算法可达到高于4/5的近似比，则 P=NP。对撒谎问题，研究人员定义 LEAP-0（Lying under egalitarian pacts problem），证明其是 Σ₂^p完全（Σ₂^p-complete）。案例研究使用西班牙社会研究中心（CIS）调查数据，八个政党（PP、PSOE、VOX、Sumar、Podemos、ERC、Junts、Bildu）就25项法律达成协议；提供 LLGA（Lower Level Genetic Algorithm）求最佳协议，ULGA（Upper Level Genetic Algorithm）搜索最佳谎言。结果表明，简单限制可实际阻止撒谎。意义在于为平等主义协议提供计算复杂性理论，并说明启发式算法与机制限制的可行性。

关键技术方法（不超过250字）：主要使用计算复杂性归约：将3-SAT（3-SAT）归约到 EAP-0 以证 NP完全性；将 FUPLP（Fake utility problem under partially locked preferences）归约到 LEAP-0 以证 Σ₂^p完全性。使用两层遗传算法：LLGA 以协议位串为个体，ULGA 以虚假偏好向量为个体，ULGA 的适应度需调用 LLGA 求解。样本队列来源为西班牙社会研究中心（CIS）关于八个主要政党选民对25项法律偏好的调查数据。设置 Unlimited 与 Limited 两种撒谎限制场景，并用偏差模拟对其他政党偏好预测的不精确性。

研究结果：
1 Introduction：提出最佳协议问题，区分功利主义与平等主义社会福利，选择平等主义作为目标。
2 Related work：政治博弈与联盟形成长期受关注；既有政治协议中欺骗研究多依赖社会方法，缺乏形式化计算复杂性框架；计算社会选择中 NP完全、多项式层级、投票操纵等被研究；平等主义福利已有形式化工作，但本文关注平等主义政治协议下战略撒谎，此前未被探索。
3 EAP-0：给出形式定义，目标最大化最不满意政党满意度，未通过法律收益为0，每个政党收益绝对值总和为1。
3.1 Computational complexity of EAP-0：通过3-SAT归约证明 EAP-0 为 NP完全；证明 EAP-0 在 APX 中具有1/2性能比，且若存在高于4/5近似比的多项式算法则 P=NP。
4 Lying in an egalitarian environment：定义最优谎言为在该谎言诱导的平等主义协议下最大化撒谎者真实满意度；引入 p_min 和 order_num_B 处理平局；给出 LEAP-0。
4.1 Computational complexity of LEAP-0：通过 FUPLP 归约证明 LEAP-0 为 Σ₂^p完全；表明其比 NP完全更高一级，需一个优化嵌套另一个优化。
5 Case study：使用 CIS 数据，八党25法律；LLGA 求协议，ULGA 求谎言；每次 ULGA 评估需 LLGA 计算协议。
5.1 Dealing with simple lying strategies：Unlimited 场景中简单低估偏好策略可显著增加撒谎者收益；Limited 场景中基本策略均不能增加收益，不如说真话。
5.2 Lying by means of a genetic algorithm：ULGA 在 Unlimited 和 Limited 均能找到有用谎言，明显改善撒谎者真实收益；但计算昂贵，每次 ULGA 迭代约270秒，200次约15小时。
5.3 Dealing with imprecise information：Unlimited 谎言对偏好估计偏差较稳健，σ=0.032 内总胜，σ=0.256 时说真话略优；Limited 谎言非常敏感，σ=0.001 已100例中29例真话更好，σ=0.004 平衡，σ=0.008 真话更好，σ=0.016 真话90%胜。因此 Limited 限制在实际中足以阻止撒谎。
6 Conclusions：总结 EAP-0 NP完全且不可近似4/5，LEAP-0 Σ₂^p完全；遗传算法可找到好解；简单限制可消除实际撒谎激励。

讨论与结论翻译：讨论部分总结：研究人员指出，平等主义社会福利下最佳协议求解是 NP完全且不可近似（4/5），因此需要启发式方法；遗传算法在类似场景中表现良好。撒谎问题因 Σ₂^p完全而更难，需第二层遗传算法。案例研究验证遗传算法能找到好解；简单限制可实际阻止撒谎。研究结论部分翻译如下：在本论文中，研究人员已经表明，在平等主义社会福利下寻找最佳可能协议的问题不仅是NP完全的，而且在某个常数程度（4/5）上不可近似。这种计算复杂性证明，有必要使用启发式方法在合理时间内求解该问题。特别地，遗传算法已被证明是这些情境中的良好方法。此外，研究人员研究了在该场景下撒谎有多困难。因此，研究人员考虑了寻找最佳可能谎言以使平等主义社会福利尽可能使自身受益的问题。在这种情况下，寻找这种最优谎言甚至更复杂，因为结果表明它是一个Σ₂^p完全问题，即在多项式层级中比NP完全高一级。这种计算复杂性表明，求解该问题需要在另一个优化之上执行一个优化。因此，一个合理的方法是提供第二层遗传算法，即其适应度函数反过来需要另一个遗传算法计算的遗传算法。在本文中，研究人员不仅提供了这样的遗传算法，还在具有真实数据的案例研究中测试了它们。所获得的实验结果表明，研究人员的遗传算法能够找到良好解。另一方面，研究的另一个主要目标是阻止参与者撒谎。在这方面，研究人员已经表明，引入一个简单限制足以消除实际中的撒谎激励。该限制仅仅包括为每个政党设定一个固定数量的点数，使其在支持的法律之间分配，以及另一个固定数量的点数在其反对的法律之间分配。有了这个简单限制，每个参与者需要拥有关于其他参与者偏好的几乎完美信息，撒谎才会有任何用处。