博弈论

Two-Person Zero-Sum Games

Strategic Form of 2-person: The strategic form, or normal form, of a two-person zero-sum game is given by a triplet $(X,Y,A)$, where

1. $X$ is a nonempty set, the set of strategies of Player I
2. $Y$ is a nonempty set, the set of strategies of Player II
3. $A$ is a real-valued function defined on $X\times Y$. (Thus, $A(x,y)$ is a real number for every $x\in X$ and every $y\in Y$)

The interpretation is as follows. Simultaneously, Player I chooses $x\in X$ and Player II chooses $y\in Y$, each unaware of the choice of the other. Then their choices are made known and I wins the amount $A(x,y)$ from II.

Matrix Games : A finite two-person zero-sum game in strategic form, $(X,Y,A)$, is sometimes called a matrix game because the essential information of the game, the payoff function A, can be represented by a matrix.
If X = { x 1 , . . . , x m } X =\{x_1 , . . . , x_m\} X={x1​,...,xm​} and Y = { y 1 , . . . , y n } Y = \{y_1, . . . , y_n\} Y={y1​,...,yn​}, then by the game matrix or payoff matrix we mean the matrix where $a_{ij}=A(x_i,y_j)$

Removing Dominated Strategies: We say the i th row of a matrix $A=(a_{ij})$ dominates the k th row if $a_{ij}\ge a_{kj}$ for all j. We say the i th row of A strictly dominates the k th row if $a_{ij}>a_{kj}$ for all j. Similarly, the j th column of A dominates (strictly dominates)the k th column if $a_{ij}\le a_{ik}$ (resp. $a_{ij}<a_{ik}$ ) for all i.

Best Response: Let $(X,Y,A)$ be a matrix game. Let $x\in X$ be a strategy of Player I. Then, $y\in Y$ is called a Best Response to $x$ if $A(x,y)\ge A(x,y’)$ for any $y’\in Y$. Equivalently, Let $y\in Y$ be a strategy of Player II. Then, $x\in X$ is called a Best Response to $y$ if $A(x,y)\ge A(x’,y)$ for any $x’\in X$.

We may apply the following two principles to analyze the game.

1. Equilibrium Principle: Best Responses to each other
   This principle involves the interactions of the players.
2. Maximin Principle: Safety First
   Under this principle, each player only concerns his/her own payoff.

Saddle points: If some entry $a_{ij}$ of the matrix $A$ has the property that

1. $a_{ij}$ is the minimum of the $i$ th row,
2. $a_{ij}$ is the maximum of the $j$ th column,

then we say $a_{ij}$ is a saddle point. If $a_{ij}$ is a saddle point, then Player I can then win at least $a_{ij}$ by choosing row i, and Player II can keep her loss to at most $a_{ij}$ by choosing column j. <Row i, Column j> is then an equilibrium pair, i.e. BR to each other.

Maximin Principle means to find the “risk” for each strategy and then find the strategy, called the safety strategy, with minimum risk.

Suppose A = ( − 2 3 3 − 4 ) A=

A=(−23​3−4​) If Player I uses Row 1, the worst payoff is -2. If Player I uses Row 2, the worst payoff is -4. Therefore, the “best” of the worst case is -2. ${\max }_i{\min }_{j}A(x_i,x_j)=-2$

Mixed Strategies : Consider a finite 2-person zero-sum game, $(X,Y,A)$, with $m\times n$ matrix, $A$. Let us take the strategy space $X$ to be the first $m$ integers, X = { 1 , 2 , . . . , m } X = \{1, 2, . . .,m\} X={1,2,...,m}, and similarly, Y = { 1 , 2 , . . . , n } Y = \{1, 2, . . . , n\} Y={1,2,...,n}. A mixed strategy for Player I may be represented by a column vector, $(p_1,p_2,...,p_m{)}^T$ of probabilities that add up to 1. Similarly, a mixed strategy for Player II is an n-tuple $q=(q_1,q_2,...,q_n{)}^T$.

The sets of mixed strategies of players I and II will be denoted respectively by $X^{\ast },Y^{\ast }$.

X ∗ = { p = ( p 1 , . . . , p m ) T ∣ p i ≥ 0 , f o r      i = 1 , . . . , m      a n d      p 1 + . . . + p m = 1 } X^* = \{p = (p_1 , . . . , p_m )^T | p_i \geq 0, for \;\;i = 1, . . . , m \;\;and \;\;p_1 +...+ p_m =1\} X∗={p=(p1​,...,pm​)T∣pi​≥0,fori=1,...,mandp1​+...+pm​=1}

Y ∗ = { q = ( q 1 , . . . , q n ) T ∣ q j ≥ 0 , f o r      j = 1 , . . . , n      a n d      q 1 + . . . + q n = 1 } Y^* = \{q = (q1 , . . . , qn )^T | q_j \geq 0, for \;\;j = 1, . . . , n \;\;and \;\; q_1 +...+ q_n =1\} Y∗={q=(q1,...,qn)T∣qj​≥0,forj=1,...,nandq1​+...+qn​=1}

$p=(p_1,...,p_m{)}^T$ means playing Row 1 with probability $p_1$, playing Row 2 with probability $p_2$ ,…, playing Row m with probability $p_m$.

The m-dimensional unit vector $e_k\in X^{\ast }$ with a one at the kth component and zeros elsewhere may be identified with the pure strategy of choosing row k.

We could if we like consider the game $(X,Y,A)$ in which the players are allowed to use mixed strategies as a new game $(X^{\ast },Y^{\ast },A)$, where $A(p,q)=p^{T}Aq={\sum }_i{\sum }_j{p}_i{a}_{ij}{q}_j$

Utility Assumption : The basic premise of utility theory is that one should evaluate a payoff by its utility to the player rather than on its numerical monetary value.

Safety Strategies :For each $p\in X^{\ast }$ , the worst payoff is ${\min }_{q\in Y^{\ast }}{p}^{T}Aq$ The minimum is achieved at a pure strategy of Player II.

Theorem : There exists $p^{\prime }\in X^{\ast }$ such that
$$V^{\prime }=\underset{q\in Y^{\ast }}{\min }{p}^{\prime T}Aq=\underset{p\in X^{\ast }}{\max }\underset{q\in Y^{\ast }}{\min }{p}^{T}Aq$$
$p^{\prime }$ is called the safety strategy of Player I and the value $V^{\prime }$ is called the lower value of the game

The minimum is achieved by a pure strategy of Player II.

If Player I use his safety strategy then he is guaranteed to lose at lease $V^{\prime }$ no matter what Player II does

Theorem 2 : There exists $q^{\prime }\in Y^{\ast }$ such that
$$V^{\prime \prime }=\underset{p\in X^{\ast }}{\max }{p}^{T}A{q}^{\prime }=\underset{q\in Y^{\ast }}{\min }\underset{p\in X^{\ast }}{\max }{p}^{T}Aq$$
$q^{\prime }$ is called the safety strategy of Player II and the value $V^{\prime \prime }$ is called the upper value of the game

If Player II use his safety strategy then he is guaranteed to lose at most $V^{\prime \prime }$ no matter what Player I does

Theorem : $V^{\prime }\le V^{\prime \prime }$

Minimax Theorem : $V=V^{\prime }=V^{\prime \prime }$ is called the value of the game.

Finding safety strategies for 2-strategy games

Theorem : The two lines will meet within [0,1] iff No saddle point.

Solving $2\times n$ and $m\times 2$ games ( $m\times 2$ games ) :

1. Check for saddle point first. If there is a saddle point then we solve the game already.
2. Suppose there is no saddle point. Using the graphical method, we can find the safety strategy of Player II for $m\times 2$ games. Since the Minimax occurs at the intersection of two lines, Player I, knowing that Player II will play his/her safety strategy, will play the two Rows giving rise to the two lines. The situation then reduces to $2\times 2$ games.

Example : Reduction by removing dominated strategies.
A = ( 0 4 6 5 7 4 9 6 3 ) A=

A=⎝⎛​059​476​643​⎠⎞​
We can eliminate column 2 by a mixture of Column 1 & 3.
1 3 ( 0 5 9 ) + 2 3 ( 6 4 3 ) ≤ ( 4 7 6 ) \frac{1}{3}

⎛⎝⎜059⎞⎠⎟$$\left(\begin{array}{c}0\\ 5\\ 9\end{array}\right)$$

+\frac{2}{3}

⎛⎝⎜643⎞⎠⎟$$\left(\begin{array}{c}6\\ 4\\ 3\end{array}\right)$$

\leq

⎛⎝⎜476⎞⎠⎟$$\left(\begin{array}{c}4\\ 7\\ 6\end{array}\right)$$

31​⎝⎛​059​⎠⎞​+32​⎝⎛​643​⎠⎞​≤⎝⎛​476​⎠⎞​
Theorem : Maximin Principle $\iff$ Equilibrium Principle.

Lemma : Let p belong to $X^{\ast }$ and we let J p = { j : C o l u m n    j    i s    a    B R    t o    p } J_p=\{j: Column\; j\; is \;a\; BR\; to\; p\} Jp​={j:ColumnjisaBRtop}, the set of best response columns to p. Then, $q=(q_1,...q_n{)}^T$ is a BR to $p$ iff $q_j>0$ implies j belongs to $J_p$.

The Lemma says that a BR to p of Player I uses only the BR columns to p. Similarly, a BR to q of Player II uses only the BR rows to p.

Theorem (Principle of Indifference) : Let $p=(p_1,...p_m{)}^T$ lie in $X^{\ast }$ and $q=(q_1,...q_n{)}^T$ lie in $Y^{\ast }$ such that $<p,q>$ is an equilibrium pair. Let $p^{T}Aq=V$. Then, $a_{i1}{q}_1+...+a_{in}{q}_n=V$ for all i for which $p_i>0$ and $a_{1j}{p}_1+...+a_{mj}{p}_m=V$ for all j for which $q_j>0$

The Principle of Indifference gives the following recipe to find all the best response strategies to a given strategy :

1. Find all best response pure strategies
2. Use only those BR pure strategy to compose your mixed strategy

Equilibrium Principle is equivalent to Maximin Principle

Theorem : Let $<p_1,q_1>$, $<p_2,q_2>$ be equilibrium pairs. Then, $<p_1,q_2>$ is also an equilibrium pair.

Equalizing strategy : To define an equalizing strategy we only need to know that it equalizes on the opponent’s pure strategies.

Magic Square Games:A magic square game is an matrix game such that the row sums and the column sums of the payoff matrix are all equal. Then, $<\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}>$ is an equalizing strategy for Player I and, $<\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}>$ is an equalizing strategy for Player II.

Diagonal Games : A diagonal game is a game such that its payoff matrix is a diagonal matrix.

Solution for diagonal games :

1. $d_i$ are all positive or all negative. Then, $\frac{1}{\frac{1}{d_1}+...+\frac{1}{d_n}}(\frac{1}{d_1},...,\frac{1}{d_n})$ is an equalizing strategy for each player.
2. Otherwise, 0 is a saddle point.

Finding safety (Optimal) strategies when the value is given : ${\min }_q{p}^{T}Aq=V$ can be expressed as a system of n inequalities by noting that for a fixed p, the minimum of $p^{T}Aq$ is attained at a pure strategy $q$.

Theorem: Let $A=(a_{ij})$ be a matrix game with value V. The $p$ is a safety strategy for Player I iff The following n inequalities are satisfied.
$$\begin{gathered} {p}_1{a}_{11}+...+p_m{a}_{m1}\ge V \\ ... \\ {p}_1{a}_{1n}+...+p_m{a}_{mn}\ge V \end{gathered}$$

Symmetric Games : A game is symmetric if the rules do not distinguish between players. Both players have the same options, and the payoff when Player I uses i and Player II uses j is the negative of the payoff when Player I uses j and Player II uses i. Thus the payoff matrix can be arranged to be skew-symmetric, i.e. $A=-A^T$ .

Theorem : A finite symmetric game has value zero. Any strategy optimal (safety) for one player is also optimal for the other.

Theorem : Let the value of the game be V. Let P be the set of optimal strategies of Player I. Let Q be the set of optimal strategies of Player II. P, Q are compact convex polyhedra.

Let C be a convex set. A point x in C is called an extreme point if and only if one cannot find y, z in C distinct from x such that x=(y + z)/2. Note that the extreme points of a compact convex polyhedron are its vertices.

Essential submatrix : An essential submatrix of a matrix game is characterized by the following.

1. It is a square matrix;
2. Considered as a game in itself. It has a unique equalizing strategy for each player;
3. The equalizing strategy from (ii), extended by 0’s as necessary, are optimal in the original game.

The Primal Problem of a linear programming problem is in the following form.

Choose $x_1$,…,$x_m$ To minimize $c_1{x}_1+...+c_m{x}_m$

Subject to the constraints :
$$\begin{gathered} {a}_{11}{x}_1+...+a_{m1}{x}_m\ge b_1 \\ ... \\ {a}_{1n}{x}_1+...+a_{mn}{x}_m\ge b_n \end{gathered}$$

and $x_i\ge 0$ for $i=1,...,m$

The Dual Problem to the primal problem is to choose $y_1,...,y_n$ To maximize $b_1{y}_1+...+b_n{y}_n$

Subject to the constraints :
$$\begin{gathered} {a}_{11}{y}_1+...+a_{1n}{y}_n\le c_1 \\ ... \\ {a}_{m1}{y}_1+...+a_{mn}{y}_n\le c_m \end{gathered}$$
and $y_j\ge 0$ for $j=1,...,n$

Theorem : (Duality Theorem of LP) The optimal value of the Primal Problem and the optimal value of the Dual Problem are equal

The Duality Theorem implies the Minimax Theorem in game theory.

Solution to the Primal Problem in 2-Person Zero-Sum Game :

Choose $p_1$,…,$p_m$ To maximize $v$

Subject to the constraints :
$$\begin{gathered} {a}_{11}{p}_1+...+a_{m1}{p}_m\ge v \\ ... \\ {a}_{1n}{p}_1+...+a_{mn}{p}_m\ge v \\ {p}_1+...p_m=1 \end{gathered}$$
and $p_i\ge 0$ for $i=1,...,m$

Let $x_i=\frac{p_i}{v}$，then

Choose $x_1$ ,…,$x_m$ To minimize $x_1+...x_m$

Subject to the constraints :
$$\begin{gathered} {a}_{11}{x}_1+...+a_{m1}{x}_m\ge 1 \\ ... \\ {a}_{1n}{x}_1+...+a_{mn}{x}_m\ge 1 \end{gathered}$$
and $x_i\ge 0$ for $i=1,...,m$

Games in Extensive Form

In the extensive form, games are sequential, interactive processes which moves from one position to another in response to the wills of the players or the wills of chance.

Games in Extensive Form : Three new concepts make their appearance in the extensive form of a game: the game tree, chance moves, and information sets

The Game Tree : The extensive form of a game is modeled using a directed Graph that we have seen in combinatorial games. The vertices represent positions of the game. The followers, F(x), of a position, x, are those positions that can be reached from x in one move.

A path from a vertex $t_0$ to a vertex $t_1$ then represents the whole history of play in the game moving from position $t_0$ to $t_1$

The Kuhn tree of a game : When a tree is used to define a game, the vertices are interpreted as positions and the edges as moves. Each nonterminal position is assigned either to the player responsible to choosing the next move or to chance.

Chance Moves : Many games involve chance moves. It is assumed that the players are aware of the probabilities of the various outcomes resulting from a chance move. To incorporate chance moves in the Kuhn tree, we introduce a new player called Chance. The moves from Chance carry different probabilities. The probabilities assigned to the edges leading out of each chance vertex must be displayed.

Play starts at the initial vertex and continues along one of the paths eventually ending in one of the terminal vertices. Each directed path from the root to terminal vertex describes a possible course of play.

Information : Another important aspect we must consider in studying the extensive form of games is the amount of information available to the players about past moves of the game. When a player choosing a move is uninformed about some of the previous moves (concealed moves, simultaneous moves etc.), we draw little “balloons” around set of vertices which the player making the choice cannot discriminate. These are called information sets, and the player in question must make the same choice for all vertices in the set.(The player has the same information on the vertexes in the same balloon)

Edges issuing from vertices in the information set must be labeled the same. For example, {paper, scissor, rock}

In summary, the following are the basic elements of a Kuhn tree :

1. A finite set N, representing the players.
2. A finite rooted tree representing positions and moves. The root represents the start of the game and the terminal vertices the possible conclusions.
3. Terminal vertices represent the possible conclusions of the game. The payoff to each player is labeled at this vertex as a vector.
4. Vertices are labeled to name of the player and Chance. A move by them at these positions means choosing a particular edge leading out from this vertex.
5. Edges coming out from Chance should be labeled with the probability of this particular occurrence.
6. Information sets: The vertices of each player are partitioned into information sets. The player labelled cannot distinguished the vertices within this information set. Hence, there are same number of edges with the same label leading out from each vertex in the information set.

Games of Perfect Information : A game of perfect information is a game in extensive form in which each
information set of every player contains a single vertex.

Games of perfect recall : Games in which players remember all past information they once knew and all past moves they made are called games of perfect recall.

Games of complete information : Games in which both players know the rules of the game, that is, in which both players know the Kuhn tree, are called games of complete information.

Reduction of a Game in Extensive Form to Strategic Form

Pure strategy : A pure strategy is a player’s complete plan for playing the game. It should cover every
contingency. A pure strategy for a Player is a rule that tells him exactly what move to make in each of his information sets. It should specify a particular edge leading out from each information set

If the set of edges coming out from the information sets are { A , B } , { E , F } , { C , D } \{A,B\}, \{E,F\}, \{C,D\} {A,B},{E,F},{C,D} , Set of Pure Strategies : { A , B } × { C , D } × { E . F } = { A C E , A C F , A D E , A D F , B C E , B C F , B D E , B D F } \{A,B\}\times\{C,D\}\times\{E.F\}=\{ACE, ACF, ADE, ADF, BCE, BCF, BDE, BDF\} {A,B}×{C,D}×{E.F}={ACE,ACF,ADE,ADF,BCE,BCF,BDE,BDF}

Reduced pure strategy : Specification of choices at all information sets except those that are eliminated by the previous moves.

Random payoffs : The actual outcome of the game for given pure strategies of the players depends on the chance moves selected, and is therefore a random quantity. We represent random payoffs by their expected values.

Game in strategic form (normal form) :

• Set of players: { 1 , … , n } \{1,…,n\} {1,…,n}
• A set of pure strategies for player $i$, $X_{i}i=1,\dots ,n$
• Payoff function for the ith player. $u_i:X_1\times \dots \times X_n\to R$

Set of reduced strategies for I : { A E , A F , B C , B D } \{AE,AF, BC,BD\} {AE,AF,BC,BD}

Set of reduced strategies for II : { a c , a d , b c , b d } \{ac,ad, bc,bd\} {ac,ad,bc,bd}

Strategic Form :

Strategic Equilibrium : A vector of pure strategy choices $(x_1,x_2,...,x_n)$ with $x_i\in X_i$ for $i=1,...,n$ is said to be a pure strategic equilibrium, or PSE for short, if for all $i=1,2,...,n$, and for all $x\in X_i$
$$u_i(x_1,...,x_{i-1},x_i,x_{i+1},...,x_n)\ge u_i(x_1,...,x_{i-1},x,x_{i+1},...,x_n)$$
Equation says that if the players other than player $i$ use their indicated strategies, then the best player $i$ can do is to use $x_i$. Such a pure strategy choice of player $i$ is called a best response to the strategy choices of the other players.

Labeling Algorithm for Finding All PSE’s(2 Person)

• Put an asterisk after each of Player I’s payoffs that is a maximum of its column.
• Put an asterisk after each of Player II’s payoffs that is a maximum of its row.
• Then any entry of the matrix at which both I’s and II’s payoffs have asterisks is a PSE, and conversely.

Bad News : Many games have no PSE’s

Method of Backward Induction : Starting from any terminal vertex and trace back to the vertex leading to it. The player at this vertex will discard those edges with lower payoff. Then, treat this vertex as a terminal vertex and repeat the process. Then, we get a path from the root to a terminal vertex.

Theorem : The path obtained by the method of backward induction defines a PSE.

If a strategic Form comes from an extensive form with perfect information then there exists at least one PSE by the method of Backward Induction.

Theorem : The PSE obtained by the method of backward induction satisfies stronger properties so that it is called a perfect pure strategy equilibrium or PPSE.

Subgame : A subgame of a game presented in extensive form is obtained by taking a vertex in the Kuhn tree and all the edges and paths originated from this vertex.

Theorem : A PSE of a game in extensive form is called a Perfect Pure Strategy Equilibrium (PPSE) if it is a PSE for all subgames.

Subgame perfect implies that when making choices, a player look forward and assumes that the choice that will subsequently be made by himself and by others will be rational. Threats which would be irrational to carry through are ruled out. It is precisely this kind of forward looking rationality that is most suited to economic applications.

PSE allow players to make noncredible threats provided they never have to carry them out. Decisions on the equilibrium path are driven in part by what the players expect will happen off the equilibrium path.

Behavior Strategies : A behavior strategy is obtained if the Player makes a randomized choice independently at each of his/her information sets.

Example : Player I has 3 information sets. The set of edges coming out from the information sets are P = { A , B } , Q = { E , F } , R = { C , D } P=\{A,B\}, Q=\{E,F\}, R=\{C,D\} P={A,B},Q={E,F},R={C,D}

A behavior strategy $(p,q,r)$ means Probability $pqr$ for ACE, $p(1-q)r$ for ADE, $pq(1-r)$ for ACF, $p(1-q)(1-r)$ for ADF. This is a mixed strategy for Player I.

Each behavior strategy induces a probability distribution on the set of terminal vertices.

Each mixed strategy induces a probability distribution on the set of terminal vertices.

Dimension of behavior strategies : Suppose the Player has m information sets such that there are $k_i$ choices at the ith information set. Then, the dimension of behavior strategies for this player is $(k_1-1)+(k_2–1)+\dots +(k_m–1)$. Note that the space of mixed strategies is$(k_1{k}_2\dots k_m-1)$

Question: Can each mixed strategy represented by an “equivalent” behavior strategy?

From the consideration of dimension, the answer should be negative without additional assumptions.

Theorem (Harold Kuhn) : For a game of perfect recall, mixed strategies are equivalent to behavior strategies.

Two-Person General-Sum Games

General-Sum Strategic Form Games : The normal or strategic form of a two person game is given by two sets $X$ and $Y$ of pure strategies of the players, and two real-valued functions $u_1(x,y)$ and $u_2(x,y)$ defined on $X\times Y$, representing the payoffs to the two players. If Player I chooses $x\in X$ and Player II chooses $y\in Y$, then Player I receives $u_1(x,y)$ and Player II receives $u_2(x,y)$

The Maximin Principle does not apply to bimatrix games!

The theory is generally divided into two branches, the noncooperative theory and the cooperative theory.

1. In the noncooperative theory, either the players are unable to communicate before decisions are made, or if such communication is allowed, the players are forbidden or are otherwise unable to make a binding agreement on a joint choice of strategy. The main noncooperative solution concept is the strategic equilibrium (SE)
2. In the cooperative theory, it is assumed that the players are allowed to communicate before the decisions are made. They may make threats and counter-threats, proposals and counterproposals, and hopefully come to some compromise. They may jointly agree to use certain strategies, and it is assumed that such an agreement can be made binding. The cooperative theory itself breaks down into two branches, depending on whether or not the players have comparable units of utility and are allowed to make monetary side payments in units of utility as an incentive to induce certain strategy choices. The corresponding solution concept is called:
   1. TU cooperative value if side payments are allowed.
   2. NTU cooperative value if side payments are forbidden or otherwise unattainable

Safety Levels : In a bimatrix game with m×n matrices A and B, Player I can guarantee winning on the average at least $v_1={\max }_p{\min }_j(p_1{a}_{1j}+\dots +p_m{a}_{mj})=Val(A)$. This is called the safety level of Player I. A strategy, p, that achieves the maximum is caled a maxmin strategy for Player I.

Noncooperative Games Strategic Equilibrium : A vector of mixed strategy choices (also called a strategy profile) ($p_1,p_2,...,p_n)$ with $p_i\in X_i^{\ast }$ for $i=1,...,n$ is said to be a strategic equilibrium, or SE for short, if for all $i=1,2,...,n$, and for all $p\in X_i^{\ast }$, $u_i(p_1,...,p_{i-1},p_i,p_{i+1},...,p_n)\ge u_i(p_1,...,p_{i-1},p,p_{i+1},...,p_n)$ (*). Any mixed strategy $p_i$ that satisfies (*) for all $p\in X_i^{\ast }$ is a best response of player I to the mixed strategies of the other players.

Nash equilibria : Every finite n-person game in strategic form has at least one strategic equilibrium.

Theorem : $<p,q>$ is a SE whenever the following two conditions are valid.

1. $p_i>0$ implies Row is a BR to $q$.
2. $q_j>0$ implies Column j is a BR to $p$.

Labeling algorithm to check for SE’s : Let $[A,B]$ be a bimatrix game. Given a mixed strategy $p=(p_1,\dots p_m)$ for Player I, and $q=(q_1,\dots ,q_n)$ a mixed strategy for Player II, there is a simple labeling algorithm to determine whether $<p,q>$ is a SE.

1. Put the label BR to the best response rows to $q$
2. Put the label $+$ at the ith row where $p_i$ is positive
3. Put the label BR to the best response columns to $p$
4. Put the label $+$ at the jth column where $q_j$ is positive
5. $<p,q>$ is a SE whenever a $+$ label is accompanied by a BR label

Theorem : <p, q> is a SE if $p,q,\alpha ,\beta$ satisfy the following optimization problem.

$\max (p^T(A+B)q-\alpha -\beta )$ , ${\Pi }_n=(1,1,1,...,1{)}^T$ , Subject o the following constraints
$$\begin{gathered} Aq-\alpha {\Pi }_m\le 0 \\ {p}^T{\Pi }_m-1=0 \\ {p}^{T}B-\beta {\Pi }_n^T\le 0 \\ {q}^T{\Pi }_n-1=0 \\ 0\le q,0\le p \end{gathered}$$

Remark: The optimal value is 0.

Tetraskelion Method to find all SE’s for $2\times 2$ games :

1. For each mixed strategy $(p,1-p)$ of Player I, we use the method as in 0-zero sum games to find the best response columns.
2. Plot this in the unit square as a graph parameterized by $p$, $0\le p\le 1$.
3. For each mixed strategy $(q,1-q)$ of Player II, we use the method as in 0-zero sum games to find the best response rows.
4. Plot this in the unit square in the above as a graph parameterized by $q$, $0\le q\le 1$.
5. The SE’s are the intersections of the two graphs

Duopoly : There are two firms sending out fishing boats every day to catch fish to sell in the market the same day. The day’s catch of fish is brought into port by 9:00 am and must be sold the same day. Each day is taken to be entirely separate in the sense that the two firms concern themselves with the profit of only the current day and engage in no longer-term planning at all. When they set sail, each has already decided on the catch to bring back that day, and neither knows what the other has decided. Perhaps each has an educated guess, but neither has spies in the other’s camp or any source of factual knowledge of the other’s commitments. Each of them, however, does know both cost functions, as well as the market demand function which is a single market price because the catches of the two firms are identical. The decision variables of the firms are their output levels.

Cournot 1838 : Two firms produce the same product. Cost function for Firm 1: $C_1(q_1)=q_1$. Cost function for Firm 2: $C_2(q_2)=q_2$. $q_1,q_2$ are the quantities produced. Price function: $P(q)=25-q$, where $q$ is the total amount in the market

Duopoly: Firm 1 and Firm 2 will use quantity as strategy. Profit to Firm 1: $P_1(q_1)=(25-q)q_1-q_1$, Profit to Firm 2: $P_2(q_2)=(25-q)q_2-q_2$, where $q=q_1+q_2$. Firm 1 will find $q_1$ to maximize profit. Firm 2 will find $q_2$ to maximize profit.

Stackelberg Leader and Follower : Suppose Firm 1 moves first. Firm 1 announces the quantity $q_1$ (strategy) that it will produce. Knowing this, Firm 2 will choose its quantity $q_2$ to maximize profit (as BR). Then, $q_2=\frac{1}{2}(24-q_1)$ , Firm 1 knows this, its profit is $(25-q)q_1-q_1$ , where $q=q_1+\frac{1}{2}(24-q_1)$

Correlated Equilibrium

Crossing Game :

A traffic light might be installed. The traffic light is merely a randomization device which, with a certain probability, tells each of the two drivers whether to Cross or to Yield. This is not much different from a pair of mixed strategies. Except that now the two players’ probability distribution on strategies can be correlated. For example, the traffic light can be

Will the players comply or will they deviate from the traffic light’s instruction? If the traffic light is operated in a way that
both players see that it is in their best interest to comply then we have an EQUILIBRIUM! We will call this a Correlated
Equilibrium.

Suppose Player I knows that Player II will comply with the traffic light instructions. When Player I sees the signal to Cross, he will not deviate because he knows that (Cross, Cross) occurs with $prob=0$. When Player I sees the signal to Yield, he can compute the conditional probability of instructions to Player II given that his instruction is Yield. Then,
$$\begin{gathered} Prob(IItoCross|ItoYield)=\frac{Prob(IItoCross,ItoYield)}{Prob(ItoYield)}=\frac{0.4}{0.45} \\ Prob(IItoYield|ItoYield)=\frac{Prob(IItoYield,ItoYield)}{Prob(ItoYield)}=\frac{0.05}{0.45} \end{gathered}$$
Then, the expected payoff to Player I if he complies with the instruction to Yield is $0\frac{8}{9}+(-1)\frac{1}{9}=-\frac{1}{9}$. The expected payoff to Player I if he deviates from the instruction to Yield is $-10\frac{8}{9}+5\frac{1}{9}=-\frac{75}{9}$. This is far inferior to his payoff if he complies with the instruction. Same does Player II.

Therefore, it is for the best interest of both players to comply with the instruction of the traffic light.This probability distribution over the outcomes is then called a Correlated Equilibrium.

Correlated Equilibrium : In general, let $[A,B]$ be an $m\times n$ bimatrix game where $A=(a_{ij}),B=(b_{ij})$. A probability distribution of the outcomes of this game is given by $p_{ij},p_{ij}\ge 0$, ${\sum }_{i,j}{p}_{ij}=1$. This means that the instruction of playing
(Row i, Column j) to the players with probability $p_{ij}$. This probability distribution is called a Correlated Equilibrium (CE) if it is for the best interest for players to comply with the instruction.

$Prob(ColumnjforII|RowiforI)=\frac{Prob(ColumnjforII,RowiforI)}{Prob(RowiforI)}=\frac{p_{ij}}{{\sum }_k{p}_{ik}}$. For Player I to comply with the instruction to play Row i, the payoff must be better than deviating the instruction in playing Row r instead. This means
∑ j p i j ∑ k p i k a i j ≥ ∑ j p i j ∑ k p i k a r j      ∀ r ∈ { 1 , 2 , 3... m } \sum_j \frac{p_{ij}} {\sum_k p_{ik}}a_{ij} \geq \sum_ j \frac{p_{ij}} {\sum_kp_{ik}}a_{rj}\;\;\forall r \in\{1,2,3...m\} j∑​∑k​pik​pij​​aij​≥j∑​∑k​pik​pij​​arj​∀r∈{1,2,3...m}
Equivalently and similarly,
$$\begin{gathered} \sum _j{p}_{ij}(a_{ij}–a_{rj})\ge 0\forall i,r=1,...m \\ \sum _i{p}_{ij}(b_{ij}–b_{is})\ge 0\forall j,s=1,...n. \end{gathered}$$
For an $m\times n$ game, there are $m(m-1)+n(n-1)$ inequalities to characterize an CE.

Proposition: Any SE is a CE (correlated equilibrium).

Proposition: The convex combination of two CE’s is a CE.

The corresponding payoff of a CE may be outside the convex hull of the corresponding payoff points of SEs.

Proposition: Let [A, -A] be a 2-person 0-sum game with value V. For any CE of [A, -A], the payoff vector is (V, -V).

Computation of CE : Find $(p_{ij})$ such that
$$\begin{gathered} \sum _j{p}_{ij}(a_{ij}–a_{rj})\ge 0\forall i,r=1,...m \\ \sum _i{p}_{ij}(b_{ij}–b_{is})\ge 0\forall j,s=1,...n \\ {p}_{ij}\ge 0,\sum _{i,j}{p}_{ij}=1 \end{gathered}$$
We can represent the above inequalities as finding an optimal strategy, $(p_{ij})$, of the row chooser of a certain 2-person 0-sum game whose value is nonnegative. The payoff matrix A of this game is an $mn\times (m(m-1)+n(n-1))$ matrix.

For $2\times 2$ Game,

1. The rows of A is labeled by $ij,i=1,...m,j=1,...n$.
2. The columns of A is labeled by $(i,r),i\ne r,i,r=1,...,m$ and by $(j,s)j\ne s,j,s=1,...,n$.
3. The entry at row ij and column (i, r) is $(a_{ij}–a_{rj})$
4. The entry at row ij and column (j, s) is $(b_{ij}–b_{is})$
5. All the other entries are 0.

Application of Game Theory to Biology

Example : Hawk & Dove

• Hawk: keep fighting until you or your opponent is injured
• Dove: run away
• Winner gets a prize of V and injury means your fitness goes down by D.

We are then studying the symmetric bimatrix game $[A,A^T]$. From Game Theory, we will arrive at the concept of
finding a strategy p such that $<p,p>$ is a SE i.e. p is a BR to p.

Evolution Stable Strategy($p^{ESS}$) : A mutation occurs, producing a small numbers of players with mutant strategy $p^M$, $p^M\ne p^{ESS}$. The proportion of the population with this mutant strategy is $\epsilon$. Then for a player using $p^{ESS}$ the expected payoff is
$${\pi }^{ESS}=(1-\epsilon )\pi (p^{ESS},p^{ESS})+\epsilon \pi (p^{ESS},p^M)$$
A player using $p^M$ the payoff is
$${\pi }^M=(1-\epsilon )\pi (p^M,p^{ESS})+\epsilon \pi (p^M,p^M)$$
We want ${\pi }^M<{\pi }^{ESS}$ , This is guaranteed if for $p^M\ne p^{ESS}$

• $\pi (p^{ESS},p^{ESS})\ge \pi (p^M,p^{ESS})$
• $\pi (p^M,p^M)<\pi (p^{ESS},p^M)$

Theorem: Suppose the payoff matrix is $(A,A^T)$. Suppose for the jth column of $A$ is such that its diagonal element, $a_{jj}$, is the largest (strictly) of the column. Then playing the jth strategy is an ESS.

Necessary and sufficient condition for an ESS : Let $[A,A^T]$ be a given bimatrix game, where $A$ is an $n\times n$ matrix. Let $p=(p_1,\dots ,p_n)$ be a mixed strategy. Then $p$ is an ESS iff

1. $p_j>0$ implies jth strategy is a BR row to $p$
2. Let $B$ be the matrix $(b_{ij})$ such that $b_{ij}=a_{ij}$ if i, j are BR rows to $p$ and $b_{ij}=0$ otherwise. Then, $Z^{T}BZ<0$ where $Z^T=(z_1,\dots z_n)\ne 0$ satisfies
   1. $z^i=0$ if i is not a BR row to $p$ and
   2. $z_1+\dots +z_n=0$.

Let $A$ be the Paper-Scissor-Rock payoff matrix. Then $[A,A^T]$ does not have an ESS.

An evolutionary process has two basic elements: mutation and selection mechanism. The ESS concept highlights mutation. Replicator dynamics highlights the role of selection.

Replicator dynamics is formalized as a system of ODE that does not include any mutation mechanism. Instead robustness against mutation is indirectly taken care of by dynamic stability criteria

Replicator Dynamics : Let $p=(p_1,\dots p_n{)}^T$ be a mixed strategy for a symmetric bimatrix game $[A,A^T]$. $p_i$ denotes the proportion of population using the ith strategy. Payoff to strategy i against $p$ is ${\sum }_j{a}_{ij}{p}_j$. Payoff to strategy $p$ against $p$ is ${\sum }_i{\sum }_j{a}_{ij}{p}_i{p}_j$

We assume the growth rate of the population using strategy i is proportional to the advantage of that strategy over the whole population. For simplicity, we assume the constant is 1. Therefore, growth rate of the population playing strategy i is
$$\sum _j{a}_{ij}{p}_j-\sum _{k,j}{p}_k{a}_{kj}{p}_j$$
Replicator Dynamics Equations : $\frac{d{p}_i}{dt}=[{\sum }_j{a}_{ij}{p}_j-{\sum }_{k,j}{p}_k{a}_{kj}{p}_j]p_i$ , $i=1,\dots n$.

An equilibrium point of the set of Replicator Dynamics Equations is for a solution such that RHS= 0.

RHS=0 iff ${\sum }_j{a}_{ij}{p}_j={\sum }_{k,j}{p}_k{a}_{kj}{p}_j\forall p_i\ne 0$. iff $p$ is a BR to $p$.

Therefore, equilibrium point of Replicator Dynamics Equations iff is a SE.

Repeat Games

Repeat Game : Introduce a discount factor β. x at the nth game is worth β^n-1x.

Finite Automata :

1. Input: Some “history” of the game. Player I’s action at he nth stage.
2. Output: Player I’s action at the (n+1)th stage.
3. A finite automata can only remember a finite number of things.

1-memory automata : The player can only remember what happened in the previous move and make decision based on that. f : { C C , C D , D C , D D } → { C , D } f: \{CC, CD, DC, DD\}\rightarrow\{C, D\} f:{CC,CD,DC,DD}→{C,D} When both players are using a1-memory automata, we can use the technique of transition matrix in the study. Each row of the matrix is a probability vector giving the probability of transiting to one of the 4 possible states (CC, CD, DC, DD).

Let $v^T=(p_1,p_2,p_3,p_4)$ be a probability vector of the outcomes from the previous game. Then, the result for the next game will be $(v^{T}P{)}^T=P^{T}v$.

PR: Permanent Retaliation

Cooperate, until, if ever, the opponent defects, then defect for ever.

Tit-for-Tat : Cooperate first, then do what your opponent’s previous move.

<PR, PR> is a SE if β is large enough.

<TFT, TFT> is a SE when β is large enough (β>1/6 in this case).

A strategy is said to be Nice: Start cooperating and never the first to defect

Let S be a nice strategy and that <S, S> is a SE. Then β is sufficiently large.

Let S be a nice strategy and that <S, S> is a SE. Then S should be provoked (when the opponent plays D, S must retaliate by playing D at some later move) by the defection of the opponent.

Cooperative Games

In the cooperative theory, we allow communication of the players and also allow binding agreements to be made. This requires some outside mechanism to enforce the agreements.

The cooperative theory is divided into two classes of problems depending on whether or not her is a mechanism for transfer of utility from one player to the other. TU/NTU

Feasible Sets of Payoff Vectors. For any game its important to know the set of feasible payoffs vectors for the players. For a noncooperative game, this set is called the noncooperative feasible set.

When players cooperate in a bimatrix game with matrices [A,B], they may agree to achieve a payoff vector of any of the m*n points, ($a_{ij},b_{ij}$) for i= 1, . ., m and j= 1. . ,n. They may also agree to any probability mixture of these points.

The NTU feasible set is the convex hull of the m*n points, ($a_{ij},b_{ij}$) for i=1, . ., m and j =1. . ,n.

The distinguishing feature of the TU case is that he players may make side payments of utility as part of the agreement.

Thus the whole line of slope −1 through the point (aij, bij) is part of the TU feasible set.

A feasible payoff vector, ($v_1,v_2$), is said to be Pareto optimal if or any feasible payoff vector ($v_1’,v_2’$) such that $v_1’\ge v_1$ and $v_2’\ge v_2$ implies ($v_1’,v_2’$) =($v_1,v_2$).

The TU-Problems

The TU Solution: If the players come to an agreement, then rationality implies that they will agree to play to achieve the largest possible total payoff, call it $\sigma$, σ = max ⁡ { ( a i j + b i j ) : i , j } σ =\max \{(a_{ij} + b_{ij}): i,j \} σ=max{(aij​+bij​):i,j} as the payoff to be divided between them.

Suppose now that he players have selected their threat strategies, say p for Player I and q for Player II. This point is in the NTU feasible set and is called the disagreement point or threat point.

Player I will accept no less than $D_1$ and Player II will accept no less than $D_2$ since these can be achieved if no agreement is reached.

They will split evenly the excess of $\sigma$ over $D_1+D_2$

The resolution point is then $\varphi =({\varphi }_1,{\varphi }_2)=(\frac{1}{2}(\sigma +D_1–D_2),\frac{1}{2}(\sigma -D_1+D_2))$ To select the threat optimally, Player I wants to maximize $D_1-D_2$ and Player I wants to minimize it.

Let $\delta =Val(A-B)={p^{\ast }}^T(A-B)q^{\ast }$, $\varphi =(\frac{1}{2}(\sigma +\delta ),\frac{1}{2}(\sigma -\delta ))$

All such disagreement points must be on the same 45 degrees line.

Nash Bargaing Model. A bargaing problem is given by $(S,u^{\ast },v^{\ast })$ such that

1. S is a compact (i.e. bounded and closed), convex set, in the plane.
   It is somewhat more general in that it does not have to be a polyhedral set. It could be a circle or an ellipse, for example.
2. $(u^{\ast },v^{\ast })\in S$, is called the threat point, disagreement point or status-quo point.
   The bargaining players have to decide on a point in S. The status-quo point, $(u^{\ast },v^{\ast })$, is the settlement when negotiation breaks down.

Given an NTU-feasible set, S, and a threat point or status-quo point, $(u^{\ast },v^{\ast })\in S$, the problem is to find a point, $(u^{\#},v^{\#})=f(S,u^{\ast },v^{\ast })$ , to be considered a “fair and reasonable outcome” or “solution” of the game for an arbitrary compact convex set S and point $(u^{\ast },v^{\ast })\in S$.

Nash Axioms for $f(S,u^{\ast },v^{\ast })=(u^{\#},v^{\#})$.

1. Feasibility. $(u^{\#},v^{\#})\in S$.
2. Pareto Optimality. $(u^{\#},v^{\#})$ is Pareto optimal in S.
3. Symmetry. If S is symmetric about the 45 degrees line $u=v$,and if $u^{\ast }=v^{\ast }$, then $u^{\#}=v^{\#}$
4. Independence of irrelevant alternatives. If T is a closed convex, subset of S, and if the threat point $(u^{\ast },v^{\ast })\in T$ and $f(S,u^{\ast },v^{\ast })=(u^{\#},v^{\#})\in T$, then $f(T,u^{\ast },v^{\ast })=(u^{\#},v^{\#})$.
5. Invariance under change of location and scale. If T = { ( u _ , v _ ) : u _ = α 1 u + β 1 , v _ = α 2 v + β 2      f o r ( u , v ) ∈ S } T =\{(u\_,v\_):u\_=α_1u +β_1, v\_= α_2v +β_2\;\;for (u, v)\in S\} T={(u_,v_):u_=α1​u+β1​,v_=α2​v+β2​for(u,v)∈S} where ${\alpha }_1>0,{\alpha }_2>0$, ${\beta }_1$ and ${\beta }_2$ are given numbers, then $f(T,{\alpha }_1{u}^{\ast }+{\beta }_1,{\alpha }_2{v}^{\ast }+{\beta }_2)=({\alpha }_1{u}^{\#}+{\beta }_1,{\alpha }_2{v}^{\#}+{\beta }_2)$.

Theorem. There exist a unique function f satisfying the Nash axioms. Moreover, if there exists a point $(u,v)\in S$ such that $u>u^{\ast }$ and $v>v^{\ast }$ , then $f(S,u^{\ast },v^{\ast })$ is that point of S that maximizes $(u-u^{\ast })(v-v^{\ast })$ among points of S such that $u\ge u^{\ast }$ and $v\ge v^{\ast }$. It’s called Nash product.

Kali-Smorodinsky solution: For any bargaining problem $(S,(d_1,d_2))$, define I 1 = max ⁡ { u : f o r    s o m e    v , ( u , v ) ∈ S , d 1 ≤ u , d 2 ≤ v } I_1 = \max \{u: for \;some \;v, (u,v)\in S, d_1\leq u, d_2\leq v \} I1​=max{u:forsomev,(u,v)∈S,d1​≤u,d2​≤v}, I 2 = max ⁡ { v : f o r    s o m e    u , ( u , v ) ∈ S , d 1 ≤ u , d 2 ≤ v } I_2 = \max \{v: for\; some\; u,(u, v)\in S, d_1 \leq u, d_2 \leq v \} I2​=max{v:forsomeu,(u,v)∈S,d1​≤u,d2​≤v} The Kali-Smorodinsky solution $(u_1,u_2)$ is on the Pareto optimal boundary such that $(u_1–d_1)/(I_1–u_1)=(u_2–d_2)/(I_2–u_2)$

Zeuthen’s Principle

Suppose that, at a given stage of the bargaining process, Player I’s last offer corresponded to the payoff vector $v=(v_1,v_2)$ whereas Player II’s last offer corresponded to the payoff vector $w=(w_1 , w_2) $ such that v and w belong to the Pareto Optimal boundary of the cooperative feasible set, with $v_1>w_1$ but $v_2<w_2$. Which player will have to make the next concession?

If Player I accepts his opponent’s last offer w, then he will get payoff $w_1$. On the other hand, if he insists on his own last offer v, then he will obtain either payoff $v_1$ or will obtain the disagreement point payoff $d_1$ i.e Player II sticks to his last offer.

Suppose Player I assigns probability p to the later possibility and assigns probability (1-p) to the former possibility. Then, he must conclude that by insisting on his last offer v and by making no further concession he will get the expected payoff $(1-p)v_1+p{d}_1$, whereas by being conciliatory and accepting Player II’s last offer w he will get $w_1$ Therefore, Player I can rationally stick to his last offer only if $(1-p)v_1+p{d}_1\ge w_1$ i.e. if $p\le (v_1-w_1)/(v_1-d_1)=r_1$

We will call $r_1$, $r_2$ the two players’ risk limits expressed as ratio of difference in payoffs.

Zeuthen suggests that the next concession must always come from the player with a smaller risk limit

Theorem: If the two players follow Zeuthen’s Principle then the next concession will always made by the player whose last offer is associated with a smaller Nash product (unless both are associated with equal Nash product, in which case both of them have to make concessions).

Games in Coalitional Form

A coalition, S, is defined to be a subset of N, $S\subset N$, and the set of al coalitions is denoted by 2^N. We also speak of the empty set, Ø, as a coalition, the empty coalition. The set N is also a coalition, called the grand
coalition.

The coalitional form of a n-person game is given by the pair (N, v), where v is a real-valued function, called the characteristic function of the game, defined on the set, 2^N, of all coalitions (subsets of N), and satisfying

1. v(Ø) =0
2. (superadditivity) if S and T are disjoint coalitions (S ∩ T= Ø), then v(S) +v(T) ≤v(S ∪ T).

We define v(S) for each S∈ 2^N as the value of the 2-person zero-sum game obtained when the coalition S acts as one player and the complementary coalition, S^C = N −S, acts as the other player, and where the payoff to S is ${\sum }_{i\in S}{u}_i(x_1...x_n)$ the total of the payoffs to the players in S

The value, v(S), is the analogue of the safety level. It represents the total amount that coalition S can guarantee for itself.v is a characteristic function.

A game in coalitional form is said to be constant sum, if v(S)+v(S^C) =v(N) for all coalitions S∈ 2^N. It is said to be zero-sum if, in addition, v(N) =0.

A payoff vector, $x=(x_1,x_2,..,x_n)$, is said to be group rational or efficient if $x_1+\dots +x_n=v(N)$.

A payoff vector, x, is said to be individually rational if x i ≥ v ( { i } ) x_i ≥ v(\{i\}) xi​≥v({i})

An imputation is a payoff vector that is group rational and individually rational.

A game in coalitional form is said to be inessential if ∑ i v ( { i } ) = v ( N ) \sum_iv(\{i\})=v(N) ∑i​v({i})=v(N), and essential if ∑ i v ( { i } ) ≠ v ( N ) \sum_iv(\{i\})\not=v(N) ∑i​v({i})​=v(N).

An imputation x is said to be unstable through a coalition S if $v(S)>{\sum }_{i\in S}{x}_i$

The set, C, of stable imputations is called the core, C = { x = ( x 1 , . . , x n ) : ∑ i ∈ N x i = v ( N ) a n d ∑ i ∈ S x i ≥ v ( S ) , f o r a l l S ⊂ N } C =\{x = (x_1, . ., x_n) :\sum_{i∈N} x_i = v(N) and \sum _{i∈S}x_i \geq v(S), for all S\subset N\} C={x=(x1​,..,xn​):∑i∈N​xi​=v(N)and∑i∈S​xi​≥v(S),forallS⊂N}.

The core of an essential n-person constant-sum game is empty.

Shapley Value

The Shapley Value is to assign to each game in coalitional form a unique vector of payoffs, called the value. The ith entry of the value vector may be considered as a measure of the value or power of the ith player in the game.

${\phi }_i(v)$ represents the worth or value of player in the game with characteristic function v. The axioms of fairness are placed on the function, $\phi$.

The Shapley Axioms for φ(v):

1. Efficiency. ${\sum }_i{\phi }_i(v)=v(N)$.
2. Symmetry. If i and j are such that v ( S ∪ { i } ) = v ( S ∪ { j } ) v(S∪\{i\}) =v(S∪\{j\}) v(S∪{i})=v(S∪{j}) for every coalition S not containing i and j, then ${\phi }_i(v)={\phi }_j(v)$.
3. Dummy Axiom. If i is such that v ( S ) = v ( S ∪ { i } ) v(S) =v(S ∪\{i\}) v(S)=v(S∪{i}) for every coalition S not containing i, then ${\phi }_i(v)=0$.
4. Additivity. If u and v are characteristic functions, then $\phi (u+v)=\phi (u)+\phi (v)$.

Example: Let $S\subset N$ Define a characteristic function $w_S$ such that $w_S(T)=1$if $S\subset T$ $w_S(T)=0$ otherwise. Find $\phi (w_S)$

Solution : ${\phi }_i(w_S)=0$ for $i\notin S$, ${\phi }_i(w_S)=\frac{1}{|S|}$ for $i\in S$

Theorem : There exist a unique function φ satisfying the Shapley axioms.

Claim : Any v may be written as $v={\sum }_{S\subseteq N}{c}_S{w}_S$

$c_T=v(T)-S⊊T{c}_S$

The Shapley value is just he average payoff to the players if the players are entered in completely random order.

Theorem: The following value satisfies the Shapley axioms.$\phi =({\phi }_1,..,{\phi }_n)$, where for $i=1,..,n$, φ i ( v ) = ∑ S ⊆ N , i ∈ S [ ( ∣ S ∣ − 1 ) ! ( n − ∣ S ∣ ) ! ] [ v ( S ) − v ( S − { i } ) ] / n ! φ_i(v) =\sum_{S⊆N,i∈S}[(|S|−1)!(n−|S|)!] [v(S)−v(S −\{i\})]/ n! φi​(v)=∑S⊆N,i∈S​[(∣S∣−1)!(n−∣S∣)!][v(S)−v(S−{i})]/n! .

The Shapley value doesn’t necessarily lie in the core if the core is not empty.

Definition. A game $(N,v)$ is simple if for every coalition $S\subset N$ , either $v(S)=0$ or $v(S)=1$.

φ i ( v ) = ∑ S    w i n n i n g , S − { i }    l o s i n g ( ∣ S ∣ − 1 ) ! ( n − ∣ S ∣ ) ! / n ! φ_i(v) =\sum_{S\; winning ,S−\{i\}\; losing} (|S| −1)!(n −|S|)!/n! φi​(v)=∑Swinning,S−{i}losing​(∣S∣−1)!(n−∣S∣)!/n!

The Shapley value individually rational, i.e is φ i ( v ) ≥ v ( { i } ) φ_i(v)≥v(\{i\}) φi​(v)≥v({i})

Strong Monotonicity Axiom: A value function $\phi$ is said to be strongly monotonic if for any two set functions v, w such that whenever v ( S ∪ { i } ) – v ( S ) ≥ w ( S ∪ { i } ) – w ( S ) v(S\cup \{i\}) – v(S) \geq w(S\cup \{i\}) –w(S) v(S∪{i})–v(S)≥w(S∪{i})–w(S) for any S not containing i, we must have ${\phi }_i(v)\ge {\phi }_i(w)$

Theorem: (P. Young): Shapley value is the unique set function satisfying the Efficiency Axiom, Symmetry Axiom, Dummy Axiom and Strong Monotonicity Axiom.

The Nucleolus

Given characteristic function, v, and try to find an imputation $x=(x_1,..,x_n)$ that minimizes the worst inequity. That is, we ask each coalition S how dissatisfied its with the proposed imputation x and we try to minimize the maximum dissatisfaction.

Definition of Excess: As a measure of the inequity of an imputation x for a coalition S is defined as the excess, $e(x,S)=v(S)-{\sum }_{j\in S}{x}_j$

When the largest excess has been made as small as possible, we concentrate on the next largest excess, and adjust x to make it as small as possible, and so on. When we cannot improve further, the imputation we get is called the nucleolus.

The Bankruptcy Game : (O’Niel (1982)) A small company goes bankrupt owing money to three creditors. The
company owes creditor A $10000 ,creditor B$20000 ,and creditor C$30000. If the company has only $36000 to cover these debts, how should the money be divided among the creditors?

A pro rata split of the money would lead to the allocation of $6000 for A, $12000 for B, and $18000 for C, denoted by x = (6, 12, 18) in thousands of dollars.

The first step of finding the nucleolus is to find a vector $x=(x_1,..,x_n)$ that minimizes the maximum of the excesses $e(x,S)$ over all S subject to $\sum x_j=v(N)$. This problem of minimizing the maximum of a collection of linear functions subject to a linear constraint is easily converted to a linear programing problem and can thus be solved by the simplex method, for example. After this done, one may have to solve a second linear programing problem to minimize the next largest excess, and so on.

Theorem : The nucleolus of a game in coalitional form exist and is unique. The nucleolus is group rational, individually rational, and satisfies the symmetry axiom and the dummy axiom. If the core is not empty, the nucleolus in the core.

The Marriage Game

Definition: A matching W is said to be stable if no boy and girl not matched in W prefer each other to their W-mates.

Deferred Acceptance Algorithm

Definition: Call a boy (girl) feasible for a girl (boy) if there exists a stable matching in which they are matched.

Theorem: In a girl-propose algorithm, no girl is ever rejected by a boy feasible for her. Similarly, in a boy-propose algorithm, no boy is ever rejected by a girl feasible for him.

Corollary: In the girl-propose algorithm, the girls are matched to optimal feasible boys. Therefore, girl-propose algorithm is girl-optimal.

The College Admission Game

One-sided Matching

David Gale’s Top Trading Cycle algorithm