博弈论(Game Theory),有时也称为对策论,或者赛局理论,数学的一个应用分支, 目前在生物学,经济学,计算机科学和其他很多学科都有广泛的应用。是研究具有斗争或竞争性质现象的数学理论和方法。也是运筹学的一个重要学科。
具有竞争或对抗性质的行为成为对策行为。在这类行为中,参加斗争或竞争的各方各自具有不同的目标或利益。为了达到各自的目标和利益,各方必须考虑对手的各种可能的行动方案,并力图选取对自己最为有利或最为合理的方案。比如日常生活中的下棋,打牌等。对策论就是研究对策行为中斗争各方是否存在着最合理的行为方案,以及如何找到这个合理的行为方案的数学理论和方法。
博弈论简史
对于博弈论的研究,开始于策墨洛(Zermelo,1913),波雷尔(Borel,1921)及冯·诺伊曼(von Neumann, 1928),后来由冯·诺伊曼和奥斯卡·摩根斯坦(von Neumann and Morgenstern,1944,1947)首次对其系统化和形式化(参照Myerson, 1991)。随后约翰·纳什(Nash, 1950, 1951)利用不动点定理证明了均衡点的存在,为博弈论的一般化奠定了坚实的基础。
博弈分类
博弈的分类根据不同的基准也有不同的分类。一般的,博弈可以分为合作博弈和非合作博弈;以不同的所持信息又可以分为完美博弈、完全博弈和不完全博弈(贝叶斯博弈);以博弈进行的次数或者持续长短可以分为有限博弈和无限博弈;以表现形式也可以分为一般型(战略型)或者展开型,等等。
博弈论相关概念
纳什均衡
纳什均衡,又称为非合作博弈均衡,是博弈论的一个重要术语,以约翰·纳什命名。
在一个博弈过程中,无论对方的策略选择如何,当事人一方都会选择某个确定的策略,则该策略被称作支配性策略。如果两个博弈的当事人的策略组合分别构成各自的支配性策略,那么这个组合就被定义为纳什均衡。
例子
| 囚犯甲 |
招供 | 不招供 |
囚犯乙 | 招供 | 判刑五年 | 判刑十年 |
不招供 | 判刑三月 | 判刑一年 |
一个著名的例子就是囚徒困境,囚徒困境是一个非零和博弈。 大意是:一个案子的两个嫌疑犯被分开审讯,警官分别告诉两个囚犯,如果两人均不招供,将被判刑一年;如果你招供,而对方不招供,则你将被判刑三个月,而对方将被判刑十年;如果两人均招供,将均被判刑五年。 于是,两人同时陷入招供还是不招供的两难处境。
基于经济学中Rational agent的前提假设,两个囚犯符合自己利益的选择是坦白招供,原本对双方都有利的策略不招供从而均被判刑1年就不会出现。这样两人都选择坦白的策略以及因此被判5年的结局被称为“纳什均衡”,也叫非合作均衡。