Developing a Web Framework to Visualize Fictitious Play’s Convergence to Nash Equilibrium, Study Duality Gap Statistics, and Examine Validity of Karlin’s Conjecture

In 1951, Julia Robinson showed that Fictitious Play (FP) converges to Nash Equilibrium at a slow rate that depends on the dimensions of the problem. In 1959, Karlin conjectured that instead of a slow rate, FP converges to the Nash Equilibrium at the more natural rate of , where t is the number of iterations of FP. However, in 2014, Daskalakis and Pan showed a counterexample in which FP converged at a rate as slow as . They used the adversarial tie-breaking method in their proof.

In my project, I aimed to run the simultaneous FP process on various kinds of payoff matrices using the lexicographic tie-breaking method. I was interested in exploring if FP converged to Nash equilibrium and if Karlin’s conjecture held. To explore this question, I developed a Flask-based computer program that accepts input from the user (such as a payoff matrix and players’ starting positions) and presents 2D and 3D visualizations of FP’s convergence and duality gap statistics. Though I wrote code to support both simultaneous and alternating FP in my computer program, I focused on simultaneous FP in my experiments. Using the FP convergence graphs, I could verify whether FP converged to the pure or mixed strategy Nash equilibrium. Using the duality gap statistics, I could check whether Karlin’s conjecture held based on whether the squared unnormalized duality gap per iteration’s curve was linear. I ran these experiments on matrices having different features, and my report presents my results for 8 matrices of different dimensions, characteristics (identity, diagonal, and randomly generated), and properties (with and without strictly dominated strategies). In all cases, FP converged to (or got close to converging to) the pure or mixed strategy Nash equilibrium after 10000 iterations. Karlin’s conjecture also held in all cases. In addition, the interactive computer program I developed may be used for further research in the field.