Game Theory 即博弈论，目前在经济学中运用得最多(纳什更因为他在这上面的工作拿到了诺贝尔经济学奖)。但在最近几年，理论计算机界对它的研究也很热。
Game Theory 主要是研究在两人甚至多人的系统中，各方如何选择自己的策略使自己的效益最大化。这里每个人的收益不光决定于自己的决策，还决定于其它人的决策。主要有两种不同的游戏，一种是两人零和游戏，只一个人赢的就是另一个人亏损的。一个典型的例子是下面这个，前两天有人在水木社区数学版问的：
某个村庄上只有一名警察，他要负责整个村的治安。小村的两头住着两个全村最富有的村民 A 和 B ， A、B 分别需要保护的财产为 2 万元、1 万元。整个小村某一天来了个小偷，要在村中偷盗 A 和 B 的财产，这个消息被警察得知。
因为分身乏术，警察一次只能在一个地方巡逻；而小偷也只能偷盗其中一家。若警察在某家看守财产，而小偷也选择了去该富户家，就会被警察抓住；若警察没有看守财产的富户家而小偷去了，则小偷偷盗成功。
小偷将会去偷哪家？警察又应该守哪家？
还有一种是非零和博弈，经典的囚徒困境就是这一类。在这类博弈中，有可能产生合作实现双赢或者互相欺骗最后双输。
但无论哪种游戏（零和博弈可以看作非零和博弈的一种特殊情况，而 n 人非零和游戏又可视为 n+1 人的零和游戏），都存在均衡策略（指各方在知道对方的策略后不会主动改变自己现在的策略）。这就是纳什获得诺贝尔奖的主要结果，后世称此种均衡态为纳什均衡。
理论计算机里的 Game Theory 主要是研究计算纳什均衡的算法和复杂度。对于两人零和游戏，均衡点的计算即为一个线性规划的问题，目前已经有有效的算法。对于两人(和多人)非零和游戏，均衡点的计算已经被证明为PPAD-complete，一个在P 和 NP之间的复杂类。
Q. E. D.
