Game Theory

Contents......Page 9
Acknowledgments......Page 16
Notations......Page 17
What is game theory?......Page 25
How to use this book......Page 27
1.1 Schematic description of the game......Page 29
1.2 Analysis and results......Page 30
1.4 Exercises......Page 35
2.1 Preference relations and their representation......Page 37
2.2 Preference relations over uncertain outcomes......Page 40
2.3 The axioms of utility theory......Page 42
2.3.1 Continuity......Page 44
2.3.3 Simplification of lotteries......Page 45
2.3.4 Independence......Page 46
2.4 The characterization theorem......Page 47
2.5 Utility functions and affine transformations......Page 50
2.7 Attitude towards risk......Page 51
2.8 Subjective probability......Page 54
2.9.1 The assumption of completeness......Page 55
2.9.3 Perceptions of probability......Page 56
2.9.5 Other aspects that can influence preferences......Page 57
2.11 Exercises......Page 59
Chapter summary......Page 67
3.1 An example......Page 68
3.2 Graphs and trees......Page 69
3.3 Game trees......Page 70
3.4 Chomp: David Gale's game......Page 75
3.5 Games with chance moves......Page 77
3.6 Games with imperfect information......Page 80
3.6.1 Strategies in games with imperfect information......Page 84
3.7 Exercises......Page 85
Chapter summary......Page 103
4.1 Examples and definition of strategic-form games......Page 104
4.2 The relationship between extensive and strategic forms......Page 110
4.3 Strategic-form games: solution concepts......Page 112
4.5 Domination......Page 113
4.6 Second-price auctions......Page 119
4.8 Stability: Nash equilibrium......Page 123
4.9 Properties of the Nash equilibrium......Page 128
4.9.3 Equilibrium and evolution......Page 129
4.10 Security: the maxmin concept......Page 130
4.11 Elimination of dominated strategies......Page 134
4.12 Two-player zero-sum games......Page 138
4.13 Games with perfect information......Page 146
4.14.1 A two-player zero-sum game on the unit square......Page 149
4.14.2 A two-player non-zero-sum game on the unit square......Page 151
4.16 Exercises......Page 156
Chapter summary......Page 172
5.1 The mixed extension of a strategic-form game......Page 173
5.2 Computing equilibria in mixed strategies......Page 180
5.2.1 The direct approach......Page 181
5.2.2 Computing equilibrium points......Page 185
5.2.3 The indifference principle......Page 187
5.2.4 Dominance and equilibrium......Page 190
5.2.5 Two-player zero-sum games and linear programming......Page 192
5.2.6 Two-player games that are not zero sum......Page 193
5.3 The proof of Nash's Theorem......Page 194
5.4 Generalizing Nash's Theorem......Page 198
5.5 Utility theory and mixed strategies......Page 200
5.6 The maxmin and the minmax in n-player games......Page 204
5.7 Imperfect information: the value of information......Page 208
5.8 Evolutionarily stable strategies......Page 214
5.10 Exercises......Page 222
Chapter summary......Page 247
6.1 Behavior strategies......Page 249
6.2.1 Conditions for the existence of an equivalent mixed strategy to any behavior strategy......Page 254
6.2.2 Representing (x;) as a product of probabilities......Page 256
6.2.3 Proof of the second direction of Theorem 6.11: sufficiency......Page 257
6.2.4 Conditions guaranteeing the existence of a behavior strategy equivalent to a mixed strategy......Page 259
6.3 Equilibria in behavior strategies......Page 263
6.4 Kuhn's Theorem for infinite games......Page 266
6.4.1 Definitions of pure strategy, mixed strategy, and behavior strategy......Page 268
6.4.2 Equivalence between mixed strategies and behavior strategies......Page 269
6.4.3 Statement of Kuhn's Theorem for infinite games and its proof......Page 270
6.5 Remarks......Page 271
6.6 Exercises......Page 272
Chapter summary......Page 279
7.1 Subgame perfect equilibrium......Page 280
7.2 Rationality, and backward and forward induction......Page 288
7.3 Perfect equilibrium......Page 290
7.3.1 Perfect equilibrium in strategic-form games......Page 292
7.3.2 Perfect equilibrium in extensive-form games......Page 295
7.4 Sequential equilibrium......Page 299
7.6 Exercises......Page 312
Chapter summary......Page 328
8.1 Examples......Page 329
8.2 Definition and properties of correlated equilibrium......Page 333
8.4 Exercises......Page 341
Chapter summary......Page 347
9.1 The Aumann model and the concept of knowledge......Page 350
9.2 The Aumann model with beliefs......Page 362
9.3 An infinite set of states of the world......Page 372
9.4 The Harsanyi model......Page 373
9.4.1 Belief hierarchies......Page 377
9.4.2 Strategies and payoffs......Page 379
9.4.3 Equilibrium in games with incomplete information......Page 381
9.5 A possible interpretation of mixed strategies......Page 389
9.6 The common prior assumption......Page 393
9.7 Remarks......Page 395
9.8 Exercises......Page 396
10.1 Belief spaces......Page 414
10.2 Belief and knowledge......Page 419
10.3 Examples of belief spaces......Page 422
10.4 Belief subspaces......Page 428
10.5 Games with incomplete information......Page 435
10.6 The concept of consistency......Page 443
10.8 Exercises......Page 451
Chapter summary......Page 468
11.1 Belief hierarchies......Page 470
11.2 Types......Page 478
11.3 Definition of the universal belief space......Page 481
11.5 Exercises......Page 484
Chapter summary......Page 489
12.2 Common auction methods......Page 492
12.3 Definition of a sealed-bid auction......Page 493
12.4 Equilibrium......Page 496
12.5 The symmetric model......Page 499
12.5.1 Analyzing auctions: an example......Page 500
12.5.2 Equilibrium strategies......Page 502
12.5.3 The Revenue Equivalence Theorem......Page 506
12.5.4 Entry fees......Page 510
12.6 The Envelope Theorem......Page 512
12.7 Risk aversion......Page 516
12.8 Mechanism design......Page 520
12.8.1 The revelation principle......Page 524
12.8.2 The Revenue Equivalence Theorem......Page 525
12.9 Individually rational mechanisms......Page 528
12.10 Finding the optimal mechanism......Page 529
12.11 Remarks......Page 536
12.12 Exercises......Page 537
Chapter summary......Page 547
13.1 The model......Page 548
13.2 Examples......Page 549
13.3 The T-stage repeated game......Page 552
13.3.1 Histories and strategies......Page 553
13.3.2 Payoffs and equilibria......Page 555
13.3.3 The minmax value......Page 557
13.4 Equilibrium payoffs of the T-stage repeated game......Page 558
13.4.1 Proof of the Folk Theorem: example......Page 559
13.4.2 Detailed proof of the Folk Theorem......Page 562
13.5 Infinitely repeated games......Page 565
13.6 The discounted game......Page 570
13.7 Uniform equilibrium......Page 574
13.8 Discussion......Page 582
13.10 Exercises......Page 583
Chapter summary......Page 597
14.1 Notation......Page 598
14.2 The model......Page 600
14.3 Examples......Page 601
14.4 Approachable and excludable sets......Page 602
14.5 The approachability of a set......Page 604
14.6 Characterizations of convex approachable sets......Page 613
14.7 Application 1: Repeated games......Page 618
14.8 Application 2: Challenge the expert......Page 628
14.8.1 The model......Page 629
14.8.2 Existence of a no-regret strategy: a special case......Page 631
14.8.3 Existence of a no-regret strategy: the general case......Page 633
14.9 Discussion......Page 634
14.10 Remarks......Page 635
14.11 Exercises......Page 636
Chapter summary......Page 650
15.2 The model......Page 653
15.3 Properties of the Nash solution......Page 654
15.3.2 Efficiency......Page 655
15.3.3 Covariance under positive affine transformations......Page 656
15.3.4 Independence of irrelevant alternatives (IIA)......Page 657
15.4 Existence and uniqueness of the Nash solution......Page 658
15.5 Another characterization of the Nash solution......Page 663
15.5.1 Interpersonal comparison of utilities......Page 665
15.5.2 The status quo region......Page 666
15.6 The minimality of the Nash solution......Page 667
15.7 Critiques of the properties of the Nash solution......Page 669
15.8 Monotonicity properties......Page 671
15.9 Bargaining games with more than two players......Page 678
15.11 Exercises......Page 681
Chapter summary......Page 687
16.1.1 Profit games......Page 689
16.1.2 Cost games......Page 690
16.1.3 Simple games......Page 691
16.1.4 Weighted majority games......Page 692
16.1.6 Sequencing games......Page 693
16.1.7 Spanning tree games......Page 694
16.1.8 Cost-sharing games......Page 695
16.2 Strategic equivalence......Page 696
16.3 A game as a vector in a Euclidean space......Page 698
16.4 Special families of games......Page 699
16.5 Solution concepts......Page 700
16.6 Geometric representation of the set of imputations......Page 704
16.8 Exercises......Page 706
Chapter summary......Page 714
17.1 Definition of the core......Page 715
17.2 Balanced collections of coalitions......Page 719
17.3 The Bondareva--Shapley Theorem......Page 723
17.3.1 The Bondareva--Shapley condition is a necessary condition for the nonemptiness of the core......Page 725
17.3.2 The Bondareva--Shapley condition is a sufficient condition for the nonemptiness of the core......Page 726
17.3.3 A proof of the Bondareva--Shapley Theorem using linear programming......Page 729
17.4 Market games......Page 730
17.4.1 The balanced cover of a coalitional game......Page 736
17.4.2 Every totally balanced game is a market game......Page 737
17.5 Additive games......Page 740
17.6 The consistency property of the core......Page 743
17.7 Convex games......Page 745
17.8 Spanning tree games......Page 749
17.9 Flow games......Page 752
17.10 The core for general coalitional structures......Page 760
17.12 Exercises......Page 763
Chapter summary......Page 776
18.1.2 Symmetry......Page 777
18.1.4 The null player property......Page 778
18.2 Solutions of some of the Shapley properties......Page 779
18.3 The definition of the Shapley value......Page 782
18.4 Examples......Page 786
18.5.1 The marginality property......Page 788
18.5.2 The second characterization of the Shapley value......Page 789
18.6 Application: the Shapley-Shubik power index......Page 791
18.6.1 The power index of the United Nations Security Council......Page 793
18.7 Convex games......Page 795
18.8 The consistency of the Shapley value......Page 796
18.10 Exercises......Page 802
Chapter summary......Page 810
19.1 Definition of the bargaining set......Page 812
19.3 The bargaining set in three-player games......Page 816
19.4 The bargaining set in convex games......Page 822
19.5 Discussion......Page 825
19.7 Exercises......Page 826
Chapter summary......Page 829
20.1 Definition of the nucleolus......Page 830
20.2 Nonemptiness and uniqueness of the nucleolus......Page 833
20.3 Properties of the nucleolus......Page 837
20.4 Computing the nucleolus......Page 843
20.5 Characterizing the prenucleolus......Page 844
20.6 The consistency of the nucleolus......Page 851
20.7 Weighted majority games......Page 853
20.8 The bankruptcy problem......Page 859
20.8.2 The case n=2......Page 861
20.8.3 The case n>2......Page 863
20.8.4 The nucleolus of a bankruptcy problem......Page 866
20.9 Discussion......Page 870
20.10 Remarks......Page 871
20.11 Exercises......Page 872
Chapter summary......Page 881
21.1 Social welfare functions......Page 884
21.2 Social choice functions......Page 892
21.3 Non-manipulability......Page 899
21.4 Discussion......Page 901
21.6 Exercises......Page 902
Chapter summary......Page 912
22.1 The model......Page 914
22.2 The men's courtship algorithm......Page 916
22.3 The women's courtship algorithm......Page 918
22.4 Comparing matchings......Page 920
22.4.1 The lattice structure of the set of stable matchings......Page 925
22.5.1 When the number of men does not equal the number of women......Page 926
22.5.2 Strategic considerations......Page 927
22.5.3 The desire to remain single, or: getting married, but not at any price......Page 928
22.5.4 Polygamous matching: placement of students in universities......Page 931
22.5.5 Unisexual matchings......Page 932
22.7 Exercises......Page 933
23.1 Fixed point theorems......Page 944
23.1.1 Sperner's Lemma......Page 945
23.1.2 Brouwer's Fixed Point Theorem......Page 963
23.1.3 Kakutani's Fixed Point Theorem......Page 966
23.1.4 The KKM Theorem......Page 969
23.2 The Separating Hyperplane......Page 971
23.3 Linear programming......Page 973
23.5 Exercises......Page 978
References......Page 986
Index......Page 996