Finding Dominant Strategy, Pure Nash Equilibrium and Mixed Nash Equilibrium in 2 player zero-sum game

Question

I am solving Computational Game Theory problems. I want to check if any two player zero-sum game has Dominant Strategy, Pure Nash Equilibrium and Mixed Nash Equilibrium.
I know that unfortunately Dominant Strategy and Pure Nash Equilibrium does not always exists. As far i know finding Mixed Nash Equilibrium is considerably harder than finding Dominant Strategy solutions or Pure Nash Equilibrium, even when the game is finite and there are only a constant number of players. But couldn't figure it out why?

I want to know how can I find them or can check if there exists any DS, PNE and MNE, for any two player zero-sum game. For example consider a zero-sum game given by the following matrix:

I would really appreciate it if someone can give me a better explanation about how to check if the above game has any Dominant Strategy, Pure Nash Equilibrium and Mixed Nash Equilibrium.

N.B. The example above is used just to make my question more clearer. You are welcome to explain this approach with any other matrix. Any resource link that has a clear derivation will also be count as an answer to my question.

Answer 1

The below functions provide a simple implementation for checking dominating strategy and pure Nash equilibrium for a 2-player game.

To find a dominant strategy for a given player we need to check if there exists a strategy that always leads to better payoff, irrespective of the other player's strategy.

To check whether a given pair of moves corresponds to a (pure) Nash equilibrium, we need to check whether any of the players can do better by changing his strategy or not.

import numpy as np
import pandas as pd

def get_dominating_strategy(player, payoffs_df, other_strategies):
    other_player = 'p2' if player == 'p1' else 'p1'
    all_best_strategies = set([])
    for other_strategy in other_strategies:
        sdf = payoffs_df[payoffs_df[other_player + '_strategy'] == other_strategy]
        cur_strategy = sdf.loc[sdf[player + '_payoff'].idxmax(), player + '_strategy']
        all_best_strategies.add(cur_strategy)
    return list(all_best_strategies)[0] if len(all_best_strategies) == 1 else None

def exists_better_strategy(player, cur_strategy, cur_payoff, other_strategy, payoffs_df, strategies):
    other_player = 'p2' if player == 'p1' else 'p1'
    sdf = payoffs_df[payoffs_df[other_player + '_strategy'] == other_strategy]
    for i in sdf.index:
        if sdf.loc[i, player + '_payoff'] > cur_payoff:
            return True
    return False
            
def get_pure_nash_equilibriums(payoffs_df, p1_strategies, p2_strategies):
    nash_equlibriums = []
    for i in range(len(payoffs_df)):
        cur_state = payoffs_df.loc[i]
        p1_payoff, p2_payoff = cur_state['p1_payoff'], cur_state['p2_payoff']
        p1_strategy, p2_strategy = cur_state['p1_strategy'], cur_state['p2_strategy']
        nash_equlibrium_found = True
        if exists_better_strategy('p1', p1_strategy, p1_payoff, p2_strategy, payoffs_df, p1_strategies):
            nash_equlibrium_found = False
            continue
        if exists_better_strategy('p2', p2_strategy, p2_payoff, p1_strategy, payoffs_df, p2_strategies):
            nash_equlibrium_found = False
            continue
        if nash_equlibrium_found:
            nash_equlibriums.append((p1_strategy, p2_strategy))
    return None if len(nash_equlibriums) == 0 else nash_equlibriums
    

Now, let's test for the famous Prisoner Dilemma game with the following payoff table, here let's use pandas DataFrame to store the utility table.

p1_strategies = ['confess', 'silent']
p2_strategies = ['confess', 'silent']
payoffs_PD = pd.DataFrame({'p1_strategy': ['confess', 'confess', 'silent', 'silent'],
                           'p2_strategy': ['confess', 'silent', 'confess', 'silent'],
                           'p1_payoff': [0, 3, -1, 1],
                           'p2_payoff': [0, -1, 3, 1]})

print(payoffs_PD)  # utilities
#       p1_strategy p2_strategy  p1_payoff  p2_payoff
# 0     confess     confess          0          0
# 1     confess      silent          3         -1
# 2      silent     confess         -1          3
# 3      silent      silent          1          1

ds_p1 = get_dominating_strategy('p1', payoffs_PD, p2_strategies)
ds_p2 = get_dominating_strategy('p2', payoffs_PD, p1_strategies)
print(ds_p1, ds_p2) # dominating strategy for the players
# confess confess

nes = get_pure_nash_equilibriums(payoffs_PD, p1_strategies, p2_strategies)
# pure Nash equlibriums, only 1 here
print(nes)
# [('confess', 'confess')]

Let's test with another game with the following utilities:

p1_strategies = ['T', 'B']
p2_strategies = ['L', 'R']
payoffs_df = pd.DataFrame({'p1_strategy': ['T', 'T', 'B', 'B'],
                           'p2_strategy': ['L', 'R', 'L', 'R'],
                           'p1_payoff': [7, 0, 2, 4],
                           'p2_payoff': [6, 5, 0, 3]})

print(payoffs_df)
#   p1_strategy p2_strategy  p1_payoff  p2_payoff
# 0           T           L          7          6
# 1           T           R          0          5
# 2           B           L          2          0
# 3           B           R          4          3

ds_p1 = get_dominating_strategy('p1', payoffs_df, p2_strategies)
ds_p2 = get_dominating_strategy('p2', payoffs_df, p1_strategies)
print(ds_p1, ds_p2) # no dominating strategy exists for any of the players
# None None

nes = get_pure_nash_equilibriums(payoffs_df, p1_strategies, p2_strategies)
print(nes) # 2 NE solutions exist
# [('T', 'L'), ('B', 'R')]

In case of mixed strategy equilibrium, we need to solve a linear system of equations, For example, consider the following payoff table

#              player 2 
#              S1      S2         probability
# player 1 S1  a \ e   b \ f      p_1 
#          S2  c \ g   d \ h      p_2
# probability    q_1     q_2

The player1 takes strategy S1, S2 with probability p_1 and p_2, respectively.

The player2 takes strategy S1, S2 with probability q_1 and q_2, respectively.

Then we must have p_1 + p_2 = 1 and q_1 + q_2 = 1.

At Nash equilibrium, player2 becomes indifferent of his strategy S1 and S2, so we must have the expected payoffs equal:

p_1*a + p_2*c = p_1*b + p_2*d => p_1(a-b) + p_2*(c-d) = 0

Hence we have the following linear system of equations to solve for (p_1, p_2) at NE:

1*p_1 + 1*p_2 = 1

(a-b)*p_1 + (c-d)*p_2 = 0

In matrix form, in order to find (p_1, p_2) at NE, we need to solve(A, b), where A = [[1, 1], [a-b, c-d]] and b=[1,0]. Similarly for (q_1, q_2), we need to solve another linear system.

Generalizing, we can implement the mixed strategy NE as follows.

def get_mixed_nash_equilibriums(payoffs_df, p1_strategies, p2_strategies):
    m, n = len(p1_strategies), len(p2_strategies)
    assert(m == n) # assuming player1 and player2 have same number of strategies, for simplicity
    A = np.zeros((m, m))
    b = [1] + [0]*(m-1)
    A[0] = [1]*m  # p_1 + p_2 + ... + p_m = 1
    for j in range(n-1):
        for i in range(m):
            s, s1, s2 = p1_strategies[i], p2_strategies[j], p2_strategies[j+1]
            A[j+1, i] = payoffs_df.loc[(payoffs_df['p1_strategy'] == s) & (payoffs_df['p2_strategy'] == s1), 'p2_payoff']
            A[j+1, i] -= payoffs_df.loc[(payoffs_df['p1_strategy'] == s) & (payoffs_df['p2_strategy'] == s2), 'p2_payoff']
    ps = np.linalg.solve(A, b)
    A = np.zeros((n, n))
    b = [1] + [0]*(n-1)
    A[0] = [1]*n  # q_1 + q_2 + ... + q_n = 1
    for j in range(m-1):
        for i in range(n):
            s, s1, s2 = p2_strategies[i], p1_strategies[j], p1_strategies[j+1]
            A[j+1, i] = payoffs_df.loc[(payoffs_df['p2_strategy'] == s) & (payoffs_df['p1_strategy'] == s1), 'p1_payoff']
            A[j+1, i] -= payoffs_df.loc[(payoffs_df['p2_strategy'] == s) & (payoffs_df['p1_strategy'] == s2), 'p1_payoff']
    qs = np.linalg.solve(A, b)
    return (ps, qs)

Now, let's test the following game for the existence of DS, pure NE and mixed NE:

p1_strategies = ['H', 'T']
p2_strategies = ['H', 'T']
payoffs_df = pd.DataFrame({'p1_strategy': ['H', 'H', 'T', 'T'],
                           'p2_strategy': ['H', 'T', 'H', 'T'],
                           'p1_payoff': [1, -1, -1, 1],
                           'p2_payoff': [-1, 1, 1, -1]})
print(payoffs_df)
#  p1_strategy p2_strategy  p1_payoff  p2_payoff
#0           H           H          1         -1
#1           H           T         -1          1
#2           T           H         -1          1
#3           T           T          1         -1
ds_p1 = get_dominating_strategy('p1', payoffs_df, p2_strategies)
ds_p2 = get_dominating_strategy('p2', payoffs_df, p1_strategies)
print(ds_p1, ds_p2)
# None None
nes = get_pure_nash_equilibriums(payoffs_df, p1_strategies, p2_strategies)
print(nes)
# None
ps, qs = get_mixed_nash_equilibriums(payoffs_df, p1_strategies, p2_strategies)
print(ps, qs)
# [0.5 0.5] [0.5 0.5]

Note that both DS and pure NE don't exist in above case where a mixed NE exists.

Let's try another game, where the same thing happens, although with different probabilities:

p1_strategies = ['F', 'B']
p2_strategies = ['F', 'B']
payoffs_df = pd.DataFrame({'p1_strategy': ['F', 'F', 'B', 'B'],
                           'p2_strategy': ['F', 'B', 'F', 'B'],
                           'p1_payoff': [90, 20, 30, 60],
                           'p2_payoff': [10, 80, 70, 40]})
print(payoffs_df)
#  p1_strategy p2_strategy  p1_payoff  p2_payoff
#0           F           F         90         10
#1           F           B         20         80
#2           B           F         30         70
#3           B           B         60         40
ds_p1 = get_dominating_strategy('p1', payoffs_df, p2_strategies)
ds_p2 = get_dominating_strategy('p2', payoffs_df, p1_strategies)
print(ds_p1, ds_p2)
# None None
nes = get_pure_nash_equilibriums(payoffs_df, p1_strategies, p2_strategies)
print(nes)
# None
ps, qs = get_mixed_nash_equilibriums(payoffs_df, p1_strategies, p2_strategies)
print(ps, qs)
# [0.3 0.7] [0.4 0.6]