《博弈论lecture1.docx》由会员分享，可在线阅读，更多相关《博弈论lecture1.docx（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1, 12, 23, 34, 43, 30, 44, 01, 1G T: L Instructor: Xiang Sun*Updated: 22:35, September 9, 20131IntroductionGametheoryisabagofanalyticaltoolsdesignedtohelpusunderstandthephenomenathatweobservewhendecision-makers interact. It is concerned wih general analysis of strategic interaction among individuals
2、.2 Timelineofthemainevolutionofgametheory In 1928, the paper Zur eorie der Gesellschasspiele (团队游戏之理论) by John von Neumann. In 1944, the book eory of Games and Economic Behavior by John von Neumann and Oskar Morgenstern.LRTBA zero-sum game In 1950, Nashs equilibrium points (John F. Nash Jr.).Dont Co
3、nfessConfessDont ConfessConfessPrisoners Dilemma In 1950, Nash bargaining solution (John F. Nash Jr.). In 1953, Shapleys value (Lloyd S. Shapley).To each cooperative game Shapleys value assigns a unique distribution (among the players) of a total surplus gen- erated by the coalition of all players.
4、In 1953, stochastic game (Lloyd S. Shapley).Stochasticgameisadynamicgamewithprobabilistictransitionsplayedbyoneormoreplayers. egameisplayed in a sequence of stages. At the beginning of each stage the game is in some state. e players select actions and each player receives a payoff that depends on th
5、e current state and the chosen actions. e game then moves to a new random state whose distribution depends on the previous state and the actions chosen by the players. e*E-mail: xiangsun.econ. Suggestion and comments are always welcome.13, 13, 11, 21, 22, 10, 02, 10, 0Game eory2/7Lecture 1procedure
6、is repeated at the new state and play continues for a finite or infinite number of stages. e total payoff to a player is oen taken to be the discounted sum of the stage payoffs or the limit inferior of the averages of the stage payoffs. In 1960, mechanism design (Leonid Hurwicz).A communication syst
7、em in which participants send messages to each other and/or to a message center, and where a pre-specified rule assigns an outcome (such as an allocation of goods and services) for every collection of received messages. In 1962, deferred-acceptance procedure (David Gale and Lloyd S. Shapley).Example
8、: 3 students S = 1, 2, 3, 2 colleges C = a,b. Students preferences: P1 : b,a, ; P2 : a, ; P3 : a,b, . Colleges preferences and quotas Pa : 1, 2, 3, qa = 1; Pb : 3, 1, 2, qb = 1. Outcome:a2, 3/21, 2/b11/, 33312 In 1965, subgame perfect equilibrium (Reinhard Selten).Nash equilibria that rely on non-cr
9、edible threats or promises can be eliminated by the requirement of subgame perfection.LLLRRLRRLR In 1967, games with incomplete information (John C. Harsanyi). In 1972, incentive compatibility (Leonid Hurwicz). In 1973, revelation principle, and implementation theory (Gibbard, Dasgupta, Hammond, Eri
10、c S. Maskin, Holm-strom, Roger B. Myerson and etc.).To any Bayesian Nash equilibrium of a game of incomplete information, there exists a payoff-equivalent revelation mechanism that has an equilibrium where the players truthfully report their types.Fix a set of outcomes and look for a game that yield
11、s that set of outcomes as equilibria. In 1974, correlated equilibrium (Robert J. Aumann).Generalize the notion of mixed strategy equilibrium to allow correlated information.M,M1, LL, 10, 00, 01, LL, 1M,MGame eory3/7Lecture 1 In 1976, agreeing to disagree (Robert J. Aumann).Within the framework of pa
12、rtitional information structures, Aumann demonstrates the impossibility of agreeing to disagree: For any posteriors with a common prior, if the agents posteriors for an event E are different (= they disagree), then the agents cannot have common knowledge (= agreeing), of these posteriors. In 1982, b
13、argaining model (Ariel Rubinstein).ARubinsteinbargainingmodelreferstoaclassofbargaininggamesthatfeaturealternatingoffersthroughaninfinitetime horizon. In 1989, e-mail game (Ariel Rubinstein).ABABABABGa (probability 1 p)Gb (probability p)Figure 1: e parameters satisfy L M 1 and p 0 that anygivenmessa
14、gedoesnotarriveatitsintendeddestination,however. (Ifacomputerreceivesamessagethen itautomaticallysendsaconfirmation;thisissonotonlyfortheoriginalmessagebutalsofortheconfirmation, the confirmation of the confirmation, and so on) If a message does not arrive then the communication stops. Attheendofcom
15、munication,eachplayersscreendisplaysthenumberofmessagesthathismachinehassent. is game has a unique Nash equilibrium in which both players choose A.Rubinsteins e-mail game tells that players strategic behavior under almost common knowledge may be very different from that under common knowledge. Even
16、if both players know that the game is Gb and the noise is arbitrarily small, the players act as if they had no information and play A, as they do in the absence of an electronic mail system.3Nobelprizelaureates In 1994, John C. Harsanyi (UC Berkeley), John F. Nash Jr. (Princeton) and Reinhard Selten
17、 (Bonn) were awardedthe Nobel Prize, for their pioneering analysis of equilibria in the theory of non-cooperative games.(a) John C. Harsanyi(b) John F. Nash Jr.(c) Reinhard Selten In2005, RobertJ.Aumann (Hebrew)and omasC.Schelling wereawardedtheNobelPrize,forhavingenhancedour understanding of confli
18、ct and cooperation through game-theory analysis.Game eory5/7Lecture 1(a) Robert J. Aumann(b) omas C. Schelling In 2007, Leonid Hurwicz (Minnesota), Eric S. Maskin (Harvard, Princeton) and Roger B. Myerson (Northwestern,Chigaco) were awarded the Nobel Prize, for having laid the foundations of mechani
19、sm design theory.(a) Leonid Hurwicz(b) Eric S. Maskin(c) Roger B. Myerson In 2012, Alvin E. Roth (Harvard, Stanford) and Lloyd S. Shapley (UCLA) were awarded the Nobel Prize, for thetheory of stable allocations and the practice of market design.Game eory6/7Lecture 1(a) Alvin E. Roth(b) Lloyd S. Shap
20、ley4PotentialNobelprizewinners(a) Paul Milgrom (Stanford)(b) Ariel Rubinstein (Tel Aviv, NYU)(c) Jean Tirole (Toulouse)5Rationalbehaviore basic assumptions that underlie game theory are that decision-makers pursue well-defined exogenous objectives (they are rational) and take into account their know
21、ledge or expectations of other decision-makers behavior (they are reason strategically).A model of rational choice: A: set of actions, with typical element a; : set of states, with typical element ; C: set of outcomes; g: outcome function g : A C; u: utility function u : C R.A decision-maker is rati
22、onal if the decision-maker chooses an action a A that maximizes the expected value ofGame eory7/7Lecture 1u(g(a,), with respect to some probability distribution , i.e., a solvesmaxaAEu(g(a, ).6CommonknowledgeE is common knowledge to players 1 and 2 if 1 knows E and 2 knows E; 1 knows that 2 knows E
23、and 2 knows that 1 knows E; 1 knows that 2 knows that 1 knows E and 2 knows that 1 knows that 2 knows E; 1 knows that 2 knows that 1 knows that 2 knows E and 2 knows that 1 knows that 2 knows that 1 knows E; and so on, and so on.For example, a handshake is common knowledge between the two persons involved. When I shake hand with you, I know you know I know you know that we shake hand. Neither person can convince the other that she does not know that they shake hand. So, perhaps it is not entirely random that we sometimes use a handshake to signal an agreement or a deal.