Communication NetworksConcave, Learning, CooperativeConcave GamesConcave Games: PreliminariesConcave GameSlide 6Slide 7Slide 8Slide 9Slide 10Slide 11Learning in GamesMotivationExamples: 1Examples: 2ModelsFictitious PlaySlide 18Slide 19Stochastic Fictitious PlaySlide 21Slide 22Slide 23Slide 24Cooperative GamesCooperative Games: MotivationCooperative Games: EquilibriaCooperative Games: Nash B.E.Slide 29Slide 30Shapley ValueFixed Point TheoremsBrowerSlide 34Notes on KakutaniKakutaniSlide 37Communication NetworksA Second CourseJean WalrandDepartment of EECSUniversity of California at BerkeleyConcave, Learning, Cooperative•Concave Games•Learning in Games•Cooperative GamesConcave GamesMotivation•In many applications, the possible actions belong to a continuous set.For instance one chooses prices, transmission rates, or power levels.•In such situations, one specifies reward functions instead of a matrix or rewards.•We explain results on Nash equilibria for such gamesConcave Games: PreliminariesMany situations are possible:No NE3 NE 1 NEJ.B. Rosen, “ Existence and Uniqueness of Equilibrium Points forConcave N-Person Games,” Econometrica, 33, 520-534, July 1965J.B. Rosen, “ Existence and Uniqueness of Equilibrium Points forConcave N-Person Games,” Econometrica, 33, 520-534, July 1965Concave GameDefinition: Concave GameDefinition: Nash EquilibriumConcave GameTheorem: ExistenceProofConcave GameSpecialized Case:Concave GameDefinition: Diagonally Strictly ConcaveConcave GameTheorem: UniquenessConcave GameTheorem: Uniqueness - Bilinear Case:Concave GameLocal ImprovementsLearning in Games•Motivation•Examples•Models•Fictitious Play•Stochastic Fictitious PlayFudenberg D. and D.K. Levine (1998), The Theory of Learning in Games. MIT Press, Cambridge, Massachusetts. Chapters 1, 2, 4.Fudenberg D. and D.K. Levine (1998), The Theory of Learning in Games. MIT Press, Cambridge, Massachusetts. Chapters 1, 2, 4.Motivation•Explain equilibrium as result of players “learning” over time (instead of as the outcome of fully rational players with complete information)Examples: 1•Fixed Player Model•If P1 is patient and knows P2 chooses her play based on her forecast of P1’s plays, then P1 should always play U to lead P2 to play R•A sophisticated and patient player who faces a naïve opponent can develop a reputation for playing a fixed strategy and obtain the rewards of a Stackelberg leader•Large Population Models•Most of the theory avoids possibility above by assuming random pairings in a large population of anonymous users•In such a situation, P1 cannot really teach much to the rest of the population, so that myopic play (D, L) is optimal•Naïve play: Ignore that you affect other players’ strategiesL RU 1, 0 3, 2D 2, 1 4, 0Examples: 2•Cournot Adjustment Model•Each player selects best response to other player’s strategy in previous period•Converges to unique NE in this case•This adjustment is a bit naïve …12BR2BR1NEModels•Learning Model: Specifies rules of individual players and examines their interactions in repeated game•Usually: Same game is repeated (some work on learning from similar games)•Fictitious Play: Players observe result of their own match, play best response to the historical frequency of play•Partial Best-Response Dynamics: In each period, a fixed fraction of the population switches to a best response to the aggregate statistics from the previous period•Replicator Dynamics: Share of population using each strategy grows at a rate proportional to that strategy’s current payoffFictitious Play•Each player computes the frequency of the actions of the other players (with initial weights)•Each player selects best response to the empirical distribution (need not be product)•Theorem: •Strict NE are absorbing for FP•If s is a pure strategy and is steady-state for FP, then s = NEProof: Assume s(t) = s = strict NE. Then, with a := a(t) …, p(t+1) = (1 – a)p(t) + a(s), so thatu(t+1, r) = (1 – a)u(p(t), r) + au((s), r), which is maximized by r = s if u(p(t), r) is maximized by r = s.Converse: If converges, this means players do not want to deviate, so limit must be NE…Fictitious Play•Assume initial weights (1.5, 2) and (2, 1.5). Then(T, T) (1.5, 3), (2, 2.5) (T, H), (T, H) (H, H), (H, H), (H, H) (H, T)…•Theorem: •If under FP empirical converge, then product converges to NEProof: If strategies converge, this means players do not want to deviate, so limit must be NE…•Theorem:•Under FP, empirical converge if one of the following holds•2x2 with generic payoffs•Zero-sum•Solvable by iterated strict dominance•…•Note: Empirical distributions need not convergeH TH 1, -1 -1, 1T -1, 1 1, -1Fictitious Play•Assume initial weights (1, 20.5) for P1 and P2. Then(A, A) (2, 20.5) (B, B) (A, A) (B, B) (A, A), etc•Empirical frequencies converge to NE•However, players get 0•Correlated strategies, not independent(Fix: Randomize …)A BA 0, 0 1, 1B 1, 1 0, 0Stochastic Fictitious Play•Motivation: •Avoid discontinuity in FP•Hope for a stronger form of convergence: not only of the marginals, but also of the intended playsStochastic Fictitious Play•Definitions: •Reward of i = u(i, s) + n(i, si), n has positive support on interval•BR(i, )(si) = P[n(i, si) is s.t. si = BR to ]•Nash Distribution: if i = BR(i, ), all i•Harsanyi’s Purification Theorem: •For generic payoffs, ND NE if support of perturbation 0.•Key feature: BR is continuous and close to original BR.•Definitions: •Reward of i = u(i, s) + n(i, si), n has positive support on interval•BR(i, )(si) = P[n(i, si) is s.t. si = BR to ]•Nash Distribution: if i = BR(i, ), all i•Harsanyi’s Purification Theorem: •For generic payoffs, ND NE if support of perturbation 0.•Key feature: BR is continuous and close to original BR.Matching PenniesStochastic Fictitious Play•Theorem (Fudenberg and Kreps, 93): •Assume 2x2 game has unique mixed NE•If smoothing is small enough, then NE is globally stable for SFP•Theorem (K&Y 95, B&H 96)•Assume 2x2 game has unique strict NE•The unique intersection of smoothed BR is a global attractor for SFPAssume 2x2 game has 2 strict NE and one mixed NE. The SFP converges to one of the strict NE, w.p. 1.•Note: Cycling is possible for SFP in multi-player games•Theorem (Fudenberg and Kreps, 93): •Assume
View Full Document
Unlocking...