arXiv:2412.14570cs.GTcs.AI2024-12被引 5

提出更稳健的程序博弈均衡,扩展了AI间合作的可能性。

Characterising Simulation-Based Program Equilibria

  • 用模拟对手程序的方式构建博弈策略,提升稳定性与实用性。
  • 在有共享随机源时证明了广义的福利定理,实现更多均衡结果。
  • 揭示了无共享随机源下模拟程序的局限性,补全理论边界。

在Tennenholtz的程序均衡中,博弈方提交程序代为行动,程序接收对方代码并输出动作,适用于涉及AI代理、互信机构或承诺的场景。尽管Tennenholtz(2004)证明了程序博弈的福利定理,但其构造的均衡极为脆弱。本文考虑基于模拟的程序——即通过运行对手程序来决策的程序,这类方法更具鲁棒性(相同行为的程序被同等对待),且比基于证明的方法更实用。Oesterheld(2019)提出的εGroundedπBot即为此类方法,但仅适用于两玩家博弈,且均衡范围有限。本文提出对εGroundedπBot的泛化,证明在拥有共享随机源的设定下存在福利定理;并在无共享随机源下刻画其均衡特性。无论是否有共享随机源,新方法均实现了远超原版的均衡范围。最后,我们证明:在无共享随机源的情况下,模拟程序无法实现Tennenholtz的福利定理。

原文摘要 · Abstract (English)

In Tennenholtz's program equilibrium, players of a game submit programs to play on their behalf. Each program receives the other programs' source code and outputs an action. This can model interactions involving AI agents, mutually transparent institutions, or commitments. Tennenholtz (2004) proves a folk theorem for program games, but the equilibria constructed are very brittle. We therefore consider simulation-based programs -- i.e., programs that work by running opponents' programs. These are relatively robust (in particular, two programs that act the same are treated the same) and are more practical than proof-based approaches. Oesterheld's (2019) $ε$Grounded$π$Bot is such an approach. Unfortunately, it is not generally applicable to games of three or more players, and only allows for a limited range of equilibria in two player games. In this paper, we propose a generalisation to Oesterheld's (2019) $ε$Grounded$π$Bot. We prove a folk theorem for our programs in a setting with access to a shared source of randomness. We then characterise their equilibria in a setting without shared randomness. Both with and without shared randomness, we achieve a much wider range of equilibria than Oesterheld's (2019) $ε$Grounded$π$Bot. Finally, we explore the limits of simulation-based program equilibrium, showing that the Tennenholtz folk theorem cannot be attained by simulation-based programs without access to shared randomness.

程序博弈均衡分析AI合作

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。