We are given a collection of piles of chips. Two players play alternately. On a player’s turn, they remove at least one chip from a pile. The first player who cannot move loses the game.
Example.
1, 1, 2. First player takes both chips from the 2-pile, forces a win.
6, 9. First player takes 3 from the 9-pile, mimic the moves of the second player to force a win.
If there is a move which forces a win, then the game is a winning position. From a losing position, any move leads to a winning position for the other player.
Lemma: If we have exactly 2 piles, with n, m chips, then player I wins if and only if n \neq m.
Example. G = (1, 1, 2) game in Nim. Four possible moves.
G = (1, 1, 2) \rightarrow \begin{cases}&H_1 = (1, 1, 1) \\ &H_2 = (1, 1, 0) \\ &H_3 = (0, 1, 2) \\\ &H_4 = (1, 0, 2)\end{cases}
Impartial games can be recursively defined by its position and options.
Definition: A game H that is reachable from G by a sequence of moves is simpler than G.
Lemma: In any game G, it is a winning position for player I or player II.
We proceed by induction on the simplicity of G. If G has no allowed moves, then it is a winning position for the player not in their turn. Assume G has allowed moves, assume claim is true for games simpler than G. Assume player I is the current player. Consider all options of G. If one of them is a winning position for player I, then player I moves to that option, wins that game, then also wins G. Otherwise, all options are winning positions for player II. So any move player I makes will make player II win. So G is a winning position for player II.
Definition: Let G, H be two games with options G_1, ..., G_m, and H_1, ..., H_n respectively. We define G + H as the game with options G_1 + H, ..., G_m + H, G + H_1, ..., G + H_n.
Example: We denote \star n to be a game of Nim with one pile of n chips. Then \star 1 + \star 1 + \star 2 is the game of three piles with (1, 1, 2) chips.
Let \bf G be the set of all impartial games.
Aside: These are properties of an abelian group except for the inverse property.
Definition: Two games G, H are equivalent is if for any game J, G + J is a losing game if and only if H + J is a losing game. Adding the same game does not alter the outcome.
Notation: G \equiv H.
Example: \star 3 \equiv \star 3. \star 3 \not\equiv \star 4 since \star 3 + \star 3 is a losing game and \star 4 + \star 3 is a winning game. So \star n \equiv \star m if and only if n = m.
\equiv is an equivalence relation.
Quick exercise to verify.
Exercise: If G \equiv H then G + J \equiv H + J for any J.
Lemma: G is a losing game if and only if G \equiv \star 0.
Note: Start of proving that every impartial game is equivalent to a some Nim game.
(\Leftarrow) If G \equiv \star 0, then G + \star 0 is a losing game if and only if \star 0 + \star 0 is a losing game. We know \star 0 + \star 0 is a losing game.
(\Rightarrow) Suppose that G is a losing game. We want to show G + J is a losing game if and only if \star 0 + J = J is a losing game.
(\leftarrow) Suppose J is a losing game. Use induction on the simplicity of G + J. Base case \equiv if left as an exercise. Consider G + J. Player I can move in G or in J.
- Suppose player I moves from G + J to G + J^\prime. Since J is a losing game, J^\prime is a winning game. So player II has a winning move from J^\prime to J^{\prime\prime} such that J^{\prime\prime} is a losing game. By induction, G + J^{\prime\prime} is a losing game. So player I loses.
- Similar if we go from G + J to G^\prime + J. Player II moves to G^{\prime\prime} + J which is by induction a losing game. So player I loses.
So in both cases, G + J is a losing game.
(\rightarrow) Suppose G + J is a losing game. Suppose by way of contradiction J is a winning game. Then PI has a winning move J \to J^\prime. So J^\prime is a losing game. Then by induction, G + J^\prime is a losing game. Then G + J is a winning game, contradiction.
Corollary: If G is a losing game, then J has the same outcome as J + G.
Since G is a losing game, G \equiv \star 0. Add J to both sides. G + J \equiv \star 0 + J = J.
Example:
Lemma (Copycat Principle): For any game G, G + G \equiv \star 0.
This is true when G has no options. Consider G + G and without loss of generality player I moves to G^\prime + G. Then player II can move to G^\prime + G^\prime. By induction G^\prime + G^\prime \equiv \star 0, so it is a losing game for player I. So G + G is a losing game, so G + G \equiv \star 0.
Aside: If we treat our games as equivalence classes, then the inverse of a game is itself. Adding G + G gives the identity \star 0.
Lemma: G \equiv H if and only if G + H \equiv \star 0.
(\Rightarrow) If G \equiv H then G + G = \star 0 \equiv H + G.
(\Leftarrow) If G + H \equiv \star 0 then G + G + H \equiv H \equiv \star 0 + G \equiv G
Example: \star 1 + \star 2 + \star 3 \equiv \star 0. By Lemma, \star 1 + \star 2 \equiv \star 3.
Lemma: If the options of G are equivalent to the options of H, then G \equiv H. (More precisely: there is a bijection between the options of G and H, where the paired options are equivalent).
Example: We can show \star 1 + \star 2 \equiv \star 3 using this lemma.
\star 1 + \star 2 \rightarrow \begin{cases}&\star 2 \\ &\star 1 \\ &\star 1 + \star 1 \equiv \star 0 \end{cases} \star 3 \rightarrow \begin{cases}&\star 2 \\ &\star 1 \\ &\star 0 \end{cases}
Converse is not true.
It suffices to show G + H \equiv \star 0, or G + H is a losing game. If G, H have no options, then G + H \equiv \star 0. Now WLOG, suppose player I moves to G^\prime + H. By assumption, G^\prime \equiv H^\prime for some option H^\prime of H. So player II moves to G^\prime + H^\prime. By Lemma, G^\prime + H^\prime \equiv \star 0, so it is a losing game for player I.
Definition: If \star m + \star n \equiv \star k, then k is the Nim sum of m, n.
Unproven Theorem: Suppose n = 2^{a_1} + 2^{a_2} + ..., where a_1 > a_2 > .... Then \star n \equiv \star 2^{a_1} + \star 2^{a_2} + ....
Proven below.
Examples.
This is an xor operation.
When is \star b_1 + \star b_2 + ... + \star b_k \equiv \star 0? When each power of 2^a appears in even number of terms.
Given \star b_1 + \star b_2 + ... + \star b_k \equiv \star c, where c > 0, what is a winning move? We want to make a move so the resulting game is equivalent to \star 0. We add \star c to both sides. We only affect one stack, so we can replace a stack b_i with \star b_i + \star c. This is only valid if the Nim sum of b_i and c is strictly smaller than b_i. This will happen to at least one of b_1, ..., b_k.
Example: \star 11 + \star 13 \equiv \star 6. Add \star 6 to \star 11 or \star 13.
\star 13 + \star 6 \equiv \star 11, so the winning move is removing 2 from \star 13.
Lemma: If \star b_1 + ... + \star b_k \equiv \star s, where s \ge 0, then there exists i where the Nim sum of b_i and s is strictly less than b_i.
Suppose s = 2^{a_1} + 2^{a_2} + ... where a_1 > a_2 > .... An odd number of b_i’s contain 2^a_i, let a specific b_i be one of them. Let \star t \equiv \star b_i + \star s. Since 2^{a_1} is in both b_i and t, they cancel and do not appear in t. At worst, 2^{a_2}, 2^{a_3}, ... appear in t. So t \le b_i - 2^{a_i} + 2^{a_2} + 2^{a_3} + ... < b_i.
Theorem: Suppose n = 2^{a_1} + 2^{a_2} + ..., where a_1 > a_2 > .... Then \star n \equiv \star 2^{a_1} + \star 2^{a_2} + ....
This theorem uses the following lemma. Lemma: Let 0 \le p, q < 2^a. Suppose our theorem holds for all values less than 2^a. Then Nim sum of p and q is also strictly less than 2^a.
Theorem proof illustration: We will use induction. Consider \star 7. 7 = 4 + 2 + 1, want to prove \star 7 \equiv \star 4 + (\star 2 + \star 1). We have \star 7 \equiv \star 4 + \star 3 by induction, so we need to show \star 7 \equiv \star 4 + \star 3. We can show that the two sides have equivalent options.
By induction on n. When n = 1, n = 2^0, and \star 1 \equiv \star 2^0. Suppose n = 2^{a_1} + 2^{a_2} + ..., where a_1 > a_2 > .... Let q = n - 2^{a_1}. When q = 0, \star n \equiv \star 2^{a_1}. Assume q \ge 1. By induction, \star q \equiv \star 2^{a_2} + \star 2^{a_3} + .... It remains to show that \star n \equiv \star 2^{a_1} + \star q. We do this by showing the options are equivalent. The options of \star n are \star (n-1), ..., \star 0. There are two types of options for \star 2^{a_1} + \star q.
- \star i + \star q, 0 \le i < 2^{a_i}. Suppose \star i + \star q \equiv \star r_i for some r_i. Since i < 2^{a_i} and q < 2^{a_i}, by induction and lemma, r_i < 2^{a_i}. If \star r_i \equiv \star r_j, then \star i + \star q \equiv \star j + \star q, so \star i \equiv \star j, so i = j. So r_0, ..., r_{a_1 - 1} are all distinct and less than 2^{a_1}. By pigeonhole-ish, \{r_0, ..., r_{2^{a_1 - 1}}\} = \{\star 0, ..., \star 2^{a_1 - 1}\}.
- \star 2^{a_1} + \star i, where 0 \le i < q. Let i = 2^{b_1} + 2^{b_2} + ..., then none of the b_i’s is equal to a_1. Then 2^{a_1} + 2^{b_1} + ... is a sum of distinct powers of 2. Using induction, \star 2^{a_i} + \star i \equiv \star 2^{a_1} + \star 2^{b_1} + \star 2^{b_2} + ... \equiv \star(2^{a_1} + i). The options of this type are equivalent to \{\star 2^{a_1}, \star (2^{a_1} + 1), ..., \star(2^{a_1} + q - 1)\}. Since the two sides have equivalent options, \star n \equiv \star 2^{a_1} + \star q.
We want to show that all impartial games are equivalent to Nim games with 1 pile.
Example: \star 11 + \star 13 \equiv \star 6.
Suppose we go to \star 11 + \star 4 \equiv \star 15. Similar to adding 9 chips to \star 6. What is the effect of allowing stacks to increase?
Consider the game of poker Nim. It consists of a regular Nim game plus a bag of B chips. We not allow regular Nim moves and adding B^\prime \le B chips to one pile. If we face a losing game in Nim, we could add chips instead. But the other player can just take the same chips away, and nothing changed. So poker Nim is essentially the same as Nim.
Suppose a game G with options \star 0, \star 1, \star 2, \star 5, \star 10, \star 24. We claim that this is equivalent to \star 3. The options of \star 0, \star 1, \star 2 are present. If we add chips to \star 3, then the second player can remove them back to \star 3. We get 3 as the smallest non-negative integer not in \{\star 0, \star 1, \star 2, \star 5, \star 10, \star 24\}. We define mex(S) to be the smallest non-negative integer not in S (minimum excluded integer).
Theorem: Let G be an impartial game whose options are equivalent to \{\star s: s \in S\}. Then G \equiv \star mex(S).
Let m = mex(S). It suffices to show that G + \star m \equiv \star 0.
Suppose we move to G + \star m^\prime where m^\prime < m. Since m = mex(S), m^\prime \in S. So there exists an option G^\prime of G equivalent to \star m^\prime. Player II moves to G^\prime + \star m^\prime and this is a losing game. So G + \star m is a losing game for player I.
Suppose we move to G^\prime + \star m. Then G^\prime \equiv \star k for some k \in S. Then G^\prime + \star m \equiv \star k + \star m \not\equiv \star 0 since k \neq mex(S). So G^\prime + \star m is a winning game for player II. So G + \star m is a losing game for player I.
If m = 0, then all options of G are winning games. So G \equiv \star 0, and G + \star m \equiv \star 0 + \star 0 \equiv \star 0.
Corollary: Any impartial game G is equivalent to some Nim game \star n.
If G has no options then G \equiv \star 0. Suppose G has options G_1, G_2, ..., G_q. By induction, G_i \equiv \star n_i for some n_i, for each i. By theorem, G \equiv \star mex(\{n_1, ..., n_q\}).
Example:
\star 1 + \star 1 + \star 2 \to \begin{cases}\star 1 + \star 2 \equiv \star 3 \\ \star 1 + \star 1 \equiv \star 0 \\ \star 1 + \star 1 + \star 1 \equiv \star 1\end{cases} By theorem, \star 1 + \star 1 + \star 2 \equiv \star mex(\{0, 1, 3\}) \equiv \star 2.
Exercise: A game cannot be equivalent to one of its options.
Example: In the rook game, we have an m \times n chess board, and a rook at position (i, j). A move consists of moving the rook any positive number of spaces to the left or up. The player with no move loses.
\begin{bmatrix} \star 0 & \star 1 & \star 2 & \star 3 \\ \star 1 & \star 0 & \star 1 & \star 2 \\ \star 2 & \star 1 & \star 0 & \star 1 \\ \star 3 & \star 2 & \star 1 & \star 0 \\ \end{bmatrix}
The Nim value of (i, j) is mex(\{(i^\prime, j): 0 \le i^\prime < i - 1\} \cup \{(i, j^\prime): 0 \le j^\prime < j - 1\}).
Example: In the subtraction game, we have one pile of n chips. A move is taking away 1, 2, or 3 chips. Let S_n be the Nim values of the game with n chips. Then S_n = mex(\{S_{n-1}, S_{n-2}, S_{n-3}\}).
n S_n 0 0 1 1 2 2 3 3 4 0 5 1 6 2 7 3
Suppose we change valid moves to removing 2, 5, or 6 chips.
n S_n 0 0 1 0 2 1 3 1 4 0 5 2 6 1 7 3 8 0 9 2 10 1 11 0 12 0 13 1 14 1
Losing game if and only if n = 0, 1, 2, 4, 8 \pmod {11}.
Example: Rook game at (4, 2) + second subtraction game n = 7.
Equivalent to \star 2 + \star 3 \equiv \star 1. So it is a winning game. Winning moves are removing 2 from the subtraction game, and moving left with the rook.
Definition: Given by specifying a set N = \{1, ..., n\} of players, and for each player i, there is a set S_i of strategies and a utility function u_i: S_1 \times ... \times S_n \to \mathbb{R}.
Example: Two players I, II. Rows are PI strategies, columns are PII strategies. Cells are the utility of PI, PII.
\begin{bmatrix} 5K, 5K & 0, 10K \\ 10K, 0 & 1, 1 \end{bmatrix}
Theorem: In second-price bid auction, v_i is a dominant strategy for all i.
Consider strategy profile b \in S. We first show that u_i(v_i, b_{-i}) \ge u_i(b) for all b_i \in S.
- Suppose v_i is the winning bid in (v_i, b_{-i}). Let b_j be the second highest bid in b. u_i(v_i, b_{-i}) = v_i - b_i \ge 0. Let us switch our bid to b_i. Suppose b_i < b_j, so b_i is still winning, so u_i(b_i, b_{-i}) = u_i(v_i, b_{-i}). Suppose b_i < b_j, so b_i is a losing bid, u_i(b_i, b_{-i}) \le 0.
- Suppose v_i is a losing bid. Suppose b_i < b_j, then b_i is a losing bid, u_i(b_i, b_{-i}) = 0. Suppose b_i > b_j, then b_i is a winning bid, u_i(b_i, b_{-i}) = v_i - b_j \le 0.
It remains to show that for every i, there exists b_i \in S_i \setminus \{v_i\} such that u_i(v_i, b_{-i}) > v_i(b_i, b_{-i}).
- Suppose b_i < v_i. Let k \in (b_i, v_i). Set b_j = k for i \neq j. Then u_i(v_i, b_{-i}) > 0, but u_i(b_i, b_{-i}) = 0.
- Suppose b_i > v_i. Let k \in (v_i, b_i). Set b_j = k for i \neq j. Then u_i(v_i, b_{-i}) = 0, but b_i is a winning bid, so u_i(b_i, b_{-i}) < 0.
Definition: Best response function B_i(\overline{x}^{-i}) for player i is the set of all mixed strategies with maximum expected utility against \overline{x}^{-i}.
Proposition: \overline{x} = (\overline{x}^1, ..., \overline{x}^n) is a mixed Nash equilbrium if and only if \overline{x}^i \in B_i(\overline{x}^{-i}) for all i \in N.
Example: Matching pennies.
Suppose x^1 = (p, 1 - p), x^2 = (q, 1 - q). For player I, expected utility for playing H is q(1) + (1-q)(-1) = 2q - 1. Expected utility for player T is q(-1) + (1-q) = 1 - 2q. So the overall expected utility is p(-2 + 4q) + (1 - 2q). Given q we find p that gives maximum u_i(x^2). q is constant, so 1 - 2q is constant. Suppose q < \frac{1}{2}, maximized when p = 0. Suppose q = \frac{1}{2}, any value of p gives the same utility. Suppose q > \frac{1}{2}, maximized when p = 1. So B_1(x^2) = \begin{cases}[0],\ &q < \frac{1}{2}\\ [0, 1],\ &q = \frac{1}{2}\\ [1],\ &q > \frac{1}{2}\end{cases}.
Let us maximize utility for player i given \overline{x}^{-i}.
\begin{aligned} \max\ &\sum_{s \in S_i} x^i_s u_i(s, \overline{x}^{-i}) \\ \text{s.t. } &\sum_{s \in S_i} x^i_s = 1\\ &x^i \ge 0 \end{aligned}
This is a LP with x^i as the variables. Let us take the dial.
\begin{aligned} \min\ &y \\ \text{s.t. } &y \ge u_i(s, \overline{x}^{-i}),\ \forall s \in S_i \end{aligned}
(P) is feasible, (D) is feasible, so they have an optimal solution by the fundamental theorem of LP. By strong duality theorem, their optimal solutions have the same objective value. The value of y minimizing (D) is \max_{s \in S_i} u_i(s, \overline{x}^{-i}). We reconstruct the optimal value of (P).
Recal: Complementary slackness conditions. For every s \in S_i, either x^i_s = 0 or y = u_i(s, \overline{x}^{-i}). So if x^i_s > 0, then y = u_i(s, \overline{x}^{-i}), meaning only pure strategies with the highest expected utility could have non-zero probabilities in the best repsonse.
Recall: Feasible solutions (\overline{x}^i, y) are optimal if and only if they satisfy the complementary slackness conditions.
Theorem: Given \overline{x}^{-i}, mixed strategy x^i \in B_i(\overline{x}^{-i}) if and only if \overline{x}^i_s > 0 implies s \in S_i is a pure strategy of maximum expected utility against \overline{x}^{-i}.
Note: By strong duality, the overall expected mixed strategy utility is equal to the maximum utility when playing a pure strategy. Any probability distribution over all strategies with maximum expected utility is a best response.
Theorem: Every finite strategy game has a mixed Nash equilibrium.
We focus on 2-player zero-sum games. A strategic game is zero-sum if \sum_{i \in N} u_i(s) = 0 for every strategy profile s. For 2-player games, we can define this game using a single payoff matrix A \in \mathbb{R}^{m \times n}, where u_1(i, j) = A_{i, j}, u_2(i, j) = -A_{i, j}.
Suppose player I players x^1. They expected player II to use a strategy from their best response. Player II’s expected utility when playing j is (-x^1)^TA_{.,j}, where A_{.,j} is the jth column of A. Player II looks for \max_{j^\prime} -(x^1)^T A_{.,j^\prime} = -\min_{j^\prime} (x^1)^T A_{.,j^\prime}. This is also the overall expected utility. Since this a zero-sum game, the expected utility for player I is \min_{j^\prime} (x^1)^T A_{.,j^\prime}. Player I wants to maximize this value.
\begin{aligned} \max\ &y\\ \text{s.t. } &y \le (x^1)^T A_{.,j^\prime}\ &\forall j^\prime \in \{1, ..., m\} \\ &\sum_{i=1}^m x^1_i = 1 \\ &x^1 \ge 0 \end{aligned}
For player II, we have a similar LP.
\begin{aligned} \min\ &y\\ \text{s.t. } &(x^2)^T A_{i^\prime, .} \le y\ &\forall i^\prime \in \{1, ..., n\} \\ &\sum_{j=1}^n x^2_j = 1 \\ &x^2 \ge 0 \end{aligned}
These LP are duals of each other, where both are feasible, so they have optimal solutions with equal value. The optimal solutions are best responses to each other, so they are a mixed Nash equilibrium.
Theorem: Any 2-player zero-sum game has a mixed Nash equilibrium which can be efficiently computed.
Suppose there are two candiates A, B, with a, b supporters respectively. Without loss of generality, assume a \ge b. Voters gain utility 2 if the supporting candidate wins, 1 if they tie, 0 if they lose. Voters either abstain or vote with cost c. Assume c \in (0, 1).
Example: a = b.
- Everyone votes, 1 - c utility for all. Abstaining changes utility to 0, Nash equilibrium.
- Not everyone votes but there is a tie. A voter who abstains will vote, changing utility from 1 to 2 - c. Not a Nash equilibrium.
- Candidate wins by 1 vote. A voter who abstains will vote, changing utility from 0 to 1 - c. Not a Nash equlibrium.
- Candidate wins by \ge 2 votes. A voter who voted will abstain, changing utility from 2 - c to 2. Not a Nash equlibrium.
So in a close election, more people vote.
Example: Possible Mixed Nash equilibrium.
Suppose b of the supporters of A vote. Suppose all supporters of B vote with probability p. The best that B can do is a tie.
Consider a supporter of B. if they abstain, B loses with expected utility 0. Voting has expected utility p^{b-1}(1-c) + (1 - p^{b-1})(-c) = p^{b-1} - c. In a mixed Nash equilibirum, 0 = p^{b-1} - c, so p = c^{\frac{1}{b-1}}.
Finite set of vectors x^0, ..., x^n are affinely independent if for \lambda_0, ..., \lambda_n \in \mathbb{R}, \sum_{i=0}^n \lambda_i x^i = 0 and \mathbb{1}^T \lambda = 0 implies \lambda_0 = ... = \lambda_n = 0.
Note: This is the case if and only if x_0 - x_1, ..., x_0 - x_n are linearly independent.
When x_0, ..., x_n are affinely independent points, we call conv(\{x_0, ..., x_n\}) an n-simplex. Let e^i be the ith n-dimensional unit vector. We call the n-simplex conv(\{e^0, ..., e^n\}) the standard n-simplex.
Definition: Simplical subdivision of an n-simplex T is a finite collection T_1, ..., T_q of simplices such that \cup_{i=1}^q T_i = T, and any two distict simplices either do not intersect, or intersect at a common face.
Given an n-simplex T and a simplical sub-division S, let V be the set of all extreme points. Then every v \in V lies in T, so it is representable as an convex combination of it’s extreme points. Let x(v) = \{i \in \{0, ..., n\} \mid \lambda_i > 0\} be the index set of vertices of T needed in v’s convex combination.
We say that a function L: V \to \{0, ..., n\} is a proper labelling of V if L(v) \in x(v) for all v \in V. When L assumes all n + 1 values of the vertices of T, then T is completely labelled by L.
Proof by induction on n. When n = 0, the statement is vacuously true. When n > 0, let us drop x^n of T = conv(\{x^0, ..., x^n\}) and consider T^\prime = conv(\{x^0, ..., x^{n-1}\}). This is a n-1-simplex, so S^\prime = \{T_i \cap T^\prime \mid T_i \in S\} is a simplical subdivision of T^\prime. V^\prime of S^\prime are a subset of the vertices V of S, so a proper labelling of L for V is a proper labelling L^\prime of V^\prime. So S^\prime has an odd number of completely labelled simplices by the hypothesis.
Assume that S comsists of n-simplices. Let F_i represent these simplices, with F_i = conv(\{v_j \mid i \neq j\}) for i \in \{0, ..., n\}. Let \mathbb{F} represent the set of facets of simplices in S, let \mathbb{F}_n be those facets whose n vertices have labels 0, ..., n - 1. We create a graph G_n which has a vertex for every f \in F_n, and an edge ff^\prime if f, f^\prime \in F_n are facets of a common simplex in S.
We see that a simplex S has a facet f \in F_n has at most one f^\prime \in F_n. So the maximum vertex degree is 2. Recall that we know S^\prime of T^\prime has an odd number of fully labelled sub-simplices, f_1, ..., f_{2p + 1} \in F_n. These have degree 1 in G_n, so they must be the endpoint of a path in this graph. Let us partiton the paths P = P_1 \cup P_2 such that P_1 is the set of paths with both ending in \{f_1, ..., f_{2p+1}\}. Then 2p + 1 = 2|P_1| + |P_2|, so it must be the case that |P_2| is odd. Consider a path p \in P_2, let f^\prime be the endpoint whose corresponding facet does not lie on T^\prime. Then the labels of f^\prime are in \{0, ..., n-1\}, so f^\prime cannot be part of a facet of T other than T^\prime. So f^\prime is a facet of a fully labelled simplex in S. So there are an odd number of fully labelled simplices in S that correspond to paths in P_2.
There may be paths P_3 which do not end in \{f_1, ..., f_{2p + 1}\}. This path must start and end in a distinct fully labelled simplex of S. So the number 2|P_3| of such fully labelled simplices is even. G_n may also have cycles C, which do not touch fully labelled simplices of S.
Since every fully labelled simpliex S has exactly one of its facets in F_n, every such simplex must correspond to the endpoint of a path in P_2 \cup P_3. So the number of fully labbelled simplices in S is |P_2| + 2|P_3|, so odd.
Continuous function f: \Delta_m \to \Delta_m has a fixed point z \in \Delta_m such that f(z) = z.
Every finite strategic game has a mixed Nash equilibirum.
Given a mixed strategy profile x \in \Phi_{i \in N} \Delta_{|S_i| - 1} \to \Phi_{i \in N} \Delta_{|S_i| - 1}, we define \Phi^i_{s_i}(x) = \max\{0, u_i(s_i, x^{-i}) - u_i(x)\}. So \Phi^i_{s_i}(x) is positive if and only if x^i is the best response to x^{-i}.
We define f(x) = \overline{x} where \overline{x} = \frac{x^i_{s_i} + \Phi^i_{s_i}(x)}{\sum_{s_i \in S_i}(x^i_{s_i} + \Phi^i_{s_i}(x))} = \frac{x^i_{s_i} + \Phi^i_{s_i}(x)}{1 + \sum_{s_i \in S_i} \Phi^i_{s_i}(x)}.
Note that f is continuous since \Phi^i_{s_i} are continuous. So f has a fixed point \hat{x}. Consider a player i \in N and let s_i \in S_i be a pure strategy such that \hat{x}^i_{s_i} > 0 and u_i(s_i, \hat{x}^{-i}) \le u_i(\hat{x}). It follows that \Phi^i_{s_i}(x) = 0, so it must be the case that \Phi^i_{s^\prime_i} = 0 for all i, s^\prime_i. So \hat{x}^i is a best response to \hat{x}^{-i} for all i \in N, so it is a mixed Nash equilibrium.
We want to design rules for games for rational players so that system-wide optimal goal is achieved
Definition: An auction is dominant-strategy incentive compatible (DSIC) if truthful bidding is a dominant strategy, and yields non-negative utility for all players.
Definition: Social welfare of a single item is \sum_{i \in N} v_i x_i, x \in \{0, 1\}^N, \sum_{i \in N}x_i = 1. Auction is welfare-maximizing if truthful bidding maximizes social welfare.
Definition: Auction is ideal if.
k \ge 1 slots for sponsored links. For every slot j, a_j \in [0, 1] is probability user clicks on ad. Assume a_1 \ge a_2 \ge ... \ge a_k.
Social welfare is \sum_{i \in N} v_i x_i, where x_i = a_j if slot j assigned to player i. Welfare-maximizing allocation is to assign slot j to the j-th highet valuation.
To get DSIC pricing, use Myerson’s Lemma.
Aside: Payment as the j+1th highest bid is not DSIC. Player’s could switch to a lower slot with higher utility.
Definition: Given a single parameter environment, direct revelation mechanism.
x: B \to X is an allocation rule, p: B \to \mathbb{R}_+^N is a payment rule.
Myerson’s Lemma: Fix a single parameter environment.
(\Rightarrow) Assume x is implementable. So there is payment rule p such that (x, p) is DISC. Fix player i, b_{-i} \in B_{-i}. Required to prove that y \ge z implies x_i(y, b_{-i}) \ge x_i(z, b_{-i}). Use x(y), p(y) to represent x_i(y, b_{-i}) and p_i(y, b_{-i}).
(x, p) is independent of player valuations, so DSIC for any possible valuation. So DSIC when player i’s valuation is y. So u(y) \ge u(z), y x(y) - p(y) \ge y x(z) - p(z). This also holds when player i’s valuation is z. So z x(z) - p(z) \ge z x(y) - p(y).
Combining inequalities we have z(x(y) - x(z)) \le p(y) - p(z) \le y(x(y) - x(z)). Since z \le y, z, y \ge 0, we know x(y) - x(z) \ge 0, so x(y) \ge x(z). So x is monotone.
(\Leftarrow). Assume x is monotone. First show that there is only one possible payment rule under monotone and DSIC. Then show the payment rule is DSIC. Consider x that is either piecewise constant, or differentiable.
Assume y > x. Suppose x is piecewise constant with intervals [0, \overline{z}_1], (\overline{z}_1, \overline{z}_2], ..., (\overline{z_q}, \infty). Define h_j to be the jump at \overline{z_j}, h_j = \lim_{w \to \overline{z}_j^+} x(w) - x(\overline{z}_j). Fix z \in (\overline{z}_j, \overline{z}_{j+1}) for some j. From payment sandwich, divide by y - z.
z \frac{x(y) - x(z)}{y - z} \le \frac{p(y) - p(z)}{y - z} \le y \frac{x(y) - x(z)}{y - z}
\lim_{y \to z^+} \frac{x(y) - x(z)}{y - z} = x^\prime(z) = 0 since x is constant at z. So both of the ends of the inequality approach 0, so \lim_{y\to z^+}\frac{p(y) - p(z)}{y - z} = p^\prime(z) = 0. So p is constant within every piece of x.
Consider z = \overline{z}_j for some j. \lim_{y \to z^+} y(x(y) - x(z)) = z \cdot h_j. Also, \lim_{y \to z^+}z(x(y) - x(z)) = z \cdot h_j. So the payment jumps by \overline{z}_j h_j and \overline{z}_j. We assumed p(0) = 0, so this is unique, p(z) = p_i(z, b_{-i}) = \sum_{k=1}^j \overline{z}_k h_k.
Consider the case where x is differentiable. p(z) = p(z) - p(0) = \int_{0}^z p^\prime(t) dt = \int_0^z t x^\prime(t) dt.
Example: Managing advertising slots, T seconds to fill. N potential advertisers where advertiser i has ad of length t_i, derives value v_i. Run an auction to determine which players get their ads aired. The set of feasible allocations is X = \{x \in \{0, 1\}^N: \sum_{i \in N} t_i x_i \le T\}. Social welfare is \sum_{i \in N} v_i x_i. This is equivalent to binary knapsack problem, NP-hard. So requirements 2, 3 of ideal auction cannot simulatneously hold unless P = NP.
We relax condition 2 so that we have approximate welfare maximization while keeping efficiency.
An approximation is to look for an items value density, which is the value divided by space or time. Sort items so that \frac{v_1}{t_1} \ge ... \ge \frac{v_n}{t_n}.
One possible algorithm is to fill with the largest index until the bag is full. This does not work well in general. Consider v_1 = t_1 = 1, v_2 = T - 1, t_2 = T. Algorithm returns \{1\} with value 1 but a better solution is \{2\} with value T-1.
Refinement: Still pick i, but if V_{i+1} > v_1 + ... + v_i< then return \{i+1\} instead of S.
Suppose OPT is optimal value of knapsack problem, APX is approximate.
Theorem: APX \ge \frac{1}{2}OPT.
Consider LP relaxation, \max\{v_1x_1 + ... + v_n x_n: t_1x_1 + ... + t_n x_n \le T, 0 \le x \le 1\}. Then solution x_1, ..., x_i = 1, x_{i+1} = \frac{T - t_1 - ... - t_i}{t_{i+1}}, x_{i+2} = ... = x_n = 0 is optimal. Let v* be the optimal value. Then OPT \le v^*. We will show APX \ge \frac{1}{2} v^*.
- If v(S) \ge v_{i+1}, then APX = v(S). Then v^* \le v(S) + v_{i+1} \le 2 V(S) = 2 APX.
- If v(S) < v_{i+1}, then APX = v_{i+1}. Then v^* \le v(S) + v_{i+1} \le 2 v_{i+1} = 2APX.
The allocation is monotone so there is payment rule that is DSIC. Allocation has one jump from 0 to 1 at soem point, say \overline{b}_j. Payment for winning is \overline{b}_j. To find \overline{b}_j, brute force test out different values.
Look at payment rules from a different angle.
Theorem: In every general mechanism design environment, there is a DSIC welfare-maximizing mechanism.
Suppose we are given bids b_1, ..., b_n, every bid indexed by \omega. Allocation that is welfare-maximizing is x(b) = arg \max_{\omega \in \Omega} \sum_{i=1}^n b_i(w), the outcome \omega \in Omega that gives the highest sum of values. Payment rule is p_i(b) = \max_{\omega \in \Omega} \sum_{j \neq i} b_j(w) - \sum_{j \neq i} b_j(\omega^*), where \omega^* = x(b).
We claim that (x, p) is DSIC. Prove that bidding truthfully is a dominant strategy. For i, b_{-i}. When we pick an outcome x(b) = \omega^*, the utility for player i is v_i(\omega^*) - p_i(b) = \left[v_i(\omega^*) + \sum_{j \neq i}b_j(\omega^*)\right] - \left[\max_{\omega \in \Omega} \sum_{j \neq i} b_j(\omega)\right]. The first term is the thing we maximize, the second is a constant value since i is not in the auction.
Consider arbitrary \omega^* chosen as the allocation. The allocation x(b) maximizes \sum_{i=1}^n b_j(\omega^*) = b_i(\omega^*) + \sum_{j \neq i} b_j(\omega^*). So the first term is maximized when b_i(\omega^*) = v_i(\omega^*). So we get maximum utility by bidding truthfully.
Definition: Cooperative game is given by a set of N players, and characteristic function v: 2^N \to \mathbb{R} that assigns a value v(S) for every coalition S \subseteq N. The set N is called the grand coalition.
Assume that v(\emptyset) = 0, and v(S) \ge 0.
The definition does not tell us how value is distributed within a group. How do we distribute the value to achieve certain goals?
Example: Ice cream. P, S, G want to buy ice cream. 3 sizes of ice cream, 1, 1.5, 2 which sosts 7, 9, 11 respectively. P has 3, S has 4, G has 5.
| S | \emptyset, \{P\}, \{S\}, \{G\} | \{P, S\} | \{P, G\} | \{S, G\} | \{P, S, G\} |
|---|---|---|---|---|---|
| v(S) | 0 | 1 | 1 | 1.5 | 2 |
Example: In a matching game, we have a graph G = (V, E) and weights w: E \to \mathbb{R}_+. Players are the vertices, for any subset S \subseteq N, the value is the maximum weight of any matching inside S.
Definition: Given a coop game (N, v), a coalition structure is a partition \pi of N, \pi = (c_1, ..., c^k), c_i \subseteq N, c^i \cap c^j = \emptyset when i \neq j, and c^1 \cup ... \cup c^k = N. A payoff vector x \in \mathbb{R}_+^N such that \sum_{i \in c^j} x_i = x(c^j) \le v(c^j) for every j \in \{1, ..., k\}. An outcome consists of (\pi, x). It is efficient if x(c^j) = v(c^j) for every j \in \{1, ..., k\}.
Example: An outcome for the ice cream game is \pi = (\{P\}, \{S, G\}), X(P) = 0, X(S) = 0.7, X(G) = 0.8. This is efficient.
Proposition: A game (N, v) is convex if and only if for every S, T where S \subseteq T \subseteq N and every player i \in N, v(T \cup \{i\}) - v(t) \ge v(S \cup \{i\}) - v(S).
What do we want as an outcome in a cooperative game?
Shapley values deal with the fairness of payoff vectors. Assume the players form the grand coalition. How do we quantify contributions? Compare the value of the coalition before and after a player joins it.
Example: Contribution of G is the difference between v(\{P, S\}) and v(\{P, S, G\}).
The total contribution may exceed total value. Look at all possible ordering, average the contribution.
Notation: Permutation \sigma of N has the form (\sigma_1, ..., \sigma_n) where every \sigma_i is a distinct member of N (or a bijection between N and N). The set of all permutations of N is S_N. Given \sigma \in S_N, marginal contribution of player \sigma_i.
\Delta_\sigma (\sigma_i) = v(\{\sigma_1, ..., \sigma_i\}) - v(\{\sigma_1, ..., \sigma_{i-1})
Definition: The Shapley value of player i is \phi_i = \frac{1}{n!}\sum_{\sigma \in S_N}\Delta_\sigma(i).
Example: Calculate \phi_P in the ice cream game.
S_n = \{\sigma_1 = (P, S, G), \sigma_2 = (P, G, S), \sigma_3 = (S, P, G), \sigma_4 = (S, G, P), \sigma_5 = (G, P, S), \sigma_6 = (G, S, P)\}.
\begin{aligned} \Delta_{\sigma_1}(P) &= v(\{P\}) - v(\emptyset) = 0 \\ \Delta_{\sigma_2}(P) &= v(\{P\}) - v(\emptyset) = 0 \\ \Delta_{\sigma_3}(P) &= v(\{S, P\}) - v(\{S\}) = 1 \\ \Delta_{\sigma_4}(P) &= v(\{S, G, P\}) - v(\{S, G\}) = 0.5 \\ \Delta_{\sigma_5}(P) &= v(\{G, P\}) - v(\{G\}) = 1 \\ \Delta_{\sigma_6}(P) &= v(\{G, S, P\}) - v(\{G, S\}) = 0.5 \\ \end{aligned}
So \phi_P = \frac{1}{2}.
For any \sigma \in S_N, sum of all marginal contributions of all players is v(N).
\begin{aligned} \sum_{i=1}^n \Delta_{\sigma}(i) &= \sum_{i=1}^n \Delta_{\sigma} (\sigma_i) \\ &= [v(\{\sigma_1\}) - v(\emptyset)] + [v(\{\sigma_1, \sigma_2\}) - v(\{\sigma_1\})] + ... \\ &= v(\{\sigma_1, ..., \sigma_n\}) - v(\emptyset) \\ &= v(N) \end{aligned}
So the sum of all players’ maginal contributions over all permutations is n! v(N). So Shapley value is v(N).
For any permutation \sigma \in S_N, say i, then \Delta_\sigma(i) = v(\{\sigma_1, ..., \sigma_{j-1}, i\}) - v(\{\sigma_1, ..., \sigma_{j-1}) = 0. So \phi_i = 0.
Define f: S_N \to S_N where f(\sigma) swaps the positions of i, j. This is a bijection. We claim that \Delta_\sigma(i) = \Delta_{f(\sigma)}(j).
Suppose i precedes j in \sigma. Let c be all elements preceding i. Then \Delta_\sigma(i) = v(c \cup \{i\}) - v(c). \Delta_{f(\sigma)}(j) = v(c \cup \{j\}) - v(c). c does not contain i, j. By symmetry, v(c \cup \{i\}) = v(c \cup \{j\}). So \Delta_\sigma(i) = \Delta_{f(\sigma)}(j).
Suppose j precedes i in \sigma. Let c be all elements preceding i in \sigma except for j. Then \Delta_\sigma(i) = v(c \cup \{i, j\}) - v(c \cup \{i\}). \Delta_{f(\sigma)}(i) = v(c \cup \{i, j\}) - v(c \cup \{i\}). So \Delta_\sigma(i) = \Delta_{f(\sigma)}(j) by symmetry.
\begin{aligned} \phi_i &= \frac{1}{n!}\sum_{\sigma \in S_n} \Delta_\sigma(i) \\ &= \frac{1}{n!} \sum_{\sigma \in S_n} \Delta_{f(\sigma)}(j) \\ &= \frac{1}{n!} \sum_{\sigma \in S_n} \Delta_\sigma(j) \\ &= \phi_j \end{aligned}
\begin{aligned} \Delta_\sigma^3(i) &= v^3(\{\sigma_1, ..., \sigma_{i - 1}, \sigma_i\}) - v^3(\{\sigma_1, ..., \sigma_{i-1}\}) \\ &= v^1(\{\sigma_1, ..., \sigma_{i - 1}, \sigma_i\}) - v^1(\{\sigma_1, ..., \sigma_{i-1}\}) + v^2(\{\sigma_1, ..., \sigma_{i - 1}, \sigma_i\}) - v^2(\{\sigma_1, ..., \sigma_{i-1}\})\\ &= \Delta_\sigma^1(i) + \Delta_\sigma^2(i) \\ \ \\ \phi^3_i &= \frac{1}{n!} \sum_{\sigma \in S_n} \Delta^3_\sigma(i) \\ &= \frac{1}{n!} \sum_{\sigma \in S_n} \left[\Delta^1_\sigma(i) + \Delta^2_\sigma(i)\right] \\ &= \frac{1}{n!} \sum_{\sigma \in S_n} \Delta^1_\sigma(i) + \frac{1}{n!} \sum_{\sigma \in S_n} \Delta^2_\sigma(i) \\ &= \phi^1_i + \phi^2_i \end{aligned}
Example: Unanimity game. |N| = n, v(N) = 1, v(c) = 0 for all c \subsetneq N. Any pair of players is symemtric. Since it is efficient, the sum of shapley values is 1. So \phi_i = \frac{1}{n} for all i \in N.
We want an outcome (\pi, x) that is stable, no group is incentivized to deviate from their assigned coalition. Given (\pi, x) a coalition c not in \pi is more likely to break away if x(c) < v(c).
Definition: Core consists of all outcomes (\pi, x) such that x(c) \ge v(c) for any c \subseteq N.
Example: Ice cream game. Assume (\pi, x) is in the core. Assume that \pi has at least 2 parts. Then at least one part is a single player with value of 0. The player has x value 0, so x(N) \le 1.5, but v(N) = 2, so \pi cannot have more than 1 part. So \pi = (N). The payoff x must satisfy x(c) \ge v(c) for all c \subseteq N and x(N) = v(N). If x = (x_P, x_S, x_G), then x_P + x_S + x_G = 2, x_P, x_S, x_G \ge 0, x_P + x_S \ge 1, x_P + x_G \ge 1, x_S + x_G \ge 1.5.
By definition of a core, x(c) \ge v(c). Since (\pi, x) is valid, x(c) \le v(c). So x(c) = v(g).
Since (\pi, x) is in the core, x(c^\prime) \ge v(c^\prime) for any c^\prime \in \pi^\prime (x(c) \ge v(c) for any c \subseteq N). So \sum_{c^\prime \in \pi^\prime} x(c^\prime) \ge \sum_{c^\prime \in \pi^\prime} v(c^\prime) = v(\pi^\prime). We also know that the sum over all x(c^\prime) is the same regardless of the partition, so \sum_{c^\prime \in \pi^\prime} x(c^\prime) = \sum_{c \in \pi} x(c) = \sum_{c \in \pi} v(c) = v(\pi). So v(\pi) \ge v(\pi^\prime).
3-player majority game. N = \{1, 2, 3\}. v(S) = \begin{cases}1,\ &|S| \ge 2 \\0,\ &|S| \ge 1\end{cases}. Suppose (\pi, x) is a core. Since v(N) = 1, x_1 + x_2 + x_3 \ge 1, x_1, x_2, x_3 \ge 0. So at least one x_i \ge \frac{1}{3}. The total value of any coalition structure is at most 1, so x_1 + x_2 + x_3 \le 1. x(N \setminus \{i\}) \le \frac{2}{3}. v(N \setminus \{i\}) = 1. Contradiction.
V(S \cup T) \ge V(S) + V(T), for disjoint S, T \subseteq N.
Players want to form the grand coalition, but not all cores consist of only the frand coalition. We claim that the question of existence of cores can be answered by looking at the grand coalition.
Strict superadditive case: v(S \cup T) > v(S) + v(T) for disjoint, non-empty S, T \subseteq N.
Suppose (\pi, x) is a core where \pi is not the grand coalition. Say c^1, c^2 \in \pi. Then x(c^1) + x(c^2) = x(c^1 \cup c^2) \ge v(c^1 \cup c^2) > v(c^1) + v(c^2). This is a contradiction because x(c^i) = v(c^i). So for strict superadditive game if a core exists, it has the form ((N), x).
Superadditive case. If (\pi, x) is in the core, then ((N), x) is also in the core.
Since (\pi, x) is in the core, x(c) \ge v(c0 for all c \subseteq N. We need to verify that ((N), x) is a vlaid outcome, so x(N) \le v(N). x(N) = \sum_{c \in \pi}x(c) = \sum_{c \in \pi} v(c) \le v(N).
We only need to look at the payoff vector in the core. This is the polyhedron C = \{x \in \mathbb{R}_+^N: x(N) = v(N), x(c) \ge v(c) \forall c \subseteq N\}.
Example: N = \{1, 2, 3, 4\}. v(S) = 1 if |S| \ge 2, 0 otherwise. v(N) = 1 is not max value, since \pi = (\{1, 2\}, \{3, 4\}), v(\pi) = 2. So (N) is not in the core.
Definition: For any (N, v), its superadditive cover is (N, v^*), where for every S \subseteq N, v^*(S) = \max \{v(\pi): \pi \text{ is a partition of } S\}.
Example: v^*(N) = 2.
Proposition: Game (N, v) has a non-empty core if and only if its superadditive cover (N, v^*) has a non-empty core.
(\Rightarrow) Suppose (\pi, x) is in the core of (N, v). We claim that it is in the core of (N, v^*). Required to show that x(c) \ge v^*(c) for all c \subseteq N.
Let \pi^\prime = argmax \{v(\pi^\prime): \pi^\prime \text{ is a partition of } c\}. v^*(c) = v(\pi^\prime) = \sum_{c^\prime \in \pi^\prime} v(c^\prime) \le \sum_{c^\prime \in \pi^\prime} x(c^\prime) = x(c). So (\pi, x) is in the core of (N, v^*).
(\Leftarrow): Suppose (N, v^*) has a non-empty core. Superadditive game, so ((N), x) is in the core. So x(N) \le v^*(N), let \pi represent the partition such that v^*(N) = v(\pi). We claim that (\pi, x) is in the core of (N, v). \sum_{c \in \pi} x(c) = x(N) \le v^*(N) = v(\pi), so it is a feasible allocation. Consider c \subseteq N. x(c) \ge v^*(c) \ge v(c), so (\pi, x) is in the core of (N, v).
V(S \cup T) + v(S \cap T) \ge v(S) + v(T), for any S, T \subseteq N.
Proposition: Convex games have a non-empty core.
Convex games are supperadditive, so it suffices to find x such that x(N) = v(N), x(c) \ge v(c) for all c \subseteq N. Let \sigma \in S_N. Without loss of generality, assume \sigma = (1, 2, ..., n). Define x_i = \Delta_\sigma(i). We proved x(N) = v(N) in a Shapley value proof. Let c \subseteq N, say C = \{i_1,..., i_k\}. Without loss of generality assume i_1 < ... < i_k. v(c) = [v(\{i_1\}) - v(\emptyset)] + v(\{i_1, i_2\}) - v(\{i_1\})] + ....
We want to show that the jth term is at most \Delta_\sigma(i_j) = v(\{1, ..., i_j\}) - v(\{1, ..., i_{j} - 1\}). Using supermodularity, v(\{i_1, ..., i_j\}) + v(\{1, ..., i_j - 1\}) \le v(\{1, ..., i_j\}) + v(\{1, ..., i_{j-1}\}). So x_{i_j} = v(\{1, ..., i_j\}) - v(\{1, ..., i_j - 1\}) \ge v(\{i_1, ..., i_j\}) - v(\{i_i, ..., i_{j-1}\}), So v(c) \le x_{i_1} + ... + x_{i_k} = x(c).
N players, played on a graph G = (N, E). Let w_e \ge 0 be a weight for every edge in E. The value v(S) of S \subseteq N is the maximum weight of a matching using vertices in S. This is superadditive, so we only need to look at the grand coalition. ((N), x) is in the core if and only if x \in C, C = \{x \in \mathbb{R}_+^N: x(N) = v(N), x(c) \ge v(c) \forall c \subseteq N\}. There are exponentially many constraints, so we simplify as C^\prime = \{x \in \mathbb{R}_+^N: x(N) = v(N), x_u + x_v \ge w_{uv} \forall uv \in E\}.
Proposition: C = C^\prime.
Every constraint C is also in C^\prime, so C \subseteq C^\prime. Let x \in C^\prime. x(N) = v(N). Let c \subseteq N. Let M be a maximum weight matching in c. Then v(c) = w(M). We want to show that x(c) \ge v(c) = w(M).
\begin{aligned} x(c) &\ge \sum_{uv \in M} (x_u + x_v) \text{ (since $M$ is a matching)} \\ &\ge \sum_{uv \in M} w_{uv} \text{ (since $x \in C^\prime$)}\\ &= w(M) \end{aligned}
LP Formulation: We solve feasibility problem of C^\prime using the following LP.
\begin{aligned} \min\ &x(N) \\ \text{s.t. } &x_u + x_v \ge w_{uv},\ \forall uv \in E \\ &x \ge 0 \end{aligned} This is feasible with large x. As C = C^\prime, x(N) \ge v(N). So the solution is bounded by v(N). So there is an optimal solution. The dual is given by the followinig LP.
\begin{aligned} \max\ &\sum_{e \in E} w_e y_e \\ \text{s.t. } &\sum_{e \in \delta(v)} y_e \le 1,\ \forall v \in N \\ &y \ge 0 \end{aligned}
When y is integral, this is the maximum weight matching problem. This is the LP relaxation. (D) could have fractional optimal solution, for example a triangle with all edge weights being 3 would have a maximum matching of 3 but the LP relaxation optimal would be y = \left(\frac{1}{2}, \frac{1}{2}, \frac{1}{2}\right), 4.5.
Proposition: The core of the matching game is non-empty if and only if (D) has an integral optimal solution.
It suffices to show that (P) has an optimal value v(N) if and only if (D) has an integer optimal solution.
(\Rightarrow) Suppose (P) has optimal value v(N), so x(N) = v(N). Let M be a matching of value v(N), w(M) = v(N). Let y be the vector where y_e = \begin{cases} 1\ &e \in M\\0,\ &e \not\in M\end{cases}. So y is feasible for (D), with objective value w(M). By weak duality, y is optimal for (D), y is integral.
(\Leftarrow) Suppose y is optimal integral solution for (D). Let M^\prime = \{e \in E: y_e = 1\}. Then M^\prime is a matching with optimal value w(M^\prime), and M^\prime is a maximum weight matching. Then w(M^\prime) = v(N). By strong duality, (P) has optimal value v(N).
Note: When G is bipartite, (D) has integral optimal solution, so the core is non-empty. Determining the integrality of (D) is polytime.
Network bargaining game is a game played on a graph G = (N, E). Every edge uv represents a potential partnership between u,v which generates value w_{uv}. How are pairs formed? How should the value be split?
An outcome consists of a matching M and a payoff vector x \in \mathbb{R}_+^N such that x_u + x_v = w_{uv} for all uv \in M, x_v = 0 if v is not matched in M.
Definition: For an outcome (M, x) and player u, the outside option of player u is \alpha_u = \max\{w_{uv} - x_v: uv \in \delta(u) \setminus M\}. If \delta(u) \setminus M = \emptyset, then \alpha_u = 0. This is the maximum value that u receives by defecting from their current partner in M. It is stable if there is no incentive to switch.
Definition: An outcome (M, v) is stable if x_u \ge \alpha_u for all u \in N.
In a stable outcome, for any edge uv, x_u + x_v \ge w_{uv} (x_u \ge \alpha_u \ge w_{uv} - x_v).
Proposition: A stable outcome exists in a network bargaining game if and only if the correpsonding matching game has a non-empty core.
Definition: Outcome (M, v) is balanced if for all uv \in M, x_u - \alpha_u = x_v - \alpha_v. Alternatively, x_u = \alpha_u + \frac{w_{uv} - \alpha_u - \alpha_v}{2}.
Definition: For any cooperative game (N, v) and a payoff vector x \in \mathbb{R}_+^N, the surplus of i over j is S_{ij} = \max\{v(c) - x(c): c \subseteq N, i \in c, j \not\in C\}.
v(c) - x(c) is the excess value not distributed. The max represents what player i could potentially get without working with j. If S_{ij}(x) > S_{ji}(x), then player i could demand more from j if they work together.
Definition: The prekernel is P = \{x \in \mathbb{R}_+^N: S_{ij}(x) = S_{ji}(x)\ \forall i, j \in N\}.
Application to network bargaining.
Proposition: If x is in the intersection of the core and the prekernel of the matching game corresponding to the network bargaining game, then x is a balanced outcome in the network bargaining game.
Let ij be an edge. We first prove that the surplus of i over j is S_{ij} = \begin{cases} \max \{w_{ik} - x_i - x_k: ik \in \delta(i) \setminus \{ij\}\},\ &\delta(i) \setminus \{ij\} \neq \emptyset \\ -x_i\ &\delta(i) \setminus \{ij\} = \emptyset\end{cases} = \alpha_i - x_i.
Let c \subseteq N, i \in c, j \not\in c be a minimal set where S_{ij}(x) = v(c) - x(c). Let M be a matching in c where v(c) = w(M). Suppose there exists uv \in M that is not incident with i. Since x is in the core, x_u + x_v \ge w_{uv}.
\begin{aligned} v(c \setminus \{u, v\}) - x(c \setminus \{u, v\}) &= v(c) - w_{uv} - (x(c) - x_u - x_v) \\ &= v(c) - x(c) + x_u + x_v - w_{uv} \\ &\ge v(c) - x(c) \end{aligned}
This implies v(c \setminus \{u, v\}) - x(c \setminus \{u, v\}) = v(c) - x(c), contradicting the minimality of c. Similarly, c cannot include and vertex other that i that is not matched in M (eitehr it would increase S_{ij}, or make a smaller c). So c is either \{i\} or \{i, k\} where ik \in \delta(i) \setminus \{ij\}. This givs our formula for S_{ij}(x). Finally, since x is in the prekernel, S_{ij}(x) = S_{ji}(x). So \alpha_i - x_i = \alpha_j - x_j, so x is balanced.
Schmeidler showed that in general, if the core is non-empty, then the intersection of hte core and the prekernel is non-empty.
Theorem: A network bargaining game is a balanced outcome if and only if it has a stable outcome.