Code editing task: nash_equilibrium
Topic: DSA; change kind: adaptive

Original code:
from typing import List, Tuple


class Cell:
    def __init__(self, pay1, pay2):
        self.pay1 = pay1
        self.pay2 = pay2


class Game:
    def __init__(self, p1: List[str], p2: List[str], payoffs: List[List[Cell]]) -> None:
        """
        p1: list of strategies for player 1
        p2: list of strategies for player 2
        payoffs: list of lists of Cells, representing the payoff matrix

        Example game:
              A     B
          |-----|-----|
        X | 1,2 | 2,1 |
          |-----|-----|
        Y | 3,3 | 4,4 |
          |-----|-----|

        p1 = ["X", "Y"]
        p2 = ["A", "B"]
        payoffs = [
            [Cell(1, 2), Cell(2, 1)],
            [Cell(3, 3), Cell(4, 4)]
        ]
        """

        # validate that this is a proper payoff matrix
        assert len(p1) == len(payoffs)
        assert len(p2) == len(payoffs[0])
        assert all(len(row) == len(p2) for row in payoffs)

        self.p1 = p1
        self.p2 = p2
        self.payoffs = payoffs

    def does_dominate(self, s1: str, s2: str, p: int, weak: bool = False) -> bool:
        assert p in [0, 1], "invalid player index"
        if p == 0:
            assert s1 in self.p1 and s2 in self.p1, "invalid strategy"
        else:
            assert s1 in self.p2 and s2 in self.p2, "invalid strategy"

        s1_index = self.p1.index(s1) if p == 0 else self.p2.index(s1)
        s2_index = self.p1.index(s2) if p == 0 else self.p2.index(s2)

        domination = True
        strict_found = False

        for i in range(len(self.payoffs)):
            if p == 0:
                payoff_s1 = self.payoffs[s1_index][i].pay1
                payoff_s2 = self.payoffs[s2_index][i].pay1
            else:
                payoff_s1 = self.payoffs[i][s1_index].pay2
                payoff_s2 = self.payoffs[i][s2_index].pay2

            if weak:
                if payoff_s1 < payoff_s2:
                    domination = False
                    break
                elif payoff_s1 > payoff_s2:
                    strict_found = True
            else:
                if payoff_s1 <= payoff_s2:
                    domination = False
                    break

        if weak:
            return domination and strict_found
        else:
            return domination

    def best_response(self, s: str, p: int) -> List[str]:
        """
        Returns the best response(s) for player p to strategy s
        made by the other player.
        Can be multiple in the case of two or more equally good responses.
        """
        assert p in [0, 1], "invalid player index"
        if p == 0:
            assert s in self.p2, "invalid strategy for player 2"
            s_index = self.p2.index(s)
            best_payoff = float('-inf')
            best_response = None
            for i, strategy in enumerate(self.p1):
                payoff = self.payoffs[i][s_index].pay1
                if payoff > best_payoff:
                    best_payoff = payoff
                    best_response = [strategy]
                elif payoff == best_payoff:
                    assert best_response is not None
                    best_response.append(strategy)
        else:
            assert s in self.p1, "invalid strategy for player 1"
            s_index = self.p1.index(s)
            best_payoff = float('-inf')
            best_response = None
            for i, strategy in enumerate(self.p2):
                payoff = self.payoffs[s_index][i].pay2
                if payoff > best_payoff:
                    best_payoff = payoff
                    best_response = [strategy]
                elif payoff == best_payoff:
                    assert best_response is not None
                    best_response.append(strategy)

        return best_response if best_response is not None else []

Instruction (descriptive):
Add a new method to the `Game` class called `nash_equilibriums(self) -> List[Tuple[str, str]]` that returns a list of Nash equilibriums for the game,
with each pair being the strategy for player 1 and player 2. If there are no Nash equilibriums, return an empty list. A nash 
equilibrium happens when both players are playing their best response to the other player's strategy.

Instruction (lazy):
Write a method `nash_equilibrium(self) -> List[Tuple[str, str]]` in the Game class that returns the nash equilibrium(s) as (s1, s2) pairs.

Edited code:
from typing import List, Tuple


class Cell:
    def __init__(self, pay1, pay2):
        self.pay1 = pay1
        self.pay2 = pay2


class Game:
    def __init__(self, p1: List[str], p2: List[str], payoffs: List[List[Cell]]) -> None:
        """
        p1: list of strategies for player 1
        p2: list of strategies for player 2
        payoffs: list of lists of Cells, representing the payoff matrix

        Example game:
              A     B
          |-----|-----|
        X | 1,2 | 2,1 |
          |-----|-----|
        Y | 3,3 | 4,4 |
          |-----|-----|

        p1 = ["X", "Y"]
        p2 = ["A", "B"]
        payoffs = [
            [Cell(1, 2), Cell(2, 1)],
            [Cell(3, 3), Cell(4, 4)]
        ]
        """

        # validate that this is a proper payoff matrix
        assert len(p1) == len(payoffs)
        assert len(p2) == len(payoffs[0])
        assert all(len(row) == len(p2) for row in payoffs)

        self.p1 = p1
        self.p2 = p2
        self.payoffs = payoffs

    def does_dominate(self, s1: str, s2: str, p: int, weak: bool = False) -> bool:
        assert p in [0, 1], "invalid player index"
        if p == 0:
            assert s1 in self.p1 and s2 in self.p1, "invalid strategy"
        else:
            assert s1 in self.p2 and s2 in self.p2, "invalid strategy"

        s1_index = self.p1.index(s1) if p == 0 else self.p2.index(s1)
        s2_index = self.p1.index(s2) if p == 0 else self.p2.index(s2)

        domination = True
        strict_found = False

        for i in range(len(self.payoffs)):
            if p == 0:
                payoff_s1 = self.payoffs[s1_index][i].pay1
                payoff_s2 = self.payoffs[s2_index][i].pay1
            else:
                payoff_s1 = self.payoffs[i][s1_index].pay2
                payoff_s2 = self.payoffs[i][s2_index].pay2

            if weak:
                if payoff_s1 < payoff_s2:
                    domination = False
                    break
                elif payoff_s1 > payoff_s2:
                    strict_found = True
            else:
                if payoff_s1 <= payoff_s2:
                    domination = False
                    break

        if weak:
            return domination and strict_found
        else:
            return domination

    def best_response(self, s: str, p: int) -> List[str]:
        """
        Returns the best response(s) for player p to strategy s
        made by the other player.
        Can be multiple in the case of two or more equally good responses.
        """
        assert p in [0, 1], "invalid player index"
        if p == 0:
            assert s in self.p2, "invalid strategy for player 2"
            s_index = self.p2.index(s)
            best_payoff = float('-inf')
            best_response = None
            for i, strategy in enumerate(self.p1):
                payoff = self.payoffs[i][s_index].pay1
                if payoff > best_payoff:
                    best_payoff = payoff
                    best_response = [strategy]
                elif payoff == best_payoff:
                    assert best_response is not None
                    best_response.append(strategy)
        else:
            assert s in self.p1, "invalid strategy for player 1"
            s_index = self.p1.index(s)
            best_payoff = float('-inf')
            best_response = None
            for i, strategy in enumerate(self.p2):
                payoff = self.payoffs[s_index][i].pay2
                if payoff > best_payoff:
                    best_payoff = payoff
                    best_response = [strategy]
                elif payoff == best_payoff:
                    assert best_response is not None
                    best_response.append(strategy)

        return best_response if best_response is not None else []

    def nash_equilibriums(self) -> List[Tuple[str, str]]:
        """
        Returns a list of Nash equilibriums.
        """
        s1_brs = {s: self.best_response(s, 0) for s in self.p2}
        s2_brs = {s: self.best_response(s, 1) for s in self.p1}

        nash_equilibriums = []
        for s1, brs in s1_brs.items():
            for s2 in brs:
                if s1 in s2_brs[s2]:
                    nash_equilibriums.append((s2, s1))

        return nash_equilibriums

Tests:
### START TESTS ###
if True: # pragma: no cover
    p1 = ["X", "Y"]
    p2 = ["A", "B"]
    payoffs = [
        [Cell(1, 2), Cell(2, 1)],
        [Cell(3, 3), Cell(4, 4)]
    ]
    game = Game(p1, p2, payoffs)
    assert len(game.p1) == len(payoffs)
    assert len(game.p2) == len(payoffs[0])
    assert all(len(row) == len(p2) for row in game.payoffs)

    try:
        p1 = ["X"]  # Incorrect length
        game = Game(p1, p2, payoffs)
    except AssertionError:
        assert True
    else:
        assert False, "Assertion did not raise as expected"


    try:
        p2 = ["A"]
        game = Game(p1, p2, payoffs)
    except AssertionError:
        assert True
    else:
        assert False, "Assertion did not raise as expected"


    try:
        payoffs = [[Cell(1, 2)], [Cell(3, 3), Cell(4, 4)]]
        game = Game(p1, p2, payoffs)
    except AssertionError:
        assert True
    else:
        assert False, "Assertion did not raise as expected"

    #              A     B
    #          |-----|-----|
    #        X | 1,2 | 2,1 |
    #          |-----|-----|
    #        Y | 3,3 | 4,4 |
    #          |-----|-----|


    assert game.nash_equilibriums() == [("Y", "B")]
    assert game.does_dominate("X", "Y", 0) == False
    assert game.does_dominate("Y", "X", 0) == True

    assert game.does_dominate("A", "B", 1) == False
    assert game.does_dominate("B", "A", 1) == False
    assert game.does_dominate("A", "B", 1, weak=True) == False
    assert game.does_dominate("B", "A", 1, weak=True) == False

    assert game.best_response("A", 0) == ["Y"]
    assert game.best_response("B", 0) == ["Y"]
    assert game.best_response("X", 1) == ["A"]
    assert game.best_response("Y", 1) == ["B"]

    #              A     B
    #          |-----|-----|
    #        X | 1,2 | 2,2 |
    #          |-----|-----|
    #        Y | 3,3 | 4,4 |
    #          |-----|-----|

    p1 = ["X", "Y"]
    p2 = ["A", "B"]
    payoffs = [
        [Cell(1, 2), Cell(2, 2)],
        [Cell(3, 3), Cell(4, 4)]
    ]
    game = Game(p1, p2, payoffs)

    assert game.nash_equilibriums() == [("Y", "B")]
    assert game.does_dominate("X", "Y", 0) == False
    assert game.does_dominate("Y", "X", 0) == True

    assert game.does_dominate("A", "B", 1) == False
    assert game.does_dominate("B", "A", 1) == False
    assert game.does_dominate("A", "B", 1, weak=True) == False
    assert game.does_dominate("B", "A", 1, weak=True) == True

    assert game.best_response("A", 0) == ["Y"]
    assert game.best_response("B", 0) == ["Y"]
    assert game.best_response("X", 1) == ["A", "B"]
    assert game.best_response("Y", 1) == ["B"]


    try:
        game.does_dominate("A", "B", 2)
    except AssertionError:
        pass
    else:
        assert False, "Assertion did not raise as expected"

    try:
        game.does_dominate("A", "C", 1)
    except AssertionError:
        pass
    else:
        assert False, "Assertion did not raise as expected"

    # can't empty game
    try:
        onebyone = Game([], [], [])
    except:
        pass
    else:
        assert False, "Assertion did not raise as expected"


    p1 = ["X", "Y", "Z"]
    p2 = ["A", "B", "C"]
    payoffs = [
        [Cell(1, 2), Cell(2, 1), Cell(3, 4)],
        [Cell(3, 3), Cell(4, 5), Cell(5, 5)],
        [Cell(6, 6), Cell(7, 7), Cell(8, 8)]
    ]
    game = Game(p1, p2, payoffs)

    #              A     B     C
    #          |-----|-----|-----|
    #        X | 1,2 | 2,1 | 3,4 |
    #          |-----|-----|-----|
    #        Y | 3,3 | 4,5 | 5,5 |
    #          |-----|-----|-----|
    #        Z | 6,6 | 7,7 | 8,8 |
    #          |-----|-----|-----|


    assert game.nash_equilibriums() == [("Z", "C")]
    assert game.does_dominate("X", "Y", 0) == False
    assert game.does_dominate("Y", "X", 0) == True
    assert game.does_dominate("X", "Y", 0, weak=True) == False
    assert game.does_dominate("Y", "X", 0, weak=True) == True
    assert game.does_dominate("Z", "X", 0) == True
    assert game.does_dominate("X", "Z", 0) == False
    assert game.does_dominate("Z", "Y", 0) == True
    assert game.does_dominate("Y", "Z", 0) == False

    assert game.does_dominate("A", "B", 1) == False
    assert game.does_dominate("B", "A", 1) == False
    assert game.does_dominate("A", "B", 1, weak=True) == False
    assert game.does_dominate("B", "A", 1, weak=True) == False
    assert game.does_dominate("C", "B", 1) == False
    assert game.does_dominate("B", "C", 1) == False
    assert game.does_dominate("C", "B", 1, weak=True) == True
    assert game.does_dominate("B", "C", 1, weak=True) == False
    assert game.does_dominate("C", "A", 1) == True
    assert game.does_dominate("A", "C", 1) == False

    assert game.best_response("A", 0) == ["Z"]
    assert game.best_response("B", 0) == ["Z"]
    assert game.best_response("C", 0) == ["Z"]
    assert game.best_response("X", 1) == ["C"]
    assert game.best_response("Y", 1) == ["B", "C"]
    assert game.best_response("Z", 1) == ["C"]

    # construct 1x1 game
    onebyone = Game(["X"], ["A"], [[Cell(1, 2)]])

    assert onebyone.nash_equilibriums() == [("X", "A")]
    assert onebyone.does_dominate("X", "X", 0) == False
    assert onebyone.does_dominate("A", "A", 1) == False
    assert onebyone.best_response("A", 0) == ["X"]
    assert onebyone.best_response("X", 1) == ["A"]

    # game with multiple nash_equilibriums

    p1 = ["X", "Y"]
    p2 = ["A", "B"]
    payoffs = [
        [Cell(1, 2), Cell(2, 1)],
        [Cell(1, 2), Cell(2, 1)]
    ]

    #              A     B
    #          |-----|-----|
    #        X | 1,2 | 2,1 |
    #          |-----|-----|
    #        Y | 1,2 | 2,1 |
    #          |-----|-----|

    game = Game(p1, p2, payoffs)
    assert game.nash_equilibriums() == [("X", "A"), ("Y", "A")]

    # game with no nash_equilibriums

    p1 = ["Rock", "Paper", "Scissors"]
    p2 = ["Rock", "Paper", "Scissors"]

    payoffs = [
        [Cell(0, 0), Cell(-1, 1), Cell(1, -1)],
        [Cell(1, -1), Cell(0, 0), Cell(-1, 1)],
        [Cell(-1, 1), Cell(1, -1), Cell(0, 0)]
    ]

    game = Game(p1, p2, payoffs)
    assert game.nash_equilibriums() == []
    assert game.best_response("Rock", 0) == ["Paper"]
    assert game.best_response("Rock", 1) == ["Paper"]
    assert game.best_response("Paper", 0) == ["Scissors"]
    assert game.best_response("Paper", 1) == ["Scissors"]
    assert game.best_response("Scissors", 0) == ["Rock"]
    assert game.best_response("Scissors", 1) == ["Rock"]