CO456

Professor: Martin Pei | Term: Fall 2025

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

Lecture 1

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

Lecture 2: 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 teh 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.

Lecture 3: 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. $■$

Lecture 4: 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. $■$

Lecture 5: 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$.

Lecture 6: 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$.

Lecture 7: 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' '< 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\}))$. $■$

Lecture 8: 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)$

Lecture 9: 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).

Lecture 10

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),thentheaverageis$\frac{11}{3}$,and$\frac{2}{3}$averageis$2 + \frac{4}{9}$.Player2istheclosest,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.

Lecture 11: 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.

Lecture 12: 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 }$. $■$

Lecture 13: 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^*$,isaNashequilibriumof$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.

Lecture 14

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.