提出新后悔定义,让学习算法在复杂游戏中更难被对手操纵。
Swap Regret and Correlated Equilibria Beyond Normal-Form Games
- 引入'策略组合后悔'新概念,解决非正则博弈中的可操纵性问题。
- 设计高效算法,保证最多O(√T)的后悔值,且该值为最优阶数。
- 发现该机制实现的结果集小于中介可实现的范围,揭示新限制。
交换后悔是博弈论中核心概念,尤其在一般和博弈中,其最小化能收敛至相关均衡并抵御自利对手的操纵。然而,在贝叶斯博弈、序贯博弈等更广义博弈类中,交换后悔的定义不唯一,且缺乏可高效最小化的变体以维持类似非操纵性保障。本文提出适用于多面体博弈的新后悔形式——‘策略组合后悔’,证明其子线性化是任意学习算法免于对手操纵的充要条件(解决Mansour等人2022年提出的开放问题)。尽管策略组合后悔在给定对弈记录下计算为NP难,但本文设计出能保证至多$O(\sqrt{T})$策略组合后悔的高效学习算法。最后,研究了低策略组合后悔行为所诱导的相关均衡,发现其可实现结果集与第三方中介可实现结果集之间存在差距,与正则博弈情形不同。
原文摘要 · Abstract (English)
Swap regret is a notion that has proven itself to be central to the study of general-sum normal-form games, with swap-regret minimization leading to convergence to the set of correlated equilibria and guaranteeing non-manipulability against a self-interested opponent. However, the situation for more general classes of games -- such as Bayesian games and extensive-form games -- is less clear-cut, with multiple candidate definitions for swap-regret but no known efficiently minimizable variant of swap regret that implies analogous non-manipulability guarantees. In this paper, we present a new variant of swap regret for polytope games that we call ``profile swap regret'', with the property that obtaining sublinear profile swap regret is both necessary and sufficient for any learning algorithm to be non-manipulable by an opponent (resolving an open problem of Mansour et al., 2022). Although we show profile swap regret is NP-hard to compute given a transcript of play, we show it is nonetheless possible to design efficient learning algorithms that guarantee at most $O(\sqrt{T})$ profile swap regret. Finally, we explore the correlated equilibrium notion induced by low-profile-swap-regret play, and demonstrate a gap between the set of outcomes that can be implemented by this learning process and the set of outcomes that can be implemented by a third-party mediator (in contrast to the situation in normal-form games).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。