The Price War Between Two Bakeries

Two bakeries on the same street set their bread prices every Monday, at the same time. Bakery A picks a row i, bakery B a column j, and payoff[i][j] = (a, b) gives their weekly profits in hundreds of dollars.

• A cell (i, j) is a (pure-strategy) Nash equilibrium when A's payoff is the largest in column j and B's payoff is the largest in row i (ties allowed): neither bakery gains by changing its own price alone.
• The total payoff of a cell is a + b.
• A cell (i, j) is Pareto-dominated when some other cell gives both bakeries at least as much and at least one of them strictly more.

Write dilemma(payoff) that returns a tuple (equilibria, best_total, dominated):

1. equilibria: all Nash equilibria (i, j);
2. best_total: all cells (i, j) whose total payoff is the largest in the table;
3. dominated: the equilibria (from list 1) that are Pareto-dominated.

Every list is in row-major order (by i, then by j) and may be empty.

Examples

Input:  payoff = [[(6, 6), (1, 8)],
                  [(8, 1), (3, 3)]]
Output: ([(1, 1)], [(0, 0)], [(1, 1)])
Explanation: row 1 and column 1 mean "cut the price". Whatever the other does, cutting
pays more (8 > 6 and 3 > 1), so both cut and earn 3 each, though keeping prices high
would give each 6. That is a prisoners' dilemma.

Input:  payoff = [[(3, 2), (0, 0)],
                  [(0, 0), (2, 3)]]
Output: ([(0, 0), (1, 1)], [(0, 0), (1, 1)], [])

Input:  payoff = [[(2, 4), (1, 5)],
                  [(3, 0), (2, 2)]]
Output: ([(1, 1)], [(0, 0), (0, 1)], [(1, 1)])
Explanation: (0, 0) gives A the same 2 and B more (4 > 2), so the equilibrium is dominated.

Goals

• Find the pure-strategy Nash equilibria and the cells with the largest total payoff
• Test whether some other outcome makes both players at least as well off and one better off
• See how each player's own best response can leave both worse off