Attaining equilibria using control sets

doi:10.1016/j.tcs.2026.115790

2026-02-01

PRE

Gleb Polevoy *

Jonas Schweichhart

DOI：10.1016/j.tcs.2026.115790

原文链接

原文求助

摘要

En 中文

许多互动稳定于社会次优均衡，或通过非均衡状态进行转移，而从这些状态通过实际动力学达到期望均衡要么耗时过长，要么不可能实现。因此，我们为规划者提出一个新的理论及实践上有意义的直接控制集问题：给定一个博弈、任意策略配置s和任意期望均衡d，找出玩家集合A的最小子集，使得当A中的玩家偏离至d时，d对A外的所有玩家都成为最佳回应。我们首先证明，如果期望均衡具有某些直接控制集，则该均衡必须是强均衡。我们证明直接控制集优化问题是NP难的，且无法在因子n(1-ε)（对于任意ε>0）内近似。随后，我们解决了博弈图为树形时的特例，并利用局部比率在影响另一玩家效用的玩家数量范围内近似解。接着，我们系统地研究问题的难度与近似性，考察势博弈和调和博弈，这两类博弈涵盖了有限博弈。对于势博弈，即使寻找具有常数因子近似的直接控制集，问题仍然是NP难的，但我们解决了单例拥塞博弈，并对协调博弈和对称博弈等特定势博弈进行了详细处理。至于调和博弈，我们解决了两玩家博弈，并证明对于更多玩家的情况，该问题几乎与一般博弈一样困难。最后，我们考虑了直接控制集问题的自然变体，为未来的多项研究铺平道路。

Keyword:

Equilibrium

Control set

Best response

Dynamic programming

Local ratio

Potential games

Harmonic games