03964.com

文档资料库 文档搜索专家

文档资料库 文档搜索专家

Algorithmic Game Theory

Over the last few years, there has been explosive growth in the research done at the interface 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 University 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. ? Tardos is a Professor in the Department of Computer Science at Cornell University. Eva 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.

Algorithmic Game Theory

Edited by

Noam Nisan

Hebrew University of Jerusalem

Tim Roughgarden

Stanford University

? Tardos Eva

Cornell University

Vijay V. Vazirani

Georgia Institute of Technology

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

? Tardos, Vijay V. Vazirani 2007 Noam Nisan, Tim Roughgarden, Eva

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. I. Nisan, Noam. II. Title. QA269.A43 2007 519.3–dc22 2007014231 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.

Contents

Foreword Preface Contributors

page xiii xvii xix

I Computing in Games

1 Basic Solution Concepts and Computational Issues ? Tardos and Vijay V. Vazirani Eva 1.1 Games, Old and New 1.2 Games, Strategies, Costs, and Payoffs 1.3 Basic Solution Concepts 1.4 Finding Equilibria and Learning in Games 1.5 Re?nement of Nash: Games with Turns and Subgame Perfect Equilibrium 1.6 Nash Equilibrium without Full Information: Bayesian Games 1.7 Cooperative Games 1.8 Markets and Their Algorithmic Issues Acknowledgments Bibliography Exercises 2 The Complexity of Finding Nash Equilibria Christos H. Papadimitriou 2.1 Introduction 2.2 Is the Nash Equilibrium Problem NP-Complete? 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

3 3 9 10 16 18 20 20 22 26 26 26 29 29 31 33 36 39 41 45 49 50 50

vi

contents

3 Equilibrium Computation for Two-Player Games in Strategic and Extensive Form Bernhard von Stengel 3.1 Introduction 3.2 Bimatrix Games and the Best Response Condition 3.3 Equilibria via Labeled Polytopes 3.4 The Lemke–Howson Algorithm 3.5 Integer Pivoting 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 Avrim Blum and Yishay Mansour 4.1 Introduction 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 Vijay V. Vazirani 5.1 Introduction 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

contents 5.14 Algorithm for Single-Source Multiple-Sink Markets 5.15 Discussion and Open Problems Bibliography Exercises

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

6 Computation of Market Equilibria by Convex Programming Bruno Codenotti and Kasturi Varadarajan 6.1 Introduction 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) Noam Nisan 9.1 Introduction 9.2 Social Choice 9.3 Mechanisms with Money 9.4 Implementation in Dominant Strategies 209 209 211 216 222

viii

contents 9.5 Characterizations of Incentive Compatible Mechanisms 9.6 Bayesian–Nash Implementation 9.7 Further Models 9.8 Notes Acknowledgments Bibliography

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

10 Mechanism Design without Money James Schummer and Rakesh V. Vohra 10.1 Introduction 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 Liad Blumrosen and Noam Nisan 11.1 Introduction 11.2 The Single-Minded Case 11.3 Walrasian Equilibrium and the LP Relaxation 11.4 Bidding Languages 11.5 Iterative Auctions: The Query Model 11.6 Communication Complexity 11.7 Ascending Auctions 11.8 Bibliographic Notes Acknowledgments Bibliography Exercises 12 Computationally Ef?cient Approximation Mechanisms Ron Lavi 12.1 Introduction 12.2 Single-Dimensional Domains: Job Scheduling 12.3 Multidimensional Domains: Combinatorial Auctions 12.4 Impossibilities of Dominant Strategy Implementability 12.5 Alternative Solution Concepts 12.6 Bibliographic Notes Bibliography Exercises 13 Pro?t Maximization in Mechanism Design Jason D. Hartline and Anna R. Karlin 13.1 Introduction 13.2 Bayesian Optimal Mechanism Design 13.3 Prior-Free Approximations to the Optimal Mechanism 13.4 Prior-Free Optimal Mechanism Design

contents 13.5 Frugality 13.6 Conclusions and Other Research Directions 13.7 Notes Bibliography Exercises

ix

350 354 357 358 360 363 363 366 370 379 380 381 381 383 385 385 387 391 394 400 402 405 406 408 408 410 411 411 413 417 431 435 436 437 437 439

14 Distributed Algorithmic Mechanism Design Joan Feigenbaum, Michael Schapira, and Scott Shenker 14.1 Introduction 14.2 Two Examples of DAMD 14.3 Interdomain Routing 14.4 Conclusion and Open Problems 14.5 Notes Acknowledgments Bibliography Exercises 15 Cost Sharing Kamal Jain and Mohammad Mahdian 15.1 Cooperative Games and Cost Sharing 15.2 Core of Cost-Sharing Games 15.3 Group-Strategyproof Mechanisms and Cross-Monotonic Cost-Sharing Schemes 15.4 Cost Sharing via the Primal-Dual Schema 15.5 Limitations of Cross-Monotonic Cost-Sharing Schemes 15.6 The Shapley Value and the Nash Bargaining Solution 15.7 Conclusion 15.8 Notes Acknowledgments Bibliography Exercises 16 Online Mechanisms David C. Parkes 16.1 Introduction 16.2 Dynamic Environments and Online MD 16.3 Single-Valued Online Domains 16.4 Bayesian Implementation in Online Domains 16.5 Conclusions 16.6 Notes Acknowledgments Bibliography Exercises

III Quantifying the Inef?ciency of Equilibria

17 Introduction to the Inef?ciency of Equilibria ? Tardos Tim Roughgarden and Eva 17.1 Introduction 443 443

x

contents 17.2 Fundamental Network Examples 17.3 Inef?ciency of Equilibria as a Design Metric 17.4 Notes Bibliography Exercises

446 454 456 457 459 461 461 462 468 472 478 480 483 484 487 487 489 494 502 506 511 511 513 517 517 522 524 529 533 537 538 540 542 543 543 544 551 559 564

18 Routing Games Tim Roughgarden 18.1 Introduction 18.2 Models and Examples 18.3 Existence, Uniqueness, and Potential Functions 18.4 The Price of Anarchy of Sel?sh Routing 18.5 Reducing the Price of Anarchy 18.6 Notes Bibliography Exercises 19 Network Formation Games and the Potential Function Method ? Tardos and Tom Wexler Eva 19.1 Introduction 19.2 The Local Connection Game 19.3 Potential Games and a Global Connection Game 19.4 Facility Location 19.5 Notes Acknowledgments Bibliography Exercises 20 Sel?sh Load Balancing Berthold V¨ ocking 20.1 Introduction 20.2 Pure Equilibria for Identical Machines 20.3 Pure Equilibria for Uniformly Related Machines 20.4 Mixed Equilibria on Identical Machines 20.5 Mixed Equilibria on Uniformly Related Machines 20.6 Summary and Discussion 20.7 Bibliographic Notes Bibliography Exercises 21 The Price of Anarchy and the Design of Scalable Resource Allocation Mechanisms Ramesh Johari 21.1 Introduction 21.2 The Proportional Allocation Mechanism 21.3 A Characterization Theorem 21.4 The Vickrey–Clarke–Groves Approach 21.5 Chapter Summary and Further Directions

contents 21.6 Notes Bibliography Exercises

xi

565 566 567

IV Additional Topics

22 Incentives and Pricing in Communications Networks Asuman Ozdaglar and R. Srikant 22.1 Large Networks – Competitive Models 22.2 Pricing and Resource Allocation – Game Theoretic Models 22.3 Alternative Pricing and Incentive Approaches Bibliography 23 Incentives in Peer-to-Peer Systems Moshe Babaioff, John Chuang, and Michal Feldman 23.1 Introduction 23.2 The p2p File-Sharing Game 23.3 Reputation 23.4 A Barter-Based System: BitTorrent 23.5 Currency 23.6 Hidden Actions in p2p Systems 23.7 Conclusion 23.8 Bibliographic Notes Bibliography Exercises 24 Cascading Behavior in Networks: Algorithmic and Economic Issues Jon Kleinberg 24.1 Introduction 24.2 A First Model: Networked Coordination Games 24.3 More General Models of Social Contagion 24.4 Finding In?uential Sets of Nodes 24.5 Empirical Studies of Cascades in Online Data 24.6 Notes and Further Reading Bibliography Exercises 25 Incentives and Information Security Ross Anderson, Tyler Moore, Shishir Nagaraja, and Andy Ozment 25.1 Introduction 25.2 Misaligned Incentives 25.3 Informational Asymmetries 25.4 The Economics of Censorship Resistance 25.5 Complex Networks and Topology 25.6 Conclusion 25.7 Notes Bibliography 571 572 578 587 590 593 593 594 596 600 601 602 608 608 609 610 613 613 614 618 622 627 630 631 632 633 633 634 636 640 643 646 647 648

xii

contents

26 Computational Aspects of Prediction Markets David M. Pennock and Rahul Sami 26.1 Introduction: What Is a Prediction Market? 26.2 Background 26.3 Combinatorial Prediction Markets 26.4 Automated Market Makers 26.5 Distributed Computation through Markets 26.6 Open Questions 26.7 Bibliographic Notes Acknowledgments Bibliography Exercises 27 Manipulation-Resistant Reputation Systems Eric Friedman, Paul Resnick, and Rahul Sami 27.1 Introduction: Why Are Reputation Systems Important? 27.2 The Effect of Reputations 27.3 Whitewashing 27.4 Eliciting Effort and Honest Feedback 27.5 Reputations Based on Transitive Trust 27.6 Conclusion and Extensions 27.7 Bibliographic Notes Bibliography Exercises 28 Sponsored Search Auctions S? ebastien Lahaie, David M. Pennock, Amin Saberi, and Rakesh V. Vohra 28.1 Introduction 28.2 Existing Models and Mechanisms 28.3 A Static Model 28.4 Dynamic Aspects 28.5 Open Questions 28.6 Bibliographic Notes Bibliography Exercises 29 Computational Evolutionary Game Theory Siddharth Suri 29.1 Evolutionary Game Theory 29.2 The Computational Complexity of Evolutionarily Stable Strategies 29.3 Evolutionary Dynamics Applied to Sel?sh Routing 29.4 Evolutionary Game Theory over Graphs 29.5 Future Work 29.6 Notes Acknowledgments Bibliography Exercises Index

651 651 652 657 662 665 670 671 672 672 674 677 677 680 682 683 689 693 694 695 696 699 699 701 702 707 711 712 713 715 717 717 720 723 728 733 733 734 734 735 737

Foreword

As the Second World War was coming to its end, John von Neumann, arguably the foremost mathematician of that time, was busy initiating two intellectual currents that would shape the rest of the twentieth century: game theory and algorithms. In 1944 (16 years after the minmax theorem) he published, with Oscar Morgenstern, his Games and Economic Behavior, thus founding not only game theory but also utility theory and microeconomics. Two years later he wrote his draft report on the EDVAC, inaugurating the era of the digital computer and its software and its algorithms. Von Neumann wrote in 1952 the ?rst paper in which a polynomial algorithm was hailed as a meaningful advance. And, he was the recipient, shortly before his early death four years later, of G¨ odel’s letter in which the P vs. NP question was ?rst discussed. Could von Neumann have anticipated that his twin creations would converge half a century later? He was certainly far ahead of his contemporaries in his conception of computation as something dynamic, ubiquitous, and enmeshed in society, almost organic – witness his self-reproducing automata, his fault-tolerant network design, and his prediction that computing technology will advance in lock-step with the economy (for which he had already postulated exponential growth in his 1937 Vienna Colloquium paper). But I doubt that von Neumann could have dreamed anything close to the Internet, the ubiquitous and quintessentially organic computational artifact that emerged after the end of the Cold War (a war, incidentally, of which von Neumann was an early soldier and possible casualty, and that was, fortunately, fought mostly with game theory and decided by technological superiority – essentially by algorithms – instead of the thermonuclear devices that were von Neumann’s parting gift to humanity). The Internet turned the tables on students of both markets and computation. It transformed, informed, and accelerated markets, while creating new and theretofore unimaginable kinds of markets – in addition to being itself, in important ways, a market. Algorithms became the natural environment and default platform of strategic decision making. On the other hand, the Internet was the ?rst computational artifact that was not created by a single entity (engineer, design team, or company), but emerged from the strategic interaction of many. Computer scientists were for the ?rst time faced with an object that they had to feel with the same bewildered awe with which economists have

xiii

xiv

foreword

always approached the market. And, quite predictably, they turned to game theory for inspiration – in the words of Scott Shenker, a pioneer of this way of thinking who has contributed to this volume, “the Internet is an equilibrium, we just have to identify the game.” A fascinating fusion of ideas from both ?elds – game theory and algorithms – came into being and was used productively in the effort to illuminate the mysteries of the Internet. It has come to be called algorithmic game theory. The chapters of this book, a snapshot of algorithmic game theory at the approximate age of ten written by a galaxy of its leading researchers, succeed brilliantly, I think, in capturing the ?eld’s excitement, breadth, accomplishment, and promise. The ?rst few chapters recount the ways in which the new ?eld has come to grips with perhaps the most fundamental cultural incongruity between algorithms and game theory: the latter predicts the agents’ equilibrium behavior typically with no regard to the ways in which such a state will be reached – a consideration that would be a computer scientist’s foremost concern. Hence, algorithms for computing equilibria (Nash and correlated equilibria in games, price equilibria for markets) have been one of algorithmic game theory’s earliest research goals. This body of work has become a valuable contribution to the debate in economics about the validity of behavior predictions: Ef?cient computability has emerged as a very desirable feature of such predictions, while computational intractability sheds a shadow of implausibility on a proposed equilibrium concept. Computational models that re?ect the realities of the market and the Internet better than the von Neumann machine are of course at a premium – there are chapters in this book on learning algorithms as well as on distributed algorithmic mechanism design. The algorithmic nature of mechanism design is even more immediate: This elegant and well-developed subarea of game theory deals with the design of games, with players who have unknown and private utilities, such that at the equilibrium of the designed game the designer’s goals are attained independently of the agents’ utilities (auctions are an important example here). This is obviously a computational problem, and in fact some of the classical results in this area had been subtly algorithmic, albeit with little regard to complexity considerations. Explicitly algorithmic work on mechanism design has, in recent years, transformed the ?eld, especially in the case of auctions and cost sharing (for example, how to recover the cost of an Internet service from customers who value the service by amounts known only to them) and has become the arena of especially intense and productive cross-fertilization between game theory and algorithms; these problems and accomplishments are recounted in the book’s second part. The third part of the book is dedicated to a line of investigation that has come to be called “the price of anarchy.” Sel?sh rational agents reach an equilibrium. The question arises: exactly how inef?cient is this equilibrium in comparison to an idealized situation in which the agents would strive to collaborate sel?essly with the common goal of minimizing total cost? The ratio of these quantities (the cost of an equilibrium over the optimum cost) has been estimated successfully in various Internet-related setups, and it is often found that “anarchy” is not nearly as expensive as one might have feared. For example, in one celebrated case related to routing with linear delays and explained in the “routing games” chapter, the overhead of anarchy is at most 33% over the optimum solution – in the context of the Internet such a ratio is rather insigni?cant

foreword

xv

and quickly absorbed by its rapid growth. Viewed in the context of the historical development of research in algorithms, this line of investigation could be called “the third compromise.” The realization that optimization problems are intractable led us to approximation algorithms; the unavailability of information about the future, or the lack of coordination between distributed decision makers, brought us online algorithms; the price of anarchy is the result of one further obstacle: now the distributed decision makers have different objective functions. Incidentally, it is rather surprising that economists had not studied this aspect of strategic behavior before the advent of the Internet. One explanation may be that, for economists, the ideal optimum was never an available option; in contrast, computer scientists are still looking back with nostalgia to the good old days when artifacts and processes could be optimized exactly. Finally, the chapters on “additional topics” that conclude the book (e.g., on peer-to-peer systems and information markets) amply demonstrate the young area’s impressive breadth, reach, diversity, and scope. Books – a glorious human tradition apparently spared by the advent of the Internet – have a way of marking and focusing a ?eld, of accelerating its development. Seven years after the publication of The Theory of Games, Nash was proving his theorem on the existence of equilibria; only time will tell how this volume will sway the path of algorithmic game theory. Paris, February 2007 Christos H. Papadimitriou

Preface

This book covers an area that straddles two ?elds, algorithms and game theory, and has applications in several others, including networking and arti?cial intelligence. Its text is pitched at a beginning graduate student in computer science – we hope that this makes the book accessible to readers across a wide range of areas. We started this project with the belief that the time was ripe for a book that clearly develops some of the central ideas and results of algorithmic game theory – a book that can be used as a textbook for the variety of courses that were already being offered at many universities. We felt that the only way to produce a book of such breadth in a reasonable amount of time was to invite many experts from this area to contribute chapters to a comprehensive volume on the topic. This book is partitioned into four parts: the ?rst three parts are devoted to core areas, while the fourth covers a range of topics mostly focusing on applications. Chapter 1 serves as a preliminary chapter and it introduces basic game-theoretic de?nitions that are used throughout the book. The ?rst chapters of Parts II and III provide introductions and preliminaries for the respective parts. The other chapters are largely independent of one another. The authors were requested to focus on a few results highlighting the main issues and techniques, rather than provide comprehensive surveys. Most of the chapters conclude with exercises suitable for classroom use and also identify promising directions for further research. We hope these features give the book the feel of a textbook and make it suitable for a wide range of courses. You can view the entire book online at www.cambridge.org/us/9780521872829 username: agt1user password: camb2agt Many people’s efforts went into producing this book within a year and a half of its ?rst conception. First and foremost, we thank the authors for their dedication and timeliness in writing their own chapters and for providing important

xvii

xviii

preface

feedback on preliminary drafts of other chapters. Thanks to Christos Papadimitriou for his inspiring Foreword. We gratefully acknowledge the efforts of outside reviewers: Elliot Anshelevich, Nikhil Devanur, Matthew Jackson, Vahab Mirrokni, Herve Moulin, Neil Olver, Adrian Vetta, and several anonymous referees. Thanks to Cindy Robinson for her invaluable help with correcting the galley proofs. Finally, a big thanks to Lauren Cowles for her stellar advice throughout the production of this volume. Noam Nisan Tim Roughgarden ? Tardos Eva Vijay V. Vazirani

Contributors

Ross Anderson Computer Laboratory University of Cambridge Moshe Babaioff School of Information University of California, Berkeley Avrim Blum Department of Computer Science Carnegie Mellon University Liad Blumrosen Microsoft Research Silicon Valley John Chuang School of Information University of California, Berkeley Bruno Codenotti Istituto di Informatica e Telematica, Consiglio Nazionale delle Ricerche Yevgeniy Dodis Department of Computer Science Courant Institute of Mathematical Sciences, New York University

Joan Feigenbaum Computer Science Department Yale University Michal Feldman School of Business Administration and the Center for the Study of Rationality Hebrew University of Jerusalem Eric Friedman School of Operations Research and Information Engineering Cornell University Jason D. Hartline Microsoft Research Silicon Valley Kamal Jain Microsoft Research Redmond Ramesh Johari Department of Management Science and Engineering Stanford University Anna R. Karlin Department of Computer Science and Engineering University of Washington

xix

xx

contributors

Michael Kearns Department of Computer and Information Science University of Pennsylvania Jon Kleinberg Department of Computer Science Cornell University S? ebastien Lahaie School of Engineering and Applied Sciences Harvard University Ron Lavi Faculty of Industrial Engineering and Management, The Technion Israel Institute of Technology Mohammad Mahdian Yahoo! Research Silicon Valley Yishay Mansour School of Computer Science Tel Aviv University Tyler Moore Computer Laboratory University of Cambridge Shishir Nagaraja Computer Laboratory University of Cambridge Noam Nisan School of Computer Science and Engineering Hebrew University of Jerusalem Asuman Ozdaglar Department of Electrical Engineering and Computer Science, MIT Andy Ozment Computer Laboratory University of Cambridge

Christos H. Papadimitriou Computer Science Division University of California, Berkeley David C. Parkes School of Engineering and Applied Sciences Harvard University David M. Pennock Yahoo! Research New York Tal Rabin T. J. Watson Research Center IBM Paul Resnick School of Information University of Michigan Tim Roughgarden Department of Computer Science Stanford University Amin Saberi Department of Management Science and Engineering Stanford University Rahul Sami School of Information University of Michigan Michael Schapira School of Computer Science and Engineering The Hebrew University of Jerusalem James Schummer M.E.D.S. Kellogg School of Management Northwestern University

contributors

xxi

Scott Shenker EECS Department University of California, Berkeley R. Srikant Department of Electrical and Computer Engineering and Coordinated Science Laboratory, University of Illinois at Urbana-Champaign Siddharth Suri Department of Computer Science Cornell University ? Tardos Eva Department of Computer Science Cornell University Kasturi Varadarajan Department of Computer Science University of Iowa

Vijay V. Vazirani College of Computing Georgia Institute of Technology Berthold V¨ ocking Department of Computer Science RWTH Aachen University Rakesh V. Vohra M.E.D.S. Kellogg School of Management Northwestern University Bernhard von Stengel Department of Mathematics London School of Economics Tom Wexler Department of Computer Science Cornell University

PART ONE

Computing in Games

相关文章:

- +Algorithmic+Game+Theory.pdf
- +
*Algorithmic*+*Game*+*Theory*-*Algorithmic**Game**Theory*Over the last few years, there has been explos...

- Game Theory Lecture 1.pdf
*Algorithmic**Game**Theory*June 19, 2012 Le

- 计算复杂性理论_图文.ppt
- 而最 近,复杂性理论的研究者又进入了博弈论领域,并创立了 “算法博弈论”(
*algorithmic**game**theory*)这一...

- 3 计算复杂性理论.doc
- 特别的复杂性理论对近代密码 学的影响非常显著,而最近,复杂性理论的研究者又进入了博弈论领域,并创立 了“算法博弈论”(
*algorithmic**game**theory*)这一分支。 该...

- 大数据处理中常用算法和数据结构.pdf
*Algorithmic**game**theory*? Computational algebra ? Computational aspects of combinatorics and graph*theory*? Computational aspects of communication ? Computational ...

- 博弈论第一章.pdf
*Algorithmic**Game**Theory*and Applications Lecture 1: What is*game**theory*? Kousha Etessami Kousha Etessami AGTA: Lecture 1 1 What is*Game**Theory*? A ...

- 清华考博辅导:清华大学物理学考博难度解析及经验分享 (2).doc
- "OnRevenueMonotonicityinCombinatorialAuctions",AndrewChi-ChihYao,Proceeding sof11thInternationalSymposiumon
*AlgorithmicGameTheory*(SAGT2018),Beijing,China,Se ptember...

- 2014年全国运筹与优化前沿系列课程第一轮通知.doc
*Game*and Economics Models 课程课时间表如下: 6.19 20 21 22 30 7.1 A1...including infinite dimensional optimization,*algorithmic**game**theory*, bilevel and...

- Graph Theory and Combinatorics.pdf
- mirrokni
*Algorithmic*and Economic Aspects of the Internet*Algorithmic**Game**Theory*and Computational Economics Approximation Algorithms and Combinatorial Optimization ...

- 传统游戏的网络实现技术.pdf
- andtoreducethenetwork overheadmeanwhile.Indesignoftheseprotocols,
*algorithmicgametheory*isintroducedtoguaranteethatallplayerswillloyallyfollowtheprescribed*game*protocols....

- ...Algorithmic Combinatorial Game Theory....pdf
- Playing
*Games*with Algorithms:*Algorithmic*Combinatorial*Game**Theory*? Erik D. Demaine? Robert A. Hearn? arXiv:cs/0106019v2 [cs.CC] 22 Apr 2008 Abstrac...

- ...algorithmic mechanism based on game theory in co....pdf
- Improved
*algorithmic*mechanism based on*game**theory*in computational grids - 维普资讯 http://www.cqvi...

- Invited Talks.pdf
- Research Interests
*Algorithmic**Game**theory*and Economics: Computation of Equilibria and Mechanism Design. Approximation Algorithms and Combinatorial Optimization. ...

- Frequency Assignment Problem”,.pdf
- 3. Research Interests: Research Interest Area: Theoretical Computer Science and Applications 1 Research fields:
*Algorithmic**Game**Theory*Computational Complexity ...

- 爱丁堡大学计算机科学本科专业.pdf
- (Level 10) Querying and Storing XML Bioinformatics 2 Applied Databases Bioinformatics 1
*Algorithmic**Game**Theory*and its Applications Topics in Distributed ...

- Settling the Complexity of Computing Two-Player Nas....pdf
- We settle a long-standing open question in
*algorithmic**game**theory*. We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player ...

- Thesis “Data Acquisition System Design for the Alp....pdf
- Worked on problems in
*algorithmic**game**theory*with a focus on issues arising in the design of ad auctions such as bid optimization, budget constraints, ...

- 爱丁堡大学人工智能硕士申请.pdf
- (Level 11)
*Algorithmic**Game**Theory*and i

- 爱丁堡大学计算机科学硕士申请.pdf
- 分布式数据库 专业分类 计算机与信息科学 计算与计算 机科学 开学时间 秋季 生活费 10000 是否有语言要 求 有 主修课程 参考翻译
*Algorithmic**Game**Theory*and its...

- properties for extensive games with large trees._免....pdf
- Finding Nash equilibria of
*games*is central to*game*theoretical analysis and computing such equilibria is the principal aim of*algorithmic**game**theory*. The ...

- Algorithmic Combinatorial Game Theory1
- Playing Games with Algorithms Algorithmic Combinatorial Game Theory
- EVOLUTIONARY SOLUTIONS AND INTERNET APPLICATIONS FOR ALGORITHMIC GAME THEORY
- Improved algorithmic mechanism based on game theory in computational grids
- Game Theory
- Convex optimization Game theory and Variational inequality theory
- Game theory for wireless networks 2
- Chapter Outline for Algorithmic Game Theory Book The proposed title for my chapter is
- Open Problems at the 2002 Dagstuhl Seminar on Algorithmic Combinatorial Game Theory
- 0 Game Theory