UID:
almafu_9960117391902883
Format:
1 online resource (xiii, 341 pages) :
,
digital, PDF file(s).
ISBN:
1-316-78048-1
,
1-316-78209-3
,
1-316-77930-0
Content:
Computer science and economics have engaged in a lively interaction over the past fifteen years, resulting in the new field of algorithmic game theory. Many problems that are 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 University 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.
Note:
Title from publisher's bibliographic system (viewed on 08 Aug 2016).
,
Cover -- Half title -- Title -- Copyright -- Dedication -- 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 Sel.sh 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 Sel.sh 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 PLS-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 PPAD-Completeness -- 20.1 Computing a MNE of a Bimatrix Game -- 20.2 Total NP Search Problems (TFNP) -- *20.3 PPAD: A Syntactic Subclass of TFNP -- *20.4 A Canonical PPAD Problem: Sperner's Lemma -- *20.5 MNE and PPAD -- 20.6 Discussion -- Notes -- Exercises -- Problems -- The Top 10 List -- Hints to Selected Exercises and Problems -- Bibliography -- Index.
Additional Edition:
ISBN 1-107-17266-7
Additional Edition:
ISBN 1-316-62479-X
Language:
English
Subjects:
Mathematics
Keywords:
Einführung
URL:
Volltext
(URL des Erstveröffentlichers)
URL:
Volltext
(lizenzpflichtig)
URL:
https://doi.org/10.1017/CBO9781316779309
URL:
https://doi.org/10.1017/CBO9781316779309
Bookmarklink
