CO456 Course Notes

Professor: Martin Pei | Term: Fall 2025

I’m auditing this course. The lecture videos are available fully online under this channel

Introduction

Question

What is game theory?

Not about the theory of playing board/video games. It is about analyzing social and economic situations in a strategic environment, where individuals make decisions to maximize benefits but these benefits depend on choices of others.

There are many different aspects of game theory.

Example

Building more roads may actually make traffic worse, there is a game theory explanation for this.

Course breakdown is:

1. Combinatorial game theory
2. Strategic games
3. Mechanism design
4. Cooperative games

Impartial Games

Nim

We are given some piles of chips. Two players play alternately. On a player’s turn, they pick a pile and remove at least 1 chip from it. The first player who cannot make a move loses.

Example

3 piles: [1,1,2]. The winning strategy is for Player 1 to remove the pile of 2 chips. Player 2 must remove a pile of 1 chip. Player 1 removes the final pile of 1 chip. Player 2 has no move and loses.

Since there is a winning strategy, we call this a winning game / winning position.

Example

2 piles: [5, 5] Regardless of what Player 1 does, Player 2 can make the same move on the other pile. Player 1 loses.

Since Player 1 loses regardless of their move, then this is a losing game / losing position.

Question

What if we have two piles of unequal sizes?

Example

2 piles: [5, 7] Player 1 moves to equalize the chip count (remove 2 from the pile of 7). Player 2 starts with 2 piles of equal sizes. This is a winning game for Player 1.

Lemma

In instances of Nim with two piles of $n$, $m$ chips, it is a winning game if and only if $m\ne n$.

Nim is an example of an impartial game.

Conditions required for an impartial game:

1. There are 2 players, Player 1 and Player 2.
2. There are several positions, with a starting position.
3. A player performs one of a set of allowable moves, which depends only on the current position, and not on the player whose turn it is. Each possible move generates an option.
4. Players move alternately.
5. There is complete information.
6. No chance moves.
7. First player with no available move loses.
8. Rules guarantee that games end.

Many games are not impartial: Tic-tac-toe (7), poker (5), monopoly (6).

Example

Let $G=(1,1,2)$ be a Nim game. There are 4 possible moves (hence 4 possible options).

flowchart LR
markdown["G=(1,1,2)"]
a["H1 = (1,1,1)"] 
b["H2 = (1,1,0)"] 
c["H3 = (0,1,2)"] 
d["H4 = (1,0,2)"] 
markdown --> a
markdown --> b
markdown --> c
markdown --> d

Note: We can define an impartial game by its position and options recursively.

Definition

A game $H$ that is reachable from game $G$ by a sequence of allowable moves is simpler than $G$.

Other impartial games

1. Subtraction game: We have one pile of $n$ chips. A valid move is taking away 1, 2, or 3 chips. The first player who cannot move loses
2. Rook game: We have an $m\times n$ chess board, and a rook in position $(i,j)$. A valid move is moving the rook any number of spaces left or up. The first player who cannot move loses
3. Green hackenbush game: We have a graph and the flow. The graph is attached to the floor at some vertices. A move consists of removing an edge of the graph, and any part of the graph not connected to the floor is removed. The first player who cannot move loses.

We will prove that all impartial games are essentially Nim games.

Winning Strategy

Question

Can there be an impartial game with no winning strategy?

No.

Tip

In any game $G$, either Player 1 or Player 2 has a winning strategy.

Proof: We prove by induction on the simplicity of $G$.

If $G$ has no allowable moves, then Player 1 loses, so Player 2 has a winning strategy.

Assume $G$ has allowable moves and the lemma holds for games simpler than $G$. Among all options of $G$, if Player 1 has a winning strategy in one of them, then Player 1 moves to that option and wins. Otherwise, Player 2 has a winning strategy for all options.

So regardless of Player 2’s move, Player 2 wins. $■$

So every impartial game is either a winning game (P1 has a winning strategy) or a losing game (P2 has a winning strategy).

Example

Nim: [5,7] (Winning Game) P1: Move to [5,5] is a winning move since [5,5] is a losing game for P2

A game is a winning game if at least one option is a losing game.

A game is a losing game if all of the options are winning games.

Note: We assume players play perfectly. If there is a winning move, they will take it.

Equivalent Games

Game Sums

Definition

Let $G$ and $H$ be two games with $G_1,\dots ,G_m$ and $H_1,\dots H_n$ respectively. We define $G+H$ as the game with options $G_1+H,\dots ,G_m+H,G+H_1,\dots ,G+H_n$

Example

We denote $\ast n$ to ben a game of Nim with one pile of $n$ chips. Then $\ast 1+\ast 1+\ast 2$ is the game with 3 piles of 1,1,2 chips.

Example

If we denote $\#n$ to be the subtraction game with $n$ chips, then $\ast 5+\#7$ is a game where a move consists of either removing at least 1 chip from the pile of 5 (Nim game), or removing 1, 2, or 3 chips from the pile of 7 (subtraction game)

Lemma

Let $\mathcal{G}$ be the set of all impartial games. Then for all $G,H,J\in \mathcal{G}$.

1. $G+H\in \mathcal{G}$ (closure)
2. $(G+H)+J=G+(H+J)$ (associative)
3. There exists an identity $0\in \mathcal{G}$ (game with no options) where $G+0=0+G=G$
4. $G+H=H+G$ (symmetric)

This is an abelian group except the inverse element.

Definition

Two games $G$, $H$ are equivalent if for any game $J$, $G+J$ and $H+J$ have the same outcome (i.e. either both are winning games, or both are losing games). Notation: $G\equiv H$.

Example

$\ast 3\equiv \ast 3$. Since $\ast 3+J$ is the same game as $\ast 3+J$, so they have the same outcome.

Example

$\ast 3\ne \ast 4$. Since $\ast 3+\ast 3$ is a losing game, but $\ast 4+\ast 3$ is a winning game

Lemma

$\ast n\equiv \ast m⟺n=m$

Lemma

The relation $\equiv$ is an equivalence relation. That is, for all $G,H,K\in \mathcal{G}$

1. $G\equiv G$ (reflexive)
2. $G\equiv H⟺H\equiv G$ (symmetric)
3. If $G\equiv H$ and $H\equiv K$, then $G\equiv K$ (transitive)

Exercise: Prove that if $G\equiv H$, then $G+J\equiv H+J$ for any game $J$.

To prove this, we need to show that for every game $Y$, $(G+J)+Y$ and $(H+J)+Y$ have the same outcome.

$$\begin{array}{rl}(G+J)+Y& \equiv G+(J+Y)\\ (H+J)+Y& \equiv H+(J+Y)\end{array}$$

Let $X:=(J+Y)$. $X$ is then an arbitrary game, and we know that the outcome of $G+X$ is the same as the outcome of $H+X$ since $G\equiv H$.

By substituting $X=J+Y$, we get that the outcome of $G+(J+Y))$ is the same as the outcome of $(H+(J+Y))$. This is what we have already shown above $■$

Losing games and empty Nim

Nim with one pile $\ast n$ is a losing game $⟺n=0$.

Theorem

$G$ is a losing game if and only if $G\equiv \ast 0$

Corollary

If $G$ is a losing game, then $J$ and $J+G$ has the same outcome for any game $J$.

Proof: Since $G$ is a losing game, $G\equiv \ast 0$ by the above theorem. Then $J+G\equiv J+\ast 0\equiv J$

So $J$ and $G+J$ have the same outcome $■$

Example

1. Recall $\ast 5+\ast 5$ and $\ast 7+\ast 7$ are losing games. Then our corollary says $\ast 5+\ast 5+\ast 7+\ast 7$ is also a losing game. (Player 1 moves in either $\ast 5+\ast 5$ or $\ast 7+\ast 7$. Then Player 2 makes a winning move from the same part, equalizing piles)
2. $\underset{\text{winning}}{\underbrace{\ast 1+\ast 1+\ast 2}}+\underset{\text{losing}}{\underbrace{\ast 5+\ast 5}}$. Corollary implies this is a winning game. (Player 1 makes a winning move in $\ast 1+\ast 1+\ast 2$, so we have $\underset{\text{losing}}{\underbrace{\ast 1+\ast 1}}+\underset{\text{losing}}{\underbrace{\ast 5+\ast 5}}$. Player 2 loses)

Proof of the theorem ($G$ is a losing game if and only if $G\equiv \ast 0$)

Start with the reverse direction ($⟸$)

If $G\equiv \ast 0$, then $G+\ast 0$ has the same outcome as $\ast 0+\ast 0$. But $\ast 0$ is a losing game, so $G$ is a losing game.

Next direction ($⟹$)

Suppose $G$ is a losing game. We want to show $G\equiv \ast 0$, meaning $G+J$ and $\ast 0+J\equiv J$ have the same outcome.

1. Suppose $J$ is a losing game. We want to show that $G+J$ is a losing game. We will prove “If $G$ and $J$ are losing games, then $G+J$ is a losing game” by induction on the simplicity of $G+J$. When $G+J$ has no options, then $G$,$J$ both have no options, so $G$, $J$, $G+J$ are all losing games. Suppose $G+J$ has some options. Then Player 1 makes a move on $G$ of $J$. Without loss of generality say Player 1 makes a move in $G$, and results in $G^{\prime }+J$. Since $G$ is a losing game, $G^{\prime }$ is a winning game. So Player 2 makes a winning move from $G^{\prime }$ to $G^{\prime \prime }$, and this results in $G^{\prime \prime }+J$. Then $G^{\prime \prime }$ is a losing game, so by induction, $G^{\prime \prime }+J$ is a losing game for Player 1. So Player 1 loses, and $G+J$ is a losing game
2. Suppose $J$ is a winning game. Then $J$ has a winning move to $J^{\prime }$. So Player 1 moves from $G+J$ to $G+J^{\prime }$. Now both $G$, $J^{\prime }$ are losing games, so by 1, $G+J^{\prime }$ is a losing game. So Player 2 loses, meaning Player 1 wins, so $G+J$ is a winning game. $■$

Equivalent Games (II)

Lemma

(Copycat principle): For any game $G$, $G+G\equiv \ast 0$

Proof: Induction on the simplicity of $G$.

When $G$ has no options, $G+G$ has no options, so $G+G\equiv \ast 0$.

Suppose $G$ has options, and without loss of generality, suppose Player 1 moves from $G+G$ to $G^{\prime }+G$. Then Player 2 can move to $G^{\prime }+G^{\prime }$.

By induction, $G^{\prime }+G^{\prime }\equiv \ast 0$, so it is a losing game for Player 1. Therefore, $G+G$ is a losing game, and $G+G\equiv \ast 0$. $■$

Lemma

$G\equiv H⟺G+H\equiv \ast 0$

Proof:

First direction ($⟹$)

From $G\equiv H$, we add $H$ to both sides to get $G+H\equiv H+H\equiv \ast 0$ by the copycat principle.

Second direction ($⟸$)

From $G+H\equiv \ast 0$, we add $H$ to both sides to get $G+H+H\equiv \ast 0+H\equiv H$. But $G+H+H\equiv G+\ast 0\equiv G$ by the copycat principle.

So $G\equiv H$ $■$.

Example

$\ast 1+\ast 2+\ast 3$ is a losing game, so $\ast 1+\ast 2+\ast 3\equiv \ast 0$. By lemma $\ast 1+\ast 2\equiv \ast 3$. Or $\ast 1+\ast 3\equiv \ast 2$

Another way to prove game equivalence is by showing that they have equivalent options.

Lemma

If the options of $G$ are equivalent to options of $H$, then $G\equiv H$. (More precisely: There is a bijection between options of $G$ and $H$ where paired options are equivalent.)

Example

We can show $\ast 1+\ast 2\equiv \ast 3$ using this lemma.

flowchart LR
a --- b
a --- c
a --- d
b <-..-> e
c <-..-> f
d <-..-> g
e --- h
f --- h
g --- h

Note: The converse is false.

Proof of the above lemma:

It suffices to show that $G+H\equiv \ast 0$, i.e. $G+H$ is a losing game. This is true when $G$, $H$ both have no options. Suppose $G$, $H$ have options, and suppose without loss of generality Player 1 moves to $G^{\prime }+H$. By assumption, there exists an option of $H$, say $H^{\prime }$, such that $H^{\prime }\equiv G^{\prime }$. So Player 2 can move to $G^{\prime }+H^{\prime }$. Since $G^{\prime }\equiv H^{\prime }$, $G^{\prime }+H^{\prime }\equiv \ast 0$. So $G^{\prime }+H^{\prime }$ is a losing game for Player 1. Hence $G+H$ is a losing game. $■$

Nim and Nimbers I

Goal: Show that every Nim game is equivalent to a Nim game with a single pile.

Nimbers

Definition

If $G$ is a game such that $G\equiv \ast n$ for some $n$, then $n$ is the nimber of $G$.

Example

Any losing game has nimber 0

Theorem

Suppose $n=2^{a_1}+2^{a_2}+\cdots$ where $a_1>a_2>\cdots$, then $\ast n=\ast 2^{a_1}+\ast 2^{a_2}+\cdots$

Example

$11=2^3+2^1+2^0$. $13=2^3+2^2+2^0$. Using this theorem, $\ast 11\equiv \ast 2^3+\ast 2^1+\ast 2^0$ and $\ast 13\equiv \ast 2^3+\ast 2^2+\ast 2^0$

Then

$$\begin{array}{rl}\ast 11+\ast 13& \equiv (\ast 2^3+\ast 2^1+\ast 2^0)+(\ast 2^3+\ast 2^2+\ast 2^0)\\ & \equiv (\ast 2^3+\ast 2^3)+\ast 2^2+\ast 2^1+(\ast 2^0+\ast 2^0)\text{by associativity and commutativity}\\ & \equiv \ast 0+\ast 2^2+\ast 2^1+\ast 0\text{by copycat principle}\\ & \equiv \ast 2^2+\ast 2^1\equiv \ast (2^2+2^1)\equiv \ast 6\text{by theorem}\end{array}$$

So the nimber of $\ast 11+\ast 13$ is $6$.

Question

In general, how can we find the nimber for $\ast b_1+\ast b_2+\cdots \ast b_n$?

Look for binary expansions of each $b_i$. Copycat principle cancels any pair of identical powers of 2. So we look for powers of 2’s that appear in odd number of expansions of the $b_i$‘s.

Use binary numbers: $11$ in binary is $1011$, $13$ in binary is $1101$. Take the XOR operation.

$1011\oplus 1101=0110\leftarrow 6$

Example

Consider $\ast 25+\ast 21+\ast 11$

In binary, they are $11001,10101,01011$.

$11011\oplus 10101\oplus 01011=00111\leftarrow 7$

So $\ast 25+\ast 21+\ast 11=\ast 7$ (The nimber is $7$).

Corollory

$\ast b_1+\ast b_2+\cdots +\ast b_n\equiv \ast (b_1\oplus b_2\oplus \cdot \oplus b_n)$.

This shows us that every Nim game has a nimber.

Winning strategy for Nim

Example

$\ast 11+\ast 13\equiv \ast 6$ This is a winning game. How to find a winning move? Want to move to a game equivalent to $\ast 0$. Add $\ast 6$ to both sides: $\ast 11+\ast 13+\ast 6\equiv \ast 6+\ast 6\equiv \ast 0$ (copycat principle). Consider $\ast 11+(\ast 13+\ast 6)$. We see $13\oplus 6=11$. So this is equivalent to $\ast 11+\ast 11$, a losing game. Winning move: Remove $2$ chips from the pile of $13$.

Example

$\ast 25+\ast 21+\ast 11=\ast 7$. Add $\ast 7$ to both sides. Consider $\ast 25+(\ast 21+\ast 7)+\ast 11$ We see $21\oplus 7=18$, so this is equivalent to $\ast 25+\ast 18+\ast 11$ Winning move: remove 3 chips from the pile of 21

Question

Why did we pair $\ast 7$ with $\ast 21$ instead of $\ast 25$ or $\ast 11$?

$25\oplus 7=31$, $11\oplus 7=12$.

This means that we are adding $6$ chips to $25$, or adding $1$ chip to $11$. Not allowed in Nim.

Lemma

If $\ast b_1+\cdots +\ast b_n\equiv \ast s$ where $s>0$, then there exists some $b_i$ where $b_i\oplus s<b_i$

Idea: Look for the largest power of $2$ in $s#.

$\ast 25+\ast 21+\ast 11=\ast 7$

$11001\oplus 10101\oplus 01011=00111$

$4$ is the largest power of $2$ in the binary expansion of $7$.

This means that at least one of the three numbers has $4$ in its binary expansion ($21$).

Proof of Lemma:

Suppose $s=2^{a_1}+2^{a_2}+\cdots$ where $a_1>a_2>\cdots$. Then $2^{a_1}$ appears in the binary expansions of $b_1,\dots ,b_n$ an odd number of times. Let $b_i$ be one of them. Suppose $\ast b_i+\ast s\equiv \ast t$ for some $t$. Since $2^{a_1}$ is in the binary expansion of $t$. For $2^{a_2},2^{a_3},\dots ,$ at worse none of them are in the binary expansion of $b_i$, so all of them are in the binary expansion of $t$. So $t\le b_i-2^{a_1}+2^{a_2}+2^{a_3}+\cdots <b_i$ since $2^{a_1}>2^{a_2}+2^{a_3}+\cdots$. $■$

Finding winning moves in a winning Nim game: Say a game has nimber $s$. Look at the largest power of $2$ in the binary expansion of $s$. Pair it up with any pile $\ast b_i$ containing this power of $2$. Then $s\oplus b_i<s$. So a winning move is taking away $b_i-(s\oplus b_i)$ chips from the pile $\ast b_i$.

Nim and Nimbers II

We will prove this theorem.

Theorem

Suppose $n=2^{a_1}+2^{a_2}+\cdots$ where $a_1>a_2>\cdots$, then $\ast n=\ast 2^{a_1}+\ast 2^{a_2}+\cdots$

The proof uses the following lemma.

Lemma

Let $0\le p,q<2^a$. Then $p\oplus q<2^a$

Illustration for the proof of the theorem we will prove.

Consider $\ast 7$. $7=4+2+1$. We want to prove $\ast 7=\ast 4+\underset{\equiv \ast 3\text{ by induction}}{\underbrace{\ast 2+\ast 1}}$. Want to show $\ast 7\equiv \ast 4+\ast 3$. Lemma: Show the two sides have equivalent options.

Options of $\ast 7:\ast 0,\ast 1,\dots ,\ast 6$.

Options of $\ast 4+\ast 3$ : 1) Move on $\ast 4$ 2) Move on $\ast 3$.

$\ast 0+\ast 3\equiv \ast 3$

$\ast 1+\ast 3\equiv \ast 2$

$\ast 2+\ast 3\equiv \ast 1$

$\ast 3+\ast 3\equiv \ast 0$

Each of these are less than $4$ (and the results are distinct).

$\ast 4+\ast 2\equiv \ast 6$

$\ast 4+\ast 1\equiv \ast 5$

$\ast 4+\ast 0\equiv \ast 4$

Each power of 2 appears at most once between the two numbers $⟹$ apply induction.

Proof of Theorem:

We prove by induction on $n$. When $n=1,n=2^0$ and $\ast 1\equiv \ast 2^0$.

Suppose $n=2^{a_1}+2^{a_2}+\cdots$ where $a_1>a_2>\cdots$. Let $q=n-2^{a_1}=2^{a_2}+2^{a_3}+\cdots$.

If $q=0$, then $n=2^{a_1}$, so $\ast n\equiv \ast 2^{a_1}$.

Assume $q\ge 1$. Since $q<n$, by induction, $\ast q\equiv \ast 2^{a_2}+\ast 2^{a_3}+\cdots$ it remains to show that $\ast n\equiv \ast 2^{a_1}+\ast q$

The options of $\ast n$ are $\ast 0,\ast 1,\dots ,\ast (n-1)$. The options of $\ast 2^{a_1}+\ast q$ can be partitioned into 2 types.

Consider options of the form $\ast i+\ast q$ where $0\le i<2^{a_1}$. Since $i,q<n$, by induction, the theorem holds for $i,q$. So $\ast i,\ast q$ are equivalent to sums of Nim piles of their binary expansions. Using arguments from the last lecture, $\ast i+\ast q\equiv \ast r_i$ where $r_i=i\oplus q$. Since $i,q<2^{a_1}$, $r_i<2^{a_1}$.

We now show that these $r_i$‘s are distinct. Suppose $r_i=r_j$ for some $i,j$. Then $\ast r_i\equiv \ast r_j$, so $\ast i+\ast q\equiv \ast j+\ast q$. Adding $\ast q$ on both sides, we get $\ast i=\ast j$ (copycat principle), so $i=j$. So the $r_i$‘s are distinct. Also, there are $2^{a_1}$ of these $r_i$‘s, and there are $2^{a_1}$ possible values ($0$ to $2^{a_1}-1$). By pigeonhole, for each $0\le j\le 2^{a_1}-1$, there is one $r_i$ with $r_i=j$. So the options of this type are equivalent to $\{\ast 0,\ast 1,\dots ,\ast (2^{a_1}-1)\}$.

Consider options of the form $\ast 2^{a_1}+\ast i$ where $0\le i<q$. Suppose $i=2^{b_1}+2^{b_2}+\cdots$ where $b_1>b_2>\cdots$. Then no $b_i$ is equal to $a_1$. So $2^{a_1}+2^{b_i}+2^{b_2}+\cdots$ is a sum of distinct powers of $2$.

Then

$$\begin{array}{rl}\ast 2^{a_1}+\ast i& \equiv \ast 2^{a_1}+\ast 2^{b_1}+\ast 2^{b_2}+\cdots \text{by applying induction on }i\\ & \equiv \ast (2^{a_1}+2^{b_1}+2^{b_2}+\cdots )\text{by applying induction on }{2}^{a_1}+i\\ & \equiv \ast (2^{a_1}+i)\end{array}$$

Since $0\le i<q$, the options of this type are equivalent to $\{\ast 2^{a_1},\ast (2^{a_1}+1),\dots ,\ast \underset{n-1}{\underbrace{(2^{a_1}+q-1)}}\}$.

Combining the two types of options, we see that the options of $\ast 2^{a_1}+q$ are equivalent to the options of $\ast n$. So $\ast 2^{a_1}+\ast q\equiv \ast n$.

Sprague-Grundy

So far: All Nim games are equivalent to a Nim game of a single pile. Goal: Extend this to all impartial games.

Poker Nim

Being equivalent does not mean that they play the same way.

Example

$\ast 11+\ast 13\equiv \ast 6$. We move to $\ast 11+\ast 11\equiv \ast 0$ by removing 2 chips from $\ast 13$. RHS remove 6 chips. There are other moves, say we move to $\ast 11+\ast 8\equiv \ast 15$. We remove 5 chips from $\ast 13$. RHS adding 9 chips. Or starting with $\ast 11+\ast 11\equiv \ast 0$, any move on $\ast 11+\ast 11$ will increase $\ast 0$.

A variation on Nim : Poker nim consists of a regular Nim game plus a bag of $B$ chips. We now allow regular Nim moves and adding $B^{\prime }\le B$ chips to one pile.

Example

$\ast 3+\ast 4\to \ast 53+\ast 4$

Question

How does this change the game of Nim?

Nothing. Say we face a losing game, so any regular Nim move would lead to a loss. In poker nim, we now add some chips to one pile. The opposing player will simply remove the chips we placed, and nothing changed.

Mex

Suppose a game $G$ has options equivalent to $\ast 0,\ast 1,\ast 2,\ast 5,\ast 10,\ast 25$. We claim that $G$ is equivalent to $\ast 3$.

The options of $\ast 3$, which are $\ast 0,\ast 1,\ast 2$ are all available. If we add chips to $\ast 3$, then the opposing player can remove them to get back to $\ast 3$.

Question

How do we get 3?

Definition

Given a set of non-negative integers $s$, $mex(s)$ is the smallest non-negative integer not in $s$. “minimum excluded integer”.

Example

$mex(\{0,1,2,5,15,25\})=3$

The $mex$ function is the critical link between any impartial games and Nim games.

Theorem

Let $G$ be an impartial game, and let $s$ be the set of integers $n$ such that there exists an option of $G$ equivalent to $\ast n$. Then $G\equiv \ast (mex(s))$

flowchart LR
a[*1 + *1 + *2]
b[*1 + *2 ≡ *3]
c[*1 + *1 ≡ *0]
d[*1 + *1 + *1 ≡ *1]
a --> b
a --> c
a --> d

By theorem, $\ast 1+\ast 1+\ast 2\equiv \ast (mex(\{0,1,3\}))\equiv \ast 2$

Exercise: A game cannot be equivalent to one of its options.

Proof of above theorem: Let $m=mex(s)$. It suffices to show that $G+\ast m\equiv \ast 0$.

Suppose we move to $G+\ast m^{\prime }$ where $m^{\prime }<m$. Since $m=mex(s)$, there exists an option $G^{\prime }$ of $G$ such that $G^{\prime }\equiv \ast m^{\prime }$. Player 2 moves to $G^{\prime }+\ast m^{\prime }$, which is a losing game since $G^{\prime }\equiv \ast m^{\prime }$. So $G+\ast m$ is a losing game for Player 1, and $G+\ast m\equiv \ast 0$.

Suppose we move to $G^{\prime }+\ast m$, where $G^{\prime }$ is an option of $G$. Then $G^{\prime }\equiv \ast k$ for some $k\in s$. So $G^{\prime }+\ast m\equiv \ast k+\ast m\ne \ast 0$ since $k\ne mex(s)$. So $G^{\prime }+\ast m$ is a winning game for Player 2. Then $G+\ast m$ is a losing game for Player 1, so $G+\ast m\equiv \ast 0$. $■$

Sprague-Grundy Theorem

Any impartial game $G$ is equivalent to a poker nim game $\ast n$ for some $n$.

Proof (slightly sketchy): If $G$ has no options, then $G\equiv \ast 0$. Suppose $G$ has options $G_1,\dots ,G_k$. By induction, $G_i\equiv \ast n_i$ for some $n_i$. By the theorem, $G\equiv (mex(\{n_1,\dots ,n_k\}))$. $■$

Finding Nimo

Finding nimbers is recursive: Games with no options have nimber 0. Move backwards and use $mex$ to determine other nimbers.

Rook Game

$\ast 0$	$\ast 1$	$\ast 2$	$\ast 3$	$\ast 4$
$\ast 1$	$\ast 0$	$\ast 3$	$\ast 2$	$\ast 5$
$\ast 2$	$\ast 3$	$\ast 0$	$\ast 1$	$\ast 6$
$\ast 3$	$\ast 2$	$\ast 1$	$\ast 0$	$R$

Winning move: move to $(4,4)$, an option with nimber 0. This is like a 2-pile Nim game.

Example

Subtraction game (remove 1, 2, or 3 chips). Let $s_n$ be the nimber of a subtraction game with $n$ chips. Then $s_n=mex(\{s_{n-1},s_{n-2},s_{n-3}\})$ (if they exist).

$n$	0	1	2	3	4	5	6	7	8
$s_n$	0	1	2	3	0	1	2	3	0

Losing game if and only if $n\equiv 0(\mathrm{mod}4))$. When $n\not\equiv (\mathrm{mod}4)$, the winning move is remove just enough chips to the next multiple of 4.

Example

Subtraction game (remove 2, 5, or 6 chips). Let $s_n$ be the nimber of a subtraction game with $n$ chips. Then $s_n=mex(\{s_{n-2},s_{n-5},s_{n-36}\})$ (if they exist).

$n$	0	1	2	3	4	5	6	7	8
$s_n$	0	0	1	1	0	2	1	3	0

Losing game if and only if $n\equiv 0,1,4,8(\mathrm{mod}11)$ (repeats every 11)

Example

Combining games. Let $G$ be the rook game at $(4,2)$. Let $H$ be the second subtraction with $n=7$. Then $G\equiv \ast 2$, $H\equiv \ast 3$, so $G+H\equiv \ast 2+\ast 3\equiv \ast 1$ winning game Winning move:

• From $H$, $3\oplus 1=2$. Move to $\ast 2$. Remove 2 chips in the subtraction game
• From $G$, $2\oplus 1=3$. Move to $\ast 3$. Move to $(4,1)$ or $(3,2)$

Strategic Games

Prisoner’s dilemma

Game show version: 2 players won $10,000. They each need to make a final decision: “share” or “steal”

• If both pick “share”, then they each win $5,000
• If one picks “steal” and the other picks “share”, then the one who picks “steal” gets $10,000, the other gets nothing
• If both pick “steal”, then they both get a small consolation price with $10

Question

How would players behave?

The benefit of a player receives is dependent on their own decision and the decisions of other players.

Definition

A strategic game is defined by specifying a set $N=\{1,\dots ,n\}$ of players, and for each player $i\in N$, there is a set of possible strategies $S_i$ to play, and a utility function $u_i:S_i\times \cdots \times S_n\to \mathbb{R}$

Example

With prisoner’s dilemma above, $S_1=S_2\{\text{ share, steal}\}$. Samples of the utility functions $u_1(\text{ share, share })=5000,u_2(\text{ steal, share })=0$. We can summarize the utility functions in a payoff table.

	share	steal
share	5k, 5k	0, 10k
steal	10k, 0	10, 10

Each cell records the utilities of Player 1, Player 2 in this order given the strategies played in that row (P1) and column (P2).

Assumptions about strategic games:

• All players are rational and selfish (want to maximize their own utility)
• All players have knowledge of all game parameters
• All players move simultaneously
• Player $i$ plays a strategy $s_i\in S_i$, this forms a strategy profile $s=(s_1,\dots ,s_n)\in S_1\times \cdots \times S_n$. Player $i$ earns $u_i(s)$.

Question

Given a strategic game, what are we looking for?

One answer is we want to know how are the players expected to behave?

Resolving prisoner’s dilemma

Question

What would a rational and selfish player choose to play?

1. If you know that the other player chooses “share”, then choosing “share” gives 5k, choosing “steal” gives 10k. Steal is better.
2. If you know that the other player chooses “steal”, then choosing “share” gives 0, choosing “steal” gives 10. Steal is better.

In both cases, it is better to steal than to share. So we expect both players to choose “steal”.

This is an example of a strictly dominating strategy : regardless of how other players behave, this strategy gives the best utility over all other possible strategies. If a strictly dominating strategy exists, then we expect the players to play it.

In this case, playing a strictly dominating strategy “steal” yields very little benefit. They could get more if there is some cooperation (both share). So even though we expect strictly dominating strategy is played, it might not have the best “social welfare” (the overall utility of the players).

Nash Equilibrium

There are many games with no strictly dominating strategies.

Example

Bach or Stravinsky? Two players want to go to a concert. Player 1 likes Bach, Player 2 likes Stravinsky, but they both prefer to be with each other. Payoff table:

	Bach	Stravinsky
Bach	2, 1	0, 0
Stravinsky	0, 0	1, 2

No strictly dominating strategy exists. What do we expect to happen? If both choose “Bach”, then there is no reason for one player to switch their strategy (which gives utility 0). Similar if both choose “Stravinsky”.

These are steady states, which we call Nash equilibria : a strategy where no player is incentivized to change strategy.

There are many games with “no” Nash equilibria.

Example

Rock Paper Scissors

$R$ beats $S$, $S$ beats $P$, $P$ beats $R$. Utility 1 if they win, -1 if they lose, 0 if they tie.

”no” NE exists : regardless of what they play, someone is incentivized to switch strategy so that they win.

Question

How would we expect players to play this?

Randomly, probability $\frac{1}{3}$ each. This is a mixed strategy. it is also a NE, there is no incentive to change to a different probability distribution.

Nash's Theorem

Every strategic game with finite number of strategies has a Nash equilibrium (could be mixed strategies).

Nash Equilibrium and the Best Response Function

Recall: Strategic game is defined by

• Players $N=\{1,\dots ,n\}$
• Strategy set $S_i$ for player $i$
• Utility for player $i$ $u_i:S_1\times \cdots \times S_n\to \mathbb{R}$

A strategy profile is a vector $s=(s_1,\dots ,s_n)\in S_1\times \cdots \times S_n$ which records what the players played.

Let $S=S_1\times \cdots \times S_n$ be the set of all strategy profile. We will often compare the utilities of a player’s strategies when we fix the strategies of the remaining players. Let $S_i$ be the set of all strategy profiles of all players except player $i$ (we drop $S_i$ from the cartesian product $S_1\times \cdots \times S_n)$. If $s\in S$, then the profile obtained from $s$ by dropping $s_i$ is denoted $s_{-i}\in S_{-i}$. If player $i$ switches their strategy from $s$ to $s_{i^{\prime }}$, then the new strategy profile is denoted $(s_i^{\prime },s_{-i})\in S$

Nash equilibrium

Recall: NE is a strategy profile where no player is incentivized to switch strategy.

Definition

A strategy profile $s\ast \in S$ is a Nash equilibrium if $u_i(s\ast )\ge u_i(s_i^{\prime },s_{-1}^{\ast })\forall s_i^{\prime }\in S_i$ and $\forall i\in N$.

Back to Prisoner’s dilemma.

Let $s\ast =(\text{ steal, steal })$

From Player 1: $u_1(s\ast )=10,u_1(\underset{s_1^1}{\underbrace{\text{share}}},\underset{s_{-1}^{\ast }}{\underbrace{\text{steal}}})=0<u_1(s\ast )$ Similar for Player 2. So $s^{\ast }$ is a NE.

Example

Guessing $2/3$ average game. 3 players, a positive integer $k$. Each player simultaneously pick an integer from $\{1,\dots ,k\}$, producing the strategy profile $s=(s_1,s_2,s_3)$. There is $1 which is split among all players whose choices are closest to $\frac{2}{3}$ of the average of the 3 numbers. Other players get $0.

Question

If $s=(5,2,4)$, then the average is $\frac{11}{3}$, and $\frac{2}{3}$ average is $2+\frac{4}{9}$. Player 2 is the closest, so $u_2(s)=1,u_1(s)=u_3(s)+0$. Is $s$ a NE?

No. If Player 1 switches to 2, then $u_1(2,s_{-1})=u_1(2,2,4)=\frac{1}{2}$.

Question

Is there a NE?

Idea: Lowering the guess generally pulls the $\frac{2}{3}$ average closer. Try $(1,1,1)$. If a player switches to $t\ge 2$, then the $\frac{2}{3}$ average is $\frac{4+2t}{9}=\frac{4}{9}+\frac{2}{9}t$, which is closer to 1 than $t$.

Best Response Function (BRF)

For a NE, a player does not want to switch. If you fix the strategies of the remaining players, then you play a strategy that maximizes utility for yourself, i.e. $k$ is a “best response” to the fixed strategies.

Definition

Player $i$‘s best response function for $s_{-i}\in S_{-i}$ is given by $B_i(s_{-i})=\{s_i^{\prime }\in S_i:\underset{\text{utility of a best response}}{\underbrace{u_i(s_i^{\prime },s_{-i})}}\ge \underset{\text{utility of all possible responses}}{\underbrace{u_1(s_i,s_{-i})}}\forall s_i\in S_i\}$

Example

Prisoner’s dilemma. $B_1(\text{share})=\{\text{steal}\}$, $B_1(\text{steal})=\{\text{steal}\}$

If $s^{\ast }$ is a NE, then each player $i$ must have played a best response to $s_{-i}^{\ast }$. Changing $s_i^{\ast }$ cannot increase utility for $i$. Converse is also true.

Lemma

$s^{\ast }\in S$ is a Nash equilibrium if and only if $s_i^{\ast }\in B(s_{-1}^{\ast })$ for all $i\in N$.

This lemma helps us find NE by looking for strategies in the BRF.

Cournot’s Oligopoly Model

We have a set of $N=\{1,\dots ,n\}$ of $n$ firms producing a single type of goods sold on the common market. Each firm $i$ needs to decide the number of units of good $q_i$ to produce.

Production cost is $C_i(q_i)$ where $C_i$ is a given increasing function.

Given a strategy profile $q=(q_1,\dots ,q_n)$, a unit of the goods sell for the price of $P(q)$, where $P$ is a given non-increasing function on ${\sum }_i{q}_i$ (more goods on the market = lower price)

The utility of firm $i$ in the strategy profile $q$ is $u_i(q)=\underset{\text{revenue for selling }{q}_i\text{ units}}{\underbrace{q_{i}P(q)}}-\underset{\text{production cost}}{\underbrace{C_i(q_i)}}$

Szidarovszky and Yakowitz proved that a Nash equilibrium always exists under some continuity and differentiability assumptions on $P,C$.

Special case: Linear costs and prices

Suppose we assume

$C_i(q_i)=c{q}_i\forall i\in N$ (the cost is linear, same unit cost $c$ for all firms)

$P(q)=\max \{0,\alpha -{\sum }_j{q}_j\}$ (prices starts at $\alpha$, decreases 1 for each unit produced, min price $0$) where $0<C<\alpha$.

Utility is

$$\begin{array}{r}{u}_i(q)=q_{i}P(q)-C_i(q_i)=\{\begin{array}{ll}{q}_i(\alpha -c-{\sum }_j{q}_j)& \alpha -{\sum }_j{q}_j\ge 0\\ -c{q}_i& \alpha -{\sum }_j{q}_j<0)\end{array}\end{array}$$

Question

When is it possible to make a profit?

When $\alpha -c{\sum }_j{q}_j>0$. Separate $q_i$ from the sum: $\alpha -c-q_i-{\sum }_{i\ne j}{q}_j>0$. So $q_i<\alpha -c-{\sum }_{j\ne i}{q}_j$. Does not make sense for $q_i$ if RHS $\le 0$, so assume RHS $>0$.

The utility is $q_i(\alpha -c-q_i-{\sum }_{j\ne i}{q}_j)$. Treating $q_i$ as the variable, this utility is maximized when $q_i=\left(\alpha -c-{\sum }_{j\ne i}{q}_j)\right)/2$ (use calculus). So the best response function for firm $i$ given the production of other firms $q_{-i}$ is

$$\begin{array}{r}{B}_i(q_{-1})=\{\begin{array}{ll}\{\alpha -c-{\sum }_{j\ne i}{q}_j)/2\}& \alpha -c-{\sum }_{j\ne i}{q}_j>0\\ \{0\}& \text{otherwise}\end{array}\end{array}$$

Two-firm case

Suppose we simplify to 2 firms. Suppose $q^{\ast }=(q_1^{\ast },q_2^{\ast })$ is a Nash equilibrium. By previous lemma, a player’s choice must be the best response to the other player’s choice. So $q_1^{\ast }\in B_1(q_2^{\ast })$ and $q_2^{\ast }\in B_2(q_1^{\ast })$.

Verify that we may assume $q_1^{\ast },q_2^{\ast }>0$. Then $q_1^{\ast }=(\alpha -c-q_2^{\ast })/2$ and $q_2^{\ast }=(\alpha -c-q_1^{\ast })/2$.

Solving this gives $q_1^{\ast }=q_2^{\ast }=(\alpha -c)/3$. This is the answer we expect each firm to produce at equilibrium.

Price at equilibrium: $P(q^{\ast })=\alpha -q_1^{\ast }-q_2^{\ast }=\alpha \frac{2}{3}(\alpha -c)=\frac{\alpha }{3}+\frac{2c}{3}$

Profit at equilibrium: $u_i(q^{\ast })=q_i^{\ast }(\alpha -c-q_1^{\ast }-q_2^{\ast })=(\alpha -c{)}^2/9$

Note 1: Suppose the two firms can collude, and together they produce $Q$ units total. Total profit is $Q(\alpha -c-Q)$, which is maximized at $Q=(\alpha -c)/2$. The profit is $\left(\frac{\alpha -c}{2}\right)\left(\alpha -c-\frac{\alpha -c}{2}\right)=(\alpha -c{)}^2/4$. Each firm gets $\frac{(\alpha -c{)}^2}{8}>\frac{(\alpha -c{)}^2}{9}$

Note 2: In the general case with $n$ firms, if $q^{\ast }$ is a NE, then $q_i^{\ast }=(\alpha -c-{\sum }_{j\ne i}{q}_j^{\ast })/2$. Solving this system gives $q_i^{\ast }=\frac{\alpha -c}{n+1}$.

Price is $P(q^{\ast })=\alpha -{\sum }_j{q}_j^{\ast }=\alpha -\frac{n}{n+1}(\alpha -c)=\frac{1}{n+1}\alpha +\frac{n}{n+1}c$.

As $n\to \infty ,P(q^{\ast })\to C$. As more firms are involved, the expected market price gets closer to the production cost.

Strict Dominance

Definition

For two strategies $s_i^{(1)},s_i^{(2)}\in S_i$ for player $i$, we say that $s_i^{(1)}$ strictly dominates $s_i^{(2)}$ if for all $s_{-i}\in S_{-i}$, $u_i(s_i^{(1)},s_{-i})>u_i(s_i^{(2)},s_{-i})$

Definition

If there exists a strategy that strictly dominates $s_i$, then $s_i$ is strictly dominated.

Definition

If $s_i$ strictly dominates all strategies $s_i^{\prime }\in S_i\setminus \{s_i\}$, then $s_i$ is a strictly dominating strategy.

In prisoner’s dilemma, “steal” is a strictly dominating strategy for both players.

Lemma

If $s_i\in S_i$ is a strictly dominating strategy for player $i$ and $s^{\ast }\in S$ is a Nash equilibrium, then $s_i^{\ast }=s_i$.

In any NE, the strictly dominating strategy is played whenever it exists. A game easy to play if such a strategy exists.

We now look at strictly dominated strategies.

	X	Y	X
A	4,2	1,3	2,1
B	2,3	0,1	3,1

$Z$ is strictly dominated by $X$ since $u_2(A,X)>u_2(A,Z)$ and $u_2(B,X)>u_2(B,Z)$.

$Z$ is a strictly dominated strategy: There is no reason to play it.

Lemma

If $s^{\ast }\in S$ is a Nash equilibrium, then $s_i^{\ast }$ is not strictly dominated for any $i\in N$.

Iterated Elimination of Strictly Dominated Strategies (IESDS): Repeatedly eliminate strictly dominated strategies until we have only one strategy profile. We claim that if this works, then the surviving profile is the unique NE of the game.

Example

Facility location game. Two firms are each given a permit to open one store in one of 6 towns along a highway. (Stores are on a line from $A\to F$) Firm 1 can open in $A$, $C$, or $E$, Firm 2 can open in $B$, $D$, or $F$. Assume towns are equally spaced and equally populated. Customers in a town will go to the closest store.

Question

Where to open the stores?

Payoff Table:

	B	D	F
A	1,5	2,4	3,3
C	4,2	3,3	4,2
E	3,3	2,4	5,1

Firm 1: $A$ is strictly dominated by $C$

Firm 2: $F$ is strictly dominated by $D$

Eliminate these two strategies.

	B	D
C	4,2	3,3
E	3,3	2,4

Firm 1: $E$ is strictly dominated by $C$

Firm 2: $B$ is strictly dominated by $D$

Eliminate these two strategies.

	D
C	3,3

$(C,D)$ is a NE.

Note: Extend this to 1000 towns with alternating points. The two ends are strictly dominated by the centre towns. Eliminate them to get 998 towns. Repeat. End with the two towns in the centre as NE.

Theorem

Suppose $G$ is a strategic game. If IESDS ends with only one strategy profile $s^{\ast }$, then $s^{\ast }$ is the unique Nash equilibrium of $G$.

This is a consequence of the following result.

Theorem

Let $G$ be a strategic game where $s_i$ is a strictly dominated strategy for player $i$. Let $G^{\prime }$ be obtained from $G$ by removing $s^{\ast }$ from $S_i$. Then $s^{\ast }$ is a Nash equilibrium of $G$ if and only if $s^{\ast }$ is a Nash equilibrium of $G^{\prime }$.

Proof Sketch:

$(⟹)$

Suppose $s^{\ast }$ is a NE of $G$. Since $s_i$ is strictly dominated, it cannot appear in $s^{\ast }$ (lemma). So $s^{\ast }$ is a valid strategy profile in $G^{\prime }$. If $s^{\ast }$ is not a NE of $G^{\prime }$, then a player can deviate to get a higher utility. However, all strategies in $G^{\prime }$ are available in $G$, so such a player can do it in $G$ as well. This contradicts $s^{\ast }$ is a NE of $G$.

$(⟸)$

Suppose $s^{\ast }$ is a NE of $G^{\prime }$. Suppose $s^{\ast }$ is not a NE in $G$. Then a player can deviate to get a higher utility. This can be replicated in $G^{\prime }$ (which results in a contradiction) unless it is player $i$ switching to strategy $s_i$ (the only strategy in $G$ not in $G^{\prime }$). Then player $i$ could switch to the strategy that strictly dominates $s_i$ (available in $G$) to get a higher utility in $G^{\prime }$. This contradicts $s^{\ast }$ is a NE in $G^{\prime }$. $■$

Weak Dominance

Definition

For two strategies $s_i^{(1)},s_i^{(2)}\in S_i$ for player $i$, we say that $s_i^{(1)}$ weakly dominates $s_i^{(2)}$ if for all $s_{-i}\in S_{-i}$, $u_i(s_i^{(1)},s_{-i})\ge u_i(s_i^{(2)},s_{-i})$, and this inequality is strict for at least one $s_{-i}\in S_{-i}$

If some strategy weakly dominates $s_i$, then $s_i$ is weakly dominated.

If $s_i$ weakly dominates all strategies $s_i^{\prime }\in S_i\setminus \{s_i\}$, then $s_i$ is a weakly dominating strategy.

Iterated elimination of weakly dominated strategies (IEWDS): Remove weakly dominated strategies until there is only one strategy profile.

Theorem

Suppose $G$ is a strategic game. If IEWDS ends with only one strategy profile $s^{\ast }$, then $s^{\ast }$, is a Nash equilibrium of $G$.

Compared with a previous theorem, here we can no longer claim that the NE is unique. A different sequence of eliminations can result in a different NE.

Unlike strictly dominated strategies, weakly dominated strategies can appear in a NE. Some NE cannot be found through IEWDS.

Just like strictly dominating strategies, weakly dominating strategies are good to play.

Lemma

If for all players $i$, $s_i^{\ast }$ is a weakly dominating strategy, then $s^{\ast }$ is a Nash equilibrium.

Auctions

Set up of an auction: A seller puts one item up for an auction. Potential buyers put in bids to buy the item. Seller decides who wins (usually highest bidder) and the price they pay.

Typical auction: Open bid auctions. Buyers bid repeatedly until no one else bids. Highest bid wins and pays their bid price.

Another type: Closed bid auctions. Each buyer submits one secret bid to the seller.

First price auction: Highest bid wins, winner pays their bid.

Question

Does this simulate an open auction?

No, in the open auction setting, the winner will bid slightly over 150 and win, so they pay $\approx$ 150.

Second price auction: Highest bid wins, winner pays 2nd highest bid.

We will analyze the second price closed bid auction.

Set up: We have buyers $N=\{1,\dots ,n\}$. Buyer $i$ thinks the item has value $v_i$ “valuation”.

Suppose buyer $i$ submits the bid $b_i$, giving strategy profile $b=(b_1,\dots ,b_n)$. The winner is the buyer who submits the highest bid, pays price equal to second highest bid. If there is a tie, then the winner is the buyer with the lowest index $i$ among all tied buyers.

Given a strategy profile $b$, the utility for buyer $i$ is

$$\begin{array}{r}{u}_i(b)=\{\begin{array}{ll}{v}_i-{\max }_{j\ne i}{b}_j& i\text{ wins in }b\\ 0& \text{otherwise}\end{array}\end{array}$$

Suppose your valuation of the item is 100. Would you bid anything other than 100?

1. Say your bid wins (second highest bid 75, your bid 100)

If you pay more than $x>100$ or $75<x<100$, you still win, pay 75, and utility is 25. If we pay less than 75, we lose and utility is 0.

2. Say your bid loses (you bid 100, highest bid is 121)

If you bid less than 121, you lose, and utility is 0. If you pay more than 121, you win, pay 121, and utility is $-21$.

Utility does not increase if you bid anything else.

Theorem

In the second price auction, $v_i$ is a weakly dominating strategy for player $i\in N$.

Proof:

We first show that $u_i(v_i,b_{-i})\ge u_i(b_i,b_{-i})$ for all $b_i\in S_i$ and $b_{-i}\in S_{-i}$. There are 2 cases.

First case: $v_i$ is a winning bid in $(v_i,b_{-i})$. Let $b_j$ be the second highest bid (could equal $v_i$). The utility for player $i$ is $u_i(v_i,b_{-i})=v_i-b_j\ge 0$. Suppose player $i$ changes their bid to $b_i$. If $b_i<b_j$ or ($b_i=b_j$ and $i<j$), then $b_i$ is still the winning bid in $(b_i,b_{-i})$. Payment is $b_j$, so utility remains the same. Otherwise, $b_i$ is a losing bid, so the utility is $0$, which is at most $u_i(v_i,b_{-i})$. So $u_i(v_i,b_{-i})\ge u_i(b_i,b_{-i})$ for any $b_i$

Second case: $v_i$ is a losing bid in $(v_i,b_{-i})$. Let $b_j$ be the winning bid (so $b_j\ge v_i)$. The utility for player $i$ is $u_i(v_i,b_{-i})=0$. Suppose player $i$ changes their bid to $b_i$. If $b_i<b_j$. If $b_i<b_j$ or ($b_i=b_j$ and $i>j$), then $b_i$ is still a losing bid in $(b_i,b_{-i})$. Utility is still $0$. Otherwise, $b_i$ is a winning bid, with payment $b_j$. The utility is $u_i(b_i,b_{-i})=v_i-b_j\le 0$ (since $b_j\le v_i$).

So $u_i(v_i,b_{-i})\ge u_i(b_i,b_{-i})$ for any $b_i$.

In both cases, bidding $v_i$ gives the highest utility among all possible bids of player $i$.

We still need to show that for all $b_i\ne v_i$, there exists $b_{-i}\in S_{-i}$ such that $u_i(v_i,b_{-i})$. Two cases:

First case: Suppose $b_i<v_i$. Let $k$ be in $b_i<k<v_i$. Set $b_j=k$ for all $j\ne i$. When $v_i$ is played against $b_{-i}$, player $i$ wins $(v_i>k)$ and pays $k$. Utility $u_i(v_i,b_{-i})=v_i-k>0$. When $b_i$ is played against $b_{-i}$, player $i$ loses $(b_i<k)$, and utility $u_i(b_i,b_{-i})=0$. So $u_i(v_i,b_{-i})>u_i(b_i,b_{-i})$.

Second case: Suppose $b_i>v_i$. Let $k$ be in $v_i<k<b_i$. Set $b_j=k$ for all $j\ne i$. When $v_i$ is played against $b_{-i}$, player $i$ loses $(v_i<k)$ and utility $u_i(v_0,b_{-i})=0$. When $b_i$ is played against $b_{-i}$, player $i$ wins $(b_i>k)$ and pays $j$. Utility $u_i(b_i,b_{-i})=v_i-k<0$. So $u_i(v_i,b_{-i})>u_i(b_i,b_{-i})$.

Therefore, playing $v_i$ is a weakly dominating strategy. $■$

Note: The way we play this game does not depend on knowing how other players value the item. So it is easy to play: simply bid your valuation.

Suppose buyer 1 has highest valuation $v_1$, and buyer 2 has second highest valuation $v_2$. Then $(v_2,v_1,0,0,\dots ,0)$ is a NE.

Mixed Strategies

Example

Matching Pennies: Two player each has a penny. They simultaneously show heads or tails. If they match, then player 1 gains the penny from player 2. If they don’t match, then player 2 gets the penny from player 1.

There is no Nash equilibrium here. We can allow players to play this probabilistically. For example, PI might play $H$ $\frac{1}{3}$ of the time, and play $T$ $\frac{2}{3}$ of the time. Player 2 might play $\frac{3}{4}$ on $H$, $\frac{1}{4}$ on $T$.

Question

Is there an equilibrium here?

If player 1 plays $\frac{1}{3}$ $H$, $\frac{2}{3}$ $T$, then player 2 wants to play $H$ more often than $T$. Then player 1 wants to play $H$ more often than $T$. Then player 2 wants to play $T$ more often than $H$, etc.

Seems that it is stable only if both players play $\frac{1}{2}$ $H$, $\frac{1}{2}$ $T$.

Definition

A mixed strategy for player $i$ is a vector $x^i\in {\mathbb{R}}_{+}^{s_i}$ such that ${\sum }_{s\in S_i}{x}_s^i=1$. The set of all mixed strategies for player $i$ is denoted ${\Delta }^i$.

Definition

A mixed strategy profile is a vector $x=(x^1,\dots ,x^n)$ where $x^i\in {\Delta }^i$ is a mixed strategy for player $i$. The set of all mixed strategy profiles is denoted $\Delta ={\Delta }^1\times \cdots \times {\Delta }^n$. The mixed strategy profile with player $i$ removed is $x^{-iT}\in {\Delta }^{-i}$.

If we play a strategy with probability 1, then it is a pure strategy. As convention for this course, we use $s$‘s to represent pure strategies, $x$‘s represent mixed strategies.

Example

In matching pennies, if we order the pure strategies in the order $H,T$, then we had $x^{\prime }=(x_H^1,x_T^1)=(\frac{1}{3},\frac{2}{3})$, $x^2=(x_H^2,x_T^2)=(\frac{3}{4},\frac{1}{4})$ as mixed strategies. The strategy profile is $x=(x^1,x^2)=((\frac{1}{3},\frac{2}{3}),(\frac{3}{4},\frac{1}{4}))$.

Question

Why mixed strategies?

To introduce unpredictability in games that are played repeatedly. E.g. you do not always want to make major political announcements on Tuesdays.

Think of a player as representing a population, with probability of a strategy being proportional to the portion of the population who prefer it. Say 55% like donkeys and 45% like elephants, perhaps there will be more donkeys in zoos.

Utility

We will use expected value as utility.

Two cases for player 1:

1. If player $1$ plays $H$ as a pure strategy, then $\frac{3}{4}$ chance we get 1, $\frac{1}{4}$ chance we get $-1$. We expect to get $\frac{3}{4}\cdot 1+\frac{1}{4}\cdot (-1)=\frac{1}{2}$.
2. If player 1 plays $T$ as a pure strategy, then $\frac{3}{4}$ chance we get $-1$, $\frac{1}{4}$ chance we get $1$. We expect to get $\frac{3}{4}(-1)+\frac{1}{4}\cdot 1=-\frac{1}{2}$.

Overall, player 1 plays $H$ $\frac{1}{3}$ of the time and $T$ $\frac{2}{3}$ of the time. So the expected utility is $\frac{1}{3}\cdot (\frac{1}{2})+\frac{2}{3}\cdot (-\frac{1}{2})=-\frac{1}{6}$.

Definition

We are given a strategy profile $x=(x^1,\dots ,x^n)\in \Delta$. The expected utility of a pure strategy $s_i\in S_i$ for player $i$ is

$$\begin{array}{r}{u}_i(s_i,x^{-i})=\sum _{s_{-i}\in S_{-i}}\stackrel{\text{utility from pure strategy }{s}_i}{\overbrace{u_i(s_i,s_{-i})}}\underset{\text{probability that the remaining players play }{s}_{-i}}{\underbrace{\prod _{j\ne i}{x}_{s_j}^j}}\end{array}$$

Definition

The expected utility of player $i$ in $x$ is

$$\begin{array}{r}{u}_i(x)=\sum _{s_i\in S_i}\stackrel{\text{prob that p1 plays }{s}_i}{\overbrace{x_{s_i}^i}}\underset{\text{utility p1 gets for playing }{s}_i}{\underbrace{u_i(s_i,x^{-i})}}\end{array}$$

In the matching pennies example, $u_1(H,x^2)=\frac{1}{2}$, $u_1(T,x^2)=-\frac{1}{2}$, $u_1(x)=-\frac{1}{6}$.

Example

Suppose 3 players each make a choice between $A$ and $B$. A $1 prize is split among players who pick the majority choice. Suppose $x^1=(p,1-p)$, $x^2=(\frac{1}{2},\frac{1}{2})$, $x^3=(\frac{3}{5},\frac{3}{5})$. What is the expected utility for player 1?

When player 1 plays $A$, there are 4 cases:

1. $u_1(A,A,A)=\frac{1}{3}$. The probability this happens is $x_A^2\cdot x_A^3=(\frac{1}{2})(\frac{2}{5})=\frac{1}{5}$
2. $u_1(A,A,B)=\frac{1}{2}$. The probability this happens is $x_A^2\cdot x_B^3=(\frac{1}{2})(\frac{3}{5})=\frac{3}{10}$
3. $u_1(A,B,A)=\frac{1}{2}$. The probability this happens is $x_B^2\cdot x_A^3=(\frac{1}{2})(\frac{2}{5})=\frac{1}{5}$
4. $u_1(A,B,B)=0$. Does not matter.

Utility for playing $A$ is $u_1(A,x^{-1})$ $=(\frac{1}{5})(\frac{1}{3})+(\frac{3}{10})(\frac{1}{2})+(\frac{1}{5})(\frac{1}{2})+0=\frac{19}{60}$.

Check: $u_1(B,x^{-1})=\frac{7}{20}$.

Expected utility for player 1 is $u_1(x)=p\cdot \frac{19}{60}+(1-p)\cdot \frac{7}{20}=\frac{7}{20}-\frac{1}{15}p$.

Player 1 always plays $B$. Player 3 is more likely to pick $B$, letting us form a majority more often.

Mixed Equilibria

Definition

A mixed strategy profile $\bar{x}\in \Delta$ is a mixed Nash equilibrium if for each player $i\in N$, $u_i(\bar{x})\ge u_i(x^i,{\bar{x}}^{-i})$ for all $x^i\in {\Delta }^i$.

Definition

Given a profile ${\bar{x}}^{-i}\in {\Delta }^{-i}$, the best response function for player $i$, $B_i({\bar{x}}^{-i})$, is the set of all mixed strategies of player $i$ that have maximum utility against ${\bar{x}}^{-i}$, i.e. $B_i({\bar{x}}^{-i})=\{{\bar{x}}^i\in {\Delta }^i:u_i({\bar{x}}^i,{\bar{x}}^{-i})\ge u_i(x^i,{\bar{x}}^{-i})\forall x^i\in {\Delta }^i\}$.

Proposition: $\bar{x}=({\bar{x}}^1,\dots ,{\bar{x}}^n)\in \Delta$ is a Nash equilibrium if and only if ${\bar{x}}^i\in B_i({\bar{x}}^{-i})$ for all $i\in N$.

Back to the matching pennies example.

Suppose $x^1=(p,1-p)$ and $x^2=(q,1-q)$.

For player 1, the expected utility for playing $H$ is $q\cdot 1+(1-q)\cdot (-1)=2q-1$. The expected utility for playing $T$ is $q\cdot (-1)+(1-q)\cdot 1=1-2q$. Utility for player 1 is $p\cdot (2q-1)+(1-p)(1-2q)=p(-2+4q)+(1-2q)$.

Question

Given $q$, which $p$ maximizes this utility?

$1-2q$ is constant, so we maximize $p(-2+4q)$. There are 3 cases:

1. If $q<\frac{1}{2}$, then $-2+4q<0$. So we maximize with $p=0$.
2. If $q=\frac{1}{2}$, then $-2+4q=0$. Then any $p$ maximizes if, so $p\in [0,1]$.
3. If $q>\frac{1}{2}$, then $-2+4q>0$. Maximize with $p=1$.

BRF for player 1:

$$\begin{array}{r}{B}_1(x^2)=\{\begin{array}{ll}\{(0,1)\}& q<\frac{1}{2}\\ \{(p,1-p):p\in [0,1]\}& q=\frac{1}{2}\\ \{(1,0)\}& q>\frac{1}{2}\end{array}\end{array}$$

For player 2, the utility is $q(2-4p)+(2p-1)$. Divide cases with $p=\frac{1}{2}$. When $p<\frac{1}{2}$, $2-4p>0$, so we want $q=1$. Check remaining cases

$$\begin{array}{r}{B}_2(x^1)=\{\begin{array}{llc}\{(1,0)\}& p<\frac{1}{2}& \\ \{(q,1-q):q\in [0,1]\}& p=\frac{1}{2}& \\ \{(0,1)\}& p>\frac{1}{2}& \end{array}\end{array}$$

We look for $p$, $q$ such that $x^1,x^2$ are best responses to each other.

The intersection on the graph is where they are best responses simultaneously, hence a Nash equilibrium. $x^1=(\frac{1}{2},\frac{1}{2})$, $x^2=(\frac{1}{2},\frac{1}{2})$, and $(x^1,x^2)$ is a NE.

Support Characterization

Recall that BRF maximizes a player’s utility, $u_i(x)={\sum }_{s\in S_i}{x}_s^i{u}_i(s,x^{-i})$.

Suppose ${\bar{x}}^{-i}$ is fixed. Which $x^i\in {\Delta }^i$ maximizes $u_i(x^i,{\bar{x}}^{-i})$? We write a LP:

$$\begin{array}{rl}\max & \sum _{s\in S_i}{x}_s^i{u}_i(s,{\bar{x}}^{-i})\\ s.t.& \sum _{s\in S_i}{x}_s^i=1(P)\\ & x^i\ge 0\end{array}$$

Variables: $x_s^i$ for each $s\in S_i$. What is the dual? One dual variable $y$.

$$\begin{array}{rl}& \min Y\\ & s.t.y\ge u_i(s,{\bar{x}}^{-i})\forall s\in S_i(D)\end{array}$$

$(P)$ is feasible. $(D)$ is feasible. Therefore, $(P)$ and $(D)$ both have optimal solutions, and their optimal values are equal.

$(D)$ is easy to solve: $y={\max }_{s\in S_i}{u}_i(s,{\bar{x}}^{-i})$, maximum utility when pure strategies are played against ${\bar{x}}^{-i}$. $(P)$ also has optimal value $y$. So the maximum utility of all mixed strategies is equal to the max utility of pure strategies.

Complementary slackness conditions: $x_s^i=0$ or $y=u_i(s,{\bar{x}}^{-i})$ for all $s\in S_i$.

Equivalently, $x_s^i>0$ implies $y=u_i(s,{\bar{x}}^{-i})$. Translation: only pure strategies with maximum utility could have positive probabilities in a best response.

Theorem

Support characterization: Given ${\bar{x}}^{-i}\in {\Delta }^{-i}$, a mixed strategy $x^i\in B_i({\bar{x}}^{-i})$ if and only if $x_s^i>0$ implies $s\in S_i$ is a pure strategy of maximum utility against ${\bar{x}}^{-i}$.

Definition

For a mixed strategy $x^i\in {\Delta }^i$, the support is the set of strategies with positive probability in $x^i$.

Rephrase Theorem

$x^i$ is in the BRF if and only if the support of $x^i$ are strategies with maximum utility.

Example

Consider a 2-player game with this payoff table.

	D	E	F
A	2,2	3,3	1,1
B	3,1	0,4	2,1
C	3,4	5,1	0,7

Suppose player 2 plays $x^2=(0,\frac{1}{3},\frac{2}{3})$. What is $B_1(x^2)$?

$u_1(A,x^2)=\frac{5}{3}$, $u_1(B,x^2)=\frac{4}{3}$, $u_1(c,x^2)=\frac{5}{3}$.

By support characterization, $x_B^1=0$. Any distribution over $x_A^1$, and $x_C^1$ works. So $B_1(x^2)=\{(p,0,1-p):p\in [0,1]\}$.

The maximum utility for player 1 is $p\cdot \frac{5}{3}+(1-p)\cdot \frac{5}{3}+\frac{5}{3}$, which is equal to the max utility for a pure strategy.

Any strategy in $B_1(x^2)$ maximizes utility for player 1. Which of these maximizes utility for player 2? This will give a NE. Suppose $x^1=(p,0,1-p)$. calculate the utilities for player 2: $u_2(D,x^1)=4-2p$, $u_2(E,x^1)=1+2p$, $u_3(F,x^1)=7-6p$. If $x^2=(0,\frac{1}{2},\frac{2}{3})$ is in the best response, then $E$, $F$ must have maximum utility. $1+2p=7-6p$, so $p=\frac{3}{4}$.

Utility for $E$, $F$ is $\frac{5}{2}$. Utility for $D$ is also $\frac{5}{2}$, so indeed $E$, $F$ have max utility. So $x^1=(\frac{3}{4},0,\frac{1}{4})$ and $x^2=(0,\frac{1}{3},\frac{2}{3})$ are in the best responses for each other, and $(x^1,x^2)$ is a NE.

Voting Game

Downs paradox: Voting has costs. The probability that one vote is a decisive vote is very small. The costs outweigh the benefits. The expectation is that people do not vote. In reality, people do vote.

Model for voter participation: Suppose there are two candidates $A$, $B$ and the number of supporters are $a$, $b$ respectively. WLOG, assume $a\ge b$. Each person can choose to vote or abstain. If they vote, then they can incur a cost of $c$, where $0<c<1$. Regardless of voting or abstaining, each person gets a payoff of 2 if their supporting candidate wins, 1 for a tie, 0 for a loss.

Pure NE: Suppose $a=b=1$.

	A	V
A	$1,1$	$0,2-c$
V	$2-c,0$	$1-c,1-c$

Prisoner’s dilemma: Both players vote, get lower utility than both players abstaining.

Suppose $a=b\ge 2$. 4 cases:

1. Everyone votes. There is a tie, everyone has utility $1-c$, switching gives 0. NE.
2. Not everyone votes, and there is a tie. One who abstains can vote, $1\to 2-c>1$. Not NE.
3. One candidate wins by 1 vote. One who abstains for the losing candidate can vote, $0\to 1-c>0$. Not NE.
4. One candidate wins by at least 2 votes. One who votes for the winning candidate can abstain, $2-c\to 2$. Not NE.

In a close election, we expect more people to vote.

Mixed Nash equilibrium: One possible scenario for a mixed NE.

Suppose $a>b$. Among all $A$ supporters, $b$ of them will vote and $a-b$ of them will abstain. Suppose every $B$ supporter will vote with the same probability $p$. So the best that $B$ can do is tie. It is easy to check that $p=0$ or 1 is not a NE. Assume $p\in (0,1)$.

Consider a $B$ supporter. If they abstain, then $B$ cannot win. So utility of abstain as pure strategy is $0$. If they vote, then $B$ ties only if all other $B$ supporters vote (utility $1-c$), otherwise $B$ loses (utility $-c$). Expected utility of “vote” as a pure strategy is $p^{b-1}(1-c)+(1-p^{b-1})(-c)=p^{b-1}-c$.

Question

When is it possible that this is in a NE?

$p\in (0,1)$, so both strategies have positive probabilities. To be in the best response, support characterization implies the two utilities are equal. So $0=p^{b-1}-c$, or $p=c^{\frac{1}{b-1}}$.

Question

Given this $p$, are $A$ supporters incentivized to change their mixed strategies?

Currently, all of them are playing pure strategies. In order to switch, the utility of switching to the other pure strategy must be greater.

Consider an $A$ supporter who abstained. Expected utility is $p^b\cdot 1+(1-p^b)(2)=2-p^b$. Expected utility of voting is $2-c$ ($A$ guaranteed to win). $2-c=2-p^{b-1}\le 2-p^b(0<p<1)$. Switching to a pure strategy does not increase utility. So switching to any mixed strategy does not increase utility. No reason to switch.

Consider an $A$ supporter who voted. Expected utility is $p^b(1-c)+(1-p^b)(2-c)=2-p^b-c$. If they abstain, $A$ loses if all $B$ supporters vote; $A$ ties if $b-1$ $B$ supporters vote, 1 abstain; $A$ wins otherwise. Utility of abstaining is $p^b\cdot 0+b\cdot p^{b-1}\cdot (1-p)\cdot 1+(1-p^b-b\cdot p^{b-1}\cdot (1-p))\cdot 2=2-2p^b-b{p}^{b-1}(1-p)$. There is no reason to switch.

When $p=c^{\frac{1}{b-1}}$, this is a mixed NE.

Question

What happens to voter participation as cost increases?

If $c$ increases, then $p$ increases, so more voters will vote.

Two-Player Zero-Sum Games

Definition

A strategic game is a zero-sum game if for all strategy profiles $s\in S$, ${\sum }_{i\in N}{u}_i(s)=0$.

Examples: Matching pennies and rock paper scissors.

For a two-player zero-sum game, let $S_1=\{1,\dots ,m\}$ and $S_2=\{1,\dots ,n\}$. Define such a game with a payoff matrix $A\in {\mathbb{R}}^{m\times n}$ where $u_1(i,j)=A_{ij}$ and $u_2(i,j)=-A_{ij}$.

Note: for a mixed strategy profile $x=(x^1,x^2)$, $u_1(x^1,x^2)=-u_2(x^1,x^2)$.

Min-maxing argument for finding a NE: Given a strategy that we play, the opposing player will maximize their utility, which minimizes our utility. Knowing how they would play, what can we do to maximize our own utility?

Player 1’s perspective: Suppose player 1 plays $x^1$. They expect player 2 to play from their best response.

Player 2’s expected utility for playing pure strategy $j$ is $-(x^1{)}^{⊺}{A}_{\bullet j}$ ($A_{\bullet j}$ is the $j$th column of $A$).

Utility of player 2’s best response is equal to the maximum of these values,

$$\begin{array}{r}\underset{j\in \{1,\dots ,n\}}{\max }-(x^1{)}^{⊺}{A}_{\bullet j}=-\underset{j\in \{1,\dots ,n\}}{\min }(x^1{)}^{⊺}{A}_{\bullet j}\end{array}$$

So utility for player 2 is ${\min }_{j\in \{1,\dots ,n\}}(x^1{)}^{⊺}{A}_{\bullet j}$. Player 1 wants to maximize this.

$$\begin{array}{rl}& \max \underset{j\in \{1,\dots ,n\}}{\min }(x^1{)}^{⊺}{A}_{\bullet j}\\ s.t.\sum _{i=1}^m{x}_i^1& =1\\ x^1& \ge 0\end{array}$$

We can turn this into a linear program.

$$\begin{array}{rl}& \max u_1\\ s.t.u_1& \le (x^1{)}^{⊺}{A}_{\bullet j}\forall j\in \{1,\dots ,n\}\\ \sum _{i=1}^m{x}_i^1& =1\\ x^1& \ge 0\end{array}$$

Player 2’s perspective: Suppose player 2 plays $x^2$. Then player 1 will play from their best response. Utility of player 1’s best response is ${\max }_{i\in \{1,\dots ,m\}}(x^2{)}^{⊺}{A}_{i\bullet }$ where $A_{i\bullet }$ is the $i$th row of $A$.

Player 2’s utility is $-{\max }_{i\in \{1,\dots ,m\}}(x^2{)}^{⊺}{A}_{i\bullet }$.

Maximizing this is equivalent to minimizing ${\max }_{i\in \{1,\dots ,m\}}(x^2{)}^{⊺}{A}_{i\bullet }$.

$$\begin{array}{rl}& \min \underset{i\in \{1,\dots ,m\}}{\max }(x^2{)}^{⊺}{A}_{i\bullet }\\ s.t.\sum _{j=1}^n{x}_j^2& =1\\ x^2& \ge 0\end{array}$$ $$\begin{array}{rl}& \min u_2\\ s.t.(x^2{)}^{⊺}{A}_{i\bullet }& \le u_2\forall i=1,\dots ,m\\ \sum _{j=1}^n{x}^{2}j& =1\\ x^2& \ge 0\end{array}$$

Main result: The LPs for player 1 and player 2 are duals of each other.

Both LPs are feasible. So both have optimal solutions with the same objective value. The optimal solutions are best responses to each other, so they form a NE. Solve for this using simplex.

Theorem

Any two-player zero-sum game has a mixed Nash equilibrium, and this can be efficiently computed.

Computing NE in general is difficult. In the 3-player zero-sum game or 2-player general-sum game, no polynomial time algorithm is known.

Nash’s Theorem (I)

Theorem

Every strategic game with finitely many players and pure strategies has a Nash equilibrium.

Brouwer's Fixed Point Theorem

Let $X$ be a convex and compact set in a finite-dimensional Euclidean space, and let $f:X\to X$ be a continuous function. Then there exists $x_0\in X$ such that $f(x_0)=x_0$ (fixed point).

Example

Let $X=[0,1]$.

Consider any continuous function $f:[0,1]\to [0,1]$. The graph of $f$ will always intersect $f(x)=x$, producing a fixed point. This is a consequence of the intermediate value theorem.

Terminology from the theorem:

• We will think of an Euclidean space as ${\mathbb{R}}^n$ with the standard dot product, which defines how we measure distance and angle.
• A set is convex is for any two points in the set, the line segment joining them is also in the set. Precise definition: $S$ is convex if for all $u,v\in S$, $\lambda u+(1-\lambda )v\in S$ for all $\lambda \in [0,1]$. Note, the convex combination of any set of points is convex. $S=\{{\lambda }_1{v}_1+\cdots +{\lambda }_n{v}_n:{\lambda }_1,\dots ,{\lambda }_n\ge 0,{\lambda }_1+\dots {\lambda }_n=1\}$.
• A set is compact if it is closed and bounded. Closed all “boundary” points are in the set, e.g. $[0,1]$ is closed, $(0,1)$ is not. Bounded: there is a constant that bounds the distance between any two points.

This is a deep theorem from analysis. We do not prove it here, there are many good proofs of it. None of the proofs are constructive. We know that a fixed point exists, but the proofs do not tell us how to find one.

Illustrations:

Print a world map and place it on a desk. This is a continuous mapping from the surface of the Earth to the part of the surface by the map on your desk. The theorem implies there is a fixed point: some point on the map is directly on top of the point it represents on your desk.

Take a cup of tea and stir it. Let it settle. Then some part of the liquid is in the same spot before the stir.

Relation to strategic games

We want to use Brouwer’s fixed point theorem when $X$ is the set of all mixed strategy profiles of a finite strategic game. Need to verify that $\Delta$ is convex and compact.

Start with just one player $i$ and their set of mixed strategies ${\Delta }^i$. If the set of pure strategies is $\{1,\dots ,k\}$ then ${\Delta }^i=\{(x_1^i,\dots ,x_k^i):x_j^i\ge 0,x_1^i+\cdots +x_k^i=1\}$.

We can see that ${\Delta }^i$ is compact: it is closed, and only 2 points have distance at most 1. ${\Delta }^i$ is convex : it is the convex combination of the standard basis vectors $e_1,\dots ,e_k$. These $e_1,\dots ,e_k$ are the pure strategies of player $i$.

They set of all strategy profiles is $\Delta ={\Delta }^1\times \cdots \times {\Delta }^n$. We can pretend that this is a set in ${\mathbb{R}}^{|S_1|+\cdots +|S_n|}$. It is still compact, it is also still convex. So we can use $\Delta$ as the set in Brouwer’s fixed point theorem.

Nash’s Theorem (II)

We need $f:\Delta \to \Delta$ to relate fixed points and Nash equilibria.

Main Idea

Given a strategy profile $x=(x^1,\dots ,x^n)$, a player $i$ will look at possibly switching to a pure strategy to gain utility against $x^{-i}$. If pure strategy $s$ improves utility, then player $i$ wants to shift the probability distribution so that $s$ receives higher probability. The function will take $x$, and map it to another strategy profile where each player improves their utility.

Example

Rock paper scissors

Suppose both play rock as a pure strategy. They can increase utility by moving toward paper.

Suppose player 1 plays rock, player 2 plays paper. Player 2 cannot improve utility. Player 1 can improve utility by 1 if they move to paper, improve utility by 2 if they move to scissors. Player 1 will move more towards scissors than paper.

Defining the function

First define $\Phi$ which records the improvement of a player in switching to a pure strategy. Given strategy profile $x\in Delta$, a player $i$, and a pure strategy $s\in S_i$, define ${\Phi }_s^i(x)=\max \{0,u_i(s,x^{-i})-u_i(x)\}$. If playing $s$ increases utility for player $i$, then ${\Phi }_s^i(x)$ represents this increase. Otherwise ${\Phi }_s^i(x)=0$.

For player $i$ and strategies $s$ where ${\Phi }_s^i(x)>0$, we want to increase the probability on $s$. We want to replace $x_s^i$ by $x_s^i+{\Phi }_s^i(x)$. But the sum of probabilities is greater than 1. We can normalize this by dividing by ${\sum }_{s^{\prime }\in S_i}(x_{s^1}^i+{\Phi }_{s^{\prime }}^i(x))=1+{\sum }_{s^{\prime }\in S_i}{\Phi }_{s^{\prime }}^i(x)$.

We define $f:\Delta \to \Delta$ by $f(x)=\bar{x}$ where for each player $i$ and strategy $s\in S_i$,

$$\begin{array}{r}{\bar{x}}_s^i=\frac{x_s^i+{\Phi }_s^i(x)}{1+{\sum }_{s^{\prime }\in S_i}{\Phi }_{s^{\prime }}^i(x)}\end{array}$$

Example

In rock paper scissors, where player 1 plays rock and player 2 plays paper, the strategy profile is $x=((1,0,0),(0,1,0))$. For player 2, ${\Phi }_s^2(x)=0$ for each $s\in \{R,P,S\}$. For player 1 ${\Phi }_R^1(x)=0$, ${\Phi }_P^1(x)=1$, ${\Phi }_S^1(x)=2$. So the new strategy for player 1 is ${\bar{x}}_R^1=\frac{1}{4}$, ${\bar{x}}_p^1=\frac{1}{4}$, ${\bar{x}}_s^1=\frac{1}{2}$.

Completing the proof of Nash’s theorem

Given $x\in \Delta$, consider $\Phi$ and $f:\Delta \to \Delta$ defined above. We see that $f$ is continuous since $\Phi$ is continuous. By Brouwer’s fixed point theorem, there exists $\hat{x}\in \Delta$ such that $f(\hat{x})=\hat{x}$. We prove that $\hat{x}$ is a NE by showing ${\hat{x}}^i\in B_i({\hat{x}}^{-i})$.

For player $i$, let $s\in S_i$ be a pure strategy such that ${\hat{x}}_s^i>0$ and $u_i(s,{\hat{x}}^{-i})\le u_i(\hat{x})$. Then ${\Phi }_s^i(\hat{x})=0$. Since $\hat{x}$ is a fixed point, ${\hat{x}}_s^i=(f(\hat{x}){)}_s^i=\frac{{\hat{x}}_s^i}{(1+{\sum }_{s^{\prime }\in S_i}{\Phi }_{s^{\prime }}^i(\hat{x}))}$. Since ${\hat{x}}_s^i>0$, the denominator must be $1$. So ${\sum }_{s^{\prime }\in S_i}{\Phi }_{s^{\prime }}^i(\hat{x})=0$. But $\Phi$ is non-negative, so ${\Phi }_{s^{\prime }}^i(\hat{x})=0$ for all $s^{\prime }\in S_i$. This means that playing $u_i(s^{\prime },{\hat{x}}^{-i})\le u_i(\hat{x})$ for all $s^{\prime }\in S_i$. So playing ${\hat{x}}^i$ gives the highest utility against ${\hat{x}}^{-i}$, so ${\hat{x}}^i\in B_i({\hat{x}}^{-i})$. Since this holds for all players, $\hat{x}$ is a Nash equilibrium $■$.

This proves that a NE always exists, but does not show how to find such NE.

Cooperative Games

There are games where groups of players can work together to obtain higher utility.

Example

Alice ($A$), Bob ($B$), and Carol ($C$) want to buy ice cream. There are 3 sizes of ice cream: 1L, 1.5L, 2L with costs $7, $9, $11 respectively. $A$ has $3, $B$ has $4, $C$ has $5. On their own, they cannot buy any. But if they pool money together, they can get some ice cream.

Definition

A cooperative game is given by a set of players $N$ and a characteristic function $v:2^N\to \mathbb{R}$ that assigns a value $v(S)$ to each coalition $S\subseteq N$ of players. We use $(N,v)$ to represent this game. The set $N$ is the grand coalition.

In the ice cream game, $N=\{A,B,C\}$ and $v$ is defined by

$S$	$\varnothing ,\{A\},\{B\},\{C\}$	$\{A,B\}$	$\{A,C\}$	$\{B,C\}$	$\{A,B,C\}$
$v(S)$	$0$	$1$	$1$	$1.5$	$2$

General assumptions: $v(\varnothing )=0$, $v(S)\ge 0$ for all $S\subseteq N$.

Example

A country has a 101-member parliament. There are 4 parties $A$, $B$, $C$, $D$ with 40, 22, 30, 9 members respectively. They need to device how to spend a $1 billion windfall, they need to form a majority to spend it.

$N=\{A,B,C,D\}$

$$v(S)=\{\begin{array}{ll}10^9& \text{parties in }S\text{ has }\ge 51\text{ members}\\ 0& \text{otherwise}\end{array}$$

Example

In a matching game, we are given a graph $G=(V,E)$ and edge weights $w:E\to \mathbb{R}$. The players are the vertices, $V=N$. The weight of an edge represents the benefit if the two vertex players work together. For any subset $S\subseteq N$, the value is the maximum weight of a matching using vertices in $S$.

Outcomes of cooperative games

Outcomes of strategic games: strategy profiles (pure or mixed). Which strategy is played by each player?

Outcomes of cooperative games

1. Divide the players into groups, we call them coalitions. Each coalition will generate their assigned value. Coalition structure.
2. Distribute the value that each coalition generates among its members. Payoff vector.

Definition

Given a cooperative game $(N,v)$, a coalition structure is a partition $\pi$ of $N$, i.e. $\pi =(C^1,\dots ,C^k)$ where each $C^i\subseteq N$, $C^j\cap C^j=\varnothing$ whenever $i\ne j$, and $C^1\cup \cdots \cup C^k=N$.

Definition

A payoff vector is a vector $x\in {\mathbb{R}}^N$ such that $x\ge 0$ and ${\sum }_{i\in C^j}{x}_i\le v(C^j)$ for all $j=1,\dots ,k$.

Notation: For any $T\le N$, $x(T)={\sum }_{i\in T}{x}_i$. So the inequality here is $x(C^j)\le v(C^j)$. An outcome consists of $(\pi ,x)$. Such an outcome is efficient if $x(C^j)=v(C^j)$ for all $j$.

Some classes of Games

1. Monotone games: $S\subseteq T⟹v(S)\le v(T)$
2. Superadditive games: for disjoint $S$, $T$, $v(S)+v(T)\le v(S\cup T)$. Superadditive $⟹$ monotone, converse is not true. We usually only consider the grand coalition: $\pi =(N)$.
3. Convex games: for any $S$, $T$ $v(S)+v(T)\le v(S\cup T)+v(S\cap T)$ (supermodularity inequality). Convexity $⟹$ superadditivity, converse is not true.

Proposition: A game $(N,v)$ is convex if and only if for every $S,T$ where $S\subseteq T\subseteq N$ and for every player $i\in N\setminus T$, $v(T\cup \{i\})-v(T)\ge v(S\cup \{i\})-v(S)$.

Shapley Values (I)

Two desirable properties of an outcome in cooperative games:

1. Fairness: The payoff vector should reflect the contribution of the players to their coalitions
2. Stability: We want to incentivize the players to stay in their assigned coalition in the coalition structure.

Shapley Values

Shapley values deal with the fairness of the payoff vector. Assume players form the grand coalition.

Idea 1: Compare the value of the coalition before and after a player joins it.

Problem

The sum of the payoffs may exceed the value of the coalition.

Idea 2: Fix a sequence of the players, and see their contribution sequentially.

Problem

Different orderings of the players will receive different results.

Shapley’s Idea: Look at all possible orderings of players, average a player’s contributions.

Notations: A permutation of $N$ has the form $\sigma =({\sigma }_1,\dots ,{\sigma }_n)$ where each ${\sigma }_i$ is a distinct element of $N$. The element ${\sigma }_i$ is at the $i$th position of $\sigma$. The set of all permutations of $N$ is denoted $S_N$.

Definition

Given a population $\sigma \in S_N$, the marginal contribution of player ${\sigma }_i$ is ${\Delta }_{\sigma }({\sigma }_i)=v(\{{\sigma }_1,\dots ,{\sigma }_i\})-v(\{{\sigma }_1,\dots ,{\sigma }_{i-1}\})$. The Shapley value of player $i$ is ${\phi }_i=\frac{1}{n!}{\sum }_{\sigma \in S_N}{\Delta }_{\sigma }(i)$.

Shapley Values (II)

Recall: Shapley value ${\phi }_i=\frac{1}{n!}{\sum }_{\sigma \in S_N}{\Delta }_{\sigma }(i)$ where ${\Delta }_{\sigma }(i)$ is the marginal contribution.

4 good properties of Shapley values.

1. Efficiency: It distributes $v(N)$ to all players.

Proposition: ${\sum }_{i\in N}{\phi }_i=v(N)$

Proof: For any $\sigma \in S_N$, the sum of all marginal contributions is

$$\begin{array}{rl}\sum _{i\in N}{\Delta }_{\sigma }(i)& =\sum _{i=1}^n{\Delta }_{\sigma }({\sigma }_i)\\ & =[v(\{{\sigma }_1\})-v(\varnothing )]+[v(\{{\sigma }_1,{\sigma }_2\})-v(\{{\sigma }_1\})]+\cdots +[v(\{{\sigma }_1,\dots ,{\sigma }_n\})-v(\{{\sigma }_1,\dots ,{\sigma }_{n-1}\})]\\ & =v(\{{\sigma }_1,\dots ,{\sigma }_n\})-v(\varnothing )\\ & =v(N)\end{array}$$

So the sum of Shapley values is

$$\begin{array}{r}\sum _{i\in N}{\phi }_i=\sum _{i\in N}\frac{1}{n!}\sum _{\sigma \in S_N}{\Delta }_{\sigma }(i)=\frac{1}{n!}\sum _{\sigma \in S_N}\sum _{i\in N}{\Delta }_{\sigma }(i)=\frac{1}{n!}\sum _{\sigma \in S_N}v(N)=\frac{1}{n!}(n!)v(N)=v(N)\end{array}$$

2. Symmetric: Two players $i$, $j$ are symmetric if $v(C\cup \{i\})=v(C\cup \{j\})\forall C\subseteq N\setminus \{i,j\}$.

Proposition: If $i$, $j$ are symmetric players, then ${\phi }_i={\phi }_j$.

Proof: Define $f:S_N\to S_N$ where $f(\sigma )$ is obtained from $\sigma$ by swapping $i$ and $j$. This is a bijection $(f^{-1}=f)$. We claim ${\Delta }_{\sigma }(i)={\Delta }_{f(\sigma )}(j)$. Two cases

1. Suppose $i$ precedes $j$ in $\sigma$. Let $C$ be all elements preceding $i$. In $f(\sigma )$, $C$ is also the elements that precede $j$. So ${\Delta }_{\sigma }(i)=v(C\cup \{i\})=v(c)$ and ${\Delta }_{f(\sigma )}(j)=v(C\cup \{j\})-v(C)$. Since $C\subseteq N\setminus \{i,j\}$ and $i$, $j$ are symmetric, $v(C\cup \{i\})=v(C\cup \{j\})$. So ${\Delta }_{\sigma }(i)={\Delta }_{f(\sigma )}(j)$.
2. Suppose $j$ precedes $i$ in $\sigma$. Let $C$ be all elements preceding $i$ except $j$. In $f(\sigma )$, $C$ is also the elements that precedes $j$ except $i$. So ${\Delta }_{\sigma }(i)=v(C\cup \{j\}\cup \{i\})-v(C\cup \{j\})$ and ${\Delta }_{f(\sigma )}(j)=v(C\cup \{i\}\cup \{j\})-v(C\cup \{i\})$. Since $C\subseteq N\setminus \{i,j\}$ and $i$, $j$ are symmetric, $v(C\cup \{j\})=v(C\cup \{i\})$, so ${\Delta }_{\sigma }(i)+{\Delta }_{f(\sigma )}(j)$.

Therefore, ${\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$ $■$.

3. Dummy player: $i$ is a dummy player if $v(S\cup \{i\})=v(S)\forall S\subseteq N\setminus \{i\}$. The player does not contribute to any coalition.

Proposition: If $i$ is a dummy player, then ${\phi }_i=0$.

Proof: For any $\sigma \in S_N$, say $i$ is at the $j$th position $({\sigma }_j=i)$, the marginal contribution of $i$ is ${\Delta }_{\sigma }(i)=v(\{{\sigma }_1,\dots ,{\sigma }_{j-1},i\})-v(\{{\sigma }_1,\dots ,{\sigma }_{j-1}\})=0$ by definition of a dummy player. So ${\phi }_i=\frac{1}{n!}{\sum }_{\sigma \in S_N}{\Delta }_{\sigma }(i)=0$ $■$.

The converse is not true. If a game is monotone, then the converse is true.

4. Additivity: Suppose there are multiple games with the same set of players. We add the values together to get a new game. Then the Shapley values are also added together.

Proposition: Let $(N,V^1),(N,V^2)$ be two cooperative games. Define $V^3(S)=V^1(S)+V^2(S)\forall S\subseteq N$. Let ${\phi }_i^j$ be the Shapley values of player $i$ in $(N,v^j)$ $j=1,2,3$. Then ${\phi }_i^3={\phi }_i^1+{\phi }_i^2$ for all $i$.

Summary: The Shapley values satisfy 4 good properties: efficiency, symmetric, dummy player, additivity.

Deep result: The Shapley value function is the only one that satisfies all 4 properties. If $f$ is a function that maps $(N,v)$ to a real vector ${\mathbb{R}}^N$ and all 4 properties hold, then $f$ gives the Shapley values).

The core

Stability: Given an outcome, what would be a reason that players want to deviate from it? A group of players could generate more value than what they are receiving. $x(C)<v(C)$.

Definition

The core of a cooperative game $(N,v)$ consists of all outcomes $(\pi ,x)$ such that $x(C)\ge v(C)$ for all $C\subseteq N$.

Example

Ice cream game. Consider $(\pi ,x)$ with $\pi =(\{A,B\},\{C\})$ and $x_A=0.5$, $x_B=0.5$, $x_C=0$. If $C$ joins with $\{A,B\}$, then they produce value 2, while currently their combined payoffs is 1. Better if they form $\{A,B,C\}$, not in the core. Same reasoning gives $\pi =(N)$ if $(\pi ,x)$ is in the core. If $x_A=2$, $x_B=x_C=0$, then $\{B,C\}$ can get more value. If $x_A=0,x_B=x_C=1$, then $(\pi ,x)$ is in the core. This satisfies the inequalities.

Properties of outcomes in the core

1. They are efficient within the coalition structure.

Proposition: If $(\pi ,x)$ is in the core, then $x(C)=v(C)$ for each $C\in \pi$.

Proof: Let $C\in \pi$. By the definition of the core, $x(C)\ge v(C)$. Since $(\pi ,x)$ is a valid outcome, $x(C)\le v(C)$. Therefore, $x(C)=v(C)$ for all $C\in \pi$ $■$.

2. The coalition structure generates the maximum amount of total value among all outcomes. “Social welfare”. Notation: $v(\pi )={\sum }_{C\in \pi }v(C)$.

Proposition: If $(\pi ,x)$ is in the core, then $v(\pi )\ge v({\pi }^{\prime })$ for all partitions ${\pi }^{\prime }$ of $N$. Proof: $v(\pi )={\sum }_{C\in \pi }v(C)={\sum }_{C\in \pi }x(C)={\sum }_{i\in N}{x}_i={\sum }_{C^{\prime }\in {\pi }^{\prime }}x(C^{\prime })\ge {\sum }_{C^{\prime }\in {\pi }^{\prime }}v(C^{\prime })=v({\pi }^{\prime })$ $■$.

This proposition only says that coalition structures that maximize total value are eligible to be in the core. It does not mean that there exists an outcome in the core with this structure.

Games with empty cores

Example

3-player majority game. $N=\{1,2,3\}$, $v(s)=\{\begin{array}{ll}1& |S|\ge 2\\ 0& \text{otherwise}\end{array}$ We claim that no outcome is in the core. Suppose $(\pi ,x)$ is in the core. Then $x_1+x_2+x_3\ge 1$, $x_1,x_2,x_3\ge 0$. So $x_i\ge \frac{1}{3}$ for some $i$. The value of any coalition is at most $1$, so $x_1+x_2+x_3\le 1$. This means $x(N\setminus \{i\})\le \frac{2}{3}$. However, $v(N\setminus \{i\})=1>x(N\setminus \{i\})$. This contradicts the assumption that $(\pi ,x)$ is in the core. So the core is empty.

Cores of Superadditive Games

Recall: $(\pi ,x)$ is in the core of $(N,v)$ if $x(C)\ge v(C)$ for all $C\subseteq N$.

Recall: A game is superadditive if $v(S)+v(T)\le v(S\cup T)$ for any disjoint $S,T\subseteq N$.

Goal: Determine when a superadditive game has a non-empty core.

Narrowing the search $\to$ we only need to consider outcomes that form the grand coalition.

Proposition: Let $(N,v)$ be a superadditive game. If $(\pi ,x)$ is in the core, then $((N),x)$ is in the core.

Proof: We need to prove that the core conditions hold, and $((N),x)$ is a valid outcome.

Since $(\pi ,x)$ is in the core, $x(C)\ge v(C)$ for all $C\subseteq N$. This still holds for $((N),x)$. To show that $((N),x)$ is a valid outcome, we need to show that $x(N)\le v(N)$.

$$\begin{array}{r}x(N)\stackrel{\text{Since }\pi \text{ is a partition of }N}{\overbrace{=}}\sum _{C\in \pi }x(C)\stackrel{\text{Since }(\pi ,x)\text{ is a valid outcome}}{\overbrace{\le }}\sum _{C\in \pi }v(C)\stackrel{\text{Superadditivity}}{\overbrace{\le }}v(N)\end{array}$$

Characterizing superadditive games with non-empty cores

Given an outcome $((N),x)$, what most $x$ satisfy to be in the core? We claim that $x$ must be in the set $\mathcal{C}=\{x\in {\mathbb{R}}^N:x(N)=v(N),x(C)\ge v(C)\forall c\subseteq N\}$.

Now $\mathcal{C}$ is the intersection of half-spaces, so it is a polyhedron.

Mini-result: $(N,v)$ has a non-empty core if and only if $\mathcal{C}$ is non-empty.

We can solve the problem of “is $\mathcal{C}$ non-empty” using a linear program.

Let $(P)$ be the following LP:

$$\begin{array}{rl}& \min x(N)\\ & \text{s.t.}x(C)\ge v(C)\forall C\subseteq N\end{array}$$

Rationale: $(P)$ is feasible (take large $x$), and $x(N)\ge v(N)$ is a constraint, so $(P)$ is bounded. This implies $(P)$ has an optimal solution. If optimal value is $v(N)$, then we have optimal solution $x$ with $x(N)=v(N)$ and $x(C)\ge v(C)$ $\forall C\subseteq N$, so $x\in \mathcal{C}$.

Mini-result: $(N,v)$ has a non-empty core if and only if $(P)$ has optimal value $v(N)$.

Take the dual $(D)$.

$$\begin{array}{rl}\max \sum _{C\subseteq N}& y_{C}v(C)\\ \text{s.t.}\sum _{C\subseteq N,i\in C}{y}_C& =1\forall i\in N\\ y& \ge 0\end{array}$$

$(P)$ has optimal value $v(N)$ $⟺$ $(D)$ has optimal value $v(N)$ $⟺$ ${\sum }_{C\subseteq N}{y}_{C}v(C)\le v(N)$ for all feasible $y$.

Question

What is the meaning of the dual?

1. Feasible solution: ${\sum }_{C\in N,i\in C}{y}_C=1$. A feasible solution $y$ is a generalized coalition structure. $y_C$ represents the fraction of time each member will contribute to $C$, with a total time of $1$ from each player. Any such feasible $y$ is called a balancing weight.
2. Objective: ${\sum }_{C\subseteq N}{y}_{C}v(C)\le v(N)$. Then ${\sum }_{C\subseteq N}{y}_{C}v(C)$ is the total value of the fractional partition represented by $y$. The inequality ${\sum }_{C\subseteq N}{y}_{C}v(C)\le v(N)$ means the value of the grand coalition is maximum over the values of any fractional partition. This generalizes our previous partition.

A game that satisfies this inequality for all balancing weight $y$ is called a balanced game.

Theorem (Bondareva-Shapley)

A superadditive cooperative game has a non-empty core if and only if it is balanced.

Games With Non-Empty Cores

In superadditive games with non-empty cores, there is always an outcome in the core with the grand coalition. This is not necessarily the case for cooperative games in general.

Example

Let $N=\{1,2,3,4\}$, $v(S)=\{\begin{array}{ll}2& |S|\ge 2\\ 0& \text{otherwise}\end{array}$. Proposition: Coalition structure in the core has highest value. $v(N)=2$. But $v(\{1,2\},\{3,4\})=4$. So the grand coalition cannot be in any outcome of the core. The core is non-empty.

Checking if the core is non-empty cannot be reduced to checking only the grand coalition. But we can relate this to superadditive games.

Definition

For any cooperative game $(N,v)$, its superadditive cover is $(N,v^{\ast })$ where, for each $S\subseteq N$, $v^{\ast }(S)=\max \{v(\pi ):\pi \text{ is a partition of }S\}$.

A cooperative game $(N,v)$ has a non-empty core if and only if its superadditive cover $(N,v^{\ast })$ has a non-empty core.

Proof:

$(⟹)$ Let $(\pi ,x)$ be in the core of $(N,v)$. Goal: Show $((N),x)$ is in the core of $(N,v^{\ast })$. From before, this means showing $v^{\ast }(N)=x(N)$; and $v^{\ast }(C)\le x(C)\forall C\subseteq N$. By our previous proposition, $v(\pi )$ has the maximum value among all partitions of $N$. So by the definition of the superadditive cover, $v^{\ast }(N)=v(\pi )$.

$$\begin{array}{r}{v}^{\ast }(N)=v(\pi )=\sum _{C\in \pi }v(C)=\sum _{C\in \pi }x(C)=\sum _{i\in N}{x}_i=x(N)\end{array}$$

Let $C\subseteq N$. Suppose $v^{\ast }(c)=v({\pi }^{\prime })$ for some partition ${\pi }^{\prime }$ of $C$. Then

$$\begin{array}{r}{v}^{\ast }(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)\end{array}$$

So $((N),x)$ is in the core of $(N,v^{\ast })$.

$(⟸)$ Since $(N,v^{\ast })$ is superadditive, there exists a payoff vector $x$ such that $((N),x)$ is in the core. By the definition of the superadditive cover, $v^{\ast }(N)=v(\pi )$ for some partition $\pi$ of $N$.

A cooperative game has a non-empty core if and only if its superadditive cover is balanced.

Proof: Combine the Bondareva-Shapley theorem with the previous proposition.

Cores of Convex Games

Recall: A game is convex if $v(S)+v(T)\le v(S\cup T)+v(S\cap T)$ for all $S,T\subseteq N$. Equivalently, $v(S\cup \{i\})-v(S)\le v(T\cup \{i\})-v(T)$ for all $S\subseteq T\subseteq N\setminus \{i\}$.

Example

Bob the Banker is bankrupt. He owes three people money, $100, $200, $300 each. Bob only has $200, how should his money be divided? $50, $50, $100? $0, $0, $200? Which ones are stable?

General model: Bob has $M, he owes money to $n$ people $N$, amounts owed are in $d\in {\mathbb{R}}^N$. Assume $0\le M\le {\sum }_{i\in N}{d}_i$.

Cooperative game: $(N,v)$ where $v(S)=\max \{0,M-{\sum }_{i\in N\setminus S}{d}_i\}$ for each $S\subseteq N$.

Meaning: Players are taking a pessimistic view, $v(S)$ is the amount left if the remaining players take what they are owed.

Proposition: Convex games have non-empty cores.

Idea: The marginal contributions of players in any permutation form the payoff vector in the core.

Proof: Since convex games are superadditive, it suffices to find $x$ such that $((N),x)$ is in the core.

Let $\sigma \in S_N$. WLOG, assume $\sigma =(1,2,\dots ,n)$. Define $x$ by $x_i={\Delta }_{\sigma }(i)$.

In the proof before, $x(N)={\sum }_{i=1}^n{\Delta }_{\sigma }(i)=v(N)$.

Let $C\subseteq N$. Suppose $C=\{i_1,\dots ,i_k\}$ where $i_1<\cdots <i_k$.

For any $i_j$, the equivalent convex condition implies

$$\begin{array}{r}v(\{1,\dots ,i_j\})-v(\{1,\dots ,i_j-1\})\ge v(\{i_1,\dots ,i_j\})-v(\{i_1,\dots ,i_{j-1}\})\end{array}$$

So,

$$\begin{array}{rl}x(C)& ={\Delta }_{\sigma }(i_1)+{\Delta }_{\sigma }(i_2)+\cdots +{\Delta }_{\sigma }(i_k)\\ & =[v(\{1,\dots ,i_1\})-v(\{1,\dots ,i_1-1\})]+[v(\{1,\dots ,i_2\})-v(\{1,\dots ,i_2-1\})]+\\ & \cdots +[v(\{1,\dots ,i_k\})-v(\{1,\dots ,i_k-1\})]\\ & \ge [v(\{i_1\})-v(\varnothing )]+[v(\{i_1,i_2\})-v(\{i_1\})]+\cdots +[v(\{i_1,\dots ,i_k\})-v(\{i_1,\dots ,i_{k-1}\})]\\ & =v(\{i_1,\dots ,i_k\})-v(\varnothing )=v(c)■\end{array}$$

Any vector of marginal contributions is in the core with the grand coalition. The set of all vectors in the core is $\mathcal{C}$, which is a polyhedron, which is convex. The vector of Shapley values $\phi$ is a convex combination of the marginal contributions, so it is also in the core.

Stronger result: $\phi$ is precisely equal to the convex combinations of all marginal contribution vectors.

Matching Game

Recall: Matching game consists of a graph $G$, the players are the vertices $N=v(G)$, and non-negative edge weights $w$. The value $v(S)$ of $S\subseteq N$ is the maximum weight of a matching using vertices in $S$.

We interpret the weight of an edge as the value generated by the two players on both sides when they work together. This game is superadditive, so we only need to consider the grand coalition when determining if it has a non-empty core.

Recall: $((N),x)$ is in the core if and only if $x\in \mathcal{C}$ where $\mathcal{C}=\{x\in {\mathbb{R}}^N:x(N)=v(N),x(C)\ge v(C)\forall C\subseteq N\}$.

There are exponentially many inequalities. We can make a simplification:

Define ${\mathcal{C}}^{\prime }=\{x\in {\mathbb{R}}^N:x(N)=v(N),x_u+x_v\ge w_{uv}\forall uv\in E(G),x\ge 0\}$.

Proposition: $\mathcal{C}={\mathcal{C}}^{\prime }$.

Proof: If $x\in \mathcal{C}$, then $x$ satisfies all constraints in ${\mathcal{C}}^{\prime }$.

So $\mathcal{C}\subseteq {\mathcal{C}}^{\prime }$.

Let $x\in {\mathcal{C}}^{\prime }$. Then $x(N)=v(N)$. Let $C\subseteq N$, and let $M$ be a maximum weight matching in $C$.

Then

$$\begin{array}{rl}x(C)& \ge \sum _{uv\in M}{x}_u+x_v\\ & \ge \sum _{uv\in M}{w}_{uv}(\text{since }x\in {\mathcal{C}}^{\prime })\\ & =w(M)=v(C)■\end{array}$$

The edges in the maximum matching are “efficient” $x_u+x_v=w_{uv}$ for all $uv\in M$.

We can determine if ${\mathcal{C}}^{\prime }$ is non-empty by solving the following LP:

$$\begin{array}{rl}& \min x(N)(P)\\ \text{s.t.}{x}_u+x_v& \ge w_{uv}\forall yv\in E(G)\\ x& \ge 0\end{array}$$

${\mathcal{C}}^{\prime }$ is non-empty if and only if $(P)$ has optimal value $v(N)$.

$$\begin{array}{rl}\max \sum _{uv\in E(G)}& w_{uv}{y}_{uv}(D)\\ \text{s.t.}\sum _{\{uv:uv\in E(G)\}}{y}_{uv}& \le 1\forall u\in N\\ y& \ge 0\end{array}$$

${\mathcal{C}}^{\prime }$ is non-empty if and only if $(D)$ has optimal value $v(N)$.

Meaning of $y$: If $y$ is integral, then its value are 0 or 1. For each vertex, the number of incident edges with value 1 is at most 1. So the edges with value 1 form a matching. Maximizing integral solutions will give us the weight of a max matching, which is $v(N)$. But $y$ could be fractional. Feasible solutions to $(D)$ are generalized matchings.

As long as no fractional matching has weight higher than $v(N)$, then $v(N)$ is the optimal value achieved by a maximum matching.

Proposition: The core of the matching game is non-empty if and only if $(D)$ has an integral optimal solution.

Proof: It suffices to prove that $(P)$ has optimal value $v(N)$ if and only if $(D)$ has an integral optimal solution.

$(⟹)$ Suppose $(P)$ has optimal value $v(N)$. Suppose $v(N)=w(M)$ for some maximum matching $M$. Define $y\in {\mathbb{R}}^{E(G)}$ by $y_e=\{\begin{array}{ll}1& e\in M\\ 0& e\notin M\end{array}\forall e\in E(G)$. Then $y$ is feasible for $(D)$ since $M$ is a matching with objective value $w(M)=v(N)$. By weak duality, $y$ is optimal for $(D)$, and its integral optimal solution.

$(⟸)$ Suppose $y$ is an integral optimal solution for $(D)$. Let $M^{\prime }=\{e\in E(G):ye=1\}$. Then $M^{\prime }$ is a matching with optimal value $w(M^{\prime })$. Since $y$ is optimal, $M^{\prime }$ must be a maximum matching. So $s(M^{\prime })=v(N)$. So $(P)$ has optimal value $v(N)$ $■$.

Network Bargaining Game (I)

Alice and Bob are negotiating over how to split $1M. They can only take the money if they both agree on how to split.

The natural outcome is to split it $0.5M and $0.5M.

Suppose there are outside options: Carol offers $\alpha$ to Alice if they work together, Dan offers $\beta$ to Bob if they work together.

Lets say $\alpha$ is $0.4M, and $\beta$ is $0.7M. Then Bob will work with $D$ unless he gets $\ge$ $0.7M, which means $A$ will get $\le$ $0.3M, so $A$ will work with $C$. The negotiation between $A$, $B$ breaks down. This happens if $\alpha +\beta >$ $1M.

Consider another example.

Say $\alpha$ is $0.4M, $\beta$ is $0.2M. $A$ wants at least $ 0.4M to work with $B$. $B$ wants at least $ 0.2M to work with $A$.

There are $0.4M left. Split them equally. $A$ gets $0.6M, $B$ gets $0.4M.

Nash’s bargaining solution: Players $A$, $B$ try to split $w$, each has outside options $\alpha$, $\beta$ respectively. If $\alpha +\beta >w$, then no split is possible. Otherwise, $x_A=\alpha +\frac{w-\alpha -\beta }{2}$, $x_B=\beta +\frac{w-\alpha -\beta }{2}$.

Network Bargaining

Given a graph $G$, the players are the vertices $N=v(G)$. Each edge has weight $w_e\ge 0$.

Which pairs form? How do they split their value?

An outcome of the network bargaining game consists of 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 by $M$, $x\ge 0$.

The stability of an outcome depends on the outside options of the players.

Definition

For an outcome $(M,x)$ and a player $u$, the outside option of $u$ is

$$\begin{array}{r}{\alpha }_u=\max (\{0\}\cup \{w_{uv}-x_v:uv\in E\setminus M\})\end{array}$$

This is the maximum value that $u$ can get by detecting from their current partner in $M$. No need to defect if ${\alpha }_u\le x_u$.

Definition

An outcome $(M,x)$ is stable if ${\alpha }_u\le x_u$ for all $u\in N$.

To be stable, for each edge $uv$, $x_u\ge {\alpha }_u\ge w_{uv}-x_v$. So $x_u+x_v\ge w_{uv}$. This is in ${\mathcal{C}}^{\prime }$ from the matching game.

Proposition: A stable outcome exists in a network bargaining game if and only if the corresponding matching game has a non-empty core.

Network Bargaining Game (II)

Recall: In a stable outcome, $x_u\ge {\alpha }_u$.

A stable outcome might not reflect real life experimental results.

Idea from Nash’s bargaining solution: In a matched pair, each player take at least their outside option and split the rest. In other words, after deducting their outside options, they are equal.

Definition

An outcome $(M,x)$ is balanced if $x_u-{\alpha }_u=x_v-{\alpha }_v\ge 0$ for all $uv\in M$. Summary of results

Theorem

A network bargaining game has a balanced outcome if and only if it has a stable outcome.

Note: It is not hard to prove that balanced outcomes are stable.

Definition

A vertex $v$ in a garph $G$ is inessential if there exists a maximum matching in $G$ that does not use $v$.

Theorem

In a graph $G$ with weight 1 for each edge, the following are equivalent:

1. There is a stable outcome.
2. There is a balanced outcome.
3. No two inessential vertices are adjacent.

Aside: The set of inessential vertices is the set $D$ in the Gallai-Edmonds structure theorem. (3) means $D$ is independent.

Theorem

If a network bargaining game has a balanced outcome, then the balanced outcome must use the maximum weight matching, and there exists a polynomial time algorithm for finding a balanced outcome.

Mechanism Design: Ideal Auctions

Mechanism design: We want to design games so that players are incentivized to achieve certain overall goals.

Elections: If more people prefer $A$ over $B$, then $A$ should win

Auctions: The player who values the item the most should win. Or, maximize revenue for the seller

Sports tournaments: Best team should win, teams play the best they can.

Problem: Players look after themselves, will find loopholes and advantages to avoid playing as the game designer intended.

Question

How to set rules so that players who play for themselves will also achieve these global goals?

Ideal Auctions

In an auction, the auctioneer is selling something, players bid on the item.

Auctioneer need to decide the rules for two things: (1) who wins what item; (2) who pays what amount.

Second price auction: (1) Player who bids most wins; (2) winner pays 2nd highest bid.

Nice properties of second-price auctions:

Recall: A player bidding their valuation is a dominant strategy. “Truthful bidding”. This is easy to play: even without knowing everyone else’s valuation, bidding one’s own valuation will maximize utility.

If players give truthful bids, then their utility is never negative. This is not true for “all-pay” auctions, where every player pays regardless if they win or lose.

Definition

An auction is dominant-strategy incentive-compatible (DSIC) if truthful bidding is a dominant strategy, and yields non-negative utility.

Note: Dominant strategy here means “weakly dominant” except we don’t require a case that decrease utility.

Having DSIC is not good enough. Example: An auction where we give the item for free to player 1 is DSIC.

We need an overall goal: The item should go to the player with the highest valuation.

”Social welfare”: Sum total of values received by all players.

For one-item auctions, only one player receives the item. If player $i$ wins the auction, then they receive value $v_i$ (their valuation). Remaining players receive nothing. So the social welfare is $v_i$.

To maximize social welfare in this case, we make sure that the player with the highest valuation wins. This is easy if players bid truthfully.

Definition

An auction is welfare-maximizing if truthful bidding results in maximum social welfare.

Last good property: Second-price auction is easy to run. We can quickly determine the highest bidder and the 2nd highest bid.

Definition

An auction is ideal if

1. It is DSIC;
2. It is welfare-maximizing; and
3. It can be implemented efficiently.

Theorem

The second-price auction is ideal.

Result from the future: This is the only single-item that is ideal.

Sponsored Search Auctions

Search engines may show ads as the first entries of a search result. Selecting which ads to show and their order of placement is done through auctions.

Model

Suppose there are $k\ge 1$ slots for sponsored links on a search results page.

There are advertisers $N$ bidding for these slots with related keywords.

The slots have different “values”: top ones tend to get clicked more often. “Click through rate”.

For each slot $j$, let ${\alpha }_j\in [0,1]$ be the probability that a user clicks on an ad at slot $j$.

Assumption 1: ${\alpha }_1\ge {\alpha }_2\ge {\alpha }_3\ge \cdots$

Assumption 2: CTR is independent of the quality of the ad.

We are looking for ideal auctions: DSIC, welfare-maximizing. Need to determine who wins what, and who pays what.

General approach:

1. Assume truthful bidding, how can we assign the items that is welfare-maximizing and efficient?
2. Given the way we assign items, how can we set prices so that it is DSIC?

Social Welfare

We want to maximize the overall value for the players. What is their value to a player?

Each player $i$ has a valuation $v_i$ of how much one click on their ad is worth. If they are assigned a slot with CTR $x_i$, then their expected value is $v_i{x}_i$.

Social welfare is ${\sum }_{i\in N}{v}_i{x}_i$.

Question

What is a rule that maximizes social welfare?

Assign slot 1 to the player with the highest valuation, slot 2 to the 2nd highest, etc.

This can be efficiently implemented.

Note: Efficiency is critical. Lots of sponsored search auctions run at the same time, has to be almost instantaneous.

We want a payment rule that is DSIC, so players are incentivized to bid truthfully. This requires Myerson’s Lemma.

Aside: Consider the generalized second-price auction. The player who wins the $j$-th slot will pay the $(j+1)$-st highest bid times their CTR ${\alpha }_j$. This is not DSIC. Truthful bidding is not a dominant strategy.

Myerson’s Lemma (I)

Myerson’s Lemma characterizes auctions that have DISC payment rule, and gives a formula for the payment rule. First need an abstraction of the auction model.

Definition

In a single-parameter environment, we are given

• a set of players $N$;
• a private variation $v_i\ge 0$ for each $i\in N$, which is player $i$‘s valuation for one unit of goods $j$ and
• a set $X\subseteq {\mathbb{R}}^n$ of vectors ($x_1,\dots ,x_n)$ that describe feasible allocations, i.e. $x_i$ is the amount of goods given to player $i$

Note: This “single-parameter” since each player has only one piece of private information.

Example

In a single-item auction, $X$ is the set of all standard basis vectors in ${\mathbb{R}}^n$ ($n$-tuples with one 1 and $n-1$ 0’s). In the sponsored search auction, $X$ is the set of vectors where for each slot $j$, at most one $i\in N$ satisfies $x_i={\alpha }_j$, 0 otherwise.

We are interested in this environment, the rules of the auction. Let $B\subseteq {\mathbb{R}}^n$ be the set of all possible player bids.

Definition

Given a single-parameter environment, a direct revelation mechanism

• collects bids $b\in B$ from all players;
• choose a feasible allocation $x(B)\in X$ based on the bids; and
• choose a payment $p(b)\in {\mathbb{R}}^N$ where player $i$ pays $p_i(b)$.

We call $x:B\to X$ an allocation rule, and $p:B\to {\mathbb{R}}^N$ a payment rule. The utility of player $i$ is $u_i(b)=v_i{x}_i(b)-p_i(b)$.

As part of the DSIC condition, we assume $0\le p_i(b)\le v_i{x}_i(b)$, i.e. truthful bidding will result in non-negative utility.

Example

For the second-price auction, $x_i(b)=\{\begin{array}{ll}1& b_i\text{ is max in }b\\ 0& \text{otherwise}\end{array}$, $p_i(b)=\{\begin{array}{ll}{\max }_{j\ne i}{b}_j& b_i\text{ is max in }b\\ 0& \text{otherwise}\end{array}$ .

Two terms for an allocation rule

An allocation rule $x:B\to X$ is implementable if there exists a payment rule $p:B\to {\mathbb{R}}^N$ such that $(x,p)$ is DSIC. The single-item auction where we give the item to the highest bidder is implementable, by using the second-price rule as payment.

An allocation rule $x:B\to X$ is monotone if for all $i\in N$ and for all $b_{-i}\in B_{-i}$, $x_i(Z,b_{-i})\ge (y,b_{-i})$ whenever $z\ge y$.

Translation: The higher you bid, the more you get.

For single-item auctions, highest bid wins is monotone, but second highest bid wins is not monotone.

Theorem

Myerson’s Lemma: For a single parameter environment, an allocation rule $x:B\to X$ is implementable if and only if $x$ is monotone. Moreover, given a monotone allocation rule $x:B\to X$, there exists a unique payment rule $p:B\to {\mathbb{R}}^N$ such that $(x,p)$ is DSIC and $p_i(b)=0$ whenever $b_i=0$.

Myerson’s Lemma (II)

Lemma: If an allocation rule $x:B\to X$ is implementable, then $x$ is monotone.

Proof: Suppose $x$ is implementable. Then there exists a payment rule $p:B\to {\mathbb{R}}^n$ such that $(x,p)$ is DSIC. Fix a player $i\in N$, and bids $b_{-i}\in B_{-i}$. We use $x(y),p(y)$ to represent $x_i(y,b_{-i})$ and $p_i(y,b_{-i})$. We want to prove: If $y\ge z$, then $x(y)\ge x(z)$. Assume $y\ge z$.

Key observation: The rules $(x,p)$ are defined independent of the players’ valuations.

$(x,p)$ is DSIC if player $i$‘s valuation is $y$. So utility of bidding $y\ge$ utility of bidding $z$ $⟹$ $y\cdot x(y)-p(y)\ge y\cdot x(z)-p(z)$.

$(x,p)$ is DSIC if player $i$‘s valuation is $z$ $⟹$ $z\cdot x(z)-p(z)\ge z\cdot x(y)-p(y)$. Rearranging the inequalities to get $z(x(y)-x(z))\le p(y)-p(z)\le y(x(y)-x(z))$. Since $y\ge z\ge 0$, we get $x(y)-x(z)\ge 0$. So $x(y)\ge x(z)$.

For the converse, we will only prove the case where $x$ is piecewise constant.

Approach: Assume $x$ is monotone and $(x,p)$ is DSIC. Derive that $p$ is unique with $p_i(b)=0$ whenever $b_i=0$. Then prove that using this particular $p$, $(x,p)$ is DSIC.

Describing a generic $x$ that is monotone and piecewise constant. There are jump points $\overline{z_1}<\overline{z_2}<\cdots <\overline{z_q}$ such that $x$ is constant in the intervals $[0,\overline{z_1}],(\overline{z_1},\overline{z_2}],\dots ,(\overline{z_{q-1}},\overline{z_q}],(\overline{z_q},\infty )$. Define $h_j$ to be the jump at $\overline{z_j}$. (i.e. $h_j={\lim }_{w\to {\overline{z_j}}^{+}}x(w)-x(\overline{z_j})$).

Lemma: If $x$ is monotone and piecewise constant, and $(x,p)$ is DSIC with $p_i(b)=0$ whenever $b_i=0$, then $p$ is unique.

Proof:

We first show that $p$ is also piecewise constant. If $z$ is inside an interval, then $p^{\prime }(z)=0$.

Assume $y>z$. Suppose $z\in (\overline{z_j},\overline{z_{j+1}})$ for some $j$. We assume DSIC, so the payment sandwich applies. Divide by $y-2$ to get

$$\begin{array}{r}z\frac{x(y)-x(z)}{y-z}\le \frac{p(y)-p(z)}{y-z}\le y\cdot \frac{x(y)-x(z)}{y-z}\end{array}$$

Take the limit as $y\to z^{+}$. ${\lim }_{y\to z^{+}}\frac{x(y)-x(z)}{y-z}=x^{\prime }(z)=0$ since $x$ is constant at $z$. So both ends of the inequalities approach 0. By Squeeze Theorem, ${\lim }_{y\to z^{+}}\frac{p(y)-p(z)}{y-z}=p^{\prime }(z)=0$. So $p$ is piecewise constant with jumps at $\overline{z_1},\dots ,\overline{z_q}$. Let $z=\overline{z_j}$ for some $j$. Look at the payment sandwich ${\lim }_{y\to z^{+}}y(x(y)-x(z))=z\cdot hj$. ${\lim }_{y\to z^{+}}z(x(y)-x(z))=z\cdot hj$. By Squeeze Theorem, ${\lim }_{y\to z^{+}}p(y)-p(z)=z\cdot hj=\overline{z_j}hj$.

So the payment jump at $\overline{z_j}$ is $\overline{z_j}\cdot hj$.

By assumption, $p(0)=0$, so this uniquely defines the function $p$: If $j$ is the largest index where $z\ge \overline{z_j}$, then $p(z)=p_i(z,b_{-i})={\sum }_{k=1}^j\overline{z_k}{h}_k$ $■$.

The payment rule $p$ from our previous lemma is DSIC.

Applying Myerson’s Lemma

Recall: Payment rule $p_i(z,b_{-i})={\sum }_{k=1}^j\overline{z_k}{h}_k$.

Single item auction: Let $x$ be the allocation rule that gives the item to the highest bidder (with a consistent tie-breaking rule). This is monotone. Consider a player $i$ and bids $b_{-i}\in B_{-i}$. Let $B={\max }_{j\ne i}{b}_j$.

The allocation function for player $i$: There is one jump at $z=B$. When $b_i>B$, player $i$ wins, and the payment is $B\cdot 1=B$. This is the second-price rule, and it is unique assuming $b_i=0$ implies $p_i=0$.

Sponsored search auction: $k$ slots with CTR ${\alpha }_1\ge {\alpha }_2\ge \cdots {\alpha }_k$. Our allocation function $x$ assigns ${\alpha }_j$ to the $j$-th highest bidder. This is monotone. Apply Myerson’s lemma for the payment rule.

Consider a player $i$ and bids $b_{-i}\in B_{-i}$. Assume $b_1\ge b_2\ge \cdots \ge b_k$.

Player $i$ gets ${\alpha }_k$ if $b_k<b_i\le b_{k-1}$, ${\alpha }_{k-1}$ if $b_{k-1}<b_i\le b_{k-2},\dots$

Each jump is ${\alpha }_{j-1}-{\alpha }_j$. Using the formula, $p_i(z)={\sum }_{\{j:b_j<z\}}{b}_j({\alpha }_j-{\alpha }_{j+1})$ using ${\alpha }_{k+1}=0$. This is the unique DSIC payment rule.

Knapsack Auction (I)

Recall an ideal auction is DSIC; welfare-maximizing; efficient. We consider an auction that cannot be ideal.

Example

We are managing advertising slots for a TV station. We have $T$ seconds to fill. There are potential advertisers $N$. Advertiser $i$ has an ad of length $t_i$, and gets a value of $v_i$. We run an auction to determine whose ads to air. The set of feasible allocations: $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$. To maximize social welfare, we need $\max \{v^{⊺}x:x\in X\}$.

Recall: First stage of designing this auction is to assume players bid truthfully, and find an allocation rule that is welfare-maximizing. Then Myerson’s lemma gives us a payment rule that is DSIC.

Problem: Maximizing social welfare here is equivalent to the knapsack problem (CS341). This is NP-hard, so it is not possible to find an optimal solution efficiently (unless $P=NP$). We cannot fulfill 2 and 3 of ideal auctions simultaneously.

Solution: Recall 2 or 3. We should not give up 3, as we want this to be practical. So we need to give up on 2. Instead of finding a welfare-maximizing allocation, we will find an approximation of the allocation that is close to the maximum, while keeping efficiency.

Knapsack Auction (II)

Goal: Approximate the welfare-maximizing function for the knapsack auction.

Aside: Typically with approximation algorithms, we want some performance guarantee. The solution produced by the algorithm must be at least this close to the theoretical optimal.

$i$	$1$	$2$	$3$	$4$
$t_1$	$2$	$7$	$3$	$5$
$v_i$	$20$	$56$	$21$	$25$
$\frac{v_i}{t_i}$	$10$	$8$	$7$	$5$
$T=10$.

Idea: We have limited space, so we want to fill in each unit with as much value as possible. Calculate the value density. Higher density should give better value. We sort items in non-increasing value density, i.e. $\frac{v_1}{t_1}\ge \frac{v_2}{t_2}\ge \cdots \ge \frac{v_n}{t_n}$.

First try: Pick items $1,2,\dots$ until we cannot put the next one in the knapsack.

In the example above: Pick 1 and 2. $t_1+t_2=9\le 10$, no room for $3$. Total value $76$.

Is this a good approximation? No, there are cases where the solution produced is very bad.

Example: 2 players, $v_1=t_1=1$, $v_2=T-1$, $t_2=T$. $1$ has higher density than $2$. If we pick $1$, then we do not have room for $2$. Algorithm value $1$. Obvious optimal: pick $2$, optimal value $T-1$. Our solution is $\frac{1}{T-1}$ of the optimal.

Better idea: Suppose we stop at item $i$ above. Check the value of item $i+1$. If $v_{i+1}>v_1+\cdots +v_i$, then we will say that $i+1$ is the only winner.

Example: 2-player example. Stop at $i=1$. We see $v_2>v_1$, so we pick $v_2$ instead.

Full approximation algorithm: Assume $N=\{1,\dots ,n\}$ with $\frac{v_1}{t_1}\ge \frac{v_2}{t_2}\ge \cdots \ge \frac{v_n}{t_n}$.

1. Find $i$ such that it is the largest index with $t_1+\cdots +t_i\le T$.
2. If $v_1+\cdots +v_i\ge v_{i+1}$, then $\{1,\dots ,i\}$ are the winners. Otherwise, $\{i+1\}$ is the only winner.

Suppose APX is the value of the winners produced by the approximation algorithm, OPT is the actual optimal value.

Theorem

APX $\ge \frac{1}{2}$ OPT

Proof: A welfare-maximizing solution is optimal for this integer program (IP): $\max \{v^{⊺}x:t^{⊺}x\le T,x_i\in \{0,1\}\forall i\}$. Opt value: OPT. Its LP relaxation (LP): $\max \{v^{⊺}x:t^{⊺}x\le T,0\le x_i\le 1\forall i\}$.

Let $i$ be the largest index with $t_1+\cdots +t_i\le T$. Consider the solution $x$ where

$$\begin{array}{r}{x}_1=\cdots x_i=1,x_{i+1}=\frac{T-t_1-\cdots -t_i}{t_{i+1}},x_{i+z}=\cdots x_n=0\end{array}$$

Idea: Fill in the remaining space with a fraction of item $i+1$. In example above $x_1=x_2=1$, $x_3=\frac{1}{3}$, $x_4=0$). As we have completely filled in the knapsack with the highest density items, $x$ is optimal.

Suppose optimal value of (LP) is $v^{\ast }$ (obtained by $x$). Since (LP) is a relaxation of (IP), OPT $\le v^{\ast }$.

We want to prove APX $\ge \frac{v^{\ast }}{2}$.

Let $S=\{1,\dots ,i\}$. We see that $v^{\ast }\le v_1+\cdots +v_i+v_{i+1}=v(S)+v_{i+1}$. Two cases:

1. If $v(S)\ge v_{i+1}$, then the algorithm picks $S$, so APX $=v(S)$. Then $v^{\ast }\le v(S)+v_{i+1}\le v(S)+v(S)=2$ APX.
2. If $v(S)<v_{i+1}$, then the algorithm picks $\{i+1\}$, so APX = $v_{i+1}$. Then $v^{\ast }\le v(S)+v_{i+1}<2v_{i+1}=2$ APX.

So APX $\ge \frac{v^{\ast }}{2}\ge \frac{1}{2}$ OPT $■$.

Myerson’s lemma gives a payment rule for our allocation. A player either wins or not, so the allocation function looks like: Say this is for player $j$, and the jump occurs at $\overline{b_j}$. The payment for winning is then $\overline{b_j}$.

Voting Mechanism

Voting:

flowchart LR
b[Voting Mechanism]
c[Result]
Joe --> b
Bob --> b
Alice --> b
b --> c

If there are 2 candidates, this is easy: decide on the majority. Reflects the preferences of the people.

Condorcet’s paradox

3 candidates $a$, $b$, $c$.

$$\begin{array}{rlr}& \text{voter }1a{>}_{1}b{>}_{1}c& \text{A majority of voters prefer }a\text{, over }b\text{, }b\text{ over }c\text{, }c\text{ over }a\\ & \text{voter }2b{>}_{2}c{>}_2& ⟹a>b>c>a,\text{ not possible}\\ & \text{voter }3c{>}_{3}a{>}_{3}b& \text{If we only choose }1\text{ candidate, then a majority wants a different one}\end{array}$$

This could lead to “strategic voting”: a voter may be incentivized to not vote for their preferred candidate.

Example

$a$, $b$, are front runners, more prefer $a$ over $b$. A group of voters prefer $c$, who has no chance of winning. But they would rather $b$ win than $a$, so they vote for $b$ instead.

Problem: The usual voting mechanism does not incentivize voters to vote truthfully. So the votes that are submitted do not represent the will of the people.

Question

Is there a voting mechanism where truthful voting is a dominant strategy?

Answer: No, if we want our voting mechanism to have obvious good properties.

Social Welfare and Social Choice

Set up: Candidates $A$, voters $\{1,\dots ,n\}$. Let $L$ be the set of all total orders on $A$. (A total order is a relation $<$ on $A$ that is antisymmetric and transitive. Antisymmetric: If $a\ne b$, then $a>b$ or $b>a$. Transitive: If $a>b$ and $b>c$, then $a>c$.). Each voter $i$ has a total order of preferences ${<}_i\in L$. $a{<}_{i}b$ means voter $i$ prefers $b$ over $a$. A collection of all voter preferences $({<}_1,\dots ,{<}_n)\in L^n$.

Given a collection of voter preferences (how voters would vote), there are 2 outcomes that may be generated by a voting mechanism.

1. A social welfare function will output another total order on $A$ that represents “society’s preference” $F:L^n\to L$.
2. A social choice function will output one candidate from $A$ that represents “society’s choice” $f:L^n\to A$.

Properties of a social welfare function

Let $F:L^n\to L,({<}_1,\dots ,{<}_n)\in L^n$. Suppose $F({<}_1,\dots ,{<}_n)={<}_1$.

Good property 1: Unanimity. If every voter prefers $a$ over $b$, then society prefers $a$ over $b$.

Good property 2: Independence of irrelevant alternatives (IIA). The society’s preference between two candidates should only depend on the individual voters’ preferences of these two candidates, and not on others.

Suppose $({<}_1,\dots ,{<}_n)$, $({<}_1^{\prime },\dots ,{<}_n^{\prime })\in L^n$, $F({<}_1,\dots ,{<}_n)=<$, $F({<}_1^{\prime },\dots ,{<}_n^{\prime })={<}^{\prime }$. For two candidates $a,b\in A$, $a{<}_{i}b⟺a{<}_i^{\prime }b$ for each $i\in N$ implies $a<b⟺a{<}^{\prime }b$.

Flawed illustration of IIA: Suppose you can choose between studying game theory and cryptography (obviously choose game theory). Now you have the additional option of studying Galois theory, and you decide to study cryptography instead. This should not happen.

Bad property: Dictatorship. The society’s preferences completely agrees with one particular voter’s preferences in all cases. For all $({<}_1,\dots ,{<}_n)\in L^n$, $F({<}_1,\dots ,{<}_n)={<}_i$.

Theorem

Arrow’s impossibility theorem: Every social welfare function over a set of at least 3 candidates that satisfies unanimity and IIA is a dictatorship.

Arrow’s Impossibility Theorem

Sketchy proof: Suppose $F:L^n\to L$ satisfies unanimity and IIA.

1. We prove that given a candidate $b$, if each voter ranks $b$ at the top or bottom of their list, then $F$ also ranks $b$ at the top or bottom. Suppose otherwise, and there exist $a$, $c$ $\in A$ such that $F$ ranks $c<b<a$.

$$\begin{array}{cccccccc}\boxed{\begin{array}{c}b\\ a\\ c\end{array}}& \boxed{\begin{array}{c}b\\ c\\ a\end{array}}& \boxed{\begin{array}{c}a\\ c\\ b\end{array}}& \boxed{\begin{array}{c}c\\ a\\ b\end{array}}& \cdots & \boxed{\begin{array}{c}b\\ a\\ c\end{array}}& \boxed{\begin{array}{c}a\\ b\\ c\end{array}}& \\ \stackrel{\text{move }c\text{ just above }a}{\to }& & & & & & & \\ \boxed{\begin{array}{c}b\\ c\\ a\end{array}}& \boxed{\begin{array}{c}b\\ c\\ a\end{array}}& \boxed{\begin{array}{c}c\\ a\\ b\end{array}}& \boxed{\begin{array}{c}c\\ a\\ b\end{array}}& \cdots & \boxed{\begin{array}{c}b\\ c\\ a\end{array}}& \boxed{\begin{array}{c}a\\ b\\ c\end{array}}& \end{array}$$

Relative rankings of $a$, $b$ do not change. By IIA, relative rankings of $a$, $b$ do not change in $F$. Similar for the relative rankings of $b$, $c$. So $F$ keeps $a>b>c$ in the new preferences.

But $c$ is higher than $a$ in all voters’ lists, so by unanimity, $c>a$.

2. Find a potential voter that can be a dictator. Take an arbitrary voter preference $P\in L^n$. Create a sequence of preferences $P_0,P_1,\dots ,P_n$ by first moving $b$ to the bottom.

3. Let $a$, $c$ be two candidates other than $b$. They exist since there are at least 3 candidates. We will show that $F$ agrees with voter $i$ on the relative ranking of $a$, $c$. WLOG voter $i$ ranks $a$ above $c$ in the original $P$. Create a new voter reference $P^{\ast }$ by moving $a$ to the top of the list for voter $i$.

Note: Between $P$ and $P^{\ast }$, the relative rankings of $a$, $c$ do not change. By IIA, $F$ ranks $a$, $c$ the same in $P$ and $P^{\ast }$.

Goal: $F$ ranks $a$ above $c$ in $P^{\ast }$.

Compare $P_{i-1}$ and $P^{\ast }$. The relative rankings of $a$, $b$ do not change. By IIA, $F$ ranks $a$, $b$ the same in $P_{i-1}$ and $P^{\ast }$. $F$ ranks $b$ at the bottom in $P_{i-1}$, so $a>b$ for both $P_{i-1}$ and $P^{\ast }$.

Compare $P_i$ and $P^{\ast }$. The relative rankings of $b$, $c$ do not change. By IIA, $F$ ranks $b$, $c$ the same in $P_i$ and $P^{\ast }$. $F$ ranks $b$ at the top in $P_i$, so $b>c$ for both $P_i$ and $P^{\ast }$.

By transitivity, $F$ ranks $a>c$, which matches the ranking for voter $i$.

So $F$ agrees with voter $i$ on the relative rankings of any two candidates other than $b$.

4. Let $d$ be any candidate other than $b$. We will show that $F$ agrees with voter $i$ on $b$, $d$. There exists candidate $e$ that is not $b$, $d$. Run the arguments from 2 and 3 with $e$ instead of $b$. This gives us as voter $j$ such that $F$ agrees with voter $j$ for any two candidates that are not $e$. We show that $i=j$.

Suppose otherwise. Say $j<i$. Consider $P_{i-1}$. $F$ ranks $b$ at the bottom, so $d>b$. For voter $j$, $d$ is lower than $b$. And $F$ must agree with voter $j$ in all cases not involving $e$. So $F$ ranks $b>d$. This contradicts antisymmetric property of $F$.

Suppose $j>i$. Consider $P_i$. $F$ ranks $b>d$. But voter $j$ ranks $d$ over $b$. And $F$ agrees with voter $j$. So $d>b$ for $F$, contradiction.

So $F$ agrees with voter $i$ on the relative rankings of any two candidates. Hence voter $i$ is a dictator. $■$.

Gibbard-Satterthwaite Theorem

A social choice function $f:L^n\to A$ selects one candidate to represent the preferences of the voters. Just like social welfare functions, there cannot be a social choice function with good properties without the bad.

Good property: Strategy-proof. A voter cannot change the society’s choice to something they like better by changing their preferences. We say that $f$ can be strategically manipulated by voter $i$ if there exists $a$, $b$ $\in A$, $({<}_1,\dots ,{<}_n)\in L^n$ and ${<}_i^{\prime }\in L$ such that $a{<}_{i}b$, $f({<}_1,\dots ,{<}_i,\dots ,{<}_n)=a$, and $f({<}_1,\dots ,{<}_i^{\prime },\dots ,{<}_n)=b$. We say $f$ is strategy-proof if $f$ cannot be strategically manipulated.

Note: A strategy-proof voting mechanism will ensure that voters vote truthfully, so truthful voting is a dominant strategy.

Bad property: Dictatorship: There exists a voter $i$ such that $f$ will always choose the candidate at the top of voter $i$‘s list.

Theorem

(Gibbard-Satterthwaite): Any strategy-proof social choice function onto a set of at least 3 candidates is a dictatorship.

Main ideas for the proof: Assume $f:L^n\to A$ is strategy proof. Construct a social welfare function $F:L^n\to L$ as follows.

One can show that $f$ will pick either $a$ or $b$. If $f$ picks $a$, then set $a>b$ in $F$. Otherwise, set $b>a$. Do this for all pairs $a$, $b$ and we have constructed $F$.

Arbitrary voter preference. For some $a$, $b$ $\in A$, move them to the top of the list.

Need to show: $F$ is a total order, i.e. antisymmetric (easy) and transitive (hard). Then $F$ satisfies unanimity and IIA (not hard). Since there are at least 3 candidate, Arrow’s impossibility theorem implies that $F$ is a dictatorship. The dictator for $F$ is also the dictator for $f$.