More Like this

1. Efficient Network Protection Games Against Multiple Types Of Strategic Attackers

   https://doi.org/10.1109/ICASSP39728.2021.9413758  

   Xu, Zhifan; Baykal-Gursoy, Melike (June 2021, 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP))

   null (Ed.)

   This paper considers network protection games against different types of attackers for a heterogeneous network system with N units. A defender, by applying resources to networked units, can decrease the units’ vulnerabilities. At the same time, the defender needs to take into account the cost of using defense resources. Two non-zero sum Nash games against two different types of attackers are studied. The first type tries to maximize damage based on the value of security assets related to networked units, while the second type aims at infiltrating the network. The analyses show that there exists a cut-off index determining the set of units that will be protected in the equilibrium strategies of the first game, while either all units or none will be covered in the equilibria of the second game. An application of the network protection game to secure wireless communication networks is presented. 

   more » « less
2. A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games

   Vasconcelos, F; Vlatakis-Gkaragkounis, E-V; Mertikopoulos, P; Piliouras, G; Jordan, M I (November 2023, 7th International Conference on Quantum Techniques in Machine Learning)

   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 zerosum 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. 

   more » « less
3. 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
4. A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games

   https://doi.org/10.22331/q-2025-05-06-1737  

   Vasconcelos, Francisca; Vlatakis-Gkaragkounis, Emmanouil-Vasileios; Mertikopoulos, Panayotis; Piliouras, Georgios; Jordan, Michael I (May 2025, Quantum)

   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 $\mathcal{O}\left(d/{ϵ}^2\right)$iterations to $ϵ$-Nash equilibria in the $4^d$-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 $\mathcal{O}\left(d/ϵ\right)$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. 

   more » « less
5. On the Characterization of Saddle Point Equilibrium for Security Games with Additive Utility

   https://doi.org/10.1007/978-3-030-64793-3_19  

   Emadi, Hamid; Bhattacharya, Sourabh (July 2020, GameSec Conference)

   In this work, we investigate a security game between an attacker and a defender, originally proposed in [6]. As is well known, the combinatorial nature of security games leads to a large cost matrix. Therefore, computing the value and optimal strategy for the players becomes computationally expensive. In this work, we analyze a special class of zero-sum games in which the payoff matrix has a special structure which results from the additive property of the utility function. Based on variational principles, we present structural properties of optimal attacker as well as defender’s strategy. We propose a linear-time algorithm to compute the value based on the structural properties, which is an improvement from our previous result in [6], especially in the context of large-scale zero-sum games. 

   more » « less