基于侧信息的斯塔克伯格博弈中的遗憾最小化

Feb, 2024

基于侧信息的斯塔克伯格博弈中的遗憾最小化

Regret Minimization in Stackelberg Games with Side Information

Keegan Harris, Zhiwei Steven Wu, Maria-Florina Balcan

TL;DRStackelberg 博弈是算法博弈论的一个重要应用，通过引入附加信息和在线设置，可以实现无遗憾学习。

Abstract

In its most basic form, a Stackelberg game is a two-player game in which a leader commits to a (mixed) strategy, and a follower best-responds. Stackelberg games are perhaps one of the biggest success stories of algorithmic game theory over the last decade, as algorithms for playing in

stackelberg games algorithmic game theory side information online setting no-regret learning

发现论文，激发创造

广义和谐史塔克伯格博弈中的去中心化在线学习

我们研究了分布式和策略性在线学习问题，通过对不完全信息和附加信息两种不同情境进行研究，发现追随者在有限信息情境中按照局部最优策略响应领导者的行动，然而在附加信息情境中，追随者可以通过策略性行动操控领导者的奖励信号，以使得领导者的策略收敛到对自己更有利的均衡状态。基于这些洞察，我们针对这两种情境研究了分布式在线学习，主要贡献是提出了最后迭代收敛和样本复杂度方面的结果。尤其值得注意的是，我们设计了一种新的操控策略，用于处理附加信息情境，并证明它相对于最优应对策略具有内在优势。我们的理论结果也得到了实证结果的支持。

May, 2024

观察并学习：从明示偏好反馈中进行优化

本文提出通过揭示意向方法，解决了在 follower 效用函数未知的 Stackelberg 博弈中求解 leader 最优策略的问题，并在包括利润最大化和非原子性拥塞博弈最优通行费率问题在内的广泛问题上表现良好。

Apr, 2015

对抗无悔玩家

研究使用无遗憾算法在正态形式重复的 N 人博弈中，如何让人类玩家获得最大化效用，引入 Stackelberg 均衡和相关 Stackelberg 均衡的概念，证明玩家能够在每个回合至少保证相关 Stackelberg 期望值的效用。

Feb, 2022

分散学习对斯塔克尔贝格博弈中玩家效用的影响

探讨了两个学习代理（如推荐系统或聊天机器人）相互交流并独立学习的情况下，每个代理的目标和效用如何受到影响，并提出了一种宽容于小学习误差的放松后的后悔基准，以及相应的学习算法，实现了接近最优水平的后悔率。

Feb, 2024

有限顺序博弈的斯塔克贝格均衡计算

本文研究了在有限序贯博弈中 Stackelberg 均衡解概念，提供了几类序贯博弈的新的精确算法、近似算法和难度结果。