Two radio stations each choose a programme for the evening slot, at the same time. Station A picks a row i (one of m programmes), station B picks a column j (one of n). The payoff table gives their audiences, in thousands of listeners: payoff[i][j] = (a, b) means A gets a and B gets b when A plays i and B plays j.
A cell (i, j) is a pure-strategy Nash equilibrium when neither station can gain by switching on its own:
- no other row gives A more in column
j:payoff[i][j][0] >= payoff[k][j][0]for every rowk, and - no other column gives B more in row
i:payoff[i][j][1] >= payoff[i][k][1]for every columnk.
A tie is not a gain, so a strategy that ties for the best still counts.
Write pure_equilibria(payoff) that returns the list of all equilibria as tuples (i, j), in row-major order (by i, then by j). A game may have several equilibria, or none: then return [].
Examples
Input: payoff = [[(3, 2), (0, 0)],
[(0, 0), (2, 3)]]
Output: [(0, 0), (1, 1)]
Explanation: both stations want to match; at (0, 0) a switch by either drops it to 0.
Input: payoff = [[(1, -1), (-1, 1)],
[(-1, 1), (1, -1)]]
Output: []
Explanation: in every cell one of the two stations gains by switching.
Input: payoff = [[(2, 1), (2, 1)],
[(0, 0), (1, 3)]]
Output: [(0, 0), (0, 1)]
Explanation: in row 0 both columns give B the same 1, so B has nothing to gain by switching.
Goals
- Test a cell of a payoff table for being a pure-strategy Nash equilibrium
- List every equilibrium of a game, in row-major order, including none
- See that ties let a cell be an equilibrium without being strictly best