CONTENTS  PDF

Credits and Acknowledgments
Introduction

 

1 Distributed Constraint Satisfaction
1.1  Defining distributed constraint satisfaction problems
1.2 Domain-pruning algorithms
1.3 Heuristic search algorithms
         1.3.1 The asynchronous backtracking algorithm
         1.3.2 A simple example
         1.3.3 An extended example: the four-queen problem
         1.3.4 Beyond the ABT algorithm
1.4 History and references

2 Distributed Optimization
2.1 Distributed dynamic programming for path planning
         2.1.1 Asynchronous dynamic programming
         2.1.2 Learning real-time A*
2.2 Action selection in multiagent MDPs
2.3 Negotiation, auctions and optimization
         2.3.1 Introduction: from contract nets to auction-like optimization
         2.3.2 The assignment problem and linear programming
         2.3.3 The scheduling problem and integer programming
2.4 Social laws and conventions
2.5 History and references

3 Introduction to Noncooperative Game Theory: Games in Normal Form
3.1 Self-interested agents
         3.1.1 Example: friends and enemies
         3.1.2 Preferences and utility
3.2 Games in normal form
         3.2.1 Example: the TCP user's game
         3.2.2 Definition of games in normal form
         3.2.3 More examples of normal-form games
         3.2.4 Strategies in normal-form games
3.3 Analyzing games: from optimality to equilibrium
         3.3.1 Pareto optimality
         3.3.2 Defining best response and Nash equilibrium
         3.3.3 Finding Nash equilibria
         3.3.4 Nash's theorem: proving the existence of Nash equilibria
3.4 Further solution concepts for normal-form games
         3.4.1 Maxmin and minmax strategies
         3.4.2 Minimax regret
         3.4.3 Removal of dominated strategies
         3.4.4 Rationalizability
         3.4.5 Correlated equilibrium
         3.4.6 Trembling-hand perfect equilibrium
         3.4.7 Epsilon-Nash equilibrium
3.5 History and references

4 Computing Solution Concepts of Normal-Form Games
4.1 Computing Nash equilibria of two-player, zero-sum games
4.2 Computing Nash equilibria of two-player, general-sum games
         4.2.1 Complexity of computing a sample Nash equilibrium
         4.2.2 An LCP formulation and the Lemke--Howson algorithm
         4.2.3 Searching the space of supports
         4.2.4 Beyond sample equilibrium computation
4.3 Computing Nash equilibria of n-player, general-sum games
4.4 Computing maxmin and minmax strategies for two-player, general-sum games
4.5 Identifying dominated strategies
         4.5.1 Domination by a pure strategy
         4.5.2 Domination by a mixed strategy
         4.5.3 Iterated dominance
4.6 Computing correlated equilibria
4.7 History and references

5 Games with Sequential Actions: Reasoning and Computing with the Extensive Form
5.1 Perfect-information extensive-form games
         5.1.1 Definition
         5.1.2 Strategies and equilibria
         5.1.3 Subgame-perfect equilibrium
         5.1.4 Computing equilibria: backward induction
5.2 Imperfect-information extensive-form games
         5.2.1 Definition
         5.2.2 Strategies and equilibria
         5.2.3 Computing equilibria: the sequence form
         5.2.4 Sequential equilibrium
5.3 History and references

6 Richer Representations: Beyond the Normal and Extensive Forms
6.1 Repeated games
         6.1.1 Finitely repeated games
         6.1.2 Infinitely repeated games
         6.1.3 "Bounded rationality": repeated games played by automata
6.2 Stochastic games
         6.2.1 Definition
         6.2.2 Strategies and equilibria
         6.2.3 Computing equilibria
6.3 Bayesian games
         6.3.1 Definition
         6.3.2 Strategies and equilibria
         6.3.3 Computing equilibria
         6.3.4 Ex post equilibrium
6.4 Congestion games
         6.4.1 Definition
         6.4.2 Computing equilibria
         6.4.3 Potential games
         6.4.4 Nonatomic congestion games
         6.4.5 Selfish routing and the price of anarchy
6.5 Computationally motivated compact representations
         6.5.1 The expected utility problem
         6.5.2 Graphical games
         6.5.3 Action-graph games
         6.5.4 Multiagent influence diagrams
         6.5.5 GALA
6.6 History and references

7 Learning and Teaching
7.1 Why the subject of "learning" is complex
         7.1.1 The interaction between learning and teaching
         7.1.2 What constitutes learning?
         7.1.3 If learning is the answer, what is the question?
7.2 Fictitious play
7.3 Rational learning
7.4 Reinforcement learning
         7.4.1 Learning in unknown MDPs
         7.4.2 Reinforcement learning in zero-sum stochastic games
         7.4.3 Beyond zero-sum stochastic games
         7.4.4 Belief-based reinforcement learning
7.5 No-regret learning and universal consistency
7.6 Targeted learning
7.7 Evolutionary learning and other large-population models
         7.7.1 The replicator dynamic
         7.7.2 Evolutionarily stable strategies
         7.7.3 Agent-based simulation and emergent conventions
7.8 History and references

8 Communication
8.1 "Doing by talking" I: cheap talk
8.2 "Talking by doing": signaling games
8.3 "Doing by talking" II: speech-act theory
         8.3.1 Speech acts
         8.3.2 Rules of conversation
         8.3.3 A game-theoretic view of speech acts
         8.3.4 Applications
8.4 History and references

9 Aggregating Preferences: Social Choice
9.1 Introduction
         9.1.1 Example: plurality voting
9.2 A formal model
9.3 Voting
         9.3.1 Voting methods
         9.3.2 Voting paradoxes
9.4 Existence of social functions
         9.4.1 Social welfare functions
         9.4.2 Social choice functions
9.5 Ranking systems
9.6 History and references

10 Protocols for Strategic Agents: Mechanism Design
10.1 Introduction
         10.1.1 Example: strategic voting
         10.1.2 Example: buying a shortest path
10.2 Mechanism design with unrestricted preferences
         10.2.1 Implementation
         10.2.2 The revelation principle
         10.2.3 Impossibility of general, dominant-strategy implementation
10.3 Quasilinear preferences
         10.3.1 Risk attitudes
         10.3.2 Mechanism design in the quasilinear setting
10.4 Efficient mechanisms
         10.4.1 Groves mechanisms
         10.4.2 The VCG mechanism
         10.4.3 VCG and individual rationality
         10.4.4 VCG and weak budget balance
         10.4.5 Drawbacks of VCG
         10.4.6 Budget balance and efficiency
         10.4.7 The AGV mechanism
10.5 Beyond efficiency
         10.5.1 What else can be implemented in dominant strategies?
         10.5.2 Tractable Groves mechanisms
10.6 Computational applications of mechanism design
         10.6.1 Task scheduling
         10.6.2 Bandwidth allocation in computer networks
         10.6.3 Multicast cost sharing
         10.6.4 Two-sided matching
10.7 Constrained mechanism design
         10.7.1 Contracts
         10.7.2 Bribes
         10.7.3 Mediators
10.8 History and references

11 Protocols for Multiagent Resource Allocation: Auctions
11.1 Single-good auctions
         11.1.1 Canonical auction families
         11.1.2 Auctions as Bayesian mechanisms
         11.1.3 Second-price, Japanese, and English auctions
         11.1.4 First-price and Dutch auctions
         11.1.5 Revenue equivalence
         11.1.6 Risk attitudes
         11.1.7 Auction variations
         11.1.8 "Optimal" (revenue-maximizing) auctions
         11.1.9 Collusion
         11.1.10 Interdependent values
11.2 Multiunit auctions
         11.2.1 Canonical auction families
         11.2.2 Single-unit demand
         11.2.3 Beyond single-unit demand
         11.2.4 Unlimited supply: random sampling auctions
         11.2.5 Position auctions
11.3 Combinatorial auctions
         11.3.1 Simple combinatorial auction mechanisms
         11.3.2 The winner determination problem
         11.3.3 Expressing a bid: bidding languages
         11.3.4 Iterative mechanisms
         11.3.5 A tractable mechanism
11.4 Exchanges
         11.4.1 Two-sided auctions
         11.4.2 Prediction markets
11.5 History and references

12 Teams of Selfish Agents: An Introduction to Coalitional Game Theory
12.1 Coalitional games with transferable utility
         12.1.1 Definition
         12.1.2 Examples
         12.1.3 Classes of coalitional games
12.2 Analyzing coalitional games
         12.2.1 The Shapley value
         12.2.2 The core
         12.2.3 Refining the core: epsilon-core, least core, and nucleolus
12.3 Compact representations of coalitional games
         12.3.1 Weighted majority games and weighted voting games
         12.3.2 Weighted graph games
         12.3.3 Capturing synergies: a representation for superadditive games
         12.3.4 A decomposition approach: multi-issue representation
         12.3.5 A logical approach: marginal contribution nets
12.4 Further directions
         12.4.1 Alternative coalitional game models
         12.4.2 Advanced solution concepts
12.5 History and references

13 Logics of Knowledge and Belief
13.1 The partition model of knowledge
         13.1.1 Muddy children and warring generals
         13.1.2 Formalizing intuitions about the partition model
13.2 A detour to modal logic
         13.2.1 Syntax
         13.2.2 Semantics
         13.2.3 Axiomatics
         13.2.4 Modal logics with multiple modal operators
         13.2.5 Remarks about first-order modal logic
13.3 S5: An axiomatic theory of the partition model
13.4 Common knowledge, and an application to distributed systems
13.5 Doing time and an application to robotics
         13.5.1 Termination conditions for motion planning
         13.5.2 Coordinating robots
13.6 From knowledge to belief
13.7 Combining knowledge and belief (and revisiting knowledge)
13.8 History and references

14 Beyond Belief: Probability, Dynamics and Intention
14.1 Knowledge and probability
14.2 Dynamics of knowledge and belief
         14.2.1 Belief revision
         14.2.2 Beyond AGM: update, arbitration, fusion, and friends
         14.2.3 Theories of belief change: a summary
14.3 Logic, games, and coalition logic
14.4 Towards a logic of "intention"
         14.4.1 Some preformal intuitions
         14.4.2 The road to hell: elements of a formal theory of intention
         14.4.3 Group intentions
14.5 History and references

Appendices

A Probability Theory
A.1 Probabilistic models
A.2 Axioms of probability theory
A.3 Marginal probabilities
A.4 Conditional probabilities

B Linear and Integer Programming
B.1 Linear programs
B.2 Integer programs

C Markov Decision Problems (MDPs)
C.1 The model
C.2 Solving known MDPs via value iteration

D Classical Logic
D.1 Propositional calculus
D.2 First-order logic

 

Bibliography
Index