A market inspector decides each day whether to inspect a stall (row 0) or not (row 1); the stall-holder decides whether to cut corners (column 0) or follow the rules (column 1). They choose at the same time. payoff[i][j] = (a, b) gives the inspector's payoff a and the stall-holder's payoff b (whole numbers of points).
In the games you get, there is no pure-strategy Nash equilibrium: in every cell, one of the two players would gain by switching. Each player then randomises. In a mixed-strategy equilibrium, the inspector inspects with probability p (and skips with probability 1 - p) and the stall-holder cuts corners with probability q, where
qis such that the inspector's two rows give her the same expected payoff, andpis such that the stall-holder's two columns give him the same expected payoff.
(If one row paid more, the inspector would play it for sure, and that is not random any more.) The expected payoff of row i against the mix q is q * a(i, 0) + (1 - q) * a(i, 1); the equilibrium payoffs are the players' expected payoffs when both mix.
Write mixed_2x2(payoff) that returns (p, q, value_a, value_b), each as an exact fraction written as a pair (numerator, denominator) in lowest terms with a positive denominator (so 0 is (0, 1) and a negative number has the sign on the numerator). fractions.Fraction does the arithmetic and the reducing for you.
Examples
Input: payoff = [[(6, -9), (-2, 0)],
[(-4, 3), (0, 0)]]
Output: ((1, 4), (1, 6), (-2, 3), (0, 1))
Explanation: with q = 1/6, inspecting pays 6/6 - 2 * 5/6 = -2/3 and skipping pays
-4/6 = -2/3, the same. With p = 1/4, cutting corners pays -9/4 + 3 * 3/4 = 0,
the same as following the rules.
Input: payoff = [[(2, -2), (-1, 1)],
[(-1, 1), (1, -1)]]
Output: ((2, 5), (2, 5), (1, 5), (-1, 5))
Goals
- Find each player's mixing probability from the condition that makes the **other** player indifferent
- Compute the expected payoffs of a mixed-strategy equilibrium
- Work in exact fractions