组合博弈论博弈论的一个分支,但跟主流博弈论不同的是,组合博弈论学者的研究对象绝大部分是信息全知的且不带几率成分的。

《稳操胜券》里介绍的其中一款游戏:Hackenbush

组合博弈论的主要研究对象是信息完全、轮流行步的二人博弈。(此条目以下提及“博弈”或“游戏”一词,如非特别声明,均指的都是组合博弈论的信息完全且不带几率成分的二人博弈。)其中一个重要的研究对象是尼姆。根据斯普莱格–格隆第定理,所有无偏博弈都可对应一局尼姆博弈。

组合博弈论较早的一篇论文是查理斯·雷纳德·包顿的《拈及其相关的完全数学理论》(Nim, A Game with a Complete Mathematical Theory)。 1982年, 埃尔温·伯利坎普约翰·何顿·康威理查德·盖伊出版《稳操胜券》(Winning Ways for your Mathematical Plays,此系列书第二版出版于2001–2004年),当中分析了大量信息完全的两人游戏,此外也分析了一些单人游戏及一种“零人游戏”(zero-person game)细胞自动机。此著作里,作者利用超现实数的概念来分析信息完全的两人游戏。(超现实数的概念,后来高德纳撰写了几本小书用以普及。)

近年,在组合博弈论的研究圈子里,针对一些游戏,结合计算机科学里的计算复杂度算法分析的研究也相当活跃。

参见

编辑

相关期刊

编辑

参考

编辑

外部链接

编辑