Quantum Algorithms to Find Equilibrium in Sequential GamesJournal
: GRD Journal for Engineering (Vol.002, No. 2)
Publication Date: 2016-12-18
Authors : Arish Pitchai; A. V. Reddy; Nickolas Savarimuthu;
Page : 565-572
Keywords : Quantum algorithm; discrete quantum random walk; Quantum game theory; Algorithmic game theory; Sequential game; Nash Equilibrium; Subgame Perfect Equilibrium; Backward induction;
Source : Download Find it from : Google Scholar
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.
Last modified: 2016-12-19 01:59:28