Fictitious Play Convergence Check

Problem

Check whether a strategy is approximately a best response to itself, the fictitious-play convergence criterion.

p is the strategy and A[i][j] is player 1's payoff for action i against action j. Return True when the best-response value against p exceeds the value of p by at most tol.

Hint

Fictitious play converges when nobody wants to deviate from the empirical strategy.

Test cases

case 1

in: [[0.5,0.5],[[1,-1],[-1,1]],1e-9]

expected: true

case 2

in: [[0.7,0.3],[[3,0],[0,2]],1e-9]

expected: false

case 3

in: [[1,0],[[3,0],[0,2]],1e-9]

expected: true

case 4

in: [[0.5,0.5],[[0,2],[3,0]],1e-9]

expected: false

Starter codePython

def fictitious_play_converged(p, A, tol):
    # Your code here
    pass

4 test cases · run your code against them in the editor