Twenty Lectures on Algorithmic Game Theory Computer science and economics have engaged in a lively interaction over the past 15 years, resulting in the new field of algorithmic game theory. Many problems central to modern computer science, ranging from resource allocation in large networks to online advertising, involve interactions between multiple self- interested parties. Economics and game theory offer a host of useful models and definitions to reason about such problems. The flow of ideas also travels in the other direction, and concepts from computer science are increasingly important in economics. This book grew out of the author’s Stanford course on algorithmic game theory, and aims to give students and other newcomers a quick and accessible introduction to many of the most important concepts in the field. The book also includes case studies on online advertising, wireless spectrum auctions, kidney exchange, and network management. Tim Roughgarden is an Associate Professor of Computer Science at Stanford University. For his research in algorithmic game theory, he has been awarded the ACM Grace Murray Hopper A ward, the Presidential Early Career Award for Scientists and Engineers (PECASE), the Kalai Prize in Game Theory and Computer Science, the Social Choice and Welfare Prize, the Mathematical Programming Society’s Tucker Prize, and the EATCS-SIGACT Gödel Prize. He wrote the book Selfish Routing and the Price of Anarchy (2005) and coedited the book Algorithmic Game Theory (2007). Twenty Lectures on Algorithmic Game Theory Tim Roughgarden Stanford University, California University Printing House, Cambridge CB2 8BS, United Kingdom One Liberty Plaza, 20th Floor, New York, NY 10006, USA 477 Williamstown Road, Port Melbourne, VIC 3207, Australia 4843/24, 2nd Floor, Ansari Road, Daryaganj, Delhi − 110002, India 79 Anson Road, #06-04/06, Singapore 079906 Cambridge University Press is part of the University of Cambridge. It furthers the University’s mission by disseminating knowledge in the pursuit of education, learning, and research at the highest international levels of excellence. www.cambridge.org Information on this title: www.cambridge.org/9781107172661 10.1017/9781316779309 © Tim Roughgarden 2016 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 2016 Printed in the United States of America A catalogue record for this publication is available from the British Library. Library of Congress Cataloging in Publication Data Names: Roughgarden, Tim. Title: Twenty lectures on algorithmic game theory / Tim Roughgarden, Stanford University, California. Description: Cambridge: Cambridge University Press, 2016. | Includes bibliographical references and index. Identifiers: LCCN 2016028351 | ISBN 9781107172661 (hardback: alk. paper) Subjects: LCSH: Game theory. | Algorithms. Classification: LCC QA269. R68 2016 | DDC 519.3-dc23 LC record available at https://lccn.loc.gov/2016028351 ISBN 978-1-107-17266-1 Hardback ISBN 978-1-316-62479-1 Paperback 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. To Emma Contents Preface 1 Introduction and Examples 1.1 The Science of Rule-Making 1.2 When Is Selfish Behavior Near-Optimal? 1.3 Can Strategic Players Learn an Equilibrium? Notes Exercises Problems 2 Mechanism Design Basics 2.1 Single-Item Auctions 2.2 Sealed-Bid Auctions 2.3 First-Price Auctions 2.4 Second-Price Auctions and Dominant Strategies 2.5 Ideal Auctions 2.6 Case Study: Sponsored Search Auctions Notes Exercises Problems 3 Myerson’s Lemma 3.1 Single-Parameter Environments 3.2 Allocation and Payment Rules 3.3 Statement of Myerson’s Lemma *3.4 Proof of Myerson’s Lemma 3.5 Applying the Payment Formula Notes Exercises Problems 4 Algorithmic Mechanism Design 4.1 Knapsack Auctions 4.2 Algorithmic Mechanism Design 4.3 The Revelation Principle Notes Exercises Problems 5 Revenue-Maximizing Auctions 5.1 The Challenge of Revenue Maximization 5.2 Characterization of Optimal DSIC Mechanisms 5.3 Case Study: Reserve Prices in Sponsored Search *5.4 Proof of Lemma 5.1 Notes Exercises Problems 6 Simple Near-Optimal Auctions 6.1 Optimal Auctions Can Be Complex 6.2 The Prophet Inequality 6.3 Simple Single-Item Auctions 6.4 Prior-Independent Mechanisms Notes Exercises Problems 7 Multi-Parameter Mechanism Design 7.1 General Mechanism Design Environments 7.2 The VCG Mechanism 7.3 Practical Considerations Notes Exercises Problems 8 Spectrum Auctions 8.1 Indirect Mechanisms 8.2 Selling Items Separately 8.3 Case Study: Simultaneous Ascending Auctions 8.4 Package Bidding 8.5 Case Study: The 2016 FCC Incentive Auction Notes Exercises Problems 9 Mechanism Design with Payment Constraints 9.1 Budget Constraints 9.2 The Uniform-Price Multi-Unit Auction *9.3 The Clinching Auction 9.4 Mechanism Design without Money Notes Exercises Problems 10 Kidney Exchange and Stable Matching 10.1 Case Study: Kidney Exchange 10.2 Stable Matching *10.3 Further Properties Notes Exercises Problems 11 Selfish Routing and the Price of Anarchy 11.1 Selfish Routing: Examples 11.2 Main Result: Informal Statement 11.3 Main Result: Formal Statement 11.4 Technical Preliminaries *11.5 Proof of Theorem 11.2 Notes Exercises Problems 12 Over-Provisioning and Atomic Selfish Routing 12.1 Case Study: Network Over-Provisioning 12.2 A Resource Augmentation Bound *12.3 Proof of Theorem 12.1 12.4 Atomic Selfish Routing *12.5 Proof of Theorem 12.3 Notes Exercises Problems 13 Equilibria: Definitions, Examples, and Existence 13.1 A Hierarchy of Equilibrium Concepts 13.2 Existence of Pure Nash Equilibria 13.3 Potential Games Notes Exercises Problems 14 Robust Price-of-Anarchy Bounds in Smooth Games *14.1 A Recipe for POA Bounds *14.2 A Location Game *14.3 Smooth Games *14.4 Robust POA Bounds in Smooth Games Notes Exercises Problems 15 Best-Case and Strong Nash Equilibria 15.1 Network Cost-Sharing Games 15.2 The Price of Stability 15.3 The POA of Strong Nash Equilibria *15.4 Proof of Theorem 15.3 Notes Exercises Problems 16 Best-Response Dynamics 16.1 Best-Response Dynamics in Potential Games 16.2 Approximate PNE in Selfish Routing Games *16.3 Proof of Theorem 16.3 *16.4 Low-Cost Outcomes in Smooth Potential Games Notes Exercises Problems 17 No-Regret Dynamics 17.1 Online Decision Making 17.2 The Multiplicative Weights Algorithm 17.3 Proof of Theorem 17.6 *17.4 No Regret and Coarse Correlated Equilibria Notes Exercises Problems 18 Swap Regret and the Minimax Theorem 18.1 Swap Regret and Correlated Equilibria *18.2 Proof of Theorem 18.5 18.3 The Minimax Theorem for Zero-Sum Games *18.4 Proof of Theorem 18.7 Notes Exercises Problems 19 Pure Nash Equilibria and -Completeness 19.1 When Are Equilibrium Concepts Tractable? 19.2 Local Search Problems 19.3 Computing a PNE of a Congestion Game Notes Exercises Problems 20 Mixed Nash Equilibria and -Completeness 20.1 Computing a MNE of a Bimatrix Game 20.2 Total Search Problems ( ) *20.3 : A Syntactic Subclass of *20.4 A Canonical Problem: Sperner’s Lemma *20.5 MNE and 20.6 Discussion Notes Exercises Problems The Top 10 List Hints to Selected Exercises and Problems Bibliography Index