NATO ASI Series Advanced Science Institutes Series A series presenting the results of activities sponsored by the NATO Science Committee, which aims at the dissemination of advanced scientific and technological knowledge, with a view to strengthening links between scientific communities. The Series is published by an international board of publishers in conjunction with the NATO Scientific Affairs Division. A Life Sciences Plenum Publishing Corporation B Physics London and New York C Mathematical and Physical Sciences Kluwer Academic Publishers D Behavioural and Social Sciences Dordrecht, Boston and London E Applied Sciences F Computer and Systems Sciences Springer-Verlag G Ecological Sciences Berlin Heidelberg New York Barcelona H Cell Biology Budapest Hong Kong London Milan Global Environmental Change Paris Santa Clara Singapore Tokyo Partnership Sub-Series 1. Disarmament Technologies Kluwer Academic Publishers 2. Environment Springer-Verlag / Kluwer Academic Publishers 3. High Technology Kluwer Academic Publishers 4. Science and Technology Policy Kluwer Academic Publishers 5. Computer Networking Kluwer Academic Publishers The Partnership Sub-Series incorporates activities undertaken in collaboration with NATO's Cooperation Partners, the countries of the CIS and Central and Eastern Europe, in Priority Areas of concern to those countries. NATO-PCO Database The electronic index to the NATO ASI Series provides full bibliographical references ·(with keywords and/or abstracts) to about 50 000 contributions from international scientists published in all sections of the NATO ASI Series. Access to the NATO-PCO Database compiled by the NATO Publication Coordination Office is possible in two ways: - via online FILE 128 (NATO-PCO DATABASE) hosted by ESRIN, Via Galileo Galilei, 1-00044 Frascati, Italy. - via CD-ROM "NATO Science & Technology Disk" with user-friendly retrieval software in English, French and German (© WTV GmbH and DATA WARE Technologies Inc. 1992). The CD-ROM can be ordered through any member of the Board of Publishers or through NATO-PCO, B-3090 Overijse, Belgium. Series F: Computer and Systems Sciences, Vol. 155 Springer Berlin Heidelberg New York Barcelona Budapest Hong Kong London Milan Paris Santa Clara Singapore Tokyo Cooperation: Game-Theoretic Approaches Edited by Sergiu Hart Department of Economics and Department of Mathematics The Hebrew University ofJerusalem Givat Ram, 91904 Jerusalem, Israel Andreu Mas-Colell Facultat de Ciencies Economiques i Empresarials Universitat Pompeu Fabra c/ Ramon Trias Fargas, 25-27, E-08005 Barcelona, Spain Springer Published in cooperation with NATO Scientific Affairs Division Proceedings of the NATO Advanced Study Institute on Cooperation: Game-Theoretic Approaches, held at SUNY, Stony Brook, New York, July 18-29, 1994 Library of Congress Cataloging-in-Publication Data Cooperation: game-theoretic approaches I edited by Sergiu Hart, Andreu Mas-Colell, p. em. -- (NATO ASI series. Series F, Computer and systems sciences; no. 155) "Proceedings of the Nato Advanced Study Institute on Cooperation: Game-Theoretic Approaches.- held at SUNY, Stony Brook, New York, July 18-29, 1994"--T.p. verso. Includes bibliographical references. Additional material to tbis book can be downloaded from bttp:llextra.apringer.com. ISBN-13:978-3-642-64413-9 e·ISBN-13:978-3-642-60454-6 DOl: 10.10071978-3-642·60454-6 1. Game theory--Congresses. I. Hart, Sergiu. II. Mas-Colell, Andreu. III. Nato Advanced Study Institute on Cooperation: Game -Theoretic Approaches (1994 : Stony Brook, N.Y.) IV. Series: NATO ASI series. Series F, Computer and systems sciences; no. 155. QA269.C66 1997 519.3--DC20 96-27102 CIP CR Subject Classification (1991): H,1.1, J,4 ISBN -13: 978-3-642-64413-9 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. © Springer-Verlag Berlin Heidelberg 1997 Softcover reprint of the hardcover 1st edition 1997 Typesetting: Camera-ready by editor Printed on acid-free paper SPIN: 10537423 45/3142 - 5 432 1 0 Preface This volume includes the proceedings of the NATO Advance Study Institute on "Cooperation: Game Theoretic Approaches", that took place at Stony Brook, NY, USA, from July 18 to July 29, 1994. The Institute was a success and it is already part of a well established biannual Stony Brook tradition to which many researchers around the world look forward to. We thank the institute for Decision Sciences of the State University of New York at Stony Brook for hosting this event. It is a particular pleasure to thank Colleen Wallahora and Eileen Zapia, for the very successful organization of this AS!. June 1996 Sergiu Hart and Andreu Mas-Colell List of Authors Prof. Beth Allen, University of Minnesota, Minneapolis Prof. Robert J. Aumann, The Hebrew University of Jerusalem Prof. Joseph Greenberg, McGill University, Montreal Prof. Sergiu Hart, The Hebrew University of Jerusalem Prof. Vijay Krishna, Pennsylvania State University at University Park Prof. Andreu Mas-Colell, Harvard University, and Universitat Pompeu Fabra, Barcelona Prof. Abraham Neyman, The Hebrew University of Jerusalem, and State University of New York at Stony Brook Prof. Philip J. Reny, University ofPitlsburgh Prof. Reinhard Selten, Universitat Bonn Prof. Tomas Sjostrom, Harvard University Prof. Sylvain Sorin, Universite de Paris X, Nanterre, and Ecole Normale Superieure, Paris Prof. William Thomson, University of Rochester Prof. Rajiv Vohra, Brown University, Providence Table of Contents Preface v List of Authors ......................................... VI Introduction .......................................... . Sergiu Hart and Andreu Mas-Colell Introductory Remarks 5 Robert J. Aumann Part A Classical Cooperative Theory Cooperative Theory of Bargaining I: Classical 9 William Thomson Cooperative Theory of Bargaining II: Modem Development ........... 25 William Thomson Classical Cooperative Theory I: Core-Like Concepts ................ 35 SergiuHart Classical Cooperative Theory II: Value-Like Concepts ............... 43 Sergiu Hart Cooperative Theory with Incomplete Information .................. 51 Beth Allen Part B Non-Cooperative Approaches Bargaining Games ....................................... 69 Andreu Mas-Colell Two Lectures on Implementation Under Complete Information: General Results and the Core ................................ 91 Philip J. Reny VIII Implementation Theory with Incomplete Information ................ 115 Beth Al/en Coalitional Non-Cooperative Approaches to Cooperation ............. 127 Rajiv Vohra Situation Approach to Cooperation ............................ 143 Joseph Greenberg Part C Dynamic Models Cooperation Through Repetition: Complete Information .............. 169 Sylvain Sorin Communication, Correlation and Cooperation ..................... 199 Sylvain Sorin Rationality and Bounded Rationality ........................... 219 Robert J. Aumann Cooperation, Repetition, and Automata ......................... 233 Abraham Neyman Learning in Games: Fictitious Play Dynamics ..................... 257 Vijay Krishna and Thomas Sjostrom Evolution and Games: Replicator Dynamics ...................... 275 Vijay Krishna and Thomas Sjostrom Part D Descriptive Theory Descriptive Approaches to Cooperation ......................... 289 Reinhard Selten Introduction Sergiu Hart a and Andreu Mas-Colell b a The Hebrew University of Jerusalem b Harvard University and Universitat Pompeu Fabra, Barcelona This book constitutes a systematic exposition of the various game theoretic approaches to the issue of cooperation. Game Theory is the study of decision making in multi-person situations, where the outcome depends on everyone's choice. The goal of each participant is to maximize his own utility, while taking into account that the other participants are doing the same. In such interactive situations, cooperation between the agents may lead to results that are better, for everyone, that the non-cooperative outcomes. A simple - but extensively studied - example is the so-called "Prisoners' Dilemma": Assume each on of the two players can ask a generous donor either to give him I million dollars, or to give 4 million dollars to the other player, the donor will carry out the instructions of both players (thus, for example, if player I asks for $IM to himself and player 2 asks for $4M to the other, then player I gets $5M and payer 2 gets nothing). Clearly, whatever the other player does, it is strictly better for each player to ask for $IM to himself (more precisely, it will always lead to an additional" 1M). This yields $IM for each; cooperation, whereby each one asks for $4M to the other, would have yielded each $4M instead! The Prisoner's Dilemma is by no means an artificial example. The economic competition between firms exhibits similar phenomena: keeping a commodity in short supply may be to the advantage of all producers; at the same time, it may be better for any single producer to unilaterally increase his own production. The problems that need to be addressed are, first, whether cooperation can be reached at all; second, by what procedures are agreements reached; and third, which ones will be indeed attained. This volume will survey some of the contributions of game theory to these questions, from its early traditional theories to its current approaches. Game theoretical approaches are usually classified as either "cooperative" or " non-cooperative" . This should not be viewed as an exclusive division; these are 2 two ways of looking at the same problem. The Introductory Remarks of R. J. Aumann that follow this Introduction address this point in some detail. Part A, which opens this volume, surveys the classical cooperative approach. This starts by assuming that binding agreements are possible, and it abstracts away from the detailed bargaining procedures. The selection of the appropriate cooperative outcome is usually based on a set of desired postulates or axioms, which, when applied to a class of problems, characterize one or another solution concept. Chapters 1 and 2 by W. Thomson cover the pure bargaining problems, where only the grand coalition of all players can reach a beneficial agreement; Chapter 1 deals with the classical approaches that originate with Nash's 1950 seminal paper, and Chapter 2 deals with recent axiomatizations based on internal consistency properties (the" reduced game property"). Chapters 3 and 4, by S. Hart, survey the general n-person problems where subcoalitions of players can reach agreements as well, and this of course influences the final outcome. The classical cooperative solution concepts that arise are grouped into "core-like" notions and "value-like" notions. The former include the core, the stable sets of von Neumann and Morgenstern, the bargaining set, the kernel and the nucleolus; the latter include the Nash bargaining solution, the Shapley value and their many extensions and generalizations. Chapter 5 by B. Allen deals with games of incomplete information, i.e. , games where some of the participants may possess private information not known to the others. Here, the questions of cooperation are further complicated by the need to address the informational issues; how to ensure that the players have incentive to reveal the appropriate information. Part B is devoted to non-cooperative approaches, namely, non-cooperative models that lead to cooperative solutions. One may start from a non-cooperative bargaining model, like the Stahl-Rubinstein "alternating offers" procedure, characterize its strategic equilibria, and relate the resulting outcomes to various cooperative solutions. Or, one may start from a cooperative solution, and construct games whose equilibria yield precisely this given solution. Either way, one establishes connections between non-cooperative and cooperative setups, that further strengthen and reinforce one another. In the literature, all this is usually referred as "bargaining procedures", " non-cooperative foundations", or "implementation" . The distinctions are not always clear , in particular since some of the recent implementation literature is concerned with "natural" and "simple" games. Chapter 6 by A. Mas-Colell covers bargaining procedures that lead to value-like cooperative solutions, and the second part of Chapter 7 by P. Reny and Chapter 8 by B. Allen, for the case of complete information and incomplete information, respectively. Chapter 9 by R. Vohra discusses coalitional non cooperative approaches -i.e., models where not only individuals, but also coalitions may act strategically. Chapter 10 by J. Greenberg surveys the theory of "social situations", which looks for a stable standards of behavior in general coalitional interactions.