似乎从来没有一门课，能像game theory这样，exercise让我感到无从入手……
以往的课程只要练习做得多了（熟能生巧，题海战术，老子可是久经百"考"了啊……），自然遇到问题时有一个解题框架或思路。
但是我手头能找到的textbook、资料等，都似乎没有什么详细的解题资料。
课本上每道题解得都非常ad-hoc，里面的analysis有时会让人摸不着头脑，没有什么套路可言，时不时冒出一个
"intuitively","so","trivial"之类的，中间的计算过程完全不涉及，很难让人学习究竟如何通过定义来计算。
虽然老师上课讲得很生动，把很多复杂、晦涩的公式都说得很透彻，我也大概理解到个中的一些思想。
但是……做起题来就摊手 //
说起复杂、晦涩，这点连老师也承认，因为他不止一次地point out：
(1) 很多人觉得game theory难，是因为里面的符号、公式太多，牵涉到很多set theory的东西，一个式子就能让人花几十分钟去理解。
(2) 当俺们学完这门课程后，就NB了……因为我们已经能承受住这么bt的脑残公式……
(3) 一个很形象的比喻："game theory is sth. about Encryption and Decryption"，这句话太对了 - -!!
把复杂的公式理解的过程就是Decryption，然后再写出更复杂的公式去encryption自己的思路……
2. textbook
课本是这位大哥写的：
A Course in Game Theory
Martin J. Osborne and Ariel Rubinstein
The MIT Press. 1994.
感觉不咋的，因为很多很难的内容都一笔带过，不适合我们这种newbie。
另外文字有点晦涩（不知道是不是搞game theory的都这风格），很多句子都用了n个clause跟在后面，
我很难理解。如：
xxx with yyy of zzz against iii of jjj which .... is .... in which .... such that.... for all and for all ... for which .... where....
来个实例：
他的另外一本书内容跟这本相似，但是详细得多了：《An Introduction to Game Theory》
(我的感觉是，作者简直是在一稿多投嘛……)
也许不用考试或做题的话，这两本书都勉强能看看……
为什么说勉强呢？因为我发觉里面涉及到大量的概率、微积分、数学分析、集合论等的内容，
当作科普书籍的话门槛也太高了……
3. structure
一般在学习一门新的课程时，我都会希望自己对该学科有一个全局的概观。
但是这门课做不到……
一来因为它涉及到比较专业外的内容，二来本学期比较忙，没有时间去看课本外的东西。
同时，course title说"in computer science"，可惜似乎老师没涉及到……
于是只好自己去wikipedia上看一点介绍。
Game theory 的 中文译名为"博弈论"或"对策论"。
据说是运筹学(OR)的一个分支，也就是说其实就是数学……
只不过后来被搬到了经济学上，而且得到了成功应用，才让我之前一直以为是经济学里的东东。
冯诺依曼是它的最早创建人之一（没错，他是数学家，而不是计算机科学家）
美丽心灵里说的就是Nash Equilibrium的提出者John Nash的故事。
他提出了纳什均衡，基本上后期的研究，都是建立在这个基础上的。
说白了,其实game theory就是在研究一堆不同的game model的内在结构，以及他们认为"好"的一样东西：solution concept。
不同的game 可以定义不同的solution concept，最广为人知的就是传说中的纳什均衡拉。
基本上，按照我的理解，nash equilibrium 刻画了这么一种状态：
在一个game中，所有人相对他人的决策都是最优的。
换句话说，对于每一个player，如果假设对手strategy不变，那么他必须选择一个最佳策略。
一个具体的例子是，在一个market里面，存在有买方和卖方，其中买方有一定价格的商品而卖方有一定的能承受的价格，
那么寻找到某个对于买方和卖方都能接受的价格时就达到某种均衡。
不过事实上，起码到现在为止我还不知道这个均衡除了好看能干什么，因为他并不代表什么全局最优，甚至连个人最优都不是……
比如著名的prisoner's dilemma的均衡点对于两个prisoners就不是什么好东西……
引用一段话：
纳什定理：
任何具有有限纯策略的二人博弈至少有一个均衡偶。这一均衡偶就称为纳什均衡点。
纳什定理的严格证明要用到不动点理论，不动点理论是经济均衡研究的主要工具。通俗地说，寻找均衡点的存在性等价于找到博弈的不动点。
纳什均衡点概念提供了一种非常重要的分析手段，使博弈论研究可以在一个博弈结构里寻找比较有意义的结果。
但纳什均衡点定义只局限于任何局中人不想单方面变换策略，而忽视了其他局中人改变策略的可能性，因此，在很多情况下，纳什均衡点的结论缺乏说服力，研究者们形象地称之为"天真可爱的纳什均衡点"。
Anyway，于我，博弈论的最大意义在于，用形式化的系统和语言（集合论等数学工具）对生活中的现象（甚至是围棋等）进行刻画，
并且研究最佳策略或某些策略的模式。希望日后遇到生活中的一些事例，可以用上game theory进行分析。
（的确学习这门课很考验人的分析技巧！）
也希望能在日后的research中能用上。据说在计算机科学中，能用到的地方有multi-agent system，networking，reliability，cryptography等。
另外在计算理论领域似乎也占有一席之地，曾经在newsmth看到介绍说，
P和NP问题是计算机算法复杂性的核心问题，但是现在有三个很著名的问题，大数分解，判
断图同构，纳什均衡（线性规划），人们不知道这些问题的算法复杂性到底是P类，还是NP
类。为刻画纳什均衡的计算复杂性，Papadimitriou引入了一个新的复杂性类PPAD,来刻画
Brouwer不动点的计算复杂性，以及判断纳什均衡计算复杂性和不动点计算是否等价。
Papadimitriou证明bimatrix是PPAD的，Chenxi证明了bimatrix是PPAD-complete的，这意味
着在多项式时间的意义下，不动点计算和纳什均衡计算是等价的。
虽说在学习过程中，并没有学到如何有一个formal的算法来计算，不过估计在"algorithmic game theory"/"algorithmic mechanism design"里有提到。
先记录一下，看以后有没机会接触一下。
4. intro. & memo & examples
根据不同game的性质，可以有很多的分类方法，这就基本涵盖了我所学到的内容：
Cooperative and non-cooperative,
Simultaneous and sequential,
Perfect information and imperfection information,
Finite and infinite,
Discrete and Continuous,
.....
不过在an Introduction to Game Theory里，基本上是按照Perfect information and imperfection information来讲的。
学习了这么些东西：
(1)strategic game, Nash Equilibrium, Dominant Strategy, Symmetric Games, Symmetric Nash Equilibrium,
Strictly Competitive Games, Maxminimization, zero sum game.
e.g. Prisoner's Dilemma, Battle of Sexes(BoS), Coordination Game, Hawk-Dove, Matching Pennies, Stag Hunt, War of Attrition
(2) Mixed Strategy and Mixed Strategy Equilibrium(MSE), existence of MSE, Correlated Equilibrium, Evolutionary Equilibrium
(3)Extensive Games(with perfect information), Reduced Strategy, subgame and subgame perfect equilibrium(这个有点像AI里的min-max method...)
Simultaneous Move, Chance Move
e.g. Chain-store game, Centipede Game
(4) Repeated Game, Discounting Preference Relation, Limit of Means Preference Relation, Overtaking Preference Relation, and their Equilibrium,
Strategies as Finite Automata in Repeated Games...
e.g. Iterated Prisoner's Dilemma
(5) Infinitely Repeated Games, Feasible Payoff Profile, Enforceability of payoff and outcomes, weak separability, Trigger Strategy, Perfect Folk Theorem,
(6) Extensive Games with Imperfect Information (with perfect/imperfect recall)
and its mixed strategies and behavioral strategies, their equilibrium, and outcome-equivalence of those two kinds of strategies.
(7) assessment, belief system, sequential rationality, consitent assessment , sequantial equilibrium
(8) Coalitional Games with/without transferable payoff, Feasible Payoff Profiles, S-feasible payoff vector, Market, Core!
e.g. Majority Game
(9) Imputation, Objection, counterobjection, stable set, Bargaining set
5. stuff
用latex来写game theory作业是一件很赏心悦目的事（虽然有点费时）。
估计TA改起来也会看得比较舒服。
M.J. Osborne还专门搞了两个画博弈树的宏包，egameps以及sgame,分别用于绘制extensive game和strategic game。
效果图如下（摘自俺的作业）：
sgame还好，不需要依赖其他的。但是egameps需要用到pstricks，与pdflatex不兼容……
解决方法是使用ps4pdf宏包，把内容wrap在某个环境里面，
然后通过latex->dvips->ps2pdf生成一个pics 文件，最后再用pdflatex贴到对应的位置。
No comments:
Post a Comment