Quantum game theory and the complexity of approximating quantum Nash equilibria

Abstract

This paper is concerned with complexity theoretic aspects of a general formulation of quantum game theory that models strategic interactions among rational agents that process and exchange quantum information. In particular, we prove that the computational problem of finding an approximate Nash equilibrium in a broad class of quantum games is, like the analogous problem for classical games, included in (and therefore complete for) the complexity class PPAD. Our main technical contribution, which facilitates this inclusion, is an extension of prior methods in computational game theory to strategy spaces that are characterized by semidefinite programs.

References in corpus (10)

• Quantum Games and Quantum Strategies
• Quantum strategies
• Theoretical framework for quantum networks
• From Classical to Quantum Shannon Theory
• Quantum Circuits Architecture
• Discrete phase space based on finite fields
• Hudson's Theorem for finite-dimensional quantum systems
• Toward a general theory of quantum games
• Classical Rules in Quantum Games
• A new mathematical representation of Game Theory II

Cited by in corpus (1)

• Improving social welfare in non-cooperative games with different types of quantum resources