algorithmic game theory pdf英文版.pdf-资料库

ajiao2013-8105807-4744302543307680630.pdf-第1页.png

第1页 / 共775页

ajiao2013-8105807-4744302543307680630.pdf-第2页.png

第2页 / 共775页

ajiao2013-8105807-4744302543307680630.pdf-第3页.png

第3页 / 共775页

ajiao2013-8105807-4744302543307680630.pdf-第4页.png

第4页 / 共775页

ajiao2013-8105807-4744302543307680630.pdf-第5页.png

第5页 / 共775页

ajiao2013-8105807-4744302543307680630.pdf-第6页.png

第6页 / 共775页

ajiao2013-8105807-4744302543307680630.pdf-第7页.png

第7页 / 共775页

ajiao2013-8105807-4744302543307680630.pdf-第8页.png

第8页 / 共775页

P1: SBT FM-main CUNY1061-Nisan 0 521 87282 0 August 3, 2007 12:6 Algorithmic Game Theory Over the last few years, there has been explosive growth in the research done at the in- terface of computer science, game theory, and economic theory, largely motivated by the emergence of the Internet. Algorithmic Game Theory develops the central ideas and results of this new and exciting area. More than 40 of the top researchers in this ﬁeld have written chapters whose topics range from the foundations to the state of the art. This book contains an extensive treatment of algorithms for equilibria in games and markets, computational auctions and mechanism design, and the “price of anarchy,” as well as applications in networks, peer-to-peer systems, security, information markets, and more. This book will be of interest to students, researchers, and practitioners in theoretical computer science, economics, networking, artiﬁcial intelligence, operations research, and discrete mathematics. Noam Nisan is a Professor in the Department of Computer Science at The Hebrew Univer- sity of Jerusalem. His other books include Communication Complexity. Tim Roughgarden is an Assistant Professor in the Department of Computer Science at Stanford University. His other books include Selﬁsh Routing and the Price of Anarchy. ´Eva Tardos is a Professor in the Department of Computer Science at Cornell University. Her other books include Algorithm Design. Vijay V. Vazirani is a Professor in the College of Computing at the Georgia Institute of Technology. His other books include Approximation Algorithms. i

P1: SBT FM-main CUNY1061-Nisan 0 521 87282 0 August 3, 2007 12:6 ii

P1: SBT FM-main CUNY1061-Nisan 0 521 87282 0 August 3, 2007 12:6 Algorithmic Game Theory Edited by Noam Nisan Hebrew University of Jerusalem Tim Roughgarden Stanford University ´Eva Tardos Cornell University Vijay V. Vazirani Georgia Institute of Technology iii

P1: SBT FM-main CUNY1061-Nisan 0 521 87282 0 August 3, 2007 12:6 cambridge university press Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, S˜ao Paulo, Delhi Cambridge University Press 32 Avenue of the Americas, New York, NY 10013-2473, USA www.cambridge.org Information on this title: www.cambridge.org/9780521872829 C Noam Nisan, Tim Roughgarden, ´Eva Tardos, Vijay V. Vazirani 2007 This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published 2007 Printed in the United States of America A catalog record for this book is available from the British Library. Library of Congress Cataloging in Publication Data Algorithmic game theory / edited by Noam Nisan . . . [et al.]; foreword by Christos Papadimitriou. p. cm. Includes index. ISBN-13: 978-0-521-87282-9 (hardback) ISBN-10: 0-521-87282-0 (hardback) 1. Game theory. 2. Algorithms. QA269.A43 519.3–dc22 2007014231 2007 I. Nisan, Noam. II. Title. ISBN 978-0-521-87282-9 hardback Cambridge University Press has no responsibility for the persistence or accuracy of URLS for external or third-party Internet Web sites referred to in this publication and does not guarantee that any content on such Web sites is, or will remain, accurate or appropriate. i

P1: SBT FM-main CUNY1061-Nisan 0 521 87282 0 August 3, 2007 12:6 Contents Foreword Preface Contributors page xiii xvii xix I Computing in Games 1 Basic Solution Concepts and Computational Issues 3 ´Eva Tardos and Vijay V. Vazirani 1.1 Games, Old and New 3 1.2 Games, Strategies, Costs, and Payoffs 9 1.3 Basic Solution Concepts 10 1.4 Finding Equilibria and Learning in Games 16 1.5 Reﬁnement of Nash: Games with Turns and Subgame Perfect Equilibrium 18 1.6 Nash Equilibrium without Full Information: Bayesian Games 20 1.7 Cooperative Games 20 1.8 Markets and Their Algorithmic Issues 22 26 Acknowledgments 26 Bibliography 26 Exercises 29 2 The Complexity of Finding Nash Equilibria Introduction Is the Nash Equilibrium Problem NP-Complete? Christos H. Papadimitriou 2.1 2.2 2.3 The Lemke–Howson Algorithm 2.4 The Class PPAD 2.5 Succinct Representations of Games 2.6 The Reduction 2.7 Correlated Equilibria 2.8 Concluding Remarks Acknowledgment Bibliography v 29 31 33 36 39 41 45 49 50 50

P1: SBT FM-main CUNY1061-Nisan 0 521 87282 0 August 3, 2007 12:6 vi contents 3 Equilibrium Computation for Two-Player Games in Strategic Introduction Integer Pivoting and Extensive Form Bernhard von Stengel 3.1 3.2 Bimatrix Games and the Best Response Condition 3.3 Equilibria via Labeled Polytopes 3.4 The Lemke–Howson Algorithm 3.5 3.6 Degenerate Games 3.7 Extensive Games and Their Strategic Form 3.8 Subgame Perfect Equilibria 3.9 Reduced Strategic Form 3.10 The Sequence Form 3.11 Computing Equilibria with the Sequence Form 3.12 Further Reading 3.13 Discussion and Open Problems Bibliography Exercises 4 Learning, Regret Minimization, and Equilibria Introduction Avrim Blum and Yishay Mansour 4.1 4.2 Model and Preliminaries 4.3 External Regret Minimization 4.4 Regret Minimization and Game Theory 4.5 Generic Reduction from External to Swap Regret 4.6 The Partial Information Model 4.7 On Convergence of Regret-Minimizing Strategies to Nash Equilibrium in Routing Games 4.8 Notes Bibliography Exercises 5 Combinatorial Algorithms for Market Equilibria Introduction Vijay V. Vazirani 5.1 5.2 Fisher’s Linear Case and the Eisenberg–Gale Convex Program 5.3 Checking If Given Prices Are Equilibrium Prices 5.4 Two Crucial Ingredients of the Algorithm 5.5 The Primal-Dual Schema in the Enhanced Setting 5.6 Tight Sets and the Invariant 5.7 Balanced Flows 5.8 The Main Algorithm 5.9 Finding Tight Sets 5.10 Running Time of the Algorithm 5.11 The Linear Case of the Arrow–Debreu Model 5.12 An Auction-Based Algorithm 5.13 Resource Allocation Markets 53 53 54 57 61 63 65 66 68 69 70 73 75 75 76 77 79 79 81 82 88 92 94 96 99 99 101 103 103 105 108 109 109 111 111 115 117 118 121 122 124

P1: SBT FM-main CUNY1061-Nisan 0 521 87282 0 August 3, 2007 12:6 contents 5.14 Algorithm for Single-Source Multiple-Sink Markets 5.15 Discussion and Open Problems Bibliography Exercises 6 Computation of Market Equilibria by Convex Programming Introduction Bruno Codenotti and Kasturi Varadarajan 6.1 6.2 Fisher Model with Homogeneous Consumers 6.3 Exchange Economies Satisfying WGS 6.4 Speciﬁc Utility Functions 6.5 Limitations 6.6 Models with Production 6.7 Bibliographic Notes Bibliography Exercises 7 Graphical Games Michael Kearns 7.1 Introduction 7.2 Preliminaries 7.3 Computing Nash Equilibria in Tree Graphical Games 7.4 Graphical Games and Correlated Equilibria 7.5 Graphical Exchange Economies 7.6 Open Problems and Future Research 7.7 Bibliographic Notes Acknowledgments Bibliography 8 Cryptography and Game Theory Yevgeniy Dodis and Tal Rabin 8.1 Cryptographic Notions and Settings 8.2 Game Theory Notions and Settings 8.3 Contrasting MPC and Games 8.4 Cryptographic Inﬂuences on Game Theory 8.5 Game Theoretic Inﬂuences on Cryptography 8.6 Conclusions 8.7 Notes Acknowledgments Bibliography II Algorithmic Mechanism Design 9 Introduction to Mechanism Design (for Computer Scientists) Introduction Noam Nisan 9.1 9.2 Social Choice 9.3 Mechanisms with Money 9.4 Implementation in Dominant Strategies vii 126 131 132 133 135 135 141 142 148 150 152 155 156 158 159 159 161 164 169 176 177 177 179 179 181 181 187 189 191 197 202 203 204 204 209 209 211 216 222

P1: SBT FM-main CUNY1061-Nisan 0 521 87282 0 August 3, 2007 12:6 viii contents 9.5 Characterizations of Incentive Compatible Mechanisms 9.6 Bayesian–Nash Implementation 9.7 Further Models 9.8 Notes Acknowledgments Bibliography Introduction 10 Mechanism Design without Money James Schummer and Rakesh V. Vohra 10.1 10.2 Single-Peaked Preferences over Policies 10.3 House Allocation Problem 10.4 Stable Matchings 10.5 Future Directions 10.6 Notes and References Bibliography Exercises 11 Combinatorial Auctions Introduction Iterative Auctions: The Query Model Liad Blumrosen and Noam Nisan 11.1 11.2 The Single-Minded Case 11.3 Walrasian Equilibrium and the LP Relaxation 11.4 Bidding Languages 11.5 11.6 Communication Complexity 11.7 Ascending Auctions 11.8 Bibliographic Notes Acknowledgments Bibliography Exercises 12 Computationally Efﬁcient Approximation Mechanisms Introduction Ron Lavi 12.1 12.2 Single-Dimensional Domains: Job Scheduling 12.3 Multidimensional Domains: Combinatorial Auctions 12.4 12.5 Alternative Solution Concepts 12.6 Bibliographic Notes Bibliography Exercises Impossibilities of Dominant Strategy Implementability 13 Proﬁt Maximization in Mechanism Design Introduction Jason D. Hartline and Anna R. Karlin 13.1 13.2 Bayesian Optimal Mechanism Design 13.3 Prior-Free Approximations to the Optimal Mechanism 13.4 Prior-Free Optimal Mechanism Design 225 233 238 239 240 241 243 243 244 253 255 262 263 264 264 267 267 270 275 279 283 287 289 295 296 296 298 301 301 303 310 317 321 327 327 328 331 331 335 339 344

资料库

algorithmic game theory pdf英文版.pdf

相关推荐

课程资源

热门标签

最新资料