The Nash equilibrium plays a crucial role in game theory. Most of results are based on classical resources. Our goal in this paper is to explore multipartite zero-sum game with quantum settings. We find that in two different settings there is no strategy for a tripartite classical game being fair. Interestingly, this is resolved by providing dynamic zero-sum quantum games using single quantum state. Moreover, the gains of some players may be changed dynamically in terms of the committed state. Both quantum games are robust against the preparation noise and measurement errors.The Nash equilibrium plays a crucial role in game theory. Most of results are based on classical resources. Our goal in this paper is to explore multipartite zero-sum game with quantum settings. We find that in two different settings there is no strategy for a tripartite classical game being fair. Interestingly, this is resolved by providing dynamic zero-sum quantum games using single quantum state. Moreover, the gains of some players may be changed dynamically in terms of the committed state. Both quantum games are robust against the preparation noise and measurement errors.

EntropyJan 27, 20215 citations

Games and Algebras

Samuel J. Harris, Vern I. Paulsen

Operator TheoryJan 1, 20260 citations

Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games

Minbo Gao, Zhengfeng Ji, Tongyang Li +1 more

We propose the first online quantum algorithm for solving zero-sum games with $\widetilde O(1)$ regret under the game setting. Moreover, our quantum algorithm computes an $\varepsilon$ -approximate Nash equilibrium of an $m \times n$ matrix zero-sum game in quantum time $\widetilde O(\sqrt{m+n}/\varepsilon^{2.5})$ . Our algorithm uses standard quantum inputs and generates classical outputs with succinct descriptions, facilitating end-to-end applications. Technically, our online quantum algorithm "quantizes" classical algorithms based on the optimistic multiplicative weight update method. At the heart of our algorithm is a fast quantum multi-sampling procedure for the Gibbs sampling problem, which may be of independent interest.We propose the first online quantum algorithm for solving zero-sum games with $\widetilde O(1)$ regret under the game setting. Moreover, our quantum algorithm computes an $\varepsilon$-approximate Nash equilibrium of an $m \times n$ matrix zero-sum game in quantum time $\widetilde O(\sqrt{m+n}/\varepsilon^{2.5})$. Our algorithm uses standard quantum inputs and generates classical outputs with succinct descriptions, facilitating end-to-end applications. Technically, our online quantum algorithm "quantizes" classical algorithms based on the optimistic multiplicative weight update method. At the heart of our algorithm is a fast quantum multi-sampling procedure for the Gibbs sampling problem, which may be of independent interest.

arXiv:2304.14197neural information processing systemsJan 1, 20233 citations

A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games

Francisca Vasconcelos, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Panayotis Mertikopoulos +2 more

Recent developments in domains such as non-local games, quantum interactive proofs, and quantum generative adversarial networks have renewed interest in quantum game theory and, specifically, quantum zero-sum games. Central to classical game theory is the efficient algorithmic computation of Nash equilibria, which represent optimal strategies for both players. In 2008, Jain and Watrous proposed the first classical algorithm for computing equilibria in quantum zero-sum games using the Matrix Multiplicative Weight Updates (MMWU) method to achieve a convergence rate of O(d/ϵ2) iterations to ϵ -Nash equilibria in the 4d -dimensional spectraplex. In this work, we propose a hierarchy of quantum optimization algorithms that generalize MMWU via an extra-gradient mechanism. Notably, within this proposed hierarchy, we introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as O(d/ϵ) iterations to ϵ -Nash equilibria. This quadratic speed-up relative to Jain and Watrous' original algorithm sets a new benchmark for computing ϵ -Nash equilibria in quantum zero-sum games.Recent developments in domains such as non-local games, quantum interactive proofs, and quantum generative adversarial networks have renewed interest in quantum game theory and, specifically, quantum zero-sum games. Central to classical game theory is the efficient algorithmic computation of Nash equilibria, which represent optimal strategies for both players. In 2008, Jain and Watrous proposed the first classical algorithm for computing equilibria in quantum zero-sum games using the Matrix Multiplicative Weight Updates (MMWU) method to achieve a convergence rate of O(d/ϵ2) iterations to ϵ -Nash equilibria in the 4d -dimensional spectraplex. In this work, we propose a hierarchy of quantum optimization algorithms that generalize MMWU via an extra-gradient mechanism. Notably, within this proposed hierarchy, we introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as O(d/ϵ) iterations to ϵ -Nash equilibria. This quadratic speed-up relative to Jain and Watrous' original algorithm sets a new benchmark for computing ϵ -Nash equilibria in quantum zero-sum games.

arXiv:2311.10859QuantumMay 6, 20250 citations

The game of quandice

Trevor W. Marshall

Physics Letters AJul 1, 19803 citations

We propose the first online quantum algorithm for solving zero-sum games with

\widetilde O(1)

regret under the game setting. Moreover, our quantum algorithm computes an

\varepsilon

-approximate Nash equilibrium of an

m \times n

matrix zero-sum game in quantum time

\widetilde O(\sqrt{m+n}/\varepsilon^{2.5})

. Our algorithm uses standard quantum inputs and generates classical outputs with succinct descriptions, facilitating end-to-end applications. Technically, our online quantum algorithm "quantizes" classical algorithms based on the optimistic multiplicative weight update method. At the heart of our algorithm is a fast quantum multi-sampling procedure for the Gibbs sampling problem, which may be of independent interest.