In Algorithmic Game Theory ($AGT$), designing efficient algorithms to compute Nash equilibria poses considerable challenges. We make progress in the field and shed new light on the intersection between Algorithmic Game Theory and Integer Programming. We introduce $ZERO$ $Regrets$, a general cutting plane algorithm to compute, enumerate, and select Pure Nash Equilibria ($PNEs$) in Integer Programming Games, a class of simultaneous and non-cooperative games. We present a theoretical foundation for our algorithmic reasoning and provide a polyhedral characterization of the convex hull of the Pure Nash Equilibria. We introduce the concept of $equilibrium$ $inequality$, and devise an $equilibrium$ $separation$ $oracle$ to separate non-equilibrium strategies from $PNEs$. We test $ZERO$ $Regrets$ on two paradigmatic classes of games: the Knapsack Game and the Network Formation Game, a well-studied game in $AGT$. Our algorithm successfully solves relevant instances of both games and shows promising applications for equilibria selection.


翻译:在演算游戏理论($AGT$)中,设计计算纳什平衡的高效算法提出了相当大的挑战。我们在实地取得了进展,并重新展示了算法游戏理论和整数编程之间的交叉点。我们引入了以ZERO$(美元)为折算、计算和选择纯纳什平衡法(PNE$)的通用平面算法(PNE$),这是同时和不合作游戏的类别。我们为我们的算法推理提供了一个理论基础,并为纯纳什平衡游戏和网络构建游戏提供了综合特征。我们引入了以美元平价美元为折合金的概念,并设计了以美元为折价的折价美元为单位的折价平面平面法,将非平衡法与美元分开。我们测试了两种游戏的范式类:Knapsack游戏和网络构建游戏,这是在$GUDA的相关应用中成功展示了稳定的游戏。

0
下载
关闭预览

相关内容

Effective.Modern.C++ 中英文版,334页pdf
专知会员服务
67+阅读 · 2020年11月4日
【经典书】贝叶斯编程,378页pdf,Bayesian Programming
专知会员服务
247+阅读 · 2020年5月18日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
110+阅读 · 2020年5月15日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
152+阅读 · 2019年10月12日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Geometry of Dependency Equilibria
Arxiv
0+阅读 · 2022年1月14日
Arxiv
0+阅读 · 2022年1月13日
Arxiv
22+阅读 · 2021年12月19日
Arxiv
7+阅读 · 2020年6月29日
VIP会员
相关VIP内容
相关资讯
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Top
微信扫码咨询专知VIP会员