Two kiosks share a town square. Each morning the owner of kiosk A picks one of m menus and the owner of kiosk B picks one of n menus, at the same time, without seeing the other's choice. How much each earns depends on both choices. A payoff table records it: payoff[i][j] = (a, b) means that when A picks menu i (a row) and B picks menu j (a column), A earns a dollars and B earns b dollars that day. A is called the row player, B the column player.
A best response of A to B's menu j is a row i that gives A the most money in that column: payoff[i][j][0] is as large as any payoff[k][j][0]. Likewise a best response of B to A's row i is a column j whose payoff[i][j][1] is as large as any in that row.
Write best_replies(payoff) that returns a tuple (a_replies, b_replies):
a_replies[j]: the list of A's best responses to columnj, forj = 0, ..., n-1;b_replies[i]: the list of B's best responses to rowi, fori = 0, ..., m-1.
When several strategies tie for the best payoff, the list holds all of them, in increasing order.
Examples
Input: payoff = [[(4, 3), (1, 5)],
[(2, 2), (3, 1)],
[(4, 0), (0, 4)]]
Output: ([[0, 2], [1]], [[1], [0], [1]])
Explanation: against column 0, A earns 4, 2 or 4, so rows 0 and 2 tie.
Against row 1, B earns 2 or 1, so column 0 is B's best response.
Input: payoff = [[(-1, 2), (0, 2), (5, -3)],
[(-1, 0), (-2, 1), (5, 1)]]
Output: ([[0, 1], [0], [0, 1]], [[0, 1], [1, 2]])
Goals
- Read a two-player payoff table where each cell holds both players' payoffs
- Find a player's best responses to each strategy of the other player
- Keep every tied best response, in increasing order