Book contents
- Frontmatter
- Contents
- Credits and Acknowledgments
- Introduction
- 1 Distributed Constraint Satisfaction
- 2 Distributed Optimization
- 3 Introduction to Noncooperative Game Theory: Games in Normal Form
- 4 Computing Solution Concepts of Normal-Form Games
- 5 Games with Sequential Actions: Reasoning and Computing with the Extensive Form
- 6 Richer Representations: Beyond the Normal and Extensive Forms
- 7 Learning and Teaching
- 8 Communication
- 9 Aggregating Preferences: Social Choice
- 10 Protocols for Strategic Agents: Mechanism Design
- 11 Protocols for Multiagent Resource Allocation: Auctions
- 12 Teams of Selfish Agents: An Introduction to Coalitional Game Theory
- 13 Logics of Knowledge and Belief
- 14 Beyond Belief: Probability, Dynamics, and Intention
- Appendices: Technical Background
- Bibliography
- Index
5 - Games with Sequential Actions: Reasoning and Computing with the Extensive Form
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Credits and Acknowledgments
- Introduction
- 1 Distributed Constraint Satisfaction
- 2 Distributed Optimization
- 3 Introduction to Noncooperative Game Theory: Games in Normal Form
- 4 Computing Solution Concepts of Normal-Form Games
- 5 Games with Sequential Actions: Reasoning and Computing with the Extensive Form
- 6 Richer Representations: Beyond the Normal and Extensive Forms
- 7 Learning and Teaching
- 8 Communication
- 9 Aggregating Preferences: Social Choice
- 10 Protocols for Strategic Agents: Mechanism Design
- 11 Protocols for Multiagent Resource Allocation: Auctions
- 12 Teams of Selfish Agents: An Introduction to Coalitional Game Theory
- 13 Logics of Knowledge and Belief
- 14 Beyond Belief: Probability, Dynamics, and Intention
- Appendices: Technical Background
- Bibliography
- Index
Summary
In Chapter 3 we assumed that a game is represented in normal form: effectively, as a big table. In some sense, this is reasonable. The normal form is conceptually straightforward, and most see it as fundamental. While many other representations exist to describe finite games, we will see in this chapter and in Chapter 6 that each of them has an “induced normal form”: a corresponding normal-form representation that preserves game-theoretic properties such as Nash equilibria. Thus the results given in Chapter 3 hold for all finite games, no matter how they are represented; in that sense the normal-form representation is universal.
In this chapter we will look at extensive-form games, a finite representation that does not always assume that players act simultaneously. This representation is in general exponentially smaller than its induced normal form, and furthermore can be much more natural to reason about. While the Nash equilibria of an extensiveform game can be found through its induced normal form, computational benefit can be had by working with the extensive form directly. Furthermore, there are other solution concepts, such as subgame-perfect equilibrium (see Section 5.1.3), which explicitly refer to the sequence in which players act and which are therefore not meaningful when applied to normal-form games.
Perfect-information extensive-form games
The normal-form game representation does not incorporate any notion of sequence, or time, of the actions of the players.
- Type
- Chapter
- Information
- Multiagent SystemsAlgorithmic, Game-Theoretic, and Logical Foundations, pp. 113 - 140Publisher: Cambridge University PressPrint publication year: 2008