International Journal of Mathematical Sciences and Computing (IJMSC)
IJMSC Vol. 2, No. 3, 8 Jul. 2016
Cover page and Table of Contents: PDF (size: 499KB)
Quantum Walk Algorithm to Compute Subgame Perfect Equilibrium in Finite Two-player Sequential Games
Full Text (PDF, 499KB), PP.32-40
Views: 0 Downloads: 0
Author(s)
Index Terms
Quantum Game Theory, Sequential Games, Subgame Perfect Equilibrium, Quantum Random Walk, Backward Induction, Two-player Games, Quantum Algorithm, Quantum Computing
Abstract
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 full-width game tree of average branching factor b and height h has nodes in it. The proposed algorithm uses oracle queries to backtrack to the solution. The resultant speed-up is times better than the best known classical approach, Zermelo's algorithm.
Cite This Paper
Arish Pitchai, A V Reddy, Nickolas Savarimuthu,"Quantum Walk Algorithm to Compute Subgame Perfect Equilibrium in Finite Two-player Sequential Games", International Journal of Mathematical Sciences and Computing(IJMSC), Vol.2, No.3, pp.32-40, 2016.DOI: 10.5815/ijmsc.2016.03.03
Reference
[1]Selten, R. Reexamination of the perfectness concept for equilibrium points in extensive games, Int. J. Game Theory, 1975; 4(1):25-55.
[2]Osborne, M.J., Rubinstein, A. A course in game theory, MIT press; 1994.
[3]Venegas-Andraca, S.E. Quantum walks: a comprehensive review, Quantum Inf. Process., 2012; 11(5):1015-1106.
[4]Zermelo, E. Uber eine Anwendung der Mengenlehre auf die Theorie des Schachspiels, Proceedings of the fifth international congress of mathematicians, Cambridge UP, Cambridge, 1913; 2(2).
[5]Kuhn, H.W. Extensive games and the problem of information, Contributions to the Theory of Games, 1953; 2(28):193-216.
[6]Aumann, R.J. Backward induction and common knowledge of rationality, Games Econ. Behav., 1995; 8(1):6-19.
[7]Papadimitriou, C.H. Computational complexity, John Wiley and Sons Ltd., 2003.
[8]Fraenkel, A.S., Lichtenstein, D. Computing a perfect strategy for n× n chess requires time exponential in n, Automata, Languages and Programming, Springer Berlin Heidelberg, 1981; 278-293.
[9]Bopardikar, S. D., Borri, A., Hespanha, J. P., Prandini, M., Di Benedetto, M. D. Randomized sampling for large zero-sum games, Automatica, 2013; 49(5):1184-1194.
[10]Meyer, D. A. Quantum strategies, Phys. Rev. Lett., 1999; 82(5):1052.
[11]Eisert, J., Wilkens, M., Lewenstein, M. Quantum games and quantum strategies, Phys. Rev. Lett., 1999; 83(15):3077.
[12]Marinatto, L., Weber, T. A quantum approach to static games of complete information, Phys. Lett. A, 2000; 272(5):291-303.
[13]Iqbal, A., Toor, A.H. Backwards-induction outcome in a quantum game, Phys. Rev. A, 2002; 65(5):052328.
[14]Shenvi, N., Kempe, J., Whaley, K.B. Quantum random-walk search algorithm, Phys. Rev. A, 2003; 67(5):052307.
[15]Ambainis, A. Quantum walk algorithm for element distinctness, SIAM J. on Comput., 2007;37(1):210-239.
[16]Ambainis, A., Bačkurs, A., Nahimovs, N., Ozols, R., Rivosh, A. Search by quantum walks on two-dimensional grid without amplitude amplification, In: Theory of Quantum Computation, Communication, and Cryptography, Springer Berlin Heidelberg, 2013; 87-97.
[17]Tani, S., Claw finding algorithms using quantum walk, Theor. Comput. Sci., 2009;410(50):5285-5297.
[18]Aaronson, S., Ambainis, A. Quantum search of spatial regions, In: Proceedings. 44th Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2003; 200-209.