**Daisuke Oyama**

*Faculty of Economics, University of Tokyo*

This notebook demonstrates the functionalities of Games.jl.

The first time you run this notebook, you need to install the Games.jl package by removing the "#" below:

In [1]:

```
# Pkg.clone("https://github.com/QuantEcon/Games.jl")
```

In [2]:

```
using Games
```

An $N$-player *normal form game* is a triplet $g = (I, (A_i)_{i \in I}, (u_i)_{i \in I})$ where

- $I = \{1, \ldots, N\}$ is the set of players,
- $A_i = \{1, \ldots, n_i\}$ is the set of actions of player $i \in I$, and
- $u_i \colon A_i \times A_{i+1} \times \cdots \times A_{i+N-1} \to \mathbb{R}$ is the payoff function of player $i \in I$,

where $i+j$ is understood modulo $N$.

Note that we adopt the convention that the $1$-st argument of the payoff function $u_i$ is player $i$'s own action and the $j$-th argument, $j = 2, \ldots, N$, is player ($i+j-1$)'s action (modulo $N$).

In our package,
a normal form game and a player are represented by
the types `NormalFormGame`

and `Player`

, respectively.

A `Player`

carries the player's payoff function and implements in particular
a method that returns the best response action(s) given an action of the opponent player,
or a profile of actions of the opponents if there are more than one.

A `NormalFormGame`

is in effect a container of `Player`

instances.

`NormalFormGame`

¶There are several ways to create a `NormalFormGame`

instance.

The first is to pass an array of payoffs for all the players, i.e., an $(N+1)$-dimenstional array of shape $(n_1, \ldots, n_N, N)$ whose $(a_1, \ldots, a_N)$-entry contains an array of the $N$ payoff values for the action profile $(a_1, \ldots, a_N)$.

As an example, consider the following game ("**Matching Pennies**"):

$ \begin{bmatrix} 1, -1 & -1, 1 \\ -1, 1 & 1, -1 \end{bmatrix} $

In [3]:

```
matching_pennies_bimatrix = Array{Float64}(2, 2, 2)
matching_pennies_bimatrix[1, 1, :] = [1, -1] # payoff profile for action profile (1, 1)
matching_pennies_bimatrix[1, 2, :] = [-1, 1]
matching_pennies_bimatrix[2, 1, :] = [-1, 1]
matching_pennies_bimatrix[2, 2, :] = [1, -1]
g_MP = NormalFormGame(matching_pennies_bimatrix)
```

Out[3]:

In [4]:

```
g_MP.players[1] # Player instance for player 1
```

Out[4]:

In [5]:

```
g_MP.players[2] # Player instance for player 2
```

Out[5]:

In [6]:

```
g_MP.players[1].payoff_array # Player 1's payoff array
```

Out[6]:

In [7]:

```
g_MP.players[2].payoff_array # Player 2's payoff array
```

Out[7]:

In [8]:

```
g_MP[1, 1] # payoff profile for action profile (1, 1)
```

Out[8]:

If a square matrix (2-dimensional array) is given, then it is considered to be a symmetric two-player game.

Consider the following game (symmetric $2 \times 2$ "**Coordination Game**"):

$ \begin{bmatrix} 4, 4 & 0, 3 \\ 3, 0 & 2, 2 \end{bmatrix} $

In [9]:

```
coordination_game_matrix = [4 0;
3 2] # square matrix
g_Coo = NormalFormGame(coordination_game_matrix)
```

Out[9]:

In [10]:

```
g_Coo.players[1].payoff_array # Player 1's payoff array
```

Out[10]:

In [11]:

```
g_Coo.players[2].payoff_array # Player 2's payoff array
```

Out[11]:

Another example ("**Rock-Paper-Scissors**"):

$ \begin{bmatrix} 0, 0 & -1, 1 & 1, -1 \\ 1, -1 & 0, 0 & -1, 1 \\ -1, 1 & 1, -1 & 0, 0 \end{bmatrix} $

In [12]:

```
RPS_matrix = [0 -1 1;
1 0 -1;
-1 1 0]
g_RPS = NormalFormGame(RPS_matrix)
```

Out[12]:

The second is to specify the sizes of the action sets of the players
to create a `NormalFormGame`

instance filled with payoff zeros,
and then set the payoff values to each entry.

Let us construct the following game ("**Prisoners' Dilemma**"):

$ \begin{bmatrix} 1, 1 & -2, 3 \\ 3, -2 & 0, 0 \end{bmatrix} $

In [13]:

```
g_PD = NormalFormGame((2, 2)) # There are 2 players, each of whom has 2 actions
g_PD[1, 1] = [1, 1]
g_PD[1, 2] = [-2, 3]
g_PD[2, 1] = [3, -2]
g_PD[2, 2] = [0, 0];
```

In [14]:

```
g_PD
```

Out[14]:

In [15]:

```
g_PD.players[1].payoff_array
```

Out[15]:

Finally, a `NormalFormGame`

instance can be constructed by giving an array of `Player`

instances,
as explained in the next section.

`Player`

¶A `Player`

instance is created by passing an array of dimension $N$
that represents the player's payoff function ("payoff array").

Consider the following game (a variant of "**Battle of the Sexes**"):

$ \begin{bmatrix} 3, 2 & 1, 1 \\ 0, 0 & 2, 3 \end{bmatrix} $

In [16]:

```
player1 = Player([3 1; 0 2])
player2 = Player([2 0; 1 3]);
```

Beware that in `payoff_array[h, k]`

, `h`

refers to the player's own action,
while `k`

refers to the opponent player's action.

In [17]:

```
player1.payoff_array
```

Out[17]:

In [18]:

```
player2.payoff_array
```

Out[18]:

Passing an array of Player instances is the third way to create a `NormalFormGame`

instance:

In [19]:

```
g_BoS = NormalFormGame((player1, player2))
```

Out[19]:

Games with more than two players are also supported.

Let us consider the following version of $N$-player **Cournot Game**.

There are $N$ firms (players) which produce a homogeneous good with common constant marginal cost $c \geq 0$. Each firm $i$ simultaneously determines the quantity $q_i \geq 0$ (action) of the good to produce. The inverse demand function is given by the linear function $P(Q) = a - Q$, $a > 0$, where $Q = q_1 + \cdots + q_N$ is the aggregate supply. Then the profit (payoff) for firm $i$ is given by $$ u_i(q_i, q_{i+1}, \ldots, q_{i+N-1}) = P(Q) q_i - c q_i = \left(a - c - \sum_{j \neq i} q_j - q_i\right) q_i. $$

Theoretically, the set of actions, i.e., available quantities, may be the set of all nonnegative real numbers $\mathbb{R}_+$ (or a bounded interval $[0, \bar{q}]$ with some upper bound $\bar{q}$), but for computation on a computer we have to discretize the action space and only allow for finitely many grid points.

The following script creates a `NormalFormGame`

instance of the Cournot game as described above,
assuming that the (common) grid of possible quantity values is stored in an array `q_grid`

.

In [20]:

```
function cournot(a::Real, c::Real, ::Val{N}, q_grid::Vector{T}) where {N,T<:Real}
nums_actions = ntuple(x->length(q_grid), Val(N))
S = promote_type(typeof(a), typeof(c), T)
payoff_array= Array{S}(nums_actions)
for I in CartesianRange(nums_actions)
Q = zero(S)
for i in 1:N
Q += q_grid[I[i]]
end
payoff_array[I] = (a - c - Q) * q_grid[I[1]]
end
players = ntuple(x->Player(payoff_array), Val(N))
return NormalFormGame(players)
end
```

Out[20]:

Here's a simple example with three firms, marginal cost $20$, and inverse demand function $80 - Q$, where the feasible quantity values are assumed to be $10$ and $15$.

In [21]:

```
a, c = 80, 20
N = 3
q_grid = [10, 15] # [1/3 of Monopoly quantity, Nash equilibrium quantity]
g_Cou = cournot(a, c, Val(N), q_grid)
```

Out[21]:

In [22]:

```
g_Cou.players[1]
```

Out[22]:

In [23]:

```
g_Cou.nums_actions
```

Out[23]:

A *Nash equilibrium* of a normal form game is a profile of actions
where the action of each player is a best response to the others'.

The `Player`

object has methods `best_response`

and `best_responses`

.

Consider the Matching Pennies game `g_MP`

defined above.
For example, player 1's best response to the opponent's action 2 is:

In [24]:

```
best_response(g_MP.players[1], 2)
```

Out[24]:

Player 1's best responses to the opponent's mixed action `[0.5, 0.5]`

(we know they are 1 and 2):

In [25]:

```
# By default, returns the best response action with the smallest index
best_response(g_MP.players[1], [0.5, 0.5])
```

Out[25]:

In [26]:

```
# With tie_breaking='random', returns randomly one of the best responses
best_response(g_MP.players[1], [0.5, 0.5], tie_breaking="random") # Try several times
```

Out[26]:

`best_responses`

returns an array of all the best responses:

In [27]:

```
best_responses(g_MP.players[1], [0.5, 0.5])
```

Out[27]:

For this game, we know that `([0.5, 0.5], [0.5, 0.5])`

is a (unique) Nash equilibrium.

In [28]:

```
is_nash(g_MP, ([0.5, 0.5], [0.5, 0.5]))
```

Out[28]:

In [29]:

```
is_nash(g_MP, (1, 1))
```

Out[29]:

In [30]:

```
is_nash(g_MP, ([1., 0.], [0.5, 0.5]))
```

Out[30]:

Our package does not have sophisticated algorithms to compute Nash equilibria (yet)...
One might look at the `game_theory`

module in QuantEcon.py or Gambit,
which implement several such algorithms.

For small games, we can find pure action Nash equilibria by brute force,
by calling the method `pure_nash`

.

In [31]:

```
function print_pure_nash_brute(g::NormalFormGame)
NEs = pure_nash(g)
num_NEs = length(NEs)
if num_NEs == 0
msg = "no pure Nash equilibrium"
elseif num_NEs == 1
msg = "1 pure Nash equilibrium:\n$(NEs[1])"
else
msg = "$num_NEs pure Nash equilibria:\n"
for (i, NE) in enumerate(NEs)
i < num_NEs ? msg *= "$NE," : msg *= "$NE"
end
end
println(join(["The game has ", msg]))
end
```

Out[31]:

Matching Pennies:

In [32]:

```
print_pure_nash_brute(g_MP)
```

Coordination game:

In [33]:

```
print_pure_nash_brute(g_Coo)
```

Rock-Paper-Scissors:

In [34]:

```
print_pure_nash_brute(g_RPS)
```

Battle of the Sexes:

In [35]:

```
print_pure_nash_brute(g_BoS)
```

Prisoners' Dillema:

In [36]:

```
print_pure_nash_brute(g_PD)
```

Cournot game:

In [37]:

```
print_pure_nash_brute(g_Cou)
```

In some games, such as "supermodular games" and "potential games", the process of sequential best responses converges to a Nash equilibrium.

Here's a script to find *one* pure Nash equilibrium by sequential best response, if it converges.

In [38]:

```
function sequential_best_response(g::NormalFormGame;
init_actions::Union{Vector{Int},Void}=nothing,
tie_breaking="smallest",
verbose=true)
N = num_players(g)
a = Array{Int}(N)
if init_actions == nothing
init_actions = ones(Int, N)
end
copy!(a, init_actions)
if verbose
println("init_actions: $a")
end
new_a = Array{Int}(N)
max_iter = prod(g.nums_actions)
for t in 1:max_iter
copy!(new_a, a)
for (i, player) in enumerate(g.players)
if N == 2
a_except_i = new_a[3-i]
else
a_except_i = (new_a[i+1:N]..., new_a[1:i-1]...)
end
new_a[i] = best_response(player, a_except_i,
tie_breaking=tie_breaking)
if verbose
println("player $i: $new_a")
end
end
if new_a == a
return a
else
copy!(a, new_a)
end
end
println("No pure Nash equilibrium found")
return a
end
```

Out[38]:

A Cournot game with linear demand is known to be a potential game, for which sequential best response converges to a Nash equilibrium.

Let us try a bigger instance:

In [39]:

```
a, c = 80, 20
N = 3
q_grid = collect(linspace(0, a-c, 13)) # [0, 5, 10, ..., 60]
g_Cou = cournot(a, c, Val(N), q_grid)
```

Out[39]:

In [40]:

```
a_star = sequential_best_response(g_Cou) # By default, start with (1, 1, 1)
println("Nash equilibrium indices: $a_star")
println("Nash equilibrium quantities: $(q_grid[a_star])")
```

In [41]:

```
# Start with the largest actions (13, 13, 13)
sequential_best_response(g_Cou, init_actions=[13, 13, 13])
```

Out[41]:

The limit action profile is indeed a Nash equilibrium:

In [42]:

```
is_nash(g_Cou, tuple(a_star...))
```

Out[42]:

In fact, the game has other Nash equilibria (because of our choice of grid points and parameter values):

In [43]:

```
print_pure_nash_brute(g_Cou)
```

Make it bigger:

In [44]:

```
N = 4
q_grid = collect(linspace(0, a-c, 61)) # [0, 1, 2, ..., 60]
g_Cou = cournot(a, c, Val(N), q_grid)
```

Out[44]:

In [45]:

```
sequential_best_response(g_Cou)
```

Out[45]:

In [46]:

```
sequential_best_response(g_Cou, init_actions=[1, 1, 1, 31])
```

Out[46]:

Sequential best response does not converge in all games:

In [47]:

```
print(g_MP) # Matching Pennies
```

In [48]:

```
sequential_best_response(g_MP)
```

Out[48]:

The routine `support_enumeration`

,
which is for two-player games, visits all equal-size support pairs
and checks whether each pair has a Nash equilibrium (in mixed actions) by the indifference condition.
(This should thus be used only for small games.)
For nondegenerate games, this routine returns all the Nash equilibria.

Matching Pennies:

In [49]:

```
support_enumeration(g_MP)
```

Out[49]:

Coordination game:

In [50]:

```
support_enumeration(g_Coo)
```

Out[50]:

Rock-Paper-Scissors:

In [51]:

```
support_enumeration(g_RPS)
```

Out[51]:

Consider the $6 \times 6$ game by von Stengel (1997), page 12:

In [52]:

```
player1 = Player(
[ 9504 -660 19976 -20526 1776 -8976;
-111771 31680 -130944 168124 -8514 52764;
397584 -113850 451176 -586476 29216 -178761;
171204 -45936 208626 -263076 14124 -84436;
1303104 -453420 1227336 -1718376 72336 -461736;
737154 -227040 774576 -1039236 48081 -300036]
)
player2 = Player(
[ 72336 -461736 1227336 -1718376 1303104 -453420;
48081 -300036 774576 -1039236 737154 -227040;
29216 -178761 451176 -586476 397584 -113850;
14124 -84436 208626 -263076 171204 -45936;
1776 -8976 19976 -20526 9504 -660;
-8514 52764 -130944 168124 -111771 31680]
)
g_vonStengel = NormalFormGame(player1, player2);
```

In [53]:

```
length(support_enumeration(g_vonStengel))
```

Out[53]:

Note that the $n \times n$ game where the payoff matrices are given by the identy matrix has $2^n−1$ equilibria. It had been conjectured that this is the maximum number of equilibria of any nondegenerate $n \times n$ game. The game above, the number of whose equilibria is $75 > 2^6 - 1 = 63$, was presented as a counter-example to this conjecture.

Next, let us study the **All-Pay Acution**,
where, unlike standard auctions,
bidders pay their bids regardless of whether or not they win.
Situations modeled as all-pay auctions include
job promotion, R&D, and rent seeking competitions, among others.

Here we consider a version of All-Pay Auction with complete information, symmetric bidders, discrete bids, bid caps, and "full dissipation" (where the prize is materialized if and only if there is only one bidder who makes a highest bid).

Specifically, each of $N$ players simultaneously bids an integer from $\{0, 1, \ldots, c\}$,
where $c$ is the common (integer) bid cap.
If player $i$'s bid is higher than all the other players',
then he receives the prize, whose value is $r$, common to all players,
and pays his bid $b_i$.
Otherwise, he pays $b_i$ and receives nothing (zero value).
In particular, if there are more than one players who make the highest bid,
the prize gets *fully dissipated* and all the players receive nothing.
Thus, player $i$'s payoff function is
$$
u_i(b_i, b_{i+1}, \ldots, b_{i+N-1}) =
\begin{cases}
r - b_i & \text{if $b_i > b_j$ for all $j \neq i$}, \\ - b_i & \text{otherwise}.
\end{cases}
$$

The following is a script to construct a `NormalFormGame`

instance
for the All-Pay Auction game:

In [54]:

```
function all_pay_auction(r::T, c::Integer, ::Val{N};
dissipation::Bool=true) where {N,T<:Real}
nums_actions = ntuple(x->c+1, Val(N))
S = typeof(zero(T)/one(T))
payoff_array= Array{S}(nums_actions)
num_ties = 0
for bids in CartesianRange(nums_actions)
payoff_array[bids] = -(bids[1]-1)
num_ties = 1
for j in 2:N
if bids[j] > bids[1]
num_ties = 0
break
elseif bids[j] == bids[1]
if dissipation
num_ties = 0
break
else
num_ties += 1
end
end
end
if num_ties > 0
payoff_array[bids] += r / num_ties
end
end
players = ntuple(x->Player(payoff_array), Val(N))
return NormalFormGame(players)
end
```

Out[54]:

In [55]:

```
N = 2
c = 5 # odd
r = 8;
```

In [56]:

```
g_APA_odd = all_pay_auction(r, c, Val(N))
g_APA_odd.players[1]
```

Out[56]:

Clearly, this game has no pure-action Nash equilibrium. Indeed:

In [57]:

```
pure_nash(g_APA_odd)
```

Out[57]:

As pointed out by Dechenaux et al. (2006),
there are three Nash equilibria when the bid cap `c`

is odd
(so that there are an even number of actions for each player):

In [58]:

```
support_enumeration(g_APA_odd)
```

Out[58]:

In addition to a symmetric, totally mixed equilibrium (the third), there are two asymmetric, "alternating" equilibria (the first and the second).

If `e`

is even, there is a unique equilibrium, which is symmetric and totally mixed.
For example:

In [59]:

```
c = 6 # even
g_APA_even = all_pay_auction(r, c, Val(N))
support_enumeration(g_APA_even)
```

Out[59]:

E. Dechenaux, D. Kovenock, and V. Lugovskyy (2006), "Caps on bidding in all-pay auctions: Comments on the experiments of A. Rapoport and W. Amaldoss," Journal of Economic Behavior and Organization 61, 276-283.

B. von Stengel (1997), "New Lower Bounds for the Number of Equilibria in Bimatrix Games."