lemkehowsonalgorithm.py

# -*- coding: utf-8 -*-
"""LemkeHowsonAlgorithm

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/1lBQeCbzHm6zN2gTmecuY-Z2q00WQrgXK
"""

import numpy as np

def lemke_howson(A, B):
    m, n = A.shape
    tableau = np.zeros((m + 1, n + 1))
    tableau[:-1, :-1] = A
    tableau[-1, :-1] = -B
    tableau[:-1, -1] = 1
    basis = np.arange(n, n + m)

    # Pivot selection function
    def pivot_selection(tableau, entering):
        mask = tableau[:, entering] > 0
        ratios = tableau[mask, -1] / tableau[mask, entering]
        if len(ratios) == 0:
            return -1
        min_ratio_idx = np.argmin(ratios)
        return np.nonzero(mask)[0][min_ratio_idx]

    # Perform pivoting operation
    def pivot(tableau, basis, leaving, entering):
        pivot_row = tableau[leaving, :]
        tableau[leaving, :] /= pivot_row[entering]
        for i, row in enumerate(tableau):
            if i != leaving:
                multiplier = row[entering] / pivot_row[entering]
                tableau[i, :] -= multiplier * pivot_row
        basis[leaving] = entering

    # Phase 1: Find initial basis
    for i in range(m):
        entering = np.argmin(tableau[-1, :-1])
        if tableau[-1, entering] >= 0:
            break
        leaving = pivot_selection(tableau, entering)
        pivot(tableau, basis, leaving, entering)

    # Phase 2: Find equilibrium
    while True:
        entering = np.argmax(tableau[-1, :-1])
        if tableau[-1, entering] <= 0:
            break
        leaving = pivot_selection(tableau, entering)
        if leaving == -1:
            break
        pivot(tableau, basis, leaving, entering)

    equilibrium = np.zeros(n)
    for i in range(m):
        if basis[i] < n:
            equilibrium[basis[i]] = tableau[i, -1]

    return equilibrium

# Example usage
A = np.array([[3, -1, 2], [-2, 4, -3], [1, 3, -1]])
B = np.array([[2, -4, 1], [-3, 2, 4], [1, 3, 2]])

equilibrium = lemke_howson(A, B)
print("Nash equilibrium strategies:")
print(equilibrium)