Young / Zamir Handbook of Game Theory

1. Auflage 2014
ISBN: 978-0-444-53767-6
Verlag: Elsevier Science & Techn.
Format: EPUB
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, Band Volume 4, 1024 Seiten

Reihe: Handbook of Game Theory with Economic Applications

The ability to understand and predict behavior in strategic situations, in which an individual's success in making choices depends on the choices of others, has been the domain of game theory since the 1950s. Developing the theories at the heart of game theory has resulted in 8 Nobel Prizes and insights that researchers in many fields continue to develop. In Volume 4, top scholars synthesize and analyze mainstream scholarship on games and economic behavior, providing an updated account of developments in game theory since the 2002 publication of Volume 3, which only covers work through the mid 1990s. - Focuses on innovation in games and economic behavior - Presents coherent summaries of subjects in game theory - Makes details about game theory accessible to scholars in fields outside economics

Autoren/Hrsg.

Young, Petyon

Zamir, Shmuel

Inhaltsverzeichnis

1;Front Cover;1
2;Handbook of Game Theory;4
3;Copyright;5
4;Contents;6
5;Contributors;12
6;Preface;14
6.1;Acknowledgments;15
7;Introduction to the Series;16
8;Chapter 1: Rationality;18
8.1;1.1 Neoclassical Rationality;19
8.1.1;1.1.1 Substantive or procedural?;20
8.1.1.1;1.1.1.1 Evolution;20
8.1.2;1.1.2 Rationality as consistency;21
8.1.3;1.1.3 Positive or normative?;22
8.2;1.2 Revealed Preference;22
8.2.1;1.2.1 Independence of irrelevant alternatives;23
8.2.1.1;1.2.1.1 Aesop;23
8.2.1.2;1.2.1.2 Utility;24
8.2.1.3;1.2.1.3 Causal utility fallacy;24
8.2.2;1.2.2 Revealed preference in game theory;24
8.3;1.3 Decisions under Risk;25
8.3.1;1.3.1 VN&M utility functions;25
8.3.1.1;1.3.1.1 Attitudes to risk;25
8.3.1.2;1.3.1.2 Unbounded utility?;26
8.3.1.3;1.3.1.3 Utilitarianism;26
8.4;1.4 Bayesian Decision Theory;27
8.4.1;1.4.1 Savage's theory;27
8.4.1.1;1.4.1.1 Bayes' rule;28
8.4.2;1.4.2 Small worlds;28
8.4.2.1;1.4.2.1 Bayesianism?;29
8.4.2.2;1.4.2.2 Where do Savage's priors come from?;29
8.4.2.3;1.4.2.3 When are the worlds of game theory small?;30
8.4.2.4;1.4.2.4 Common priors?;31
8.5;1.5 Knowledge;31
8.5.1;1.5.1 Knowledge as commitment;31
8.5.1.1;1.5.1.1 Contradicting knowledge?;32
8.5.2;1.5.2 Common knowledge;33
8.5.3;1.5.3 Common knowledge of rationality?;34
8.5.3.1;1.5.3.1 Counterfactuals;34
8.6;1.6 Nash Equilibrium;35
8.6.1;1.6.1 Evolutionary game theory;36
8.6.2;1.6.2 Knowledge requirements;36
8.6.3;1.6.3 Equilibrium selection problem;37
8.6.3.1;1.6.3.1 Refinements of Nash equilibrium;37
8.7;1.7 Black Boxes;38
8.7.1;1.7.1 Nash program;39
8.7.2;1.7.2 Other preplay activity;40
8.8;1.8 Conclusion;41
8.9;Acknowledgments;41
8.10;References;42
9;Chapter 2: Advances in Zero-Sum Dynamic Games;44
9.1;2.1 Introduction;46
9.1.1;2.1.1 General model of repeated games (RG);47
9.1.2;2.1.2 Compact evaluations;48
9.1.3;2.1.3 Asymptotic analysis;48
9.1.4;2.1.4 Uniform analysis;49
9.2;2.2 Recursive Structure;50
9.2.1;2.2.1 Discounted stochastic games;50
9.2.2;2.2.2 General discounted repeated games;51
9.2.2.1;2.2.2.1 Recursive structure;51
9.2.2.2;2.2.2.2 Specific classes of repeated games;52
9.2.3;2.2.3 Compact evaluations and continuous time extension;53
9.3;2.3 Asymptotic Analysis;55
9.3.1;2.3.1 Benchmark model;55
9.3.2;2.3.2 Basic results;56
9.3.2.1;2.3.2.1 Incomplete information;56
9.3.2.2;2.3.2.2 Stochastic games;57
9.3.3;2.3.3 Operator approach;57
9.3.3.1;2.3.3.1 Nonexpansive monotone maps;58
9.3.3.2;2.3.3.2 Applications to RG;60
9.3.4;2.3.4 Variational approach;61
9.3.4.1;2.3.4.1 Discounted values and variational inequalities;62
9.3.4.2;2.3.4.2 General RG and viscosity tools;64
9.3.4.3;2.3.4.3 Compact discounted games and comparison criteria;68
9.4;2.4 The Dual Game;69
9.4.1;2.4.1 Definition and basic results;69
9.4.2;2.4.2 Recursive structure and optimal strategies of the noninformed player;70
9.4.3;2.4.3 The dual differential game;71
9.4.4;2.4.4 Error term, control of martingales, and applications to price dynamics;72
9.5;2.5 Uniform Analysis;74
9.5.1;2.5.1 Basic results;74
9.5.1.1;2.5.1.1 Incomplete information;74
9.5.1.2;2.5.1.2 Stochastic games;75
9.5.1.3;2.5.1.3 Symmetric case;75
9.5.2;2.5.2 From asymptotic value to uniform value;75
9.5.3;2.5.3 Dynamic programming and MDP;76
9.5.4;2.5.4 Games with transition controlled by one player;77
9.5.5;2.5.5 Stochastic games with signals on actions;78
9.5.6;2.5.6 Further results;79
9.6;2.6 Differential Games;80
9.6.1;2.6.1 A short presentation of differential games (DG);80
9.6.2;2.6.2 Quantitative differential games;81
9.6.3;2.6.3 Quantitative differential games with incomplete information;82
9.7;2.7 Approachability;85
9.7.1;2.7.1 Definition;85
9.7.2;2.7.2 Weak approachability and quantitative differential games;86
9.7.3;2.7.3 Approachability and B-sets;87
9.7.4;2.7.4 Approachability and qualitative differential games;88
9.7.5;2.7.5 Remarks and extensions;89
9.8;2.8 Alternative Tools and Topics;90
9.8.1;2.8.1 Alternative approaches;90
9.8.1.1;2.8.1.1 A different use of the recursive structure;90
9.8.1.2;2.8.1.2 No signals;90
9.8.1.3;2.8.1.3 State dependent signals;90
9.8.1.4;2.8.1.4 Incomplete information on the duration;90
9.8.1.5;2.8.1.5 Games with information lag;90
9.8.2;2.8.2 The ``Limit Game'';91
9.8.2.1;2.8.2.1 Presentation;91
9.8.2.2;2.8.2.2 Examples;91
9.8.2.3;2.8.2.3 Specific Properties;91
9.8.3;2.8.3 Repeated games and differential equations;92
9.8.3.1;2.8.3.1 RG and PDE;92
9.8.3.2;2.8.3.2 RG and evolution equations;92
9.8.4;2.8.4 Multimove games;93
9.8.4.1;2.8.4.1 Alternative evaluations;93
9.8.4.2;2.8.4.2 Evaluation on plays;93
9.8.4.3;2.8.4.3 Stopping games;93
9.9;2.9 Recent Advances;94
9.9.1;2.9.1 Dynamic programming and games with an informed controller;94
9.9.1.1;2.9.1.1 General evaluation and total variation;94
9.9.1.2;2.9.1.2 Dynamic programming and TV-asymptotic value;95
9.9.1.3;2.9.1.3 Dynamic programming and TV-uniform value;95
9.9.1.4;2.9.1.4 Games with a more informed controller;95
9.9.1.5;2.9.1.5 Comments;96
9.9.2;2.9.2 Markov games with incomplete information on both sides;96
9.9.3;2.9.3 Counter examples for the asymptotic approach;97
9.9.3.1;2.9.3.1 Counter example for finite state stochastic games with compact action spaces;97
9.9.3.2;2.9.3.2 Counter examples for games with finite parameter sets;97
9.9.3.3;2.9.3.3 Oscillations;98
9.9.3.4;2.9.3.4 Regularity and o-minimal structures;98
9.9.4;2.9.4 Control problem, martingales, and PDE;99
9.9.5;2.9.5 New links between discrete and continuous time games;100
9.9.5.1;2.9.5.1 Multistage approach;100
9.9.5.2;2.9.5.2 Discretization of a continuous time game;100
9.9.5.3;2.9.5.3 Stochastic games with short stage duration;101
9.9.5.4;2.9.5.4 Stochastic games in continuous time;102
9.9.5.5;2.9.5.5 Incomplete information games with short stage duration;102
9.9.6;2.9.6 Final comments;103
9.10;Acknowledgments;104
9.11;References;104
10;Chapter 3: Games on Networks;112
10.1;3.1 Introduction and Overview;113
10.2;3.2 Background Definitions;115
10.2.1;3.2.1 Players and networks;115
10.2.2;3.2.2 Games on networks;117
10.3;3.3 Strategic Complements and Strategic Substitutes;120
10.3.1;3.3.1 Defining strategic complements and substitutes;120
10.3.2;3.3.2 Existence of equilibrium;121
10.3.2.1;3.3.2.1 Games of strategic complements;121
10.3.2.2;3.3.2.2 Games of strategic substitutes and other games on networks;122
10.3.2.3;3.3.2.3 Games with strategic substitutes, continuous action spaces and linear best-replies;123
10.3.3;3.3.3 Two-action games on networks;125
10.3.3.1;3.3.3.1 Changes in behaviors as the network varies;126
10.3.3.2;3.3.3.2 Coordination games;126
10.3.3.3;3.3.3.3 Stochastically stable play in coordination games on networks;129
10.4;3.4 A Model with Continuous Actions, Quadratic Payoffs, and Strategic Complementarities;133
10.4.1;3.4.1 The benchmark quadratic model;133
10.4.1.1;3.4.1.1 Katz-Bonacich network centrality and strategic behavior;134
10.4.1.2;3.4.1.2 Nash equilibrium;135
10.4.1.3;3.4.1.3 Welfare;137
10.4.2;3.4.2 The model with global congestion;139
10.4.3;3.4.3 The model with ex ante heterogeneity;140
10.4.4;3.4.4 Some applications of the quadratic model;141
10.4.4.1;3.4.4.1 Crime;141
10.4.4.2;3.4.4.2 Education;143
10.4.4.3;3.4.4.3 Industrial organization;145
10.4.4.4;3.4.4.4 Cities;146
10.4.4.5;3.4.4.5 Conformity and conspicuous effects;147
10.5;3.5 Network Games with Incomplete Information;149
10.5.1;3.5.1 Incomplete information and contagion effects;150
10.5.1.1;3.5.1.1 A model of network games with incomplete information;150
10.5.1.2;3.5.1.2 Monotonicity of equilibria;152
10.5.1.3;3.5.1.3 A dynamic best reply process;152
10.5.2;3.5.2 Incomplete information about payoffs;156
10.5.3;3.5.3 Incomplete information with communication in networks;157
10.6;3.6 Choosing Both Actions and Links;158
10.6.1;3.6.1 Coordination games;158
10.6.2;3.6.2 Network formation in quadratic games;162
10.6.3;3.6.3 Games with strategic substitutes;166
10.7;3.7 Repeated Games and Network Structure;167
10.8;3.8 Concluding Remarks and Further Areas of Research;168
10.8.1;3.8.1 Bargaining and exchange on networks;169
10.8.2;3.8.2 Risk-sharing networks;171
10.8.3;3.8.3 Dynamic games and network structure;171
10.8.4;3.8.4 More empirical applications based on theory;172
10.8.5;3.8.5 Lab and field experiments;173
10.9;Acknowledgments;173
10.10;References;174
11;Chapter 4: Reputations in Repeated Games;182
11.1;4.1 Introduction;183
11.1.1;4.1.1 Reputations;183
11.1.2;4.1.2 The interpretive approach to reputations;184
11.1.3;4.1.3 The adverse selection approach to reputations;184
11.2;4.2 Reputations with Short-Lived Players;185
11.2.1;4.2.1 An example;185
11.2.2;4.2.2 The benchmark complete information game;187
11.2.3;4.2.3 The incomplete information game and commitment types;188
11.2.4;4.2.4 Reputation bounds;190
11.2.4.1;4.2.4.1 Relative entropy;190
11.2.4.2;4.2.4.2 Bounding the one-step ahead prediction errors;192
11.2.4.3;4.2.4.3 From prediction bounds to payoffs;193
11.2.4.4;4.2.4.4 The Stackelberg bound;197
11.2.5;4.2.5 More general monitoring structures;198
11.2.6;4.2.6 Temporary reputations under imperfect monitoring;199
11.2.6.1;4.2.6.1 The implications of reputations not disappearing;203
11.2.6.2;4.2.6.2 The contradiction and conclusion of the proof;208
11.2.7;4.2.7 Interpretation;208
11.2.8;4.2.8 Exogenously informative signals;210
11.3;4.3 Reputations with Two Long-Lived Players;213
11.3.1;4.3.1 Types vs. actions;214
11.3.2;4.3.2 An example: The failure of reputation effects;214
11.3.3;4.3.3 Minmax-action reputations;218
11.3.3.1;4.3.3.1 Minmax-action types;218
11.3.3.2;4.3.3.2 Conflicting interests;221
11.3.4;4.3.4 Discussion;222
11.3.4.1;4.3.4.1 Weaker payoff bounds for more general actions;223
11.3.4.2;4.3.4.2 Imperfect monitoring;224
11.3.4.3;4.3.4.3 Punishing commitment types;226
11.4;4.4 Persistent Reputations;227
11.4.1;4.4.1 Limited observability;228
11.4.2;4.4.2 Analogical reasoning;231
11.4.3;4.4.3 Changing types;235
11.4.3.1;4.4.3.1 Cyclic reputations;235
11.4.3.2;4.4.3.2 Permanent reputations;238
11.4.3.3;4.4.3.3 Reputation as separation;239
11.5;4.5 Discussion;245
11.5.1;4.5.1 Outside options and bad reputations;245
11.5.2;4.5.2 Investments in reputations;247
11.5.3;4.5.3 Continuous time;250
11.5.3.1;4.5.3.1 Characterizing behavior;251
11.5.3.2;4.5.3.2 Reputations without types;252
11.6;Acknowledgments;253
11.7;References;253
12;Chapter 5: Coalition Formation;256
12.1;5.1 Introduction;257
12.2;5.2 The Framework;261
12.2.1;5.2.1 Ingredients;262
12.2.2;5.2.2 Process of coalition formation;264
12.2.3;5.2.3 Equilibrium process of coalition formation;264
12.2.4;5.2.4 Some specific settings;266
12.2.4.1;5.2.4.1 State spaces;266
12.2.4.2;5.2.4.2 Characteristic functions and partition functions;267
12.2.4.3;5.2.4.3 Remarks on protocols and effectivity correspondences;270
12.2.5;5.2.5 Remarks on the response protocol;272
12.3;5.3 The Blocking Approach: Cooperative Games;273
12.3.1;5.3.1 The setting;274
12.3.2;5.3.2 Blocking;275
12.3.3;5.3.3 Consistency and farsightedness;276
12.3.4;5.3.4 The farsighted stable set;278
12.3.5;5.3.5 Internal blocking;279
12.3.5.1;5.3.5.1 A recursive definition;279
12.3.5.2;5.3.5.2 EPCF and the farsighted stable set with internal blocking;280
12.3.5.3;5.3.5.3 Characteristic functions;283
12.3.5.4;5.3.5.4 Effectivity without full support;286
12.3.5.5;5.3.5.5 Internal blocking in the presence of externalities;289
12.3.6;5.3.6 Beyond internal blocking;293
12.3.6.1;5.3.6.1 Farsighted stability for characteristic functions;293
12.3.6.2;5.3.6.2 Farsighted stability for games with externalities;296
12.4;5.4 The Bargaining Approach: Noncooperative Games;300
12.4.1;5.4.1 Ingredients of a coalitional bargaining model;301
12.4.1.1;5.4.1.1 The protocol;301
12.4.1.2;5.4.1.2 Possibilities for changing or renegotiating agreements;303
12.4.1.3;5.4.1.3 Payoffs in real time or not;303
12.4.1.4;5.4.1.4 Majority versus unanimity;304
12.4.2;5.4.2 Bargaining on partition functions;304
12.4.2.1;5.4.2.1 Equilibrium in a real-time bargaining model;304
12.4.2.2;5.4.2.2 Two elementary restrictions;306
12.4.2.3;5.4.2.3 EPCF and bargaining equilibrium;307
12.4.3;5.4.3 Some existing models of noncooperative coalition formation;308
12.4.3.1;5.4.3.1 The standard bargaining problem;309
12.4.3.2;5.4.3.2 Coalitional bargaining with irreversible agreements;311
12.4.3.3;5.4.3.3 Equilibrium coalition structure;314
12.4.4;5.4.4 Reversibility;317
12.5;5.5 The Welfare Economics of Coalition Formation;320
12.5.1;5.5.1 Two sources of inefficiency;321
12.5.2;5.5.2 Irreversible agreements and efficiency;323
12.5.3;5.5.3 Reversible agreements and efficiency;327
12.5.3.1;5.5.3.1 Temporary agreements;327
12.5.3.2;5.5.3.2 Renegotiation;328
12.6;5.6 Coalition Formation: The Road Ahead;336
12.7;Acknowledgments;339
12.8;References;339
13;Chapter 6: Stochastic Evolutionary Game Dynamics;344
13.1;6.1 Evolutionary Dynamics and Equilibrium Selection;345
13.1.1;6.1.1 Evolutionarily stable strategies;346
13.1.2;6.1.2 Stochastically stable sets;348
13.2;6.2 Equilibrium Selection in 2 2 Games;352
13.2.1;6.2.1 A simple model;352
13.2.2;6.2.2 The unperturbed process;353
13.2.3;6.2.3 The perturbed process;354
13.3;6.3 Stochastic Stability in Larger Games;357
13.3.1;6.3.1 A canonical model of adaptive learning;358
13.3.2;6.3.2 Markov processes and rooted trees;359
13.3.3;6.3.3 Equilibrium selection in larger games;362
13.4;6.4 Bargaining;366
13.4.1;6.4.1 An evolutionary model of bargaining;367
13.4.2;6.4.2 The case of heterogeneous agents;370
13.4.3;6.4.3 Extensions: Sophisticated agents and cooperative games;370
13.5;6.5 Public Goods;371
13.5.1;6.5.1 Teamwork;372
13.5.2;6.5.2 Bad apples;375
13.5.3;6.5.3 The volunteer's dilemma;378
13.5.4;6.5.4 General public-good games and potential;380
13.6;6.6 Network Games;381
13.7;6.7 Speed of Convergence;386
13.7.1;6.7.1 Autonomy;388
13.7.2;6.7.2 Close-knittedness;389
13.8;6.8 Concluding Remarks;394
13.9;References;395
14;Chapter 7: Advances in Auctions;398
14.1;7.1 Introduction;399
14.2;7.2 First-Price Auctions: Theoretical Advances;400
14.2.1;7.2.1 Mixed-strategy equilibria;401
14.2.2;7.2.2 Asymmetric buyers: Existence of mixed and pure-strategy equilibria;402
14.2.3;7.2.3 Relaxation of symmetry and independence;403
14.2.4;7.2.4 Monotonicity and the role of tie-breaking rules;405
14.2.5;7.2.5 Revenue comparisons;406
14.3;7.3 Multiunit Auctions;408
14.3.1;7.3.1 Efficient ascending-bid auctions;408
14.3.2;7.3.2 Multiple heterogeneous items;412
14.4;7.4 Dynamic Auctions;413
14.4.1;7.4.1 Dynamic population;414
14.4.2;7.4.2 Repeated ascending-price auctions;416
14.5;7.5 Externalities in Single-Object Auctions;419
14.5.1;7.5.1 A general social choice model;419
14.5.2;7.5.2 Complete information;420
14.5.3;7.5.3 Incomplete information;421
14.6;7.6 Auctions with Resale;422
14.6.1;7.6.1 First-price and second-price auctions;423
14.6.2;7.6.2 Seller's optimal mechanism;424
14.6.3;7.6.3 Further results;425
14.7;7.7 All-Pay Auctions;426
14.7.1;7.7.1 Complete information;427
14.7.2;7.7.2 Incomplete information;429
14.7.3;7.7.3 Multiple prizes;430
14.7.4;7.7.4 Bid-dependent rewards;431
14.7.5;7.7.5 Contests versus lotteries;432
14.7.6;7.7.6 All-pay auctions with spillovers;433
14.7.7;7.7.7 Bid caps;434
14.7.8;7.7.8 Research contests;435
14.7.9;7.7.9 Blotto games;436
14.7.10;7.7.10 Other topics;438
14.8;7.8 Incorporating Behavioral Economics;438
14.8.1;7.8.1 Regret;439
14.8.2;7.8.2 Impulse balance;440
14.8.3;7.8.3 Reference points;442
14.8.4;7.8.4 Buy-it-now options;443
14.8.5;7.8.5 Level-k bidding;443
14.8.6;7.8.6 Spite;444
14.8.7;7.8.7 Ambiguity;445
14.9;7.9 Position Auctions in Internet Search;447
14.9.1;7.9.1 First-price pay-per-click auctions;448
14.9.2;7.9.2 Second-price pay-per-click auctions;449
14.9.3;7.9.3 Other formats;451
14.10;7.10 Spectrum Auctions;454
14.10.1;7.10.1 3G auctions;454
14.10.2;7.10.2 4G auctions;457
14.11;7.11 Concluding Remarks;461
14.12;Acknowledgments;461
14.13;References;462
15;Chapter 8: Combinatorial Auctions;472
15.1;8.1 Introduction;472
15.2;8.2 Supporting Prices;474
15.2.1;8.2.1 The core;479
15.3;8.3 Incentives;481
15.3.1;8.3.1 When VCG is not in the core;482
15.3.2;8.3.2 Ascending implementations of VCG;484
15.3.3;8.3.3 What is an ascending auction?;486
15.3.4;8.3.4 The clock-proxy auction;488
15.4;8.4 Complexity Considerations;489
15.4.1;8.4.1 Exact methods;490
15.4.2;8.4.2 Approximation;490
15.5;References;491
16;Chapter 9: Algorithmic Mechanism Design: Through the lens of Multiunit auctions;494
16.1;9.1 Introduction;495
16.2;9.2 Algorithmic Mechanism Design and This Survey;496
16.2.1;9.2.1 The field of algorithmic mechanism design;496
16.2.2;9.2.2 Our example: multiunit auctions;498
16.2.3;9.2.3 Where are we going?;500
16.3;9.3 Representation;500
16.3.1;9.3.1 Bidding languages;501
16.3.2;9.3.2 Query access to the valuations;503
16.3.2.1;9.3.2.1 Value queries;503
16.3.2.2;9.3.2.2 General communication queries;504
16.4;9.4 Algorithms;505
16.4.1;9.4.1 Algorithmic efficiency;505
16.4.2;9.4.2 Downward sloping valuations;507
16.4.3;9.4.3 Intractability;508
16.4.3.1;9.4.3.1 NP-Completeness;509
16.4.3.2;9.4.3.2 Communication complexity;510
16.4.4;9.4.4 Approximation;512
16.5;9.5 Payments, Incentives, and Mechanisms;513
16.5.1;9.5.1 Vickrey-Clarke-Groves mechanisms;515
16.5.2;9.5.2 The clash between approximation and incentives;516
16.5.3;9.5.3 Maximum-in-range mechanisms;518
16.5.4;9.5.4 Single parameter mechanisms;521
16.5.5;9.5.5 Multiparameter mechanisms beyond VCG?;524
16.5.6;9.5.6 Randomization;528
16.6;9.6 Conclusion;531
16.7;Acknowledgments;531
16.8;References;531
17;Chapter 10: Behavioral Game Theory Experiments and Modeling;534
17.1;10.1 Introduction;535
17.2;10.2 Cognitive Hierarchy and Level-k Models;537
17.2.1;10.2.1 P-beauty contest;540
17.2.2;10.2.2 Market entry games;543
17.2.3;10.2.3 LUPI lottery;545
17.2.4;10.2.4 Summary;547
17.3;10.3 Quantal Response Equilibrium;547
17.3.1;10.3.1 Asymmetric hide-and-seek game;548
17.3.2;10.3.2 Maximum value auction;550
17.4;10.4 Learning;552
17.4.1;10.4.1 Parametric EWA learning: interpretation, uses, and limits;553
17.4.2;10.4.2 fEWA functions;556
17.4.2.1;10.4.2.1 The change-detector function 0=x"011Ei(t);557
17.4.2.2;10.4.2.2 The attention function, 0=x"010Eij(t);559
17.4.3;10.4.3 fEWA predictions;562
17.4.4;10.4.4 Example: mixed strategy games;565
17.4.5;10.4.5 Summary;568
17.5;10.5 Sophistication and Teaching;568
17.5.1;10.5.1 Sophistication;569
17.5.2;10.5.2 Strategic teaching;571
17.5.3;10.5.3 Summary;576
17.6;10.6 Sociality;577
17.6.1;10.6.1 Public goods;577
17.6.2;10.6.2 Public goods with punishment;578
17.6.3;10.6.3 Negative reciprocity: ultimatums;579
17.6.4;10.6.4 Impure altruism and social image: dictator games;581
17.6.5;10.6.5 Summary;583
17.7;10.7 Conclusion;583
17.8;References;584
18;Chapter 11: Evolutionary Game Theory in Biology;592
18.1;11.1 Strategic Analysis—What Matters to Biologists?;593
18.2;11.2 Sex Ratios—How the Spirit of Game Theory Emerged in Biology;595
18.2.1;11.2.1 There is a hitch with fitness;596
18.2.2;11.2.2 Düsing's solution—the first biological game;596
18.2.3;11.2.3 Fisher's treatment of sex-ratio theory;597
18.2.4;11.2.4 Does it suffice to count grandchildren—what is the utility?;598
18.2.5;11.2.5 Evolutionary dynamics;599
18.2.6;11.2.6 Reproductive value;600
18.2.7;11.2.7 Haplodiploid sex-ratio theory;600
18.3;11.3 The Empirical Success of Sex-Ratio Theory;601
18.3.1;11.3.1 Experimental evolution;601
18.3.2;11.3.2 Measuring the slices of the cake;602
18.3.3;11.3.3 Local mate competition;603
18.3.4;11.3.4 Environmental sex determination and the logic of randomization;603
18.4;11.4 Animal Fighting and the Official Birth of Evolutionary Game Theory;605
18.4.1;11.4.1 The basic idea of an evolutionary game;605
18.4.2;11.4.2 The concept of an evolutionarily stable strategy;606
18.4.3;11.4.3 What does the Hawk-Dove game tell us about animal fighting?;607
18.4.4;11.4.4 The current view on limited aggression;608
18.5;11.5 Evolutionary Dynamics;609
18.5.1;11.5.1 The replicator equation;610
18.5.2;11.5.2 Adaptive dynamics and invasion fitness;610
18.5.3;11.5.3 Gene-frequency dynamics and the multilocus mess;611
18.5.4;11.5.4 Finite populations and stochasticity;612
18.6;11.6 Intragenomic Conflict and Willful Passengers;612
18.6.1;11.6.1 Meiotic drive;613
18.6.2;11.6.2 Example of an ultraselfish chromosome;613
18.6.3;11.6.3 Endosymbionts in conflict with their hosts;614
18.6.4;11.6.4 Wolbachia—master manipulators of reproduction;615
18.7;11.7 Cooperation in Microbes and Higher Organisms;615
18.7.1;11.7.1 Reciprocal altruism;616
18.7.2;11.7.2 Indirect reciprocity;617
18.7.3;11.7.3 Tragedy of the commons;618
18.7.4;11.7.4 Common interest;618
18.7.5;11.7.5 Common interest through lifetime monogamy;619
18.8;11.8 Biological Trade and Markets;620
18.8.1;11.8.1 Pollination markets;621
18.8.2;11.8.2 Principal-agent models, sanctioning and partner choice;621
18.8.3;11.8.3 Supply and demand;622
18.9;11.9 Animal Signaling—Honesty or Deception?;622
18.9.1;11.9.1 Education and the Peacock's tail;623
18.9.2;11.9.2 Does the handicap principle work in practice?;624
18.9.3;11.9.3 The rush for ever more handicaps, has it come to an end?;624
18.9.4;11.9.4 Warning signals and mimicry;625
18.10;References;628
19;Chapter 12: Epistemic Game Theory;636
19.1;12.1 Introduction and Motivation;637
19.1.1;12.1.1 Philosophy/Methodology;639
19.2;12.2 Main Ingredients;641
19.2.1;12.2.1 Notation;641
19.2.2;12.2.2 Strategic-form games;641
19.2.3;12.2.3 Belief hierarchies;642
19.2.4;12.2.4 Type structures;644
19.2.5;12.2.5 Rationality and belief;646
19.2.6;12.2.6 Discussion;648
19.2.6.1;12.2.6.1 State dependence and nonexpected utility;648
19.2.6.2;12.2.6.2 Elicitation;648
19.2.6.3;12.2.6.3 Introspective beliefs and restrictions on strategies;649
19.2.6.4;12.2.6.4 Semantic/syntactic models;649
19.3;12.3 Strategic Games of Complete Information;649
19.3.1;12.3.1 Rationality and common belief in rationality;650
19.3.2;12.3.2 Discussion;652
19.3.3;12.3.3 -Rationalizability;653
19.4;12.4 Equilibrium Concepts;654
19.4.1;12.4.1 Introduction;654
19.4.2;12.4.2 Subjective correlated equilibrium;655
19.4.3;12.4.3 Objective correlated equilibrium;656
19.4.4;12.4.4 Nash equilibrium;661
19.4.5;12.4.5 The book-of-play assumption;663
19.4.6;12.4.6 Discussion;665
19.4.6.1;12.4.6.1 Condition AI;665
19.4.6.2;12.4.6.2 Comparison with aumann1987correlated;666
19.4.6.3;12.4.6.3 Nash equilibrium;666
19.5;12.5 Strategic-Form Refinements;667
19.6;12.6 Incomplete Information;671
19.6.1;12.6.1 Introduction;671
19.6.2;12.6.2 Interim correlated rationalizability;674
19.6.3;12.6.3 Interim independent rationalizability;677
19.6.4;12.6.4 Equilibrium concepts;680
19.6.5;12.6.5 -Rationalizability;682
19.6.6;12.6.6 Discussion;683
19.7;12.7 Extensive-Form Games;684
19.7.1;12.7.1 Introduction;684
19.7.2;12.7.2 Basic ingredients;687
19.7.3;12.7.3 Initial CBR;691
19.7.4;12.7.4 Forward induction;693
19.7.4.1;12.7.4.1 Strong belief;693
19.7.4.2;12.7.4.2 Examples;694
19.7.4.3;12.7.4.3 RCSBR and extensive-form rationalizability;696
19.7.4.4;12.7.4.4 Discussion;698
19.7.5;12.7.5 Backward induction;701
19.7.6;12.7.6 Equilibrium;702
19.7.7;12.7.7 Discussion;704
19.8;12.8 Admissibility;706
19.8.1;12.8.1 Basics;707
19.8.2;12.8.2 Assumption and mutual assumption of rationality;708
19.8.3;12.8.3 Characterization;709
19.8.4;12.8.4 Discussion;710
19.8.4.1;12.8.4.1 Issues in the characterization of IA;711
19.8.4.2;12.8.4.2 Extensive-form analysis and strategic-form refinements;712
19.9;Acknowledgement;714
19.10;References;714
20;Chapter 13: Population Games and Deterministic Evolutionary Dynamics;720
20.1;13.1 Introduction;722
20.2;13.2 Population Games;724
20.2.1;13.2.1 Definitions;724
20.2.2;13.2.2 Examples;725
20.2.3;13.2.3 The geometry of population games;726
20.3;13.3 Revision Protocols and Mean Dynamics;729
20.3.1;13.3.1 Revision protocols;730
20.3.2;13.3.2 Information requirements for revision protocols;731
20.3.3;13.3.3 The stochastic evolutionary process and mean dynamics;732
20.3.4;13.3.4 Finite horizon deterministic approximation;734
20.4;13.4 Deterministic Evolutionary Dynamics;735
20.4.1;13.4.1 Definition;735
20.4.2;13.4.2 Incentives and aggregate behavior;735
20.5;13.5 Families of Evolutionary Dynamics;737
20.5.1;13.5.1 Imitative dynamics;738
20.5.1.1;13.5.1.1 Definition;740
20.5.1.2;13.5.1.2 Examples;741
20.5.1.3;13.5.1.3 Basic properties;742
20.5.1.4;13.5.1.4 Inflow-outflow symmetry;743
20.5.2;13.5.2 The best response dynamic and related dynamics;744
20.5.2.1;13.5.2.1 Target protocols and target dynamics;744
20.5.2.2;13.5.2.2 The best response dynamic;744
20.5.2.3;13.5.2.3 Perturbed best response dynamics;746
20.5.3;13.5.3 Excess payoff and pairwise comparison dynamics;748
20.5.3.1;13.5.3.1 Excess payoff dynamics;749
20.5.3.2;13.5.3.2 Pairwise comparison dynamics;750
20.6;13.6 Potential Games;751
20.6.1;13.6.1 Population games and full population games;752
20.6.2;13.6.2 Definition, characterization, and interpretation;752
20.6.3;13.6.3 Examples;753
20.6.4;13.6.4 Characterization of equilibrium;755
20.6.5;13.6.5 Global convergence and local stability;757
20.6.6;13.6.6 Local stability of strict equilibria;758
20.7;13.7 ESS and Contractive Games;759
20.7.1;13.7.1 Evolutionarily stable states;759
20.7.2;13.7.2 Contractive games;761
20.7.3;13.7.3 Examples;762
20.7.4;13.7.4 Equilibrium in contractive games;762
20.7.5;13.7.5 Global convergence and local stability;764
20.7.5.1;13.7.5.1 Imitative dynamics;764
20.7.5.2;13.7.5.2 Target and pairwise comparison dynamics: global convergence in contractive games;765
20.7.5.3;13.7.5.3 Target and pairwise comparison dynamics: local stability of regular ESS;767
20.8;13.8 Iterative Solution Concepts, Supermodular Games, and Equilibrium Selection;768
20.8.1;13.8.1 Iterated strict dominance and never-a-best-response;768
20.8.2;13.8.2 Supermodular games and perturbed best response dynamics;769
20.8.3;13.8.3 Iterated p-dominance and equilibrium selection;772
20.9;13.9 Nonconvergence of Evolutionary Dynamics;774
20.9.1;13.9.1 Examples;775
20.9.2;13.9.2 Survival of strictly dominated strategies;779
20.10;13.10 Connections and Further Developments;781
20.10.1;13.10.1 Connections with stochastic stability theory;781
20.10.2;13.10.2 Connections with models of heuristic learning;782
20.10.3;13.10.3 Games with continuous strategy sets;784
20.10.4;13.10.4 Extensive form games and set-valued solution concepts;785
20.10.5;13.10.5 Applications;786
20.11;Acknowledgements;787
20.12;References;787
21;Chapter 14: The Complexity of Computing Equilibria;796
21.1;14.1 The Task;796
21.2;14.2 Problems and Algorithms;797
21.3;14.3 Good Algorithms;798
21.4;14.4 P and NP;801
21.5;14.5 Reductions and NP-complete Problems;803
21.6;14.6 The Complexity of Nash Equilibrium;806
21.7;14.7 Approximation, Succinctness, and Other Topics;818
21.8;Acknowledgments;825
21.9;References;825
22;Chapter 15: Theory of Combinatorial Games;828
22.1;15.1 Motivation and an Ancient Roman War-Game Strategy;829
22.2;15.2 The Classical Theory, Sum of Games, Complexity;832
22.2.1;15.2.1 Complexity, hardness, and completeness;837
22.3;15.3 Introducing Draws;838
22.4;15.4 Adding Interactions Between Tokens;843
22.5;15.5 Partizan Games;848
22.5.1;15.5.1 Two examples: Hackenbush and Domineering;849
22.5.2;15.5.2 Outcomes and sums;850
22.5.3;15.5.3 Values;852
22.5.4;15.5.4 Simplest forms;853
22.5.5;15.5.5 Numbers;854
22.5.6;15.5.6 Infinitesimals;856
22.5.7;15.5.7 Stops and the mean value;857
22.6;15.6 Misère Play;857
22.6.1;15.6.1 Misère Nim value;858
22.6.2;15.6.2 Genus theory;859
22.6.3;15.6.3 Misère canonical form;860
22.6.4;15.6.4 Misère quotients;861
22.7;15.7 Constraint Logic;862
22.7.1;15.7.1 The constraint-logic framework;864
22.7.2;15.7.2 One-player games;865
22.7.2.1;15.7.2.1 Bounded games;866
22.7.2.2;15.7.2.2 Unbounded games;868
22.7.3;15.7.3 Two-player games;871
22.7.4;15.7.4 Team games;872
22.8;15.8 Conclusion;873
22.9;Acknowledgment;874
22.10;References;874
23;Chapter 16: Game Theory and Distributed Control**;878
23.1;16.1 Introduction;879
23.2;16.2 Utility Design;882
23.2.1;16.2.1 Cost/Welfare-sharing games;883
23.2.2;16.2.2 Achieving potential game structures;885
23.2.3;16.2.3 Efficiency of equilibria;887
23.3;16.3 Learning Design;890
23.3.1;16.3.1 Preliminaries: repeated play of one-shot games;890
23.3.2;16.3.2 Learning Nash equilibria in potential games;891
23.3.2.1;16.3.2.1 Fictitious play and joint strategy fictitious play;891
23.3.2.2;16.3.2.2 Simple experimentation dynamics;894
23.3.2.3;16.3.2.3 Equilibrium selection: log-linear learning and its variants;895
23.3.2.4;16.3.2.4 Near potential games;897
23.3.3;16.3.3 Beyond potential games and equilibria: efficient action profiles;898
23.3.3.1;16.3.3.1 Learning efficient pure Nash equilibria;898
23.3.3.2;16.3.3.2 Learning pareto efficient action profiles;900
23.4;16.4 Exploiting the Engineering Agenda: State-Based Games;902
23.4.1;16.4.1 Limitations of strategic form games;903
23.4.1.1;16.4.1.1 Limitations of protocol design;903
23.4.1.2;16.4.1.2 Distributed optimization: consensus;905
23.4.2;16.4.2 State-based games;907
23.4.3;16.4.3 Illustrations;908
23.4.3.1;16.4.3.1 Protocol design;908
23.4.3.2;16.4.3.2 Distributed optimization;908
23.5;16.5 Concluding Remarks;912
23.6;References;913
24;Chapter 17: Ambiguity and Nonexpected Utility;918
24.1;17.1 Introduction;919
24.2;Part I Nonexpected Utility Theory Under Risk;921
24.3;17.2 Nonexpected Utility: Theories and Implications;921
24.3.1;17.2.1 Preliminaries;921
24.3.2;17.2.2 Three approaches;922
24.3.3;17.2.3 The existence of Nash equilibrium;923
24.3.4;17.2.4 Atemporal dynamic consistency;924
24.3.5;17.2.5 Implications for the theory of auctions;926
24.4;17.3 Rank-Dependent Utility Models;930
24.4.1;17.3.1 Introduction;930
24.4.2;17.3.2 Representations and interpretation;931
24.4.3;17.3.3 Risk attitudes and interpersonal comparisons ofrisk aversion;933
24.4.4;17.3.4 The dual theory;934
24.5;17.4 Cumulative Prospect Theory;936
24.5.1;17.4.1 Introduction;936
24.5.2;17.4.2 Trade-off consistency and representation;936
24.6;Part II Nonexpected Utility Theory Under Uncertainty;938
24.7;17.5 Decision Problems under Uncertainty;938
24.7.1;17.5.1 The decision problem;938
24.7.2;17.5.2 Mixed actions;940
24.7.3;17.5.3 Subjective expected utility;943
24.8;17.6 Uncertainty Aversion: Definition andRepresentation;946
24.8.1;17.6.1 The Ellsberg paradox;946
24.8.2;17.6.2 Uncertainty aversion;948
24.8.3;17.6.3 Uncertainty averse representations;949
24.9;17.7 Beyond Uncertainty Aversion;952
24.9.1;17.7.1 Incompleteness;952
24.9.2;17.7.2 Smooth ambiguity model;953
24.10;17.8 Alternative Approaches;955
24.10.1;17.8.1 Choquet expected utility;956
24.10.2;17.8.2 Uncertainty aversion revisited;958
24.10.3;17.8.3 Other models;959
24.11;17.9 Final Remarks;960
24.12;Acknowledgments;960
24.13;References;960
25;Chapter 18: Calibration and Expert Testing;966
25.1;18.1 Introduction;967
25.2;18.2 Terminology and Notation;968
25.3;18.3 Examples;971
25.3.1;18.3.1 Example 1;971
25.3.2;18.3.2 Example 2;972
25.3.3;18.3.3 Example 3;973
25.4;18.4 Calibration;974
25.4.1;18.4.1 Definition and result;974
25.4.2;18.4.2 Calibrated forecasting rule;975
25.4.3;18.4.3 Sketch of proof;976
25.4.4;18.4.4 Sketch of proof of Blackwell's theorem;978
25.5;18.5 Negative Results;979
25.5.1;18.5.1 Generalizations of Foster and Vohra's result;980
25.5.2;18.5.2 Prequential principle;982
25.5.3;18.5.3 Interpretations;983
25.6;18.6 Positive Results;985
25.6.1;18.6.1 Category tests;985
25.6.2;18.6.2 A simple example of a good test;986
25.6.3;18.6.3 Other good tests;987
25.6.4;18.6.4 Good “prequential” tests;989
25.7;18.7 Restricting the Class of Allowed Data-Generating Processes;990
25.8;18.8 Multiple Experts;992
25.9;18.9 Bayesian and Decision-Theoretic Approachesto Testing Experts;995
25.9.1;18.9.1 Bayesian approach;995
25.9.2;18.9.2 Decision-theoretic approach;996
25.10;18.10 Related Topics;997
25.10.1;18.10.1 Falsifiability and philosophy of science;997
25.10.2;18.10.2 Gaming performance fees by portfolio managers;998
25.11;Acknowledgment;1000
25.12;References;1000
26;Index;1002

Leseproben

Chapter 2 Advances in Zero-Sum Dynamic Games
Rida Laraki*,†; Sylvain Sori‡    * CNRS in LAMSADE (Université Paris-Dauphine), France
† Econimicsonomics Department at Ecole Polytechnique, France
‡ Mathematics, CNRS, IMJ-PRG, UMR 7586, Sorbonne Universites, UPMC Univ Paris 06, Univ Paris Diderot, Sorbonne Paris Cite, Paris, France Abstract
The survey presents recent results in the theory of two-person zero-sum repeated games and their connections with differential and continuous-time games. The emphasis is made on the following (1) A general model allows to deal simultaneously with stochastic and informational aspects. (2) All evaluations of the stage payoffs can be covered in the same framework (and not only the usual Cesàro and Abel means). (3) The model in discrete time can be seen and analyzed as a discretization of a continuous time game. Moreover, tools and ideas from repeated games are very fruitful for continuous time games and vice versa. (4) Numerous important conjectures have been answered (some in the negative). (5) New tools and original models have been proposed. As a consequence, the field (discrete versus continuous time, stochastic versus incomplete information models) has a much more unified structure, and research is extremely active. Keywords repeated stochastic and differential games discrete and continuous time Shapley operator incomplete information imperfect monitoring asymptotic and uniform value dual game weak and strong approachability. JEL Codes C73.C61 C62 AMS Codes 91A5 91A23 91A25 2.1 Introduction
The theory of repeated games focuses on situations involving multistage interactions, where, at each period, the Players are facing a stage game in which their actions have two effects: they induce a stage payoff, and they affect the future of the game (note the difference with other multimove games like pursuit or stopping games where there is no stage payoff). If the stage game is a fixed zero-sum game G, repetition adds nothing: the value and optimal strategies are the same as in G. The situation, however, is drastically different for nonzero-sum games leading to a family of so-called Folk theorems: the use of plans and threats generates new equilibria (Sorin's (1992) chapter 4 in Handbook of Game Theory (HGT1)). In this survey, we will concentrate on the zero-sum case and consider the framework where the stage game belongs to a family m, ?M, of two-person zero-sum games played on action sets I×J. Two basic classes of repeated games that have been studied and analyzed extensively in previous volumes of HGT are stochastic games (the subject of Mertens's (2002) chapter 47 and Vieille's (2002) chapter 48 in HGT3) and incomplete information games (the subject of Zamir's (1992) chapter 5 in HGT1). The reader is referred to these chapters for a general introduction to the topic and a presentation of the fundamental results. In stochastic games, the parameter m, which determines which game is being played, is a publicly known variable, controlled by the Players. It evolves over time and its value mn + 1 at stage n+1 (called the state) is a random stationary function of the triple (in, jn, mn) which are the moves, respectively the state, at stage n. At each period, both Players share the same information and, in particular, know the current state. On the other hand, the state is changing and the issue for the Players at stage n is to control both the current payoff gn (induced by (in, jn, mn)) and the next state mn + 1. In incomplete information games, the parameter m is chosen once and for all by nature and kept fixed during play, but at least one Player does not have full information about it. In this situation, the issue is the trade-off between using the information (which increases the set of strategies in the stage game) and revealing it (this decreases the potential advantage for the future). We will see that these two apparently very different models—evolving known state versus unknown fixed state—are particular incarnations of a more general model and share many common properties. 2.1.1 General model of repeated games (RG)
The general presentation of this section follows Mertens et al. (1994). To make it more accessible, we will assume that all sets (of actions, states, and signals) are finite; in the general case, measurable and/or topological hypotheses are in order, but we will not treat such issues here. Some theorems will be stated with compact action spaces. In that case, payoff and transition functions are assumed to be continuous. Let M be a parameter space and g a function from I×J×M to . For every m?M, this defines a two Player zero-sum game with action sets I and J for Player 1 (the maximizer) and Player 2, respectively, and with a payoff function g(?, m). The initial parameter m1 is chosen at random and the Players receive some initial information about it, say a1 (resp. b1 for Player 1 (resp. Player 2). This choice of nature is performed according to some initial probability distribution on p A×B ×M, where A and B are the signal sets ofeach Player. The game is then played in discrete time. At each stage n = 1,2,…, Player 1 (resp. Player 2) chooses an action in?I (resp. jn?J). This determines a stage payoff gn = g(in, jn, mn), where mn is the current value of the state parameter. Then, a new value mn+1 of the parameter is selected and the Players Advances in zero-sum dynamic games get some information about it. This is generated by a map Q from I×J×M to the set of probability distributions on A×B×M. Moreprecisely, atstage n+1, a triple (an+1, bn+1, mn+1) is chosen according to the distribution Q(in, jn, mn) and an+1 (resp. bn+1) is transmitted to Player 1 (resp. Player 2). Note that each signal may reveal some information about the previous choice of actions (in, jn) and/or past and current values (mn and mn + 1) of the parameter: Stochastic games (with standard signaling: perfect monitoring) (Mertens, 2002) correspond to public signals including the parameter: an + 1 = bn + 1 = {in, jn, mn + 1}. Incomplete information repeated games (with standard signaling) (Zamir, 1992) correspond to an absorbing transition on the parameter (mn = m1 for every n) and no further information (after the initial one) on the parameter, but previous actions are observed: an + 1 = bn + 1 = {in, jn}. A play of the game induces a sequence m1, a1, b1, i1, j1, m2, a2, b2, i2, j2,…, while the information of Player 1 before his move at stage n is a private history of him of the form (a1, i1, a2, i2,an) and similarly for Player 2. The corresponding sequence of payoffs is g1, g2,… and it is not known to the Players (unless it can be deduced from the signals). A (behavioral) strategy s for Player 1 is a map from Player 1 private histories to (I) the space of probability distributions on the set of actions I: in this way, s defines the probability distribution of the current stage action as a function of the past events known to Player 1: a behavioral strategy t for Player 2 is defined similarly. Together with the components of the game, p and Q, a pair (s,t) of behavioral strategies induces a probability distribution on plays, and hence on the sequence of payoffs. E(s, t) stands for the corresponding expectation. 2.1.2 Compact evaluations
Once the description of the repeated game is specified, strategy sets are well defined as well as the play (or the distribution on plays) that they...