Game theory is a branch of economics that mainly studies the behavior of individuals with competitive or adversarial characteristics under specified rules. Game theory concerns the expected and actual behavior of individuals in a game and studies their optimal strategies.
In simple terms, game theory mainly studies how multiple players in a game choose their strategies.
Basic concepts
This section briefly introduces some common concepts in game theory.
Cooperative / noncooperative games
A cooperative game is a game in which participants can form coalitions and cooperate with one another. In such games, an individual's noncooperative behavior is often punished by some external mechanism. In contrast, in a noncooperative game, no such mechanism exists; therefore, participants either cannot form coalitions or can maintain cooperation only through credible threats.
Compared with cooperative games, noncooperative games are studied in a more systematic and mature way. All games discussed in this article are noncooperative games.
Symmetric / asymmetric games
In a symmetric game, different participants receive the same payoff when they take the same action; in other words, the payoff depends only on the action itself and not on the identity of the actor. A game that does not satisfy this condition is called an asymmetric game.
Zero-sum / non-zero-sum games
Main page: Zero-sum game
A zero-sum game is a game in which the sum of the payoffs of all participants is always zero, regardless of the actions taken by the parties. Zero-sum games usually involve two participants; in that case, one party's payoff is necessarily the other party's loss. In contrast, a non-zero-sum game allows multiple parties to win or lose together, including positive-sum games and negative-sum games.
Simultaneous / sequential games
In a simultaneous game, all participants make decisions at the same time without knowing the choices of the others. Rock-paper-scissors, for example, is a typical simultaneous game. Such games are commonly represented by payoff matrices and generally do not involve the concept of time.
In contrast, a sequential game is one in which participants act in succession. Note that the later actor must be able to observe at least part of the earlier actors' behavior; otherwise, the order would be meaningless. Sequential games are usually represented by game trees.
Perfect / imperfect-information games
Perfect information means that whenever a participant makes a decision, they know all events that have occurred previously, including the initial state of the game. Chess and Go, for example, are perfect-information games, whereas Mahjong and poker are imperfect-information games because a player cannot know the cards in the hands of the other players. Perfect information is usually used to describe sequential games. Since players in a simultaneous game cannot know the actions the others are about to take, a simultaneous game is generally considered not to be a perfect-information game.
Complete / incomplete-information games
Complete information means that all participants fully understand the game structure itself, including the decisions available to each party and the final payoffs, and that this information is common knowledge. In contrast, in an incomplete-information game, some game elements, such as an opponent's available decisions or payoff function, are unknown to the participants.
It is worth noting that “complete information” and “perfect information” are two independent concepts and neither contains the other. For example, Mahjong is a complete-information but imperfect-information game: its rules and payoffs are public, but the card information is hidden. Conversely, some games with hidden objectives but fully public actions are perfect-information but incomplete-information games.
Combinatorial game theory
In algorithm contests, the most common type of game is a combinatorial game. This term usually refers to games that are difficult to solve because of their enormous number of states. Since general combinatorial games are quite complicated, combinatorial game theory mainly focuses on games with two players taking turns, perfect information, and no random factors. Chess and Go are typical combinatorial games.
Impartial combinatorial games
Main page: Impartial combinatorial game
An impartial game is a combinatorial game satisfying the following conditions:
- In any fixed state, all participants have exactly the same set of available actions; this depends only on the current state and not on their identities.
- The same state cannot be reached more than once during the game, the game ends when the participant to move has no legal action, and the game always ends without a draw after a finite number of moves.
Impartial games are always symmetric games.
Partizan combinatorial games
Main page: Partizan combinatorial game
The concept opposite to an impartial game is a partizan game, in which the actions a participant can take in a given state depend on their identity. Most board games, such as international chess, Chinese chess, Go, and Gomoku, are partizan games because each participant can operate only their own pieces.
Normal / misère games
In a combinatorial game, the usual winner is the last participant to take an action before the game ends. This is called a normal game. In contrast, in a misère game, the last participant to take an action before the game ends is the loser.
Both impartial and partizan combinatorial games can be normal or misère games.