This exciting and pioneering new overview of multiagent systems, which are online systems composed of multiple interacting intelligent agents, i.e., online trading, offers a newly seen computer science perspective on multiagent systems, while integrating ideas from operations research, game theory, economics, logic, and even philosophy and linguistics. The authors emphasize foundations to create a broad and rigorous treatment of their subject, with thorough presentations of distributed problem solving, game theory, multiagent communication and learning, social choice, mechanism design, auctions, cooperative game theory, and modal logics of knowledge and belief. For each topic, basic concepts are introduced, examples are given, proofs of key results are offered, and algorithmic considerations are examined. An appendix covers background material in probability theory, classical logic, Markov decision processes and mathematical programming. Written by two of the leading researchers of this engaging field, this book will surely serve as THE reference for researchers in the fastest-growing area of computer science, and be used as a text for advanced undergraduate or graduate courses.
Author(s): Yoav Shoham, Kevin Leyton-Brown
Publisher: Cambridge University Press
Year: 2008
Language: English
Pages: 532
Credits and Acknowledgments......Page 12
Introduction......Page 14
Distributed Constraint Satisfaction......Page 20
Defining distributed constraint satisfaction problems......Page 21
Domain-pruning algorithms......Page 23
Heuristic search algorithms......Page 27
The asynchronous backtracking algorithm......Page 29
A simple example......Page 31
An extended example: the four queens problem......Page 32
Beyond the ABT algorithm......Page 36
History and references......Page 37
Asynchronous dynamic programming......Page 38
Learning real-time A*......Page 39
Action selection in multiagent MDPs......Page 41
From contract nets to auction-like optimization......Page 47
The assignment problem and linear programming......Page 49
The scheduling problem and integer programming......Page 55
Social laws and conventions......Page 63
History and references......Page 65
Self-interested agents......Page 66
Example: friends and enemies......Page 67
Preferences and utility......Page 68
Example: the TCP user's game......Page 73
Definition of games in normal form......Page 74
More examples of normal-form games......Page 75
Strategies in normal-form games......Page 78
Analyzing games: from optimality to equilibrium......Page 79
Pareto optimality......Page 80
Defining best response and Nash equilibrium......Page 81
Finding Nash equilibria......Page 82
Nash's theorem: proving the existence of Nash equilibria......Page 84
Maxmin and minmax strategies......Page 92
Minimax regret......Page 95
Removal of dominated strategies......Page 97
Rationalizability......Page 100
Correlated equilibrium......Page 102
-Nash equilibrium......Page 104
History and references......Page 106
Computing Nash equilibria of two-player, zero-sum games......Page 108
Complexity of computing a sample Nash equilibrium......Page 110
An LCP formulation and the Lemke–Howson algorithm......Page 112
Searching the space of supports......Page 120
Beyond sample equilibrium computation......Page 123
Computing Nash equilibria of n-player, general-sum games......Page 124
Identifying dominated strategies......Page 127
Domination by a pure strategy......Page 128
Domination by a mixed strategy......Page 129
Iterated dominance......Page 131
Computing correlated equilibria......Page 132
History and references......Page 134
Perfect-information extensive-form games......Page 136
Definition......Page 137
Strategies and equilibria......Page 138
Subgame-perfect equilibrium......Page 140
Computing equilibria: backward induction......Page 143
Definition......Page 149
Strategies and equilibria......Page 150
Computing equilibria: the sequence form......Page 153
Sequential equilibrium......Page 161
History and references......Page 164
Richer Representations: Beyond the Normal and Extensive Forms......Page 166
Repeated games......Page 167
Finitely repeated games......Page 168
Infinitely repeated games......Page 169
``Bounded rationality": repeated games played by automata......Page 172
Stochastic games......Page 178
Strategies and equilibria......Page 179
Computing equilibria......Page 181
Bayesian games......Page 182
Definition......Page 183
Strategies and equilibria......Page 186
Computing equilibria......Page 189
Ex post equilibrium......Page 192
Definition......Page 193
Computing equilibria......Page 194
Potential games......Page 195
Nonatomic congestion games......Page 197
Selfish routing and the price of anarchy......Page 199
The expected utility problem......Page 204
Graphical games......Page 207
Action-graph games......Page 209
Multiagent influence diagrams......Page 211
GALA......Page 214
History and references......Page 215
The interaction between learning and teaching......Page 218
What constitutes learning?......Page 220
If learning is the answer, what is the question?......Page 221
Fictitious play......Page 225
Rational learning......Page 230
Learning in unknown MDPs......Page 234
Reinforcement learning in zero-sum stochastic games......Page 235
Beyond zero-sum stochastic games......Page 238
No-regret learning and universal consistency......Page 239
Targeted learning......Page 241
The replicator dynamic......Page 243
Evolutionarily stable strategies......Page 247
Agent-based simulation and emergent conventions......Page 249
History and references......Page 252
``Doing by talking'' I: cheap talk......Page 254
``Talking by doing'': signaling games......Page 258
``Doing by talking'' II: speech-act theory......Page 260
Speech acts......Page 261
Rules of conversation......Page 262
A game-theoretic view of speech acts......Page 264
Applications......Page 267
History and references......Page 270
Example: plurality voting......Page 272
A formal model......Page 273
Voting methods......Page 275
Voting paradoxes......Page 277
Social welfare functions......Page 279
Social choice functions......Page 282
Ranking systems......Page 286
History and references......Page 290
Example: strategic voting......Page 292
Example: buying a shortest path......Page 293
Mechanism design with unrestricted preferences......Page 294
Implementation......Page 295
The revelation principle......Page 296
Quasilinear preferences......Page 299
Risk attitudes......Page 300
Mechanism design in the quasilinear setting......Page 303
Groves mechanisms......Page 307
The VCG mechanism......Page 311
VCG and individual rationality......Page 314
VCG and weak budget balance......Page 315
Drawbacks of VCG......Page 316
Budget balance and efficiency......Page 320
The AGV mechanism......Page 321
What else can be implemented in dominant strategies?......Page 322
Tractable Groves mechanisms......Page 324
Task scheduling......Page 326
Bandwidth allocation in computer networks......Page 328
Multicast cost sharing......Page 331
Two-sided matching......Page 335
Constrained mechanism design......Page 340
Contracts......Page 341
Bribes......Page 342
Mediators......Page 343
History and references......Page 345
Single-good auctions......Page 348
Canonical auction families......Page 349
Auctions as Bayesian mechanisms......Page 351
Second-price, Japanese, and English auctions......Page 352
First-price and Dutch auctions......Page 354
Revenue equivalence......Page 356
Risk attitudes......Page 359
Auction variations......Page 360
``Optimal'' (revenue-maximizing) auctions......Page 362
Collusion......Page 364
Interdependent values......Page 367
Canonical auction families......Page 370
Single-unit demand......Page 371
Beyond single-unit demand......Page 374
Unlimited supply: random sampling auctions......Page 376
Position auctions......Page 378
Combinatorial auctions......Page 380
Simple combinatorial auction mechanisms......Page 382
The winner determination problem......Page 383
Expressing a bid: bidding languages......Page 387
Iterative mechanisms......Page 392
A tractable mechanism......Page 394
Two-sided auctions......Page 396
Prediction markets......Page 397
History and references......Page 399
Coalitional games with transferable utility......Page 402
Examples......Page 403
Classes of coalitional games......Page 405
Analyzing coalitional games......Page 406
The Shapley value......Page 407
The core......Page 410
Refining the core: -core, least core, and nucleolus......Page 413
Compact representations of coalitional games......Page 416
Weighted majority games and weighted voting games......Page 417
Weighted graph games......Page 418
Capturing synergies: a representation for superadditive games......Page 420
A decomposition approach: multi-issue representation......Page 421
A logical approach: marginal contribution nets......Page 422
Alternative coalitional game models......Page 424
History and references......Page 426
Muddy children and warring generals......Page 428
Formalizing intuitions about the partition model......Page 429
A detour to modal logic......Page 432
Semantics......Page 433
Axiomatics......Page 434
Remarks about first-order modal logic......Page 435
S5: An axiomatic theory of the partition model......Page 436
Common knowledge, and an application to distributed systems......Page 439
Termination conditions for motion planning......Page 442
Coordinating robots......Page 446
From knowledge to belief......Page 448
Combining knowledge and belief (and revisiting knowledge)......Page 450
History and references......Page 455
Knowledge and probability......Page 456
Belief revision......Page 461
Beyond AGM: update, arbitration, fusion, and friends......Page 467
Logic, games, and coalition logic......Page 472
Towards a logic of ``intention''......Page 474
Some preformal intuitions......Page 475
The road to hell: elements of a formal theory of intention......Page 477
Group intentions......Page 480
Appendices: Technical Background......Page 482
Axioms of probability theory......Page 486
Conditional probabilities......Page 487
Linear programs......Page 488
Integer programs......Page 490
Solving known MDPs via value iteration......Page 494
Propositional calculus......Page 496
First-order logic......Page 497
Index......Page 500
