A Short Tutorial on Game TheoryEE228a, Fall 2002Dept. of EECS, U.C. BerkeleyEE228a, Fall 20022Outline•Introduction• Complete-Information Strategic Games– Static Games– Repeated Games– Stackelberg Games• Cooperative Games– Bargaining Problem– CoalitionsEE228a, Fall 20023Outline•Introduction– What is game theory about?– Relevance to networking research–Elements of a game• Non-Cooperative Games– Static Complete-Information Games– Repeated Complete-Information Games– Stackelberg Games• Cooperative Games– Nash’s Bargaining Solution– Coalition: the Shapley ValueEE228a, Fall 2002Introduction4What Is Game Theory About?• To understand how decision-makers interact•A brief history– 1920s: study on strict competitions– 1944: Von Neumann and Morgenstern’s book Theory of Games and Economic Behavior– After 1950s: widely used in economics, politics, biology… Competition between firms Auction design Role of punishment in law enforcement International policies Evolution of speciesEE228a, Fall 2002Introduction5Relevance to Networking Research• Economic issues becomes increasingly important– Interactions between human users congestion control resource allocation– Independent service providers Bandwidth trading Peering agreements• Tool for system design– Distributed algorithms– Multi-objective optimization– Incentive compatible protocolsEE228a, Fall 2002Introduction6Elements of a Game: Strategies• Decision-maker’s choice(s) in any given situation• Fully known to the decision-maker•Examples– Price set by a firm– Bids in an auction– Routing decision by a routing algorithm• Strategy space: set of all possible actions– Finite vs infinite strategy space•Pure vsmixed strategies– Pure: deterministic actions– Mixed: randomized actionsEE228a, Fall 2002Introduction7Elements of a Game: Preference and Payoff• Preference– Transitive ordering among strategiesif a >> b, b >> c, then a >> c• Payoff– An order-preserving mapping from preference to R+– Example: in flow control, U(x)=log(1+x) – pxpayoffactionEE228a, Fall 2002Introduction8Rational Choice• Two axiomatic assumptions on games 1. In any given situation a decision-maker always chooses the action which is the best according to his/her preferences (a.k.a. rational play).2. Rational play is common knowledge among all players in the game.Question: Are these assumptions reasonable?EE228a, Fall 2002Introduction9Example: Prisoners’ DilemmaPrisoner APrisoner Bmumfinkmumfink–1, –1–9, 00, –9–6, –6 strategiespayoffsA’s moveB’s move–9–6–9–6outcome ofthe gameEE228a, Fall 2002Introduction10Different Types of Games• Static vsmulti-stage – Static: game is played only once Prisoners’ dilemma– Multi-stage: game is played in multiple rounds Multi-round auctions, chess games• Complete vsincomplete information– Complete info.: players know each others’ payoffs Prisoners’ dilemma– Incomplete info.: other players’ payoffs are not known Sealed auctionsEE228a, Fall 2002Introduction11Representations of a Game•Normal-vsextensive-form representation– Normal-form like the one used in previous example– Extensive-formPrisoner AmumfinkPrisoner BmummumfinkfinkEE228a, Fall 200212Outline•Introduction• Complete-Information Strategic Games– Static Games– Repeated Games– Stackelberg Games• Cooperative Games– Nash’s Bargaining Problem– Coalitions: the Shapley ValueEE228a, Fall 200213Static Games•Model– Players know each others’ payoffs– But do not know which strategies they would choose– Players simultaneously choose their strategies⇒ Game is over and players receive payoffs based on the combinationof strategies just chosen• Question of Interest: – What outcome would be produced by such a game?EE228a, Fall 200214Example: Cournot’s Model of Duopoly •Model (from Gibbons)– Two firms producing the same kind of product in quantities of q1and q2, respectively – Market clearing price p=A – q1 –q2– Cost of production is C for both firms– Profit for firm iJi= piqi–C qi= (A – q1 –q2) qi–C qi= (A –C –q1 –q2) qidefine B ≡ A–C – Objective: choose qi to maximize profitqi*= argmaxqi(B – q1 –q2) qiEE228a, Fall 200215A Simple Example: Solution•Firm i’s best choice, given its competitor’s qq1*= (B – q2)/2q2*= (B – q1)/2q1q2best-reply functionB/2Bq1*B/2Bq2*equilibrium: q1=q2=B/3fixed-point solution to the equationsEE228a, Fall 200216Solution to Static Games• Nash Equilibrium (J. F. Nash, 1950)– Mathematically, a strategy profile (s1*, …, si*,…, sn*) is a Nash Equilibrium if for each playeriUi(s1*, …, s*i-1, si*, s*i+1,…, sn*) ≥Ui(s1*, …, s*i-1, si, s*i+1,…,sn*),for each feasible strategy si– Plain English: a situation in which no player has incentive to deviate– It’s fixed-point solution to the following system of equationssi=argmaxs Ui(s1, …, si-1, s, si+1,…,sn), ∀i• Other solution concepts (see references)EE228a, Fall 200217An Example on Mixed Strategies• Pure-Strategy Nash Equilibrium may not existPlayer APlayer BHead (H)Tail (T)HT1, –1–1, 1–1, 11, –1Cause: each player tries to outguess his opponent!EE228a, Fall 200218Example: Best Reply• Mixed Strategies– Randomized actions to avoid being outguessed• Players’ strategies and expected payoffs– Players play H w.p. p and play T w.p. 1– p – Expected payoff of Player Apa pb + (1– pa) (1– pb) – pa (1– pb) – pb(1– pa)= (1 –2pb) + pa (4pb –2) So …if pb>1/2, pa*=1 (i.e. play H);if pb>1/2, pa*=0 (i.e. play T);if pb=1/2, then playing either H or T is equally goodEE228a, Fall 200219Example: Nash Equilibriumpbpa011/21/21EE228a, Fall 200220Existence of Nash Equilibrium• Finite strategy space (J. F. Nash, 1950)A n-player game has at least one Nash equilibrium, possibly involving mixed strategy.• Infinite strategy space (R.B. Rosen, 1965)A pure-strategy Nash Equilibrium exists in a n-player concave game. If the payoff functions satisfy diagonally strict concavity condition, then the equilibrium is unique.(s1 –s2)[rj∇Jj(s1) ] + (s2 –s1)[rj∇Jj(s2) ]<0EE228a, Fall 200221Distributed Computation of Nash Equilibrium• Nash equilibrium as result of “learning”– Players iteratively adjust their strategies based on locally available information– Equilibrium is reached if there is a steady state•
View Full Document
Unlocking...