双向贪心算法：用于处理非完美理性行为的算法

《ACM Transactions on Economics and Computation》：Two-way Greedy: Algorithms for Imperfect Rationality

算法机制设计中，通过结合前向和反向贪心算法实现二进制分配问题的明显策略不可证明性，扩展了近似界和策略属性，并开始探索其在集合系统中的应用。

　　

摘要

在算法设计中需要考虑自私行为这一认识，为计算机科学领域带来了许多有趣且有价值的贡献，这些贡献都属于算法机制设计的研究范畴。我们的研究源于这样一个观察：自私行为与理性行为是不同的；当代理人认为这样做有利可图时，他们就会尝试采取策略性行动。近期经济学的研究聚焦于一种特定的非理性现象，即缺乏条件推理能力，并将“明显策略安全性”（OSP）定义为一种应对这些代理人自私行为的方法。然而，至今尚不清楚应采用何种算法方法来实现OSP。在本文中，我们出人意料地发现，对于二分分配问题而言，OSP可以通过两种广为人知且被深入研究的算法技术——前向贪心算法和反向贪心算法的自然组合来完全实现。我们将这种尚未得到充分发展的算法设计范式称为“双向贪心算法”。随后，我们能够将通过贪心算法获得的各种已知近似界限应用于OSP，从而增强这一类算法的战略性能。最后，我们开始探索双向贪心算法（以及由此衍生的OSP）在集合系统中的强大应用潜力。