Commitment to Sparse Strategies in Two-Player Games

Salam Afiouni, Jakub Černý, Chun Kai Ling, Christian Kroer · 2024

Read Commitment to Sparse Strategies in Two-Player Games by Salam Afiouni, Jakub Černý, Chun Kai Ling, Christian Kroer (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-14337.txt.

Introduction

Salam Afiouni and three co-authors study strategy in two-player games in a 2024 paper. In many games, the best plan mixes many moves at random, which makes it hard to explain or carry out. The team asks what happens when one player must commit to a plan that uses only a few moves.

Finding the best such sparse plan is known to be hard to compute. The authors first show how sharply the best set of moves can change as the allowed number grows, which rules out simple step-by-step methods. They then build methods based on whole-number programming for zero-sum games and for leader-follower games. Tests on made-up and security-based cases show a welcome result. With only a few moves allowed, their methods still capture over ninety percent of the value of the best full plan.

Catalog record

CREATORSalam Afiouni, Jakub Černý, Chun Kai Ling, Christian Kroer
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-14337

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Commitment to Sparse Strategies in Two-Player Games Salam Afiouni, Jakub Černý, Chun Kai Ling, Christian Kroer Abstract While Nash equilibria are guaranteed to exist, they may exhibit dense support, making them difficult to understand and execute in some applications. In this paper, we study k k -sparse commitments in games where one player is restricted to mixed strategies with support size at most k k . Finding k k -sparse commitments is known to be computationally hard. We start by showing several structural properties of k k -sparse solutions, including that the optimal support may vary dramatically as k k increases. These results suggest that naive greedy or double-oracle-based approaches are unlikely to yield practical algorithms. We then develop a simple approach based on mixed integer linear programs (MILPs) for zero-sum games, general-sum Stackelberg games, and various forms of structured sparsity. We also propose practical algorithms for cases where one or both players have large (i.e., practically innumerable) action sets, utilizing a combination of MILPs and incremental strategy generation. We evaluate our methods on synthetic and real-world scenarios based on security applications. In both settings, we observe that even for small support sizes, we can obtain more than 90 % 90\% of the true Nash value while maintaining a reasonable runtime, demonstrating the significance of our formulation and algorithms. 1 Columbia University, USA 2 National University of Singapore, Singapore [email protected], [email protected], [email protected], [email protected] 1 Introduction Equilibrium finding in games has emerged as a key component of artificial intelligence, owing to applications in recreational game playing such as poker, Stratego, and Diplomacy, numerous applications in security, as well as logistics ( Bowling et al. 2015 ; Brown and Sandholm 2018 ; Perolat et al. 2022 ; Bakhtin et al. 2022 ; Pita et al. 2008 ; Fang, Stone, and Tambe 2015 ; Tambe 2011 ; Jain et al. 2010 ; Černý et al. 2024 ) . Central to the success of these applications are efficient approaches towards finding the optimal randomized , or mixed equilibria in their respective settings. Not only are randomized equilibria typically guaranteed to exist, they allow for the prescription of behavior that hedges over all possible opponent actions, making them particularly useful in zero-sum games. Nonetheless, a persistent difficulty faced by practitioners seeking to apply game theoretic solutions into the real world is that such solutions exhibit dense support , i.e., they could randomize over a large number of actions. Strategies with dense support are undesirable for many reasons; for instance, they are difficult to interpret and implement in practice, and are often faced with numerical issues if used for downstream processing. In this paper, we propose overcoming these limitations by computing k -sparse solutions as opposed to Nash equilibria. Loosely speaking, a distinguished player termed the sparse player (representing the practitioner) is restricted to playing a mixed strategy with a support size at most k . The other player is free to play any mixed strategy they desire. We argue that in many practical use-cases, sparse strategies can almost match the performance of dense strategies, as long as the support of the sparse player is carefully chosen. The problem of finding sparse solutions has been studied from various angles. Althöfer (1994) show that sparse approximations to strategies exist in zero-sum games without too much degradation, while seminal work by Lipton, Markakis, and Mehta (2003) show that approximate sparse Nash equilibria always exist via a sampling argument ( Feder, Nazerzadeh, and Saberi (2007) show the optimality of these results); follow up work extends this argument to correlated and other equilibria ( Babichenko, Barman, and Peretz 2014 ) . Nonetheless, these arguments are nonconstructive in nature, and finding “good” sparse equilibria can be difficult. Indeed, finding the optimal k -sparse commitment even for zero-sum games is in general intractable ( McCarthy et al. 2018 ) . Foster, Golowich, and Kakade (2023) study a variant of sparsity in Markov games where correlated equilibria distributions are expressible as a mixture of k uniform product distributions, while Anagnostides et al. (2023) show hardness of computing sparse correlated equilibria for extensive form games. The line of work closest to ours is by McCarthy et al. (2018) , who study k -sparse solutions under the name of operationalizable strategies, mainly from the perspective of security games. Our work differs from them in several ways. First, our algorithm is not restricted to finding k -uniform strategies, i.e., each of the k actions (possibly repeated) must be chosen with equal probability. Crucially, we significantly expand the scope of applications beyond that of security games, including large games with MILP representable strategy spaces. For the majority of theoretical and algorithmic work above, the term “sparse” is formally defined by asymptotics in terms of the size of the game (e.g., the number of players, and the size of their actions). For our contributions, we adopt colloquial, but often times more practically useful, meanings for the terms sparse and dense, with sparse meaning “small enough” (e.g., say, in single digits), while dense implies the converse. Secondly, a significant amount of work ( Lipton, Markakis, and Mehta 2003 ; Babichenko, Barman, and Peretz 2014 ; McCarthy et al. 2018 ) also requires sparse strategies to be k -uniform. This is a stronger restriction than our notion of k -sparsity, and it can adversely affect performance when we want a sparse strategy in the practical non-asymptotic sense where k is a very small constant; we show this both empirically and theoretically in Sections 3 and 5 . With these distinctions in mind, our key contributions are as follows. First, we formalize the notion of k -sparse commitments for two-player zero-sum games and Stackelberg equilibrium in general-sum games. Second, we study some of the properties of k -sparse commitments. We show that even for zero-sum games, supports of the optimal k -sparse equilibrium can be disjoint for almost all k , and the value function as a set function of allowable support is not submodular. We also demonstrate that k - uniform equilibria as computed by McCarthy et al. (2018) can yield a much worse performance than k -sparse equilibrium. Thirdly, we show how optimal k -sparse commitments can be computed via Mixed Integer Linear Programs (MILPs) for a variety of settings, including zero-sum games, Stackelberg equilibrium, variants of structured action sets, as well as games where one or both players have a large, but MILP-representable strategy spaces. Finally, we demonstrate empirically the efficacy of our proposed method, using both randomly generated normal-form games, as well as settings based on security applications. Our results demonstrate scalability of our method which also often performs better than k -uniform strategies. Even for small k , we are often able to capture nearly 90\% of the true optimal commitment, showing that k -sparse commitments are a practical and viable. 2 Preliminaries We are concerned with two-player games, where Player 1 and 2 have n and m actions respectively. We denote their payoff matrices by A,B\in\mathbb{R}^{n\times m} , such that A_{ij} (resp. B_{ij}) ) gives Player 1’s payoff when Player 1 plays action i and Player 2 plays action j . The spaces of mixed strategies for each player are given by \Delta^{n} and \Delta^{m}

Read the complete text