Combinatorial Game Theory(CGT)is a branch of Game Theory that has developed largely independently of Economic Game Theory (EGT), and is concerned with deep mathematical properties of two-player zero-sum games recursively defined over various combinatorial structures. The aim of this work is to lay the foundations for bridging the conceptual and technical gaps between CGT and EGT, here interpreted as multiplayer Extensive Form Games, so that they can be treated within a unified framework. More specifically, we introduce a class of $n$-player, general-sum games, called {\sc Cumulative Games}, which can be analyzed using tools from both CGT and EGT. We show how two of the most fundamental definitions of CGT, the outcome function and the disjunctive sum operator, naturally extend to the class of {\sc Cumulative Games}. The outcome function allows for efficient equilibrium computation under certain restrictions, while the disjunctive sum operator lets us define a partial order over games according to the advantage that a given player has. Finally, we show that any Extensive Form Game can be written as a {\sc Cumulative Game}.


翻译:组合博弈论(CGT)是博弈论的一个分支,其发展在很大程度上独立于经济博弈论(EGT),专注于研究基于各种组合结构递归定义的两人零和博弈的深层数学性质。本工作的目标是为弥合CGT与EGT(此处解释为多人扩展式博弈)之间的概念与技术鸿沟奠定基础,使得两者能够在统一框架下进行处理。具体而言,我们引入了一类称为“累积博弈”的n人一般和博弈,可利用CGT与EGT的工具进行分析。我们展示了CGT中最基本的两个定义——结果函数与不交和算子——如何自然扩展到“累积博弈”类中。结果函数允许在特定约束下进行高效的均衡计算,而不交和算子则使我们能够根据给定玩家的优势定义博弈间的偏序关系。最后,我们证明任何扩展式博弈均可表示为“累积博弈”。

0
下载
关闭预览

相关内容

【硬核书】博弈论,592页pdf
专知会员服务
164+阅读 · 2022年12月7日
【ICML2022】Sharp-MAML:锐度感知的模型无关元学习
专知会员服务
17+阅读 · 2022年6月10日
【CVPR2021】CausalVAE: 引入因果结构的解耦表示学习
专知会员服务
37+阅读 · 2021年3月28日
专知会员服务
41+阅读 · 2021年2月12日
【NeurIPS2019】图变换网络:Graph Transformer Network
NAACL 2019 | 一种考虑缓和KL消失的简单VAE训练方法
PaperWeekly
20+阅读 · 2019年4月24日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
VIP会员
相关VIP内容
【硬核书】博弈论,592页pdf
专知会员服务
164+阅读 · 2022年12月7日
【ICML2022】Sharp-MAML:锐度感知的模型无关元学习
专知会员服务
17+阅读 · 2022年6月10日
【CVPR2021】CausalVAE: 引入因果结构的解耦表示学习
专知会员服务
37+阅读 · 2021年3月28日
专知会员服务
41+阅读 · 2021年2月12日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员