Roughgarden T. Twenty lectures on algorithmic game theory (Cambridge; New York, 2016). - ОГЛАВЛЕНИЕ / CONTENTS
Навигация

Архив выставки новых поступлений | Отечественные поступления | Иностранные поступления | Сиглы
ОбложкаRoughgarden T. Twenty lectures on algorithmic game theory. - Cambridge; New York: Cambridge university press, 2016. - xiii, 341 p.: ill. - Bibliogr.: p.309-328. - Ind.: p.329-341. - ISBN 978-1-107-17266-1
Шифр: (И/В17-R83) 02

 

Место хранения: 02 | Отделение ГПНТБ СО РАН | Новосибирск

Оглавление / Contents
 
Preface ........................................................ xi
1  Introduction and Examples .................................... 1
   1.1  The Science of Rule-Making .............................. 1
   1.2  When Is Selfish Behavior Near-Optimal? .................. 3
   1.3  Can Strategic Players Learn an Equilibrium? ............. 6
   Notes, Problems, and Exercises ............................... 9
2  Mechanism Design Basics ..................................... 11
   2.1  Single-Item Auctions ................................... 11
   2.2  Sealed-Bid Auctions .................................... 12
   2.3  First-Price Auctions ................................... 12
   2.4  Second-Price Auctions and Dominant Strategies .......... 13
   2.5  Ideal Auctions ......................................... 15
   2.6  Case Study: Sponsored Search Auctions .................. 16
   Notes, Problems, and Exercises .............................. 20
3  Myerson's Lemma ............................................. 24
   3.1  Single-Parameter Environments .......................... 24
   3.2  Allocation and Payment Rules ........................... 26
   3.3  Statement of Myerson's Lemma ........................... 26
   3.4   Proof of Myerson's Lemma .............................. 28
   3.5   Applying the Payment Formula .......................... 31
   Notes, Problems, and Exercises .............................. 34
4  Algorithmic Mechanism Design ................................ 39
   4.1  Knapsack Auctions ...................................... 39
   4.2  Algorithmic Mechanism Design ........................... 42
   4.3  The Revelation Principle ............................... 46
   Notes, Problems, and Exercises .............................. 49
5  Revenue-Maximizing Auctions ................................. 55
   5.1  The Challenge of Revenue Maximization .................. 55
   5.2  Characterization of Optimal DSIC Mechanisms ............ 58
   5.3  Case Study: Reserve Prices in Sponsored Search ......... 65
   5.4  Proof of Lemma 5.1 ..................................... 66
   Notes, Problems, and Exercises .............................. 69
6  Simple Near-Optimal Auctions ................................ 74
   6.1  Optimal Auctions Can Be Complex ........................ 74
   6.2  The Prophet Inequality ................................. 75
   6.3  Simple Single-Item Auctions ............................ 77
   6.4  Prior-Independent Mechanisms ........................... 79
   Notes, Problems, and Exercises .............................. 82
7  Multi-Parameter Mechanism Design ............................ 87
   7.1  General Mechanism Design Environments .................. 87
   7.2  The VCG Mechanism ...................................... 88
   7.3  Practical Considerations ............................... 91
   Notes, Problems, and Exercises .............................. 93
8  Spectrum Auctions ........................................... 97
   8.1  Indirect Mechanisms .................................... 97
   8.2  Selling Items Separately ............................... 98
   8.3  Case Study: Simultaneous Ascending Auctions ........... 100
   8.4  Package Bidding ....................................... 105
   8.5  Case Study: The 2016 FCC Incentive Auction ............ 106
   Notes, Problems, and Exercises ............................. 110
9  Mechanism Design with Payment Constraints .................. 113
   9.1  Budget Constraints .................................... 113
   9.2  The Uniform-Price Multi-Unit Auction .................. 114
   9.3  The Clinching Auction ................................. 116
   9.4  Mechanism Design without Money ........................ 119
   Notes, Problems, and Exercises ............................. 123
10 Kidney Exchange and Stable Matching ........................ 128
   10.1 Case Study: Kidney Exchange ........................... 128
   10.2 Stable Matching ....................................... 136
   10.3 Further Properties .................................... 139
   Notes, Problems, and Exercises ............................. 142
11 Selfish Routing and the Price of Anarchy ................... 145
   11.1 Selfish Routing: Examples ............................. 145
   11.2 Main Result: Informal Statement ....................... 147
   11.3 Main Result: Formal Statement ......................... 149
   11.4 Technical Preliminaries ............................... 152
   11.5 Proof of Theorem 11.2 ................................. 153
   Notes, Problems, and Exercises ............................. 156
12 Over-Provisioning and Atomic Selfish Routing ............... 159
   12.1 Case Study: Network Over-Provisioning ................. 159
   12.2 A Resource Augmentation Bound ......................... 161
   12.3 Proof of Theorem 12.1 ................................. 162
   12.4 Atomic Selfish Routing ................................ 163
   12.5 Proof of Theorem 12.3 ................................. 165
   Notes, Problems, and Exercises ............................. 169
13 Equilibria: Definitions, Examples, and Existence ........... 173
   13.1 A Hierarchy of Equilibrium Concepts ................... 173
   13.2 Existence of Pure Nash Equilibria ..................... 179
   13.3 Potential Games ....................................... 181
   Notes, Problems, and Exercises ............................. 183
14 Robust Price-of-Anarchy Bounds in Smooth Games ............. 187
   14.1 A Recipe for POA Bounds ............................... 187
   14.2 A Location Game ....................................... 188
   14.3 Smooth Games .......................................... 194
   14.4 Robust POA Bounds in Smooth Games ..................... 195
   Notes, Problems, and Exercises ............................. 199
15 Best-Case and Strong Nash Equilibria ....................... 202
   15.1 Network Cost-Sharing Games ............................ 202
   15.2 The Price of Stability ................................ 205
   15.3 The POA of Strong Nash Equilibria ..................... 208
   15.4 Proof of Theorem 15.3 ................................. 210
   Notes, Problems, and Exercises ............................. 213
16 Best-Response Dynamics ..................................... 216
   16.1 Best-Response Dynamics in Potential Games ............. 216
   16.2 Approximate PNE in Selfish Routing Games .............. 219
   16.3 Proof of Theorem 16.3 ................................. 221
   16.4 Low-Cost Outcomes in Smooth Potential Games ........... 223
   Notes, Problems, and Exercises ............................. 226
17 No-Regret Dynamics ......................................... 230
   17.1 Online Decision Making ................................ 230
   17.2 The Multiplicative Weights Algorithm .................. 234
   17.3 Proof of Theorem 17.6 ................................. 236
   17.4 No Regret and Coarse Correlated Equilibria ............ 239
   Notes, Problems, and Exercises ............................. 242
18 Swap Regret and the Minimax Theorem ........................ 247
   18.1 Swap Regret and Correlated Equilibria ................. 247
   18.2 Proof of Theorem 18.5 ................................. 249
   18.3 The Minimax Theorem for Zero-Sum Games ................ 253
   18.4 Proof of Theorem 18.7 ................................. 255
   Notes, Problems, and Exercises ............................. 258
19 Pure Nash Equilibria and PLS-Completeness .................. 261
   19.1 When Are Equilibrium Concepts Tractable? .............. 261
   19.2 Local Search Problems ................................. 264
   19.3 Computing a PNE of a Congestion Game .................. 271
   Notes, Problems, and Exercises ............................. 276
20 Mixed Nash Equilibria and PPAD-Completeness ................ 279
   20.1 Computing a MNE of a Bimatrix Game .................... 279
   20.2 Total NP Search Problems (TFNP) ....................... 280
   20.3 WAD: A Syntactic Subclass of TFNP ..................... 285
   20.4 A Canonical PPAD Problem: Sperner's Lemma ............. 288
   20.5 MNE and PPAD .......................................... 290
   20.6 Discussion ............................................ 293
   Notes, Problems, and Exercises ............................. 294
The Top 10 List ............................................... 299
Hints to Selected Exercises and Problems ...................... 301
Bibliography .................................................. 309
Index ......................................................... 329


Архив выставки новых поступлений | Отечественные поступления | Иностранные поступления | Сиглы
 

[О библиотеке | Академгородок | Новости | Выставки | Ресурсы | Библиография | Партнеры | ИнфоЛоция | Поиск]
  Пожелания и письма: branch@gpntbsib.ru
© 1997-2024 Отделение ГПНТБ СО РАН (Новосибирск)
Статистика доступов: архив | текущая статистика
 

Документ изменен: Wed Feb 27 14:29:56 2019. Размер: 12,691 bytes.
Посещение N 1157 c 05.12.2017