[game theory] basic knowledge

【 Game theory 】 Basic knowledge of

1 Strategic game

Strategic game also called Static game , It is once game . Strategic game $G$ Formalized as ：
$$G=\left\{N,{\left\{A_i\right\}}_{i=1}^N,{\left\{u_i\right\}}_{i=1}^N\right\}$$
among ：

• $N$： Player set , A limited set of all players ;
• $A_i$： The player $i$ The strategy set of ： It means the player $i$ A collection of selectable policies ;
• $u_i$： The player $i$ The return function of ：$$A_1\times A_2\times \dots A_N\to R$$ Represents the benefits under a set of strategies .

Complete information static game It has the following characteristics ：

• Non cooperative game
• Act at the same time （simultaneous move）： All players make strategic choices at the same time . I don't know the strategy choice of other players when I choose the strategy
• Full information （complete information）： Each player's strategy and revenue function are the common knowledge of all players （common knowledge）

Incomplete information static game （ Also known as Static Bayesian game ） It has the following characteristics ：

• Non cooperative game
• Act at the same time （simultaneous move）： All players make strategic choices at the same time . I don't know the strategy choice of other players when I choose the strategy
• Incomplete information （incomplete information）： At least one player does not know exactly the payoff function of another player .

With Prisoner's dilemma For example ：

Complete information static game ：

Two suspect were arrested , To different cells , But the police don't have enough evidence , Two suspects were told ：

1. If neither side confesses , Were sentenced to one month ;
2. If both sides confess , Were sentenced to six months ;
3. If one party confesses and the other does not , Then the Confessor releases , The party who did not confess was sentenced to nine months .

A bivariate matrix can be used to represent the benefits of both ：

Incomplete information static game ：

Two suspect were arrested , To different cells , But the police don't have enough evidence , Two suspects were told ：

1. If neither side confesses , Were sentenced to one month ;
2. If both sides confess , Were sentenced to six months ;
3. If one party confesses and the other does not , Then the Confessor releases , The party who did not confess was sentenced to nine months .

besides , There are additional things to note ：

1. Prisoner 1 Always rational , That is, selfish
2. Prisoner 2 May be rational , It may also be altruistic , It depends on his mood
3. When Prisoner 2 It's altruistic , Then he is not so frank , He thinks confession equals “ An extra four months in prison ”
4. Prisoner 1 Unable to judge accurately Prisoner 2 Is it selfish or altruistic , But he can infer Prisoner 2 The probability of rationality is 0.8, The probability of altruism is 0.2.

2 Extended game

Extended game , Also known as Dynamic game , It corresponds to the strategic game . In an extended game , Players take turns making decisions , Usually available Game tree Depict it .

The game tree consists of node (node) and edge (edge) form , Corresponding to the game player 、 Strategy and benefits .

1. Non leaf node ： representative Game player , It indicates which game player makes a decision at this time . Each non leaf node has only one game player .
2. leaf node ： Represents each player's... At this time earnings . Benefits only exist in leaf nodes .
3. edge ： Express Strategy

Extended game $G$ Formalized as ：
$$G=\left\{N,H,P,\left\{u_i\right\}\right\}$$
among ：

• $N$ Gather for players ;
• $H$ by “ Sequence of policies ” A collection of components , It can be a finite set or an infinite set .$H$ Is called history (history). The nature includes ：
  • $\varnothing \in H$, Represents the root node of the game tree .
  • If the policy sequence $a^1{a}^2\dots a^k\in H$ also $s<k$, that $a^1{a}^2\dots a^s\in H$
  • If the infinite policy sequence ${\left(a^k\right)}_{k=1}^{\infty }$ Contentment for any $k$,$a^1{a}^2\dots a^k\in H$, that ${\left(a^k\right)}_{k=1}^{\infty }\in H$
  • Each historical sequence corresponds to a node of the game tree , Corresponding to the node reached at the end of the historical sequence
  • In the complete information extended game , History set size = Number of nodes
  • Final history collection (Terminal history set)：$Z$ = {All Terminal history}, On these nodes are earnings
• $P$ For the game player function (Player Function)：
  • $P:H\backslash Z\to N$ Assign a player set to each non - ending history $N$ An element in
  • $P(h)$ In history $h$ after , Which player makes the decision
• $u_i$ Is the income function , It means the first one $i$ Revenue from players

3 Nash equilibrium

Go on up Complete information static game An example of the prisoner's dilemma . Let's stand before the prisoner 1 From the perspective of ：

• If 2 Frankly , I choose to confess , Then the income is -6; If I don't choose to confess , Then the income is -9. So I will choose to confess ;
• If 2 No, No , I choose to confess , Then the income is 0; If I don't choose to confess , Then the income is -9, So I will choose to confess .

meanwhile , The prisoner 2 I think so . So both will confess .

Optimal response ： When the opponent's strategy is chosen , Players will adjust their strategies , Make your income the largest among several strategic choices .

Nash equilibrium ： Any player changes his strategy in this strategy combination （ The strategies of other players remain the same ） Will not improve their own income .

That is, every player's strategy is The best response When , A stable situation will be formed , That is to achieve Nash equilibrium .

The formal definition of Nash equilibrium is as follows ：

Nash equilibrium is the result of game $a^{\ast }=\left(a_1^{\ast },a_2^{\ast },\dots ,a_N^{\ast }\right)$, That is, for each player $i$ There are ：
$$u_i\left(a_i^{\ast },a_{-i}^{\ast }\right)\ge u_i\left(a_i,a_{-i}^{\ast }\right)$$
therefore , We can By finding the game result that satisfies the best response of all people at the same time , To solve the Nash equilibrium .

Reference

https://zhuanlan.zhihu.com/p/148407108

https://zhiqianghe.blog.csdn.net/article/details/107330041

https://www.docin.com/p-2590113104.html

https://zhuanlan.zhihu.com/p/199047997