Game Theory TheNewPalgraveEconomicsCollection Editors:StevenN.Durlauf,UniversityofWisconsin-Madison,USA&LawrenceE.Blume, CornellUniversity,USA Alsointheseries: BehaviouralandExperimetalEconomics EconomicGrowth MacroeconometricsandTimeSeriesAnalysis Microeconometrics MonetaryEconomics SeriesStandingOrderISBN978-0-230-24014-8hardcover SeriesStandingOrderISBN978-0-230-24013-1paperback ToreceivefuturetitlesinthisseriesastheyarepublishedquoteoneoftheISBNslistedabovetoset upastandingorder:contactyourbookseller;writetoCustomerServicesDepartment,Macmillan DistributionLtd,Houndmills,Basingstoke,Hampshire,RG216XS;[email protected]. 7,680 page Including articles by over 1,500 eminent contributors and providing a current overview of economics, this second edition of The New Palgrave is now available both in print and online. LAUST NEWS hqLlldil\' lrap ~ , .... ,~. Ih ..... ... ........ ~ .. h" ::-"'!~~~'~oI7:'!:..':~t:.~I~_!':~ , • '" .~, ,,_ • '. ~. .. .hd '", .. , .. , .. ~, •• ~I ,. .. .." ~II~._'" ..... ' . . . . & • • • • • Is regularly updated with new articles and updates to existing articles, along with new features and functionality Experience the world of economics at your fingertips! • Allows 24x7 access to members of subscribing institutions, outside library opening hours, on the move, at home or at Why not see for yourseLf how their desk vaLuabLe the online Dictionary is by encouraging your librarian to • Offers excellent search and browse facilities, both request a triaL today? full text and advanced, which make it possible to explore the Dictionary with great speed and ease Free 2 week trials of The New Palgrave Dictionary of Economics • Contains hyperlinked cross-references within articles, making On/ine are now availabLe to it an indispensable tool for researchers and students prospective institutionaL • Features carefully selected and maintained links to related sites, subscribers worLdwide. Your sources of further information and bibliographical citations Librarian can register today at www.dictionaryofeconomics.com. • Enables users to save searches, make personal annotations and bookmark articles they need to refer to regularly by using 'My Dictionary' * www.dictionaryofeconomics.com Game Theory Edited by Steven N. Durlauf University of Wisconsin-Madison, USA Lawrence E. Blume Cornell University, USA &MacmillanPublishersLtd2008,2010 Softcover reprint of the hardcover 1st edition 2010 978-0-230-23889-3 AllarticlesfirstpublishedinTheNewPalgraveDictionaryofEconomics,2ndEdition EditedbyStevenN.DurlaufandLawrenceE.Blume ineightvolumes,2008 with the exception of Incentive Compatibility which first published in The New Palgrave:ADictionaryofEconomics EditedbyJohnEatwell,MurrayMilgateandPeterNewman infourvolumes,1987 Allrightsreserved.Noreproduction,copyortransmissionofthis publicationmaybemadewithoutwrittenpermission. Noportionofthispublicationmaybereproduced,copiedortransmitted savewithwrittenpermissionorinaccordancewiththeprovisionsofthe Copyright,DesignsandPatentsAct1988,orunderthetermsofanylicence permittinglimitedcopyingissuedbytheCopyrightLicensingAgency, SaffronHouse,6-10KirbyStreet,LondonEC1N8TS. Anypersonwhodoesanyunauthorizedactinrelationtothispublication maybeliabletocriminalprosecutionandcivilclaimsfordamages. Theauthorshaveassertedtheirrighttobeidentifiedastheauthorofthis workinaccordancewiththeCopyright,DesignsandPatentsAct1988. Firstpublished2010by PALGRAVEMACMILLAN PalgraveMacmillanintheUKisanimprintofMacmillanPublishersLimited, registeredinEngland,companynumber785998,ofHoundmills,Basingstoke, HampshireRG216XS. PalgraveMacmillanintheUSisadivisionofStMartin’sPressLLC, 175FifthAvenue,NewYork,NY10010. PalgraveMacmillanistheglobalacademicimprintoftheabovecompanies andhascompaniesandrepresentativesthroughouttheworld. PalgravesandMacmillansareregisteredtrademarksintheUnitedStates, theUnitedKingdom,Europeandothercountries. ISBN 978-0-230-23890-9 ISBN 978-0-230-28084-7 (eBook) DOI 10.1057/9780230280847 Thisbookisprintedonpapersuitableforrecyclingandmadefromfully managedandsustainedforestsources.Logging,pulpingandmanufacturing processesareexpectedtoconformtotheenvironmentalregulationsofthe countryoforigin. AcataloguerecordforthisbookisavailablefromtheBritishLibrary. AcatalogrecordforthisbookisavailablefromtheLibraryofCongress. Contents List of Contributors vii epistemic game theory: incomplete information 114 General Preface ix AVIAD HEIFETZ Introduction x game theory and biology 119 bargaining 1 OLOF LEIMAR ROBERTO SERRANO games in coalitional form 127 behavioural economics and EHUD KALAI game theory 20 FARUK GUL global games 144 STEPHEN MORRIS behavioural game theory 29 COLIN F. CAMERER graphical games 153 MICHAEL KEARNS cheap talk 38 VIJAY KRISHNA AND incentive compatibility 158 JOHN MORGAN JOHN O. LEDYARD computer science and game large games (structural theory 48 robustness) 169 JOSEPH Y. HALPERN EHUD KALAI cooperation 66 learning and evolution in SAMUEL BOWLES AND games: adaptive heuristics 178 HERBERT GINTIS H. PEYTON YOUNG deterministic evolutionary dynamics 78 learning and evolution in games: an overview 184 WILLIAM H. SANDHOLM WILLIAM H. SANDHOLM epistemic game theory: an overview 87 learning and evolution in ADAM BRANDENBURGER games: belief learning 191 JOHN NACHBAR epistemic game theory: beliefs and types 89 learning and evolution in MARCIANO SINISCALCHI games: ESS 199 ROSS CRESSMAN epistemic game theory: complete information 97 mechanism design 207 ADAM BRANDENBURGER ROGER B. MYERSON vi Contents mechanism design (new reputation 300 developments) 223 MARTIN W. CRIPPS SANDEEP BALIGA AND TOMAS SJO¨STRO¨M revelation principle 312 ROGER B. MYERSON mixed strategy equilibrium 235 MARK WALKER AND JOHN WOODERS Shapley value 319 SERGIU HART Nash equilibrium, refinements of 240 stochastic adaptive dynamics 325 SRIHARI GOVINDAN AND H. PEYTON YOUNG ROBERT B. WILSON strategic and extensive Nash programme 256 form games 333 ROBERTO SERRANO MARTIN J. OSBORNE non-cooperative games strategy-proof allocation (equilibrium existence) 263 mechanisms 355 PHILIP J. RENY MARK A. SATTERTHWAITE psychological games 272 supermodularity and MARTIN DUFWENBERG supermodular games 361 purification 279 XAVIER VIVES STEPHEN MORRIS INDEX 372 repeated games 286 KANODIRI MICHIHIRO List of Contributors SANDEEP BALIGA MICHAEL KEARNS Northwestern University, USA University of Pennsylvania, USA SAMUEL BOWLES VIJAY KRISHNA University of Massachusetts, USA Penn State University, USA ADAM BRANDENBURGER JOHN O. LEDYARD New York University, USA California Institute of Technology, USA COLIN F. CAMERER California Institute of Technology, USA OLOF LEIMAR Stockholm University, Sweden ROSS CRESSMAN Wilfred Laurier University, Canada KANDORI MICHIHIRO University of Tokyo, Japan MARTIN W.CRIPPS University College London, UK JOHN MORGAN University of California Berkeley, USA MARTIN DUFWENBERG University of Arizona, USA STEPHEN MORRIS Princeton University, USA HERBERT GINTIS University of Siena, Italy &University of ROGER B. MYERSON Massachusetts, USA University of Chicago, USA SRIHARI GOVINDAN JOHN NACHBAR University of Iowa, USA Washington University, St Louis, USA FARUK GUL MARTIN J. OSBORNE Princeton University, USA University of Toronto, Canada JOSEPH Y. HALPERN PHILIP J. RENY Cornell University, USA University of Chicago, USA SERGIU HART WILLIAM H. SANDHOLM The Hebrew University Jerusalem, Israel University of Wisconsin-Madison, USA AVIAD HEIFETZ MARK A. SATTERTHWAITE The Open University, Israel Northwestern University, USA EHUD KALAI ROBERTO SERRANO Northwestern University, USA Brown University, USA viii ListofContributors MARCIANO SINISCALCHI ROBERT B. WILSON Northwestern University, USA Stanford University, USA TOMAS SJO¨STRO¨M JOHN WOODERS Rutgers University, USA University of Arizona, USA XAVIER VIVES H. PEYTON YOUNG University of Navarra, Spain Johns Hopkins University, USA MARK WALKER University of Arizona, USA General Preface All economists of a certain age remember the ‘‘little green books’’. Many own a few. ThesearetheoffspringofTheNewPalgrave:ADictionaryofEconomics;collectionsof reprints from The New Palgrave that were meant to deliver at least a sense of the Dictionary into the hands of those for whom access to the entire four volume, four million word set was inconvenient or difficult. The New Palgrave Dictionary of Economics,SecondEdition largely resolvestheaccessibility problemthroughitsonline presence. But while the online search facility provides convenient access to specific topicsinthenoweightvolume,sixmillionwordDictionaryofEconomics,nointerface has yet been devised that makes browsing from a large online source a pleasurable activityforarainyafternoon.Toourdelight,TheNewPalgrave’spublishersharesour viewofthejoysofdictionary-surfing,andwearethuspleasedtopresentanewseries, the ‘‘little blue books’’, to make some part of the Dictionary accessible in the hand or lap for teachers, students, and those who want to browse. While the volumes in this series contain only articles that appeared in the 2008 print edition, readers can, of course, refer to the online Dictionary and its expanding list of entries. The selections in these volumes were chosen with several desiderata in mind: to touch on important problems, to emphasize material that may be of more general interest to economics beginners and yet still touch on the analytical core of modern economics,andtobalanceimportanttheoreticalconcernswithkeyempiricaldebates. The 1987 Eatwell, MilgateandNewman The NewPalgrave:A DictionaryofEconomics was chiefly concerned with economic theory, both the historyof its evolution and its contemporary state. The second edition has taken a different approach. While much progresshasbeen made acrosstheboardinthe21yearsbetween thefirstandsecond editions, it is particularly the flowering of empirical economics which distinguishes the present interval from the 61 year interval between Henry Higgs’ Palgrave’s DictionaryofPoliticalEconomyandTheNewPalgrave.Itisfairtosaythat,inthelong run, doctrine evolves more slowly than the database of facts, and so some of the selections in these volumes will age more quickly than others. This problem will be solvedin the online Dictionary through an ongoing process of revisions and updates. While no such solution is available for these volumes, we have tried to choose topics which will give these books utility for some time to come. Steven N. Durlauf Lawrence E. Blume