組合博弈論
外觀
組合博弈論是博弈論的一個分支,但跟主流博弈論不同的是,組合博弈論學者的研究對象絕大部份是資訊全知的且不帶概率成份的。
組合博弈論的主要研究對象是資訊完全、輪流行步的二人博弈。(此條目以下提及「博弈」或「遊戲」一詞,如非特別聲明,均指的都是組合博弈論的資訊完全且不帶概率成份的二人博弈。)其中一個重要的研究對象是尼姆。根據斯普萊格–格隆第定理,所有無偏博弈都可對應一局尼姆博弈。
組合博弈論較早的一篇論文是查理斯·雷納德·包頓的《拈及其相關的完全數學理論》(Nim, A Game with a Complete Mathematical Theory)。 1982年, 埃爾溫·伯利坎普、約翰·何頓·康威和理查德·蓋伊出版《穩操勝券》(Winning Ways for your Mathematical Plays,此系列書第二版出版於2001–2004年),當中分析了大量資訊完全的兩人遊戲,此外也分析了一些單人遊戲及一種「零人遊戲」(zero-person game)細胞自動機。此著作裏,作者利用超現實數的概念來分析資訊完全的兩人遊戲。(超現實數的概念,後來高德納撰寫了幾本小書用以普及。)
近年,在組合博弈論的研究圈子裏,針對一些遊戲,結合電腦科學裏的計算複雜度或演算法分析的研究也相當活躍。
參見
[編輯]相關期刊
[編輯]參考
[編輯]- 埃爾溫·伯利坎普,組合博弈論之背景 (頁面存檔備份,存於互聯網檔案館)(Combinatorial Game Theory Background),擷取於2018年9月12日 (英文)
- Dierk Schleicher 及 Michael Stoll ,An Introduction to Conway's Games and Numbers (頁面存檔備份,存於互聯網檔案館),2005年 (英文)
- 約翰·何頓·康威,All Games Bright and Beautiful (頁面存檔備份,存於互聯網檔案館),原刊於《美國數學月刊》,1977年 (英文)