Quantum Algorithms to Find Equilibrium in Sequential Games
Arish Pitchai, National Institute of Technology; A. V. Reddy ,; Nickolas Savarimuthu ,
Quantum algorithm, discrete quantum random walk, Quantum game theory, Algorithmic game theory, Sequential game, Nash Equilibrium, Subgame Perfect Equilibrium, Backward induction
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.
-
[1] Aaronson, S., & Ambainis, A. (2003, October). Quantum search of spatial regions. In Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on (pp. 200-209). IEEE.
[2] Ambainis, A. (2003). Quantum walks and their algorithmic applications.International Journal of Quantum Information, 1(04), 507-518.
[3] Ambainis, A. (2007). Quantum walk algorithm for element distinctness.SIAM Journal on Computing, 37(1), 210-239.
[4] Bopardikar, S. D., Borri, A., Hespanha, J. P., Prandini, M., & Di Benedetto, M. D. (2013). Randomized sampling for large zero-sum games. Automatica,49(5), 1184-1194.
[5] Cigler, L., & Faltings, B. (2014). Symmetric subgame-perfect equilibria in resource allocation. Journal of Artificial Intelligence Research, 323-361.
[6] Deutsch, D., & Jozsa, R. (1992, December). Rapid solution of problems by quantum computation. In Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences (Vol. 439, No. 1907, pp. 553-558). The Royal Society.
[7] Durr, C., & Hoyer, P. (1996). A quantum algorithm for finding the minimum.arXiv preprint quant-ph/9607014.
[8] Eisert, J., Wilkens, M., & Lewenstein, M. (1999). Quantum games and quantum strategies. Physical Review Letters, 83(15), 3077.
[9] Grover, L. K. (1996, July). A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (pp. 212-219). ACM.
[10] Grover, L. K. (2005). Quantum Search Algorithm can be Improved.International Journal of Quantum Information, 3(01), 23-30.
[11] Iqbal, A., & Toor, A. H. (2002). Backwards-induction outcome in a quantum game. Physical Review A, 65(5), 052328.
[12] Marinatto, L., & Weber, T. (2000). A quantum approach to static games of complete information. Physics Letters A, 272(5), 291-303.
[13] Meyer, D. A. (1999). Quantum strategies. Physical Review Letters, 82(5), 1052.
[14] Nielsen, M. A., & Chuang, I. L. (2010). Quantum computation and quantum information. Cambridge university press.
[15] Osborne, M. J., & Rubinstein, A. (1994). A course in game theory. MIT press.
[16] Potoček, V., Gábris, A., Kiss, T., & Jex, I. (2009). Optimized quantum random-walk search algorithms on the hypercube. Physical Review A, 79(1), 012325.
[17] Selten, R. (1975). Reexamination of the perfectness concept for equilibrium points in extensive games. International journal of game theory, 4(1), 25-55.
[18] Shenvi, N., Kempe, J., & Whaley, K. B. (2003). Quantum random-walk search algorithm. Physical Review A, 67(5), 052307.
[19] Storer, J. A. (1983). On the complexity of chess. Journal of Computer and System Sciences, 27(1), 77-100.
[20] Van den Herik, H. J., Uiterwijk, J. W., & Van Rijswijck, J. (2002). Games solved: Now and in the future. Artificial Intelligence, 134(1), 277-311.
[21] Zermelo, E. (1913). Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. In Proceedings of the fifth international congress of mathematicians (Vol. 2, pp. 501-504). II, Cambridge UP, Cambridge.
Paper ID: GRDCF002043
Published in: Conference : International Conference on Innovations in Engineering and Technology (ICIET - 2016)
Page(s): 565 - 572
Published in: Conference : International Conference on Innovations in Engineering and Technology (ICIET - 2016)
Page(s): 565 - 572