Two ice-cream vans choose where to park along a beach for the day. Van A picks a row i (one of m spots), van B picks a column j (one of n spots), at the same time. payoff[i][j] = (a, b) gives their takings in dollars.
Row r is strictly dominated if some other row s gives A strictly more than r against every column: payoff[s][c][0] > payoff[r][c][0] for all columns c. A sensible A never plays such a row. Column c is strictly dominated if some other column d gives B strictly more in every row. Only single strategies dominate (no mixtures of strategies), and a tie in even one place means no domination.
Once a dominated strategy is crossed out, the game is smaller, and a strategy that was not dominated before may become dominated: the comparisons always use only the rows and columns that are still left. Iterated elimination repeats: while some remaining row or column is strictly dominated (among the remaining ones), cross it out. With strict dominance, the order in which you cross strategies out does not change what is left at the end.
Write survivors(payoff) that returns a tuple (rows, cols): the original indices of the rows and of the columns that are left, each in increasing order.
Examples
Input: payoff = [[(4, 2), (5, 2), (5, 5)],
[(5, 4), (0, 3), (1, 5)],
[(0, 1), (0, 2), (3, 1)]]
Output: ([0], [2])
Explanation: row 0 beats row 2 everywhere (4 > 0, 5 > 0, 5 > 3). With row 2 gone,
column 2 gives B 5 and 5 against 2 and 4 (column 0) and 2 and 3 (column 1).
Facing only column 2, row 0 (5) beats row 1 (1).
Input: payoff = [[(1, 1), (1, 0)],
[(1, 0), (0, 1)]]
Output: ([0, 1], [0, 1])
Explanation: row 0 is never worse than row 1 but ties it in column 0: no strict dominance.
Goals
- Test whether one strategy strictly beats another against every remaining choice of the rival
- Remove dominated strategies repeatedly, each time looking only at what is left
- Tell strict dominance from weak dominance