正则形式的博弈

正则形式是博弈论中描述博弈的一种方式。与扩展形式的博弈(extensive form game)不同,正则形式不用图形来描述博弈,而是用矩阵来陈述博弈。与延展形式的表述方式相比,这种方式在识别出严格优势策略和纳什均衡上更有用,但会丢失某些信息。博弈的正则形式的表达中包括每个参与者所有显然的和可能的策略,以及和与其相对应的收益。

来源:Wikipedia
简介

正则形式是博弈论中描述博弈的一种方式。与扩展形式的博弈(extensive form game)不同,正则形式不用图形来描述博弈,而是用矩阵来陈述博弈。与延展形式的表述方式相比,这种方式在识别出严格优势策略和纳什均衡上更有用,但会丢失某些信息。博弈的正则形式的表达中包括每个参与者所有显然的和可能的策略,以及和与其相对应的收益。

在完全信息的静态博弈(static games of complete,perfect information)中,正则形式的表达形式是参与者的策略空间(strategy space)和收益函数(payoff function)。策略空间是某个参与者的所有可能策略的集合而策略是参与者在博弈的每个阶段——不管在博弈中这个阶段实际上是否会出现——将要采取的行动的完整计划。每个参与者的收益函数,是从参与者策略空间的向量积到该参与者收益集合(一般是实数集,数字表示基数效用或序数效用——在正则形式的表述方式中常常是基数效用)的映射。也就是说,参与者的收益函数把策略组合(所有参与者策略的清单)作为它的输入量,然后输出参与者的收益。

正则形式的博弈结构更准确的描述如下:

有n个参与者的博弈表达为数列$G=(S_1,...,S_n;u_1,...,u_n)$,i属于(1,n)代表n个参与者,$S_i$是第i位参与者可执行的所有策略,而$u_i:S_1 x ... x S_n ——> R $为收益函数。

以最经典的囚徒困境为例,决策者可以利用下面的收益矩阵剔除劣势策略。对竖排决策者来说,比较每列第一个数字可以发现,由于3>2、1>0,因此无论横排决策者怎样选择,背叛都是最优策略;同理,对于横排决策者来说,比较每列的第二个数字表明无论竖排决策者如何选择背叛都能够获得更多的收益。因此,此博弈存在且唯一的纳什均衡是(背叛,背叛)。

合作

背叛

合作

2,2

0,3

背叛

3,0

1,1

[描述来源:维基百科URL:https://en.wikipedia.org/wiki/Normal-form_game]

发展历史

描述

博弈论的思想早已有之,但直到1928年,冯·诺依曼证明了零和博弈的极大极小定理后,博弈论才正式诞生了,这也是博弈论领域最重要的研究结果之一。而正则形式只是描述博弈的一种形式。

冯·诺依曼致力于将博弈论应用于经济学等领域,事实上,早期博弈论的应用范围也确实集中在经济、战争和政治领域上。

近年来,随着机器学习技术的不断突破,博弈论的相关概念在机器学习的算法设计中也越来越重要。从个体智能进化到群体智能的过程中需要博弈论的思想来帮助机器理解人类互相博弈的过程,Di He等人发现了用于广告搜索的竞价排名模型在上线处能够带来很大收益,但收益会随着时间的推移而减少,他们于2013年提出了“博弈机器学习”的概念,将博弈论思想引入机器学习。Haifang Li等人在2015年对博弈机器学习的泛化能力进行了分析。此外,当机器学习的应用越来越广泛,机器学习会面对知识不完备的情况,博弈论思想能够帮助机器进行决策。Vasilis Syrgkanis等人于2015年提出正则化的学习算法可以提高收敛速度,并且可以拓展到多玩家的博弈均衡问题的观点。

主要事件

年份

事件

相关论文/Reference

1928

冯·诺依曼证明了零和博弈的极大极小定理

von Neumann, J: (1928). Zur Theorie der Gesellschaftsspiele. Mathematische Annalen (in German). 100(1928): 295–320.

2013

Di He等人提出了“博弈机器学习”的概念

He D.; Chen W. et al. (2013). A Game-theoretic Machine Learning Approach for Revenue Maximization in Sponsored Search. IJCAI 2013.

2015

Haifang Li等人在2014年提出了博弈机器学习的泛化能力进行了分析

Li H. F.; Tian F.et al. (2015). Generalization Analysis for Game-theoretic Machine Learning, AAAI 2015.

2015

Vasilis Syrgkanis等人提出正则化的学习算法可以提高收敛速度,并且可以拓展到多玩家的博弈均衡问题

Syrgkanis V.; Agarwal A.; Luo H.; Schapire E. R. (2015). Fast Convergence of Regularized Learning in Games. NIPS2015.

发展分析

瓶颈

当博弈论的情况变得复杂时,其涉及到的数学理论也极其复杂,这给模型建立和分析带来了困难。

未来发展方向

博弈论在机器学习中的应用是一个比较新的研究方向,也许可以考虑对融合了博弈论思想的机器学习模型的表现进行系统地研究。

Contributor: Yuanyuan Li

相关人物
冯·诺依曼
冯·诺依曼
约翰·冯·诺伊曼(德语:John von Neumann,1903年12月28日-1957年2月8日),原名诺依曼·亚诺什·拉约什(匈牙利语:Neumann János Lajos),出生于匈牙利的美国籍犹太人数学家,现代电子计算机与博弈论的重要创始人,在泛函分析、遍历理论、几何学、拓扑学和数值分析等众多数学领域及计算机学、量子力学和经济学中都有重大贡献。
简介
相关人物