ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

Quantum Algorithms to Find Equilibrium in Sequential Games

Journal: GRD Journal for Engineering (Vol.002, No. 2)

Publication Date:

Authors : ; ; ;

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 : Downloadexternal Find it from : Google Scholarexternal

Abstract

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