Nash Equilibrium Example

Nash Equilibrium (NE) is a solution concept in game theory. In a two-player game, players A and B choose actions and receive payoffs that depend on both actions taken. The players do not receive the same payoff, and a decision made in self-interest by one player may adversely affect the other. A pair of actions chosen by the players is a NE if neither player can benefit by choosing an alternative action given the other player's choice.

We provide three examples of increasing complexity to illustrate how Hava can generate the collection of all NE pairs.

Bimatrix Example

The table below is a payoff matrix for a two-player game in which each player can take one of three possible actions. The first (second) number in each pair of numbers within each cell represents the payoff to player A (player B) if the pair of actions corresponding to that cell is chosen by the players. For example, if player A chooses option 2 and player B chooses option 3, player 1 receives 5 and player 2 receives 15. Each highlighted cell is a NE pair.

Option 1 Option 2 Option 3

Option 1 0, 0 25, 40 5, 10

Option 2 40, 25 0, 0 5, 15

Option 3 10, 5 15, 5 10, 10

	Option 1	Option 2	Option 3
Option 1	0, 0	25, 40	5, 10
Option 2	40, 25	0, 0	5, 15
Option 3	10, 5	15, 5	10, 10

Generating Nash Equilibria

For a simple example like this one, visual inspection can be used to find all NE. However, when players can take many actions, this can prove quite challenging. Instead, we can use Hava to generate all NE pairs.

We proceed in three steps:

Specify the problem data. Tokens are used to define the action sets:

token OPTION1, OPTION2, OPTION3;
ASet = (OPTION1, OPTION2, OPTION3);
BSet = (OPTION1, OPTION2, OPTION3);

Let a in ASet and b in BSet denote possible actions taken by Players A and B, respectively.
The payoffs for each player can be represented by functions:

function APayoff(a, b) = 
  collect((0, 25, 5), (40, 0, 5), (10, 15, 10))[a:ASet][b:BSet];
function BPayoff(a, b) = 
  collect((0, 40, 10), (25, 0, 15), (5, 5, 10))[a:ASet][b:BSet];

Formulate the best response functions. If Player A knows that Player B will take action b, then Player A chooses any action a that maximizes APayoff(a, b). Player B's rule is similar. These best response functions can be expressed in Hava as:
AResponse(b) = collect(a in ASet | APayoff(a, b)==ABestResponseValue(b)) {a}; ABestResponseValue(b) = max(a in ASet) {APayoff(a, b)}; BResponse(a) = collect(b in BSet | BPayoff(a, b)==BBestResponseValue(a)) {b}; BBestResponseValue(a) = max(b in BSet) {BPayoff(a, b)};
Note that the best response might include more than one action. All such actions are required to discover the collection of all NE pairs.

Enumerate all pairs, and identify those that are NE:

NashEquilibria = 
  collect(a in ASet, b in BSet | a in AResponse(b) && b in BResponse(a)) {(a, b)};

Click here to view the complete solution to the first NE problem.

Cournot Duopoly

In a Cournot duopoly, two companies compete to produce a homogeneous product for a single market. Each must decide the quantity it will produce (production quantities must be integer). Each faces a constant marginal cost, i.e., it costs the same to produce each unit. The market price depends on total supply; as total supply increases, market price decreases. Consequently, each company is directly affected by the quantity chosen by the other company.

For a concrete example, we assume that if Player A chooses quantity a and Player B chooses quantity b, then the market price and payoffs to each player are as follows:

D = 25;     // Market demand
C = 10;     // Marginal cost

function price(a, b) = D - a - b;
function APayoff(a, b) = (price(a, b) - C)*a;
function BPayoff(a, b) = (price(a, b) - C)*b;

The best response functions are expressed as:

AResponse(b) = 
  collect(a in ASet | APayoff(a, b)==ABestResponseValue(b)) {a};
ABestResponseValue(b) = max(a in ASet(b)) {APayoff(a, b)};
ASet = 0 to D;
ASet(b) = 0 to D-b;

BResponse(a) = 
  collect(b in BSet(a) | BPayoff(a, b)==BBestResponseValue(a)) {b};
BBestResponseValue(a) = max(b in BSet(a)) {BPayoff(a, b)};
BSet(a) = 0 to D-a;

The code to generate the Nash Equilibria is

NashEquilibria = 
  collect(a in ASet, b in BSet(a) | a in AResponse(b) && b in BResponse(a)) 
    {(a, b)};

Click here to view the complete solution to the Cournot Duopoly problem.

Cournot Duopoly with R&D Investment

We extend the previous example by allowing each company to spend money to lower its marginal cost of production. Specifically, if a company spends e, its constant marginal cost becomes

C(e) = C - sqrt(e);

(The square root function ensures diminishing returns to R&D investment.)
The maximum reduction in per-unit cost is 50%, and so the maximum R&D expenditure is 25.

Each company must now make two choices: its R&D expenditure, e, and its quantity, q.
We combine these into a single Hava structure:

struct Action(e, q);

The action sets for each player are now represented as:

FSet(r) = collect(e=0 to eMax, q=0 to qMax(r, e)) {Action(e, q)};
qMax(r, e) = max(floor(25-C(e)-r),0);
ASet(b) = FSet(b.q);
BSet(a) = FSet(a.q);
eMax = 25;

Click here to view the complete solution to the problem of Cournot Duopoly with R&D Investment.