Basics of Game Theory
Game Theory
Game theory is the study of mathematical models of strategic interactions among rational agents. It has applications in many fields of social science, used extensively in economics as well as in logic, systems science and computer science.
Classification
| Cooperative Game | Non-Cooperative Game |
|---|---|
| Complete Information Game Perfect Information Game Certainty Game Symmetric Game |
Incomplete Information Game Imperfect Information Game Uncertain Game Asymmetric Game |
| Static Game (Simultaneous-Move) | Dynamic Game (Sequential-Move) |
| Zero-Sum Game Constant-Sum Game |
Non-Zero-Sum Game Variable-Sum Game |
| Alliance Game | Non-Aligned Game |
Representation
- Normal form: The normal (or strategic form) game is usually represented by a matrix which shows the players, strategies, and payoffs (as pictured here).
- Extensive form: The extensive form can be used to formalize games with a time sequencing of moves. Extensive form games can be visualised using game trees (as pictured here). Here each vertex (or node) represents a point of choice for a player. The player is specified by a number listed by the vertex. The lines out of the vertex represent a possible action for that player. The payoffs are specified at the bottom of the tree.
- Characteristic function form: In games that possess removable utility, separate rewards are not given; rather, the characteristic function decides the payoff of each unity. The idea is that the unity that is 'empty', so to speak, does not receive a reward at all.
Dominant Strategy
The strategy that gives you higher (or equal) utility than any other strategy, regardless of the opponent’s action.
Dominant Strategy Equilibrium
When each player has a dominant strategy, the combination is termed a dominant strategy equilibrium.
Nash Equilibrium
In game theory, the Nash equilibrium is the most commonly-used solution concept for non-cooperative games. A Nash equilibrium is a situation where no player could gain by changing their own strategy (holding all other players' strategies fixed).
Cooperative Equilibrium
A cooperative equilibrium is a solution concept in game theory where players achieve optimal outcomes through cooperation. In this state, all participants adhere to consistent cooperative strategies to maximize their collective benefits.
Focal point
In game theory, a focal point (or Schelling point) is a solution that people tend to choose by default in the absence of communication in order to avoid coordination failure.
Cournot competition
Cournot competition is an economic model used to describe an industry structure in which companies compete on the amount of output they will produce, which they decide on independently of each other and at the same time.
Solution of Zero-sum Game
For two-player finite zero-sum games, the different game theoretic solution concepts of Nash equilibrium, minimax, and maximin all give the same solution. If the players are allowed to play a mixed strategy, the game always has an equilibrium.
Max-min strategy
For each action, consider the worst-case caused by the opponent's action, then choose the best action among these worst cases.
Saddle point
In a zero-sum matrix game, an outcome is a saddle point if the outcome is a minimum in its row and maximum in its column.
In a zero-sum game, if there exists a saddle point, then the result of the game will be that point.
Not necessarily exists.
Mixed Strategy
A mixed strategy is an assignment of a probability to each pure strategy. When enlisting mixed strategy, it is often because the game does not allow for a rational description in specifying a pure strategy (choose a single action) for the game.
Oddness Theorem
Almost all finite games (games that can be written in a finite matrix) have a finite number of solutions, and that number is also odd.
Congestion Games
Congestion games (CG) are a class of games in game theory. They represent situations which commonly occur in roads, communication networks, oligopoly markets and natural habitats. There is a set of resources (e.g. roads or communication links); there are several players who need resources (e.g. drivers or network users); each player chooses a subset of these resources (e.g. a path in the network); the delay in each resource is determined by the number of players choosing a subset that contains this resource. The cost of each player is the sum of delays among all resources he chooses. Naturally, each player wants to minimize his own delay; however, each player's choices impose a negative externality on the other players, which may lead to inefficient outcomes.
Pareto Efficiency
A state is said Pareto efficient, iff there exists no state that is better for one agent, and no worse for all the rest.
Shapley value
The Shapley value is a solution concept in cooperative game theory. It resolves problem of order dependence in marginal contribution schemes by averaging marginal contribution over all orders! \[ W(|S|)=\frac{(n-|S|)!(|S|-1)!}{n!} \] \[ \varphi_i(V)=\sum_{i\in S\subseteq I } W(|S|)[V(S)-V(S\backslash\{i\})] \]
The Shapley value is the only value division that satisfies all of the following axiomatic conditions:
- Symmetry
- Linearity: for any \(S\), if \(v(S)=w(S)+w'(S)\) holds, i.e., \(v\) can be divided into \(w\) and \(w'\), then the Shapley value for \(v\) is the sum of the Shapley values for \(w\) and \(w'\).
- Efficiency: the sum is equal to \(v(N)\).
- Null player: we call player a as null player if for any coalition \(S\) (without \(a\))，\(v(S) = v(S\cup\{a\})\) holds. Each null player obtains 0.
Core
In cooperative game theory, the core is the set of feasible allocations or imputations where no coalition of agents can benefit by breaking away from the grand coalition. One can think of the core corresponding to situations where it is possible to sustain cooperation among all agents. A coalition is said to improve upon or block a feasible allocation if the members of that coalition can generate more value among themselves than they are allocated in the original allocation. As such, that coalition is not incentivized to stay with the grand coalition.
An allocation is said to be in the core of a game if there is no coalition that can improve upon it. The core is then the set of all feasible allocations .
Nucleolus
In cooperative game theory, the nucleolus of a cooperative game is the solution (i.e., allocation of payments to players) that maximizes the smallest excess of a coalition (where the excess is the difference between the payment given to the coalition and the value the coalition could get by deviating). Subject to that, the nucleolus satisfies the second-smallest excess; and so on, in the leximin order.
The nucleolus is a single solution, for which the vector of excesses of all coalitions is largest in the leximin order. Intuitively, the nucleolus maximizes the stability of the solution by minimizing the incentives of coalitions to deviate.
Banzhaf power index
The Banzhaf power index is a power index defined by the probability of changing an outcome of a vote where voting rights are not necessarily equally divided among the voters or shareholders.
Characteristic function: \[ V(S)=\begin{cases}1 \quad\text{Allied } S \text{ wins}\\0\quad\text{else}\end{cases} \] Power Index: \[ c_j=\sum_{j\in S\subseteq I }[V(S)-V(S\backslash\{j\})] \] Power index ratio: \[ \Phi_j=\frac{c_j}{c_1+c_2+\cdots+c_n} \]
Sequential Game
In game theory, a sequential game is a game where one player chooses their action before the others choose theirs. The other players must have information on the first player's choice so that the difference in time has no strategic effect. Sequential games are governed by the time axis and represented in the form of decision trees.
Sequential games with perfect information can be analysed mathematically using combinatorial game theory.
Combinatorial game theory
Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a position that the players take turns changing in defined ways or moves to achieve a defined winning condition.
Backward induction
Backward induction is the process of determining a sequence of optimal choices by reasoning from the end point of a problem or situation back to its beginning via individual events or actions (point by point).
Stackelberg competition
The Stackelberg leadership model is a strategic game in economics in which the leader firm moves first and then the follower firms move sequentially (hence, it is sometimes described as the "leader-follower game").
There are some further constraints upon the sustaining of a Stackelberg equilibrium. The leader must know ex ante that the follower observes its action. The follower must have no means of committing to a future non-Stackelberg leader's action and the leader must know this. Indeed, if the 'follower' could commit to a Stackelberg leader action and the 'leader' knew this, the leader's best response would be to play a Stackelberg follower action.
Firms may engage in Stackelberg competition if one has some sort of advantage enabling it to move first. More generally, the leader must have commitment power. Moving observably first is the most obvious means of commitment: once the leader has made its move, it cannot undo it—it is committed to that action. Moving first may be possible if the leader was the incumbent monopoly of the industry and the follower is a new entrant. Holding excess capacity is another means of commitment.
Common Equilibrium
| Static Game | Dynamic Game | |
|---|---|---|
| Complete Information Game | Nash Equilibrium | Subgame Perfect Nash Equilibrium |
| Incomplete Information Game | Bayesian Nash Equilibrium | Perfect Bayesian Nash Equilibrium |
Leximin order
In mathematics, leximin order is a total preorder on finite-dimensional vectors. A more accurate, but less common term is leximin preorder. The leximin order is particularly important in social choice theory and fair division.
Game tree
- A state/node: a possible state of the game.
- State transition/edge: connect two states/nodes, such that the transition is valid (one-way).
- The first mover is called the MAX player, and the second mover is called the MIN plyer. The node corresponds to the turn of the first-mover is called a MAX node (similarly, MIN node).
- A node where the win/lost is determined is called a terminal node.
Scope of application:
A player makes his decision multiple times two players make their decisions alternately.
The choice of the actions of the other player in the previous turns are public.
Centipede Game
Centipede game is an extensive form game in which two players take turns choosing either to take a slightly larger share of an increasing pot, or to pass the pot to the other player. The payoffs are arranged so that if one passes the pot to one's opponent and the opponent takes the pot on the next round, one receives slightly less than if one had taken the pot on this round, but after an additional switch the potential payoff will be higher.
The unique subgame perfect equilibrium (and every Nash equilibrium) of these games results in the first player taking the pot on the first round of the game; however, in empirical tests, relatively few players do so, and as a result, achieve a higher payoff than in the subgame perfect and Nash equilibria. These results are taken to show that subgame perfect equilibria and Nash equilibria fail to predict human play in some circumstances.
Properly Layout of Talmud
Without game theory, a two millennia old mystery may still remain unsolved. The Talmud, an ancient Babylonian text central to Judaism, suggests a cryptic method of dividing a dead man’s estate between three creditors.
Contested garment rule
The contested garment (CG) rule, also called concede-and-divide, is a division rule for solving problems of conflicting claims (also called "bankruptcy problems"). The idea is that, if one claimant's claim is less than 100% of the estate to divide, then he effectively concedes the unclaimed estate to the other claimant. Therefore, we first give to each claimant, the amount conceded to him/her by the other claimant. The remaining amount is then divided equally among the two claimants.
Mechanism design
Mechanism design is a branch of economics, social choice theory, and game theory that deals with designing games (or mechanisms) to implement a given social choice function. Because it starts at the end of the game (the optimal result) and then works backwards to find a game that implements it, it is sometimes called reverse game theory.