Quantum Walk Algorithm to Compute Subgame Perfect Equilibrium in Finite Two-player Sequential Games
Arish Pitchai, A. V. Reddy, Nickolas Savarimuthu · International Journal of Mathematical Sciences and Computing · 2016
Subgame Perfect Equilibrium (SGPE) is a refined version of Nash equilibrium used in games of sequential nature.Computational complexity of classical approaches to compute SGPE grows exponentially with the increase in height of the game tree.In this paper, we present a quantum algorithm based on discrete-time quantum walk to compute Subgame Perfect Equilibrium (SGPE) in a finite two-player sequential game.A fullwidth game tree of average branching factor b and height h has (O n b oracle queries to backtrack to the solution.The resultant speed-up is () Ob times better than the best known classical approach, Zermelo's algorithm.