Quantum Algorithms to Find Equilibrium in Sequential Games

Subgame Perfect Equilibrium (SGPE) is a special refinement of Nash equilibrium used in sequential games. A couple of quantum algorithms is presented in this paper to compute SGPE in a finite extensive form game with perfect information. The quantum search tools, Grover's operator and Discrete quantum walk, are used to design the algorithms. A full-width game tree of average branching factor b and height h has n = O(bh) nodes in it. It will be shown in this paper that our algorithm uses O(n/(b1/2)) oracle queries to backtrack to the solution. The resultant speed-up is O(b1/2) times better than the best known classical approach, Zermelo's algorithm. Citation:Arish Pitchai, National Institute of Technology; A. V. Reddy ,; Nickolas Savarimuthu ,. "Quantum Algorithms to Find Equilibrium in Sequential Games." Global Research and Development Journal For Engineering : 565 - 572.