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 field 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, artificial 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 Selfish 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 Refinement 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 Specific 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 Influences on Game Theory
8.5 Game Theoretic Influences 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 Efficient 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 Profit 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