下载文档原格式
第一讲、博弈论概述献给诸位知人者智，自知者明；胜人者力，自胜者强；小胜者术，大胜者德。
第一章何为“博弈”博：博览全局弈：对弈棋局→谋定而动是指在一定的游戏规则约束下，基于直接相互作用的环境条件，各参与人依据所掌握的信息，选择各自的策略（行动），以实现利益最大化的过程。
第一节从一个简单的故事说起博弈时要搞清楚对手是谁！博弈时要搞清楚和别人比什么！行为选择既跟对手的情况有关，又跟所遇到的外部环境的变化有关。
特别提示：博弈既可以是竞争，也可以是合作！特别提示：博弈，必须学会换位思考！特别提示：博弈，只需领先一步，高人一筹！博弈就是你中有我，我中有你。
由于直接相互作用（互动），每个博弈参与者的得益不仅取决于自己的策略（行动），还取决于其他参与者的策略（行动）。
博弈的核心在于整体思维基础上的理性换位思考，用他人的得益去推测他人的策略（行动），从而选择最有利于自己的策略（行动）。
特别提示：站在别人的立场上想一想，就是为自己未来的遭遇着想。
——米兰·昆德拉特别提示：如果因为对方眼中的你的傻，而让对方更愿意和你合作，何乐而不为呢？（大智若愚）特别提示：请不要在一个充分竞争的市场去追求成功！特别提示：选对市场（对手）比选对策略更重要！特别提示：在博弈之前，博弈就已经开始了！第二节博弈的渊源一、中国的理解博+弈=下围棋略观围棋，法于用兵，怯者无功，贪者先亡。
----汉代刘向，《围棋赋》二、西方的理解game(规则)费厄泼赖（fair play）第三节学习博弈论的收益一、当局者清更有利的选择更快速的反应二、旁观者更清理解历史与现实预测未来的发展三、提出完善游戏规则（制度）的建议第二章发展简史第一节最初的探索和应用一、古诺模型参加博弈的双方以各自在同一时间内相互独立的产量作为决策的变量，是一个产量竞争模型。
二、伯川德模型该模型与古诺模型的不同之处在于，企业把其产品的价格而不是产量作为竞争手段和决策变量，通过制定一个最优的销售价格来实现利润最大化。
1 完全信息静态博弈1.0 对策论研究的内容与基本形式对策论研究的内容对策论研究多个行为主体的决策问题。
对策论研究的形式博弈(game)，由多个行为主体构成的系统。
例Stackelberg modelCournot model博弈的类型参与者行动的时间与顺序同时行动——静态博弈；先后行动——动态博弈。
参与者的信息多少信息相同——完全信息；信息不同——不完全信息。
1.1 基本理论: 博弈的标准式和纳什均衡例1 儿童游戏：“石头、剪刀、布”。
博弈的标准式表示(normal-form representation)(1) 参与人( player).n 个参与人：1, 2, …, i, …, n.(2) 战略(strategy).一个参与人的战略是他采取的一个行动。
参与人i 的战略：s i.参与人i 的战略空间: S i.战略的一个组合: s ={s1，s2, …, s n}.简化表示：s-i ={ s1，…, s i -1，s i+1, …, s n }.(3) 收益(payoff).参与人i 的收益：u i= u i(s1，s2, …, s n)n个参与人博弈的标准形式表示:G = {S1, S2, …, S n；u1, u2, … , u n}完全信息(complete information)：每个参与人知道其他人的战略空间和收益。
静态博弈(static game)：所有的参与人同时行动。
每个人行动时，不知道其他人的行动。
例1（续）：博弈{石头、剪刀、布} 的描述：参与人：1，2。
战略空间：S1 = S2 = {石头、剪刀、布}收益：两人出手的函数u1 (石头，石头) = 0，u1 (石头，剪刀) = 1，u1 (石头，布) = -1 …u2 (石头，石头) = 0，u2 (石头，剪刀) = -1，u2 (石头，布) = 1 ……收益表：两个参与人，有限个战略的博弈的表示方法。
P2石头剪刀布石头0 ，0 1 ，-1 -1 ，1P1剪刀-1 ，1 0 ，0 1 ，-1布 1 ，-1 -1 ，1 0 ，0博弈的问题：能否知道每个参与人选择的战略？例2: 囚徒困境(The Prisoner’s Dilemma)囚徒 2沉默招认沉默-1 ，-1 -9 ，0囚徒 1招认0 ，-9 -6 ，-6囚徒1的考虑：无论对方选沉默还是招认，自己选“招认”好于“沉默”。
Kousha Etessami AGTA:Lecture1
Kousha Etessami AGTA:Lecture1
Kousha Etessami AGTA:Lecture1
Kousha Etessami AGTA:Lecture1
is a pair(n-tuple)of strategies for the2players(n players)such that no player can benefit by unilaterally
(i.e.,randomized)Nash equilibrium.•Example1:The pair of dominant strategies (Defect,Defect)is a pure
solution to this zero-sum game.The“minimax value”is0, as it must be because the game is“symmetric”.)•Question:How do we compute a Nash Equilibrium for a given game?
”(also called“normal form
.
What if,as is often the case,the game is played by a sequence of moves over time?(Think,e.g.,Chess.) Consider the following2-person game tree:
•How do we analyze and compute“solutions”to extensive form
Kousha Etessami AGTA:Lecture1
(probabilistic)nodes, controlled by neither player.(Poker,Backgammon.) Also,a player may not be able to distinguish between several of its“positions”or“nodes”,because not all information is available to it.(Think Poker,with opponent’s cards hidden.)Whatever move a player employs at a node must be employed at all nodes in the same“information set
.
Theorem Afinite n-person extensive game of perfect information has an“equilibrium in pure strategies”. Again,how do we compute solutions to such games?
Kousha Etessami AGTA:Lecture1
(think EBay)Think of an auction as a multiplayer game between several bidders.If you are the auctioneer,how could you design the auction rules so that,for every bidder, bidding the maximum that an item is worth to them will be a“dominant strategy”?
One answer:Vickery auctions
Kousha Etessami AGTA:Lecture1
modeling“rational agents”and their interactions.(Similar to Econ.view.)
•Games in Modeling and analysis of reactive systems:
: e.g.,Byzantine agreement.
•Games in Algorithms
:Many computational complexity classes are definable
in terms of games:Alternation,Arthur-Merlin
:GT characterizations of logics,including modal and temporal logics,
and logics that capture computational complexity
classes(Ehrenfeucht-Fraisse games).
•Games in Semantics
:An extremely active research area at the intersection of CS and
Economics.
Basic idea:“The internet is a HUGE experiment
in interaction between agents(both human and
automated)”.
How do we set up the rules of this game to harness
“socially optimal”results?
I hope you are convinced:knowledge of the principles and algorithms of game theory will be useful to you for carrying on future work in many CS diciplines.
Γ,with n players, consists of:
1.A set N={1,...,n}of players.
2.For each i∈N,a set S i of(pure)strategies.
Let S=S1×S2×...×S n be the set of possible combinations of(pure)strategies.
3.For each i∈N,a payoff(utility)function
u i:S→R,describes the payoffu i(s1,...,s n)to player i under each combination of strategies. (Each player prefers to maximize its own payoff.)
Definition A zero-sum
Kousha Etessami AGTA:Lecture1
guess of all players wins a payoffof1.All other players get a payoffof0.(If there are ties for who is closest,all who are closest get payoff1.)
Question:What would your strategy be in such a game?
Question:What is a“Nash Equilibrium”of such a game?。
