Continuous games have compact strategy sets and continuous utility functions. Such games can have a highly complicated structure of Nash equilibria. Algorithms and numerical methods for the equilibrium computation are known only for particular classes of continuous games such as two-person polynomial games or games with pure equilibria. This contribution focuses on the computation and approximation of a mixed strategy equilibrium for the whole class of multiplayer general-sum continuous games. We extend vastly the scope of applicability of the double oracle algorithm, which was initially designed and proved to converge only for two-person zero-sum games. Specifically, we propose an iterative strategy generation technique, which splits the original problem into the master problem with only a finite subset of strategies being considered, and the subproblem in which an oracle finds the best response of each player. This simple method is guaranteed to recover an approximate equilibrium in finitely many iterations. Further, we argue that the Wasserstein distance (the earth mover's distance) is the right metric on the space of mixed strategies for our purposes. Our main result is the convergence of this algorithm in the Wasserstein distance to an equilibrium of the original continuous game. The numerical experiments show the performance of our method on several examples of games appearing in the literature.


翻译:连续游戏有紧凑的策略和连续的实用功能。 这些游戏可以有一个非常复杂的 Nash 平衡结构。 计算平衡的算法和数字方法只为特定类别的连续游戏所知道, 例如双人多式游戏或纯平衡的游戏。 这一贡献侧重于计算和近似整个类多玩者普通和连续游戏的混合战略平衡。 我们广泛扩展了双或触角算法的适用范围, 它最初设计并证明只是为两个人零和游戏所趋同。 具体地说, 我们提议了一个迭代战略生成技术, 将最初的问题分成主要问题, 仅考虑一个有限的策略, 以及一个游戏找到每个玩家最佳反应的子问题。 这个简单方法可以保证在有限的多个游戏中恢复大致的平衡。 此外, 我们争辩说, 瓦塞斯坦距离( 地球移动器的距离) 是用于我们目的的混合策略空间的正确度量度。 我们的主要结果就是, 在瓦列斯特斯坦游戏的距离中, 这个算法会结合到我们数个游戏中, 显示我们游戏的原始游戏的游戏的平局。

0
下载
关闭预览

相关内容

让 iOS 8 和 OS X Yosemite 无缝切换的一个新特性。 > Apple products have always been designed to work together beautifully. But now they may really surprise you. With iOS 8 and OS X Yosemite, you’ll be able to do more wonderful things than ever before.

Source: Apple - iOS 8
最新《联邦学习Federated Learning》报告,Federated Learning
专知会员服务
88+阅读 · 2020年12月2日
GANs最新进展,30页ppt,GANs: the story so far
专知会员服务
42+阅读 · 2020年8月2日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
已删除
将门创投
10+阅读 · 2019年3月6日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年10月28日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
已删除
将门创投
10+阅读 · 2019年3月6日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员