Two-player mean-payoff Stackelberg games are nonzero-sum infinite duration games played on a bi-weighted graph by a leader (Player~0) and a follower (Player~1). Such games are played sequentially: first, the leader announces her strategy, second, the follower chooses his strategy. This pair of strategies defines a unique infinite path in the graph and both players receive their respective payoff computed as the mean of the rewards that they receive when traversing edges along the infinite path. As a consequence, if we assume that the follower is rational then we can deduce that the follower's response to the leader strategy is a strategy that maximizes his payoff against the strategy proposed by the leader; it is thus a best-response to this strategy. Knowing that, the leader should choose a strategy that maximizes the payoff that she receives when the follower chooses a best-response to her strategy. If we cannot impose which best-response is chosen by the follower, we say that the follower, though strategic, is \emph{adversarial} towards the leader. The maximal value that the leader can get in this nonzero-sum game is called the {\em adversarial Stackelberg value} of the game. First, we show that the nonzero-sum nature of the mean-payoff Stackelberg game makes it fragile against modelling imprecisions. This is in contrast with mean-payoff games in the zero-sum setting which are robust. Second, we show how robustness is recovered when considering $\epsilon$-best responses of the follower instead of best-responses only. This lead to the notion of $\epsilon$-adversarial Stackelberg value. Third, we provide algorithms to decide the threshold problem for this robust value as well as ways to compute it effectively. Finally, we characterize the memory needed by the strategies of the leader and the follower in these games.


翻译:双玩者平均报酬 Stackelberg 游戏是非零和无限的游戏, 由领导者( Player ~ 0) 和追随者( Player ~ 1) 在双加权的图表上播放。 这种游戏是依次播放的: 首先, 领导者宣布其策略, 第二, 追随者选择其策略。 这对图中定义了一个独特的无限路径, 两个玩家在沿着无限路径翻滚时得到的回报是他们各自得到的回报的平均值。 因此, 如果我们假设追随者是理性的, 然后我们可以推断, 追随者对游戏领导者战略的反应是一种战略, 使他对领导者提出的策略的回报最大化; 因此, 这是对这个策略的最佳反应。 领导者应该选择一个在追随者选择对她的策略做出最佳反应时得到的回报最大化。 如果我们不能将最佳反应强加给后续者, 我们说, 跟踪者, 虽然战略是正对冲的, 但是, 我们的后期反应, 也是对当前领导人来说, 最高级的数值, 也就是我们向前期的 。

0
下载
关闭预览

相关内容

专知会员服务
123+阅读 · 2020年9月8日
专知会员服务
39+阅读 · 2020年9月6日
【Google】平滑对抗训练,Smooth Adversarial Training
专知会员服务
48+阅读 · 2020年7月4日
最新《生成式对抗网络》简介,25页ppt
专知会员服务
173+阅读 · 2020年6月28日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
已删除
将门创投
5+阅读 · 2018年3月21日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
1+阅读 · 2021年3月29日
Arxiv
12+阅读 · 2020年12月10日
Arxiv
5+阅读 · 2020年6月16日
VIP会员
相关VIP内容
专知会员服务
123+阅读 · 2020年9月8日
专知会员服务
39+阅读 · 2020年9月6日
【Google】平滑对抗训练,Smooth Adversarial Training
专知会员服务
48+阅读 · 2020年7月4日
最新《生成式对抗网络》简介,25页ppt
专知会员服务
173+阅读 · 2020年6月28日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
已删除
将门创投
5+阅读 · 2018年3月21日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员