More Like this

1. Hardness amplification for entangled games via anchoring

   https://doi.org/10.1145/3055399.3055433  

   Bavarian, Mohammad; Vidick, Thomas; Yuen, Henry (June 2017, Proceedings of the annual ACM Symposium on Theory of Computing)

   We study the parallel repetition of one-round games involving players that can use quantum entanglement. A major open question in this area is whether parallel repetition reduces the entangled value of a game at an exponential rate --- in other words, does an analogue of Raz's parallel repetition theorem hold for games with players sharing quantum entanglement? Previous results only apply to special classes of games. We introduce a class of games we call anchored. We then introduce a simple transformation on games called \emph{anchoring}, inspired in part by the Feige-Kilian transformation, that turns \emph{any} (multiplayer) game into an anchored game. Unlike the Feige-Kilian transformation, our anchoring transformation is completeness preserving. We prove an exponential-decay parallel repetition theorem for anchored games that involve any number of entangled players. We also prove a threshold version of our parallel repetition theorem for anchored games. Together, our parallel repetition theorems and anchoring transformation provide the first hardness amplification techniques for general entangled games. We give an application to the games version of the Quantum PCP Conjecture. 

   more » « less
2. Parallel Repetition of k-Player Projection Games

   https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2024.54  

   Bhangale, Amey; Braverman, Mark; Khot, Subhash; Liu, Yang P; Minzer, Dor (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Kumar, Amit; Ron-Zewi, Noga (Ed.)

   We study parallel repetition of k-player games where the constraints satisfy the projection property. We prove exponential decay in the value of a parallel repetition of projection games with a value less than 1. 

   more » « less
3. Model-Free Reinforcement Learning for Stochastic Parity Games

   Hahn, Ernst Moritz; Perez, Mateo; Schewe, Sven; Somenzi, Fabio; Trivedi, Ashutosh; Wojtczak, Dominik (August 2020, 31st International Conference on Concurrency Theory (CONCUR 2020))

   null (Ed.)

   This paper investigates the use of model-free reinforcement learning to compute the optimal value in two-player stochastic games with parity objectives. In this setting, two decision makers, player Min and player Max, compete on a finite game arena - a stochastic game graph with unknown but fixed probability distributions - to minimize and maximize, respectively, the probability of satisfying a parity objective. We give a reduction from stochastic parity games to a family of stochastic reachability games with a parameter ε, such that the value of a stochastic parity game equals the limit of the values of the corresponding simple stochastic games as the parameter ε tends to 0. Since this reduction does not require the knowledge of the probabilistic transition structure of the underlying game arena, model-free reinforcement learning algorithms, such as minimax Q-learning, can be used to approximate the value and mutual best-response strategies for both players in the underlying stochastic parity game. We also present a streamlined reduction from 1 1/2-player parity games to reachability games that avoids recourse to nondeterminism. Finally, we report on the experimental evaluations of both reductions 

   more » « less
4. Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games

   Zhang, B; Farina, G; Anagnostides, I; Cacciamani, F; McAleer, S; Haupt, A; Celli, A; Gatti, N; Conitzer, V; Sandholm, T (December 2023, NeurIPS23)

   We introduce a new approach for computing optimal equilibria and mechanisms via learning in games. It applies to extensive-form settings with any number of players, including mechanism design, information design, and solution concepts such as correlated, communication, and certification equilibria. We observe that optimal equilibria are minimax equilibrium strategies of a player in an extensiveform zero-sum game. This reformulation allows us to apply techniques for learning in zero-sum games, yielding the first learning dynamics that converge to optimal equilibria, not only in empirical averages, but also in iterates. We demonstrate the practical scalability and flexibility of our approach by attaining state-of-the-art performance in benchmark tabular games, and by computing an optimal mechanism for a sequential auction design problem using deep reinforcement learning. 

   more » « less
5. Nash equilibrium structure of Cox process Hotelling games

   https://doi.org/10.1017/apr.2021.45  

   Anantharam, Venkat; Baccelli, François (June 2022, Advances in Applied Probability)

   Abstract We study anN-player game where a pure action of each player is to select a nonnegative function on a Polish space supporting a finite diffuse measure, subject to a finite constraint on the integral of the function. This function is used to define the intensity of a Poisson point process on the Polish space. The processes are independent over the players, and the value to a player is the measure of the union of her open Voronoi cells in the superposition point process. Under randomized strategies, the process of points of a player is thus a Cox process, and the nature of competition between the players is akin to that in Hotelling competition games. We characterize when such a game admits Nash equilibria and prove that when a Nash equilibrium exists, it is unique and consists of pure strategies that are proportional in the same proportions as the total intensities. We give examples of such games where Nash equilibria do not exist. A better understanding of the criterion for the existence of Nash equilibria remains an intriguing open problem. 

   more » « less