Multiagent Systems

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

......(更多)