Game Theory

Covering Both Noncooperative And Cooperative Games, This Comprehensive Introduction To Game Theory Also Includes Some Advanced Chapters On Auctions, Games With Incomplete Information, Games With Vector Payoffs, Stable Matchings And The Bargaining Set. Mathematically Oriented, The Book Presents Every Theorem Alongside A Proof. The Material Is Presented Clearly And Every Concept Is Illustrated With Concrete Examples From A Broad Range Of Disciplines. With Numerous Exercises The Book Is A Thorough And Extensive Guide To Game Theory From Undergraduate Through Graduate Courses In Economics, Mathematics, Computer Science, Engineering And Life Sciences To Being An Authoritative Reference For Researchers-- Acknowledgments -- Notations -- Introduction -- 1. The Game Of Chess -- 2. Utility Theory -- 3. Extensive-form Games -- 4. Strategic-form Games -- 5. Mixed Strategies -- 6. Behavior Strategies And Kuhn's Theorem -- 7. Equilibrium Refinements -- 8. Correlated Equilibria -- 9. Games With Incomplete Information And Common Priors -- 10. Games With Incomplete Information: The General Model -- 11. The Universal Belief Space -- 12. Auctions -- 13. Repeated Games -- 14. Repeated Games With Vector Payoffs -- 15. Bargaining Games --16. Coalitional Games With Transferable Utility -- 17. The Core -- 18. The Shapley Value -- 19. The Bargaining Set -- 20. The Nucleolus -- 21. Social Choice -- 22. Stable Matching -- 23. Appendices -- Index. Michael Maschler, Eilon Solan, Shmuel Zamir ; Translated From Hebrew By Ziv Hellman ; English Editor, Mike Borns. Translation Of: Torat Ha-miśḥaḳim / Shemuʼel Zamir, Mikhaʼel Mashler ṿe-elon Solan. Includes Bibliographical References (p. 958-967) And Index. Translated From Hebrew. 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 Covering both noncooperative and cooperative games, this comprehensive introduction to game theory also includes some advanced chapters on auctions, games with incomplete information, games with vector payoffs, stable matchings and the bargaining set. Mathematically oriented, the book presents every theorem alongside a proof. The material is presented clearly and every concept is illustrated with concrete examples from a broad range of disciplines. With numerous exercises the book is a thorough and extensive guide to game theory from undergraduate through graduate courses in economics, mathematics, computer science, engineering and life sciences to being an authoritative reference for researchers. A comprehensive guide to game theory, including advanced material The treatment of the material is mathematically rigorous and has clear narrative explanations Chapters are independent, allowing instructors to easily incorporate parts of the book in their teaching A comprehensive treatment of game theory. Mathematically oriented, it examines both noncooperative and cooperative games, and includes advanced topics as well as numerous exercises, and examples from economics, mathematics, computer science and management science. Written both for students studying the subject and as a reference book for researchers.