Introduction to Game Theory

Game theory is a branch of economics that primarily studies the behaviors of competitive or adversarial individuals under specific rules. Game theory focuses on the expected and actual behaviors of individuals in a game and investigates 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/Non-cooperative Games

A cooperative game is one in which participants can form alliances and cooperate with each other. In such games, individual non-cooperative behavior is often punished by some external mechanism. In contrast, in a non-cooperative game, no such mechanism exists. Therefore, participants either cannot form alliances or can only rely on credible threat mechanisms to maintain cooperation.

Compared to cooperative games, non-cooperative games are more systematically and thoroughly studied. All games discussed in this article are non-cooperative games.

Symmetric/Asymmetric Games

In a symmetric game, different participants receive the same payoff when taking the same action. That is, the payoff depends only on the action itself, not on the identity of the actor. Games that do not satisfy this condition are called asymmetric games.

Zero-sum/Non-zero-sum Games

Main page: Zero-sum Game

A zero-sum game is one in which the sum of payoffs for all participants is always zero, regardless of the actions taken by each party. Typically discussed zero-sum games involve two participants, where one party's gain is necessarily the other'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 simultaneously without knowing the choices of others. For example, Rock-Paper-Scissors is a typical simultaneous game. Such games are often represented by payoff matrices and usually do not involve the concept of time.

In contrast, a sequential game involves participants taking actions in turn. It is important to note that later actors can observe at least some of the actions of earlier actors; otherwise, the order would be meaningless. Sequential games are typically described using game trees.

Perfect/Imperfect Information Games

Perfect information means that at any moment when making a decision, a participant has complete knowledge of all events that have occurred up to that point, including the initial state of the game. For example, chess and Go are perfect information games; whereas mahjong and poker are imperfect information games because players cannot know the hands of others. Perfect information is usually used to describe sequential games; since players in simultaneous games cannot know each other's upcoming actions, simultaneous games are generally not considered perfect information games.

Complete/Incomplete Information Games

Complete information means that all participants have full knowledge of the game structure itself (including the available decisions and final payoffs for all parties), and this information is common knowledge. In contrast, incomplete information games involve situations where certain game elements (such as opponents' available decisions or payoff functions) are unknown to the participants.

It is worth noting that "complete information" and "perfect information" are independent concepts and do not imply each other. For example, mahjong is a game with complete but imperfect information because the rules and payoffs are public, but the card information is not transparent; whereas some games with hidden objectives but fully public actions are perfect information but incomplete information games.

Combinatorial Game Theory

In algorithm competitions, the most common type of game is combinatorial games. This term usually refers to games that are difficult to solve due to the large number of states. Because general combinatorial games are quite complex, combinatorial game theory primarily focuses on the following types: two-player turn-based, perfect information, and non-random games. Chess and Go are typical combinatorial games.

Impartial Combinatorial Games

Main page: Impartial Game

An impartial game is a combinatorial game that satisfies the following conditions:

In any given state, all participants have exactly the same set of available actions, depending only on the current state and not on identity;
The same state in the game cannot be reached multiple times; the game ends when a participant cannot take any action, and it must end in a finite number of steps without a draw.

Impartial games are always symmetric games.

Partizan Combinatorial Games

Main page: Partizan Game

In contrast to impartial games, partizan games are those in which the actions available to participants in a given state depend on their identity. Most board games (such as chess, Chinese chess, Go, Gomoku, etc.) are partizan games because participants can only move their own pieces.

Normal/Misère Games

In combinatorial games, the usual winner is the last participant to take an action before the game ends. This is called a normal game. The opposite is a misère game, where 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.

References

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用