阿司匹林泡腾片 阿司匹林加维生素C泡腾片的制备

title: Strategies and Games : Theory and Practice author: Dutta, Prajit K. publisher: MIT Press isbn10 | asin: 0262041693 print isbn13: 9780262041690 ebook isbn13: 9780585070223 language: English subject Game theory, Equilibrium (Economics) publication date: 1999 lcc: HB144.D88 1999eb ddc: 330/.01/5193 subject: Game theory, Equilibrium (Economics) cover Page III Strategies and Games Theory and Practice Prajit K. Dutta THE MIT PRESS CAMBRIDGE, MASSACHUSETTS LONDON, ENGLAND page_iii Page IV © 1999 Massachusetts Institute of Technology All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher. This book was set in Melior and MetaPlus by Windfall Software using ZzTEX and was printed and bound in the United States of America. Library of Congress Cataloging-in-Publication Data Dutta, Prajit K. Strategies and games: theory and practice / Prajit K. Dutta. p. cm. Includes bibliographical references and index. ISBN 0-262-04169-3 1. Game theory. 2. Equilibrium (Economics). I. Title. HB144.D88 1999 330'.01'15193dc21 98-42937 CIP page_iv Page V MA AAR BABA KE page_v Page VII BRIEF CONTENTS Preface XXI A Reader's Guide XXIX Part One Introduction 1 Chapter 1 A First Look at the Applications 3 2 A First Look at the Theory 17 Two Strategic Form Games: Theory and Practice 33 3 Strategic Form Games and Dominant Strategies 35 4 Dominance Solvability 49 5 Nash Equilibrium 63 6 An Application" Cournot Duopoly 75 7 An Application: The Commons Problem 91 8 Mixed Strategies 103 9 Two Applications: Natural Monopoly and Bankruptcy Law 121 10 Zero-Sum Games 139 Three Extensive Form Games: Theory and Applications 155 11 Extensive Form Games and Backward Induction 157 12 An Application: Research and Development 179 13 Subgame Perfect Equilibrium 193 14 Finitely Repeated Games 209 15 Infinitely Repeated Games 227 16 An Application: Competition and Collusion in the NASDAQ Stock Market 243 17 An Application: OPEC 257 18 Dynamic Games with an Application to the Commmons Problem 275 Four Asymmetric Information Games: Theory and Applications 291 19 Moral Hazard and Incentives Theory 293 20 Games with Incomplete Information 309 page_vii Page VIII 21 An Application: Incomplete Information in a Cournot Duopoly 331 22 Mechanism Design, the Revelation Principle, and Sales to an Unknown Buyer 349 23 An Application: Auctions 367 24 Signaling Games and the Lemons Problem 383 Five Foundations 401 25 Calculus and Optimization 403 26 Probability and Expectation 421 27 Utility and Expected Utility 433 28 Existence of Nash Equilibria 451 Index 465 page_viii Page IX CONTENTS Preface XXI A Reader's Guide XXIX Part One Indroduction 1 Chapter 1 A First Look at the Applications 3 1.1 Gabes That We Play 3 1.2 Background 7 1.3 Examples 8 Summary 12 Exercises 12 Chapter 2 A First Look at the Theory 17 2.1 Rules of the Game: Background 17 2.2 Who, What, When: The Extensive Form 18 2.2.1 Information Sets and Strategies 20 2.3 Who What, When: The Normal (or Strategic) Form 21 2.4 How Much: Von Neumann-Morgenstern Utility Function 23 2.5 Representation of the Examples 25 Summary 27 Exercises 28 Part Two Strategic Form Games: Theory and Practice 33 Chapter 3 Strategic Form Games and Dominant Strategies 35 3.1 Strategic Form Games 35 3.1.1 Examples 36 3.1.2 Equivalence with the Extensive Form 39 3.2 Case Study The Strategic Form of Art Auctions 40 3.2.1 Art Auctions: A Description 40 3.2.2 Art Auctions: The Strategic Form 40 3.3 Dominant Strategy Solution 41 page_ix Page X 3.4 Cae Study Again A Dominant Strategy at the Auction 43 Summary 44 Exercises 45 Chapter 4 Dominance Solvability 49 4.1 The Idea 49 4.1.1 Dominated and Undominated Strategies 49 4.1.2 Iterated Elimination of Dominated Strategies 51 4.1.3 More Examples 51 4.2 Case Study Electing the United Nations Secretary General 54 4.3 A More Formal Definition 55 4.4 A Discussion 57 Summary 59 Exercises 59 Chapter 5 Nash Equilibrium 63 5.1 The Concept 63 5.1.1 Intuition and Definition 63 5.1.2 Nash Parables 64 5.2 Examples 66 5.3 Case Study Nash Equilibrium in the Animal Kingdom 68 5.4 Relation Between the Solution Concepts 69 Summary 71 Exercises 71 Chapter 6 An Application: Cournot Duopoly 75 6.1 Background 75 6.2 The Basic Model 76 6.3 Cournot Nash Equilibrium 77 6.4 Cartel Solution 79 6.5 Case Study Today's OPEC 81 page_x Page XI 6.6 Variants on the Main Theme I: A Graphical Analysis 82 6.6.1 The IEDS Solution to the Cournot Model 84 6.7 Variants on the Main Theme II: Stackelberg Model 85 6.8 Variants on the Main Theme III: Generalization 86 Summary 87 Exercises 88 Chapter 7 An Application: The Commons Problem 91 7.1 Background: What is the Commons? 91 7.2 A Simple Model 93 7.3 Social Optimality 95 7.4 The Problem Worsens in a Large Population 96 7.5 Case Studies Buffalo, Global Warming, and the Internet 97 7.6 Averting a Tragedy 98 Summary 99 Exercises 100 Chapter 8 Mixed Strategies 103 8.1 Definition and Examples 103 8.1.1 What Is a Mixed Strategy? 103 8.1.2 Yet More Examples 106 8.2 An Implication 107 8.3 Mixed Strategies Can Dominate Some Pure Strategies 108 8.3.1 Implications for Dominant Strategy Solution and IEDS 109 8.4 Mixed Strategies are Good for Bluffing 110 8.5 Mixed Strategies and Nash Equilibrium 111 8.5.1 Mixed-Strategy Nash Equilibria in an Example 113 8.6 Case Study Random Drug Testing 114 Summary 115 Exercises 116 page_xi Page XII Chapter 9 Tow Applications: Naturla Monopoly and Bankruptcy Law 121 9.1 Chicken, Symmetric Games, and Symmetric Equilibria 121 9.1.1 Chicken 121 9.1.2 Symmetric Games and Symmetric Equilibria 122 9.2 Natural Monopoly 123 9.2.1 The Economic Background 123 9.2.2 A Simple Example 124 9.2.3 War of Attrition and a General Analysis 125 9.3 Bankruptcy Law 128 9.3.1 The Legal Background 128 9.3.2 A Numerical Example 128 9.3.3 A General Analysis 130 Summary 132 Exercises 133 Chapter 10 Zero-Sum Games 139 10.1 Definition and Examples 139 10.2 Playing Safe: Maxmin 141 10.2.1 The Concept 141 10.2.2 Examples 142 10.3 Playing Sound: Minmax 144 10.3.1 The Concept and Examples 144 10.3.2 Two Results 146 10.4 Playing Nash: Playing Both Safe and Sound 147 Summary 149 Exercises 149 Part Three Extensive Form Games: Theory and Applications 155 Chapter 11 Extensive Form Games and Backward Induction 157 11.1 The Extensive Form 157 11.1.1 A More Formal Treatment 158 page_xii Page XIII 11.1.2 Strategies, Mixed Strategies, and Chance Nodes 160 11.2 Perfect Information Games: Definition and Examples 162 11.3 Backward Induction: Examples 165 11.3.1 The Power of Commitment 167 11.4 Backward Induction: A General Result 168 11.5 Connection With IEDS in the Strategic Form 170 11.6 Case Study Poison Pills and Other Takeover Deterrents 172 Summary 174 Exercises 175 Chapter 12 An Application: Research and Development 179 12.1 Background: R&D, Patents, and Ologopolies 179 12.1.1 A Patent Race in Progress: High-Definition Television 180 12.2 A Model of R&D 181 12.3 Backward Induction: Analysis of the Model 183 12.4 Some Remarks 188 Summary 189 Exercises 190 Chapter 13 Subgame Perfect Equilibrium 193 13.1 A Motivating Example 193 13.2 Subgames and Strategies Within Subgames 196 13.3 Subgame Perfect Equilibrium 197 13.4 Two More Examples 199 13.5 Some Remarks 202 13.6 Case Study Peace in the World War I Trenches 203 Summary 205 Exercises 205 Chapter 14 Finitely Repeated Games 209 14.1 Examples and Economic Applications 209 page_xiii Page XIV 14.1.1 Three Repeated Games and a Definition 209 14.1.2 Four Economic Applications 212 14.2 Finitely Repeated Games 214 14.2.1 Some General Conclusions 218 14.3 Case Study Treasury Bill Auctions 219 Summary 222 Exercises 222 Chapter 15 Infinitely Repeated Games 227 15.1 Detour Through Discounting 227 15.2 Analysis of Example 3: Trigger Strategies and Good Behavior 229 15.3 The Folk Theorem 232 15.4 Repeated Games With Imperfect Detection 234 Summary 237 Exercises 238 Chapter 16 An Application: Competition and Collusion in the NASDAQ Stock Market243 16.1 The Background 243 16.2 The Analysis 245 16.2.1 A Model of the NASDAQ Market 245 16.2.2 Collusion 246 16.2.3 More on Collusion 248 16.3 The Broker-Dealer Relationship 249 16.3.1 Order Preferencing 249 16.3.2 Dealers Big and Small 250 16.4 The Epilogue 251 Summary 252 Exercises 252 Chapter 17 An Application: OPEC 257 17.1 Oil: A Historical Review 257 page_xiv Page XV 17.1.1 Production and Price History 258 17.2 A Simple Model of the Oil Market 259 17.3 Oil Prices and the Role of OPEC 260 17.4 Repteated Games With Demand Uncertainty 262 17.5 Unobserved Quota Violations 266 17.6 Some Further Comments 269 Summary 270 Exercises 271 Chapter 18 Dynamic Games With An Application to the Commons Problem 275 18.1 Dynamic Games: A Prologue 275 18.2 The Commons Problem: A Model 276 18.3 Sustainable Development and Social Optimum 278 18.3.1 A Computation of the Social Optimum 278 18.3.2 An Explanation of the Social Optimum 281 18.4 Achievable Development and Game Equilibrium 282 18.4.1 A Computation of the Game Equilibrium 282 18.4.2 An Explanation of the Equilibrium 284 18.4.3 A Comparison of the Socially Optimal and the Equilibrium Outcomes 285 18.5 Dynamic Games: An Epilogue 286 Summary 287 Exercises 288 Part Four Asymmetric Information Games: Theory and Applications 291 Chapter 19 Moral Hazard and Incentives Theory 293 19.1 Moral Hazard: Examples and a Definition 293 29.2 A Principal-Agent Model 295 19.2.1 Some Examples of Incentive Schemes 297 19.3 The Optimal Incentive Scheme 299 19.3.1 No Moral Hazard 299 page_xv Page XVI 19.3.2 Moral Hazard 299 19.4 Some General Conclusions 301 19.4.1 Extensions and Generalizations 303 19.5 Case Study Compensating Primary Care Physicians in an HMO 304 Summary 305 Exercises 306 Chapter 20 Games with Incomplete Information 309 20.1 Some Examples 309 20.1.1 Some Analysis of the Examples 312 20.2 A Complete Analysis of Example 4 313 20.2.1 Bayes-Nash Equilibrium 313 20.2.2 Pure-Strategy Bayes-Nash Equilibria 315 20.2.3 Mixed-Strategy Bayes-Nash Equilibria 316 20.3 More General Considerations 318 20.3.1 A Modified Example 318 20.3.2 A General Framework 320 20.4 Dominance-Based Solution Concepts 321 20.5 Case Study Final Jeopardy 323 Summary 326 Exercises 326 Chapter 21 An Application: Incomplete Information in a Cournot Duopoly 331 21.1 A Model and its Equilibrium 331 21.1.1 The Basic Model 331 21.1.2 Bayes-Nash Equilibrium 332 21.2 The Complete Information Solution 336 21.3 Revealing Costs to a Rival 338 21.4 Two-Sided Incompleteness of Information 340 21.5 Generalizations and Extensions 341 21.5.1 Oligopoly 341 page_xvi Page XVII 21.5.2 Demand Uncertainty 342 Summary 343 Exercises 343 Chapter 22 Mechanism Design, The Revelation Priciple, and Sales to an Unknown Buyer 349 22.1 Mechanism Design: The Economic Context 349 22.2 A Simple Example: Selling to a Buyer With an Unknown Valuation 351 22.2.1 Known Passion 351 22.2.2 Unknown Passion 352 22.3 Mechanism Design and the Revelation Principle 356 22.3.1 Single Player 356 22.3.2 Many Players 357 22.4 A More General Example: Selling Variable Amounts 358 22.4.1 Known Type 359 22.4.2 Unknown Type 359 Summary 362 Exercises 362 Chapter 23 An Application: Auctions 367 23.1 Background and Examples 367 23.1.1 Basic Model 369 23.2 Second-Price Auctions 369 23.3 First-Price Auctions 371 23.4 Optimal Auctions 373 23.4.1 How Well Do the First- and Second-Price Auctions Do? 375 23.5 Final Remarks 376 Summary 377 Exercises 378 Chapter 24 Signaling Games and the Lemons Problem 383 24.1 Motivation and Two Examples 383 24.1.1 A First Analysis of the Examples 385 page_xvii Page XVIII 24.2 A Definition, an Equilibrium Concept, and Examples 387 24.2.1 Definition 387 24.2.2 Perfect Bayesian Equilibrium 387 24.2.3 A Further Analysis of the Examples 389 24.3 Signaling Product Quality 391 24.3.1 The Bad Can Drive Out the Good 391 24.3.2 Good Can Signal Quality? 392 24.4 Case Study Used CarsA Market for Lemons? 394 24.5 Concluding Remarks 395 Summary 396 Exercises 396 Part Five Foundations 401 Chapter 25 Calculus and Optimization 403 25.1 A Calculus Primer 403 25.1.1 Functions 404 25.1.2 Slopes 405 25.1.3 Some Formulas 407 25.1.4 Concave Functions 408 25.2 An Optimization Theory Primer 409 25.2.1 Necessary Conditions 409 25.2.2 Sufficient Conditions 410 25.2.3 Feasibility Constraints 411 25.2.4 Quadratic and Log Functions 413 Summary 414 Exercises 415 Chapter 26 Probability and Expectation 421 26.1 Probability 421 26.1.1 Independence and Conditional Probability 425 26.2 Random Variables and Expectation 426 26.2.1 Conditional Expectation 427 page_xviii Page XIX Summary 428 Exercises 428 Chapter 27 Utility and Expected Utility 433 27.1 Decision Making Under Certainty 433 27.2 Decision Making Under Uncertainty 436 27.2.1 The Expected Utility Theorem and the Expected Return Puzzle 437 27.2.2 Details on the Von Neumann-Morgenstern Theorem 439 27.2.3 Payoffs in a Game 441 27.3 Risk Aversion 441 Summary 444 Exercises 444 Chapter 28 Existence of Nash Equilibria 452 28.1 Definition and Examples 451 28.2 Mathematical Background: Fixed Points 453 28.3 Existence of Nash Equilibria: Results and Intuition 458 Summary 460 Exercises 461 Index 465 page_xix Page XXI PREFACE This book evolved out of lecture notes for an undergraduate course in game theory that I have taught at Columbia University for the past six years. On the first two occasions I took the straight road, teaching out of available texts. But the road turned out to be somewhat bumpy; for a variety of reasons I was not satisfied with the many texts that I considered. So the third time around I built myself a small bypass; I wrote a set of sketchy lecture notes from which I taught while I assigned a more complete text to the students. Although this compromise involved minimal costs to me, it turned out to be even worse for my students, since we were now traveling on different roads. And then I (foolishly) decided to build my own highway; buoyed by a number of favorable referee reports, I decided to turn my notes into a book. I say foolishly because I had no idea how much hard work is involved in building a road. I only hope I built a smooth one. The Book's Purpose And Its Intended Audience The objective of this book is to provide a rigorous yet accessible introduction to game theory and its applications, primarily in economics and business, but also in political science, the law, and everyday life. The material is intended principally for two audiences: first, an undergraduate audience that would take this course as an elective for an economics major. (My experience has been, however, that my classes are also heavily attended by undergraduate majors in engineering and the sciences who take this course to fulfill their economics requirement.) The many applications and case studies in the book should make it attractive to its second audience, MBA students in business schools. In addition, I have tried to make the material useful to graduate students in economics and related disciplinesPh.D. students in political science, Ph.D. students in economics not specializing in economic theory, etc.who would like to have a source from which they can get a self-contained, albeit basic, treatment of game theory. Pedagogically I have had one overriding objective: to write a textbook that would take the middle road between the anecdotal and the theorem-driven treatments of the subject. On the one hand is the approach that teaches purely by examples and anecdotes. In my experience that leaves the students, especially the brighter ones, hungering for more. On the other hand, there is the more advanced approach emphasizing a rigorous treatment, but again, in my experience, if there are too few examples and applications it is difficult to keep even the brighter students interested. I have tried to combine the best elements of both approaches. Every result is precisely stated (albeit with minimal notation), all assumptions are detailed, and at least a sketch of a proof is provided. The text also contains nine chapter-length applications and twelve fairly detailed case studies. page_xxi Page XXII Distinctive Features Of The Book I believe this book improves on available undergraduate texts in the following ways. Content a full description of utility theory and a detailed analysis of dynamic game theory The book provides a thorough discussion of the single-agent decision theory that forms the underpinning of game theory. (That exercise takes up three chapters in Part Five.) More importantly perhaps, this is the first text that provides a detailed analysis of dynamic strategic interaction (in Part Three). The theory of repeated games is studied over two and a half chapters, including discussions of finitely and infinitely repeated games as well as games with varying stage payoffs. I follow the theory with two chapter-length applications: market-making on the NASDAQ financial market and the price history of OPEC. A discussion of dynamic games (in which the game environment evolves according to players' previous choices) follows along with an application to the dynamic commons problem. I believe many of the interesting applications of game theory are dynamicstudent interest seems always to heighten when I get to this part of the courseand I have found that every other text pays only cursory attention to many dynamic issues. Style emphasis on a parallel development of theory and examples Almost every chapter that introduces a new concept opens with numerical examples, some of which are well known and many of which are not. Sometimes I have a leading example and at other times a set of (small) examples. After explaining the exam-pies, I go to the concept and discuss it with reasonable rigor. At this point I return to the examples and analyze the just introduced concept within the context of the examples. At the end of a sectiona set of chapters on related ideasI devote a whole chapter, and sometimes two, to economic applications of those ideas. Length and Organization bite-sized chapters and a static to dynamic progression I decided to organize the material within each chapter in such a fashion that the essential elements of a whole chapter can be taught in one class (or a class and a half, depending on level). In my experience it has been a lot easier to keep the students engaged with this structure than with texts that have individual chapters that are, for example, over fifty pages long. The topics evolve in a natural sequence: static complete information to dynamic complete information to static incomplete information. I decided to skip much of dynamic incomplete information (other than signaling) because the questions in this part of the subject are a lot easier than the answers (and my students seemed to have little stomach for equilibrium refinements, for example). There are a few advanced topics as well; different instructors will have the freedom to decide which subset of the advanced topics they would like to teach in their course. Sections that are more difficult are marked with the symbol . Depending on level, some instructors will want to skip page_xxii Page XXIII these sections at first presentation, while others may wish to take extra time in discussing the material. Exercises At the end of each chapter there are about twenty-five to thirty problems (in the Exercises section). In addition, within the text i