博弈論可以用於計算機的哪些領域？

01-26

計算機專業，熱愛數學，最近愛上博弈論，希望將來能做一些把博弈論用於計算機科學的研究。

1. 華為軟體精英挑戰賽2017決賽賽題，賽題介紹 | HUAWEI軟體精英挑戰賽

2. 博弈論運用在多智能體的強化學習

[1703.10069] Multiagent Bidirectionally-Coordinated Nets for Learning to Play StarCraft Combat Games 將星際爭霸中的多智能體學習視為零和隨機博弈。

https://www.researchgate.net/profile/Michael_Littman2/publication/2799903_Markov_Games_as_a_Framework_for_Multi-Agent_Reinforcement_Learning/links/54b66cbb0cf24eb34f6d19de.pdf 2個智能體基於零和（zero sum）對策下的強化學習

http://jmlr.csail.mit.edu/papers/volume4/hu03a/hu03a.pdf 基於一般和（general sum）博弈對策的多智能體強化學習，並證明在特定環境下，演算法收斂於Nash平衡點。

IEEE Control Systems Magazine 2017 年 2 月期專刊，講博弈論在自動控制中的應用：

Game Theory in Control

鏈接：IEEE Control Systems

大多數是用來做經濟和計算機結合的項目。少數用來做智能機器人。

如果你喜歡normal form game， extensive form game，那麼可以做比如資源戰略問題。那麼對於博弈論的中心解決方案納什均衡便是一個挑戰，因為一場博弈里，參與的agent不只兩家，而納什本人也證明了雖然每一場博弈都有一個納什均衡，但是三人以上的博弈並不能保證有rational的均衡。

如果你喜歡graphic game，你可以研究Markov Decision Process。這個是reinforcement learning的核心，主要研究尋找一個最優策略，MDP還可變形為stochastic game，其中很多有趣的地方。

如果你喜歡設計拍賣，你可以研究mechanism design。Ebay做得就很好，別的在下孤陋寡聞木有很清楚。

如果你喜歡研究博弈論的演算法。。。還不如去研究它的複雜度。現在GT的演算法公認屬於PPAD，但是還有很多問題沒有解決。比如有沒有可能比PSPACE更優之類的，還有很多

補充下，上學期教博弈論的老師就做過用 game theory做spectrum auction和wireless network

在手機上看到，特意上電腦上來回答問題。

博弈論在很多地方都有廣泛的運用，只要能將問題建模成需要協調，需要競爭等等這類需要交互的問題話，博弈論基本上都能提供一些有趣的思想上的指導。我對博弈論運用到別的領域並不熟悉，這裡就講講接觸了大半年的MAS（multi-agent system）

在計算機科學領域，一顆很耀眼的明珠就是人工智慧。

AI方向上的研究推動了很多領域的進步，很多我們現在覺得不是人工智慧的演算法或者不是人工智慧的運用，其實很多在最開始都是AI領域探索的。比如每次打滴滴時候，師傅開車用的導航，其中尋路的演算法，最開始就是在AI領域發展而來的，一些爆搜的剪枝演算法，其實也是當初AI領域因為機能限制而一步步發展的。

現在阿爾法狗和柯潔的比賽吸引了很多人的關注，雖然這是一家不可說的公司收購的公司做出來一個令大眾驚奇的圍棋AI，但是你想想可能不到5年，人們就會覺得這不過又是另外一個搜索演算法加估值函數罷了。

為什麼會這樣呢？其實主要原因就是對於單智能體而言，我們更多地是在解決學習一項技能的問題，如何學會這項技能，如何在這項技能上超過人類的表現，比如DeepMind最開始的Deep Q-learning在Atari上的驚人表現，還上了nature的封面。但是沒幾年，大家覺得也就那樣吧。

我覺得一個很有趣的原因是，當我們被機器超過時，我們總是找別的領域，別的借口來欺騙自己，比如找那些AI尚未突破的領域來安慰自己。還有一點很重要的原因，很多人覺得智能，並不是說做一項技能達到或者超過人類水平就可以稱上智能，更多的是在與別的智能體交互中體現。

比如，如果突然來了一個外星物體，只會下圍棋，開開車之類的，並不能給予你交流，你會覺得他是智能體嗎？還是說那種可以和你交流，可以與你交互（競爭或者合作），可以給予你情感依賴，你會覺得是智能體？

我想問題的答案很簡單吧，應該是第二種智能吧。

那麼我們應該怎麼實現，創造出第二種智能呢？一個很重要，需要解決的問題就是，該怎麼處理與別的智能體交互。

像專家系統一樣，編寫一大堆規則其實並不是一個很好的選擇，因為那種智能並不能有很好的伸縮性。我們更希望的是給予智能體一些行為的基本準則，讓智能體在交互中體現出自己的個性，學到自己的技能。

那麼，怎麼設定這些學習準則呢？一個很棒的武器就是博弈論。

在博弈論裡面，給予了multi-agent system中很多靈感，比如該怎麼設計智能體的收益與偏好，他才能學習出合作的行為。比如經典的囚徒困境，雙方都是不背叛才是最好的選擇，但是一個只關心自我的智能體只會選擇背叛。

比如下面這個博弈，你該怎麼設計才會讓你的朋友選擇boost呢？

還有很多思想的指導，比如社會利益最大化等等。

現在很多人總是在擔心未來機器人叛亂，取代人之類的問題。

我總是覺得，這樣的問題，或許博弈論中可以指導我們出做更好的機制設計，來避免這樣的情況。

繼續樓上的補充，老闆說過曾經有一個人做生物發展過程中的博弈問題，這東西水了N多論文（具體數字確實超多......）其實博弈論提供了一個非常可靠的依據和方向（因為諾貝爾獎），你講一個故事，然後這個故事和這個依據大致相符能講得通就可以了，也就是說幾乎任何地方都能用。

J.Nash證明了在n人博弈中均衡點的存在性定理，但是沒有給出均衡解的計算方法，可以利用計算機設計演算法來迭代或逼近每一個博弈的均衡解。此外還可以研究一些複雜情況下的博弈問題，網路的拓撲的處理都可以用到計算機。

讀到博弈論中Zermelos Theorem的時候，馬上想到國際象棋經典的人機對戰，深藍對戰卡斯帕羅夫，按照Zermelos Theorem，兩人對戰，如果博弈是有窮的，規則是清晰的，博弈者都是「理性」的，那麼必定可以在遊戲開始之前就判斷出誰勝誰負，而且可以判斷每一步的最優走法。這麼說的話，只要計算能力足夠，遊戲公平，任何人都敵不過計算機。

一日，看中一台品牌計算機，一家經銷商門庭若市，一家經銷商門可羅雀，果斷的跑到冷清的這家，砍價88，喜大普奔，為何? 博弈論買計算機，實用。

博弈最難是對可變條件的定義和預測。一個很小的條件變化，經過越多次博弈後越能擴大其影響。且，越複雜的博弈規則不一定帶來穩定最優的結果

其實挺多的，說幾個我知道的：

1.演算法博弈論，特別是針對稀缺資源的分配機制，近年來涉及到這個的媒體喜歡用的詞有共享經濟以及區塊鏈；

2.機器學習中的online learning/reinforcement learning；

3.smart grid.

太多了。

知乎上很多產品經理、做數據挖掘的討論，機制呀，優化呀，推薦呀的，都能用到