用内部转账机制让自私玩家达成社会最优均衡,且计算可行。
Equilibrium with Internal Transfers

- 设计可自我执行的转账规则,使社会最优策略成均衡。
- 在多矩阵博弈中,任何社会最优策略都可实现为均衡点。
- 中介绑定规则后,无需代理正则化,直接支持任意有限博弈。
纳什均衡源于个体效用最大化,但其社会福利可能远低于最优。且一般情况下计算纳什均衡是困难的。本文研究增强型博弈模型,其中参与者通过预算平衡的内部转账,在博弈前改进激励机制。我们提出自执行转账均衡(SETE),即参与者承诺非负的点对点转账,仅当接收方未偏离预定策略时才支付。对于多矩阵博弈,我们证明社会福利函数的每一个驻点(包括任何社会最优策略组合)均可作为SETE维持。这诱导出对应增强博弈的代理正规形式中的纳什均衡。我们进一步提出多项式时间算法和去中心化学习动态以计算此类乘积形式均衡。随后,我们引入中介型自执行转账均衡(M-SETE),由中介设定支付方案与预定策略为强制性要约。此额外约束解决了代理正规形式的局限性:M-SETE本身就是增强博弈的纳什均衡,而非仅其代理正规形式;在任意有限博弈中,任何社会最优策略组合均可作为预算平衡的M-SETE实现。因此,内部转账在不牺牲独立博弈路径的前提下,提升了福利与计算效率。当需要完整的序贯博弈稳定性时,绑定中介提供了相应的实施方式。
原文摘要 · Abstract (English)
Nash equilibrium (NE) arises from selfish utility maximization, yet its social welfare can be arbitrarily far from optimal. Moreover, computing an NE is intractable in general. We study augmented game models in which players use budget-balanced internal transfers to improve incentives before play. We first introduce \emph{Self-Enforcing Transfer Equilibrium} (SETE), where players commit to nonnegative peer-to-peer transfers that are paid only if the recipient does not deviate from a prescribed strategy. For polymatrix games, we show that every stationary point of the social welfare function, in particular any socially optimal strategy profile, can be sustained as a SETE. This induces a Nash equilibrium in the agent normal form of the corresponding augmented game. We further propose a polynomial-time algorithm and a decentralized learning dynamic to compute such product-form equilibria. We then introduce \emph{Mediated Self-Enforcing Transfer Equilibrium} (M-SETE), where a mediator makes both the payment schedule and the prescribed strategies binding offers. This additional enforcement resolves the agent-normal-form limitation: an M-SETE is a Nash equilibrium of the augmented game itself, not merely of its agent normal form, and any socially optimal strategy profile can be supported as an M-SETE in any finite game while preserving budget balance. Thus, internal transfers improve welfare and computation while preserving independent play on the equilibrium path. When full sequential-game stability is required, binding mediation provides the corresponding implementation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。