# Solving Large Extensive-Form Games with Strategy Constraints

arXiv: https://arxiv.org/abs/1809.07893 · HTML: https://mlsanity.com/paper/1809.07893/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Sep 2018.

## Built on by (most cited first, 2 of 2)

- [Convex-Concave Min-Max Stackelberg Games](https://mlsanity.com/paper/2110.05192/) (2021)
- [Opponent Modeling in Multiplayer Imperfect-Information Games](https://mlsanity.com/paper/2212.06027/) (2022)

## Abstract (arXiv)

Extensive-form games are a common model for multiagent interactions with imperfect information. In two-player zero-sum games, the typical solution concept is a Nash equilibrium over the unconstrained strategy set for each player. In many situations, however, we would like to constrain the set of possible strategies. For example, constraints are a natural way to model limited resources, risk mitigation, safety, consistency with past observations of behavior, or other secondary objectives for an agent. In small games, optimal strategies under linear constraints can be found by solving a linear program; however, state-of-the-art algorithms for solving large games cannot handle general constraints. In this work we introduce a generalized form of Counterfactual Regret Minimization that provably finds optimal strategies under any feasible set of convex constraints. We demonstrate the effectiveness of our algorithm for finding strategies that mitigate risk in security games, and for opponent modeling in poker games when given only partial observations of private information.