The Complexity of Pure Maxmin Strategies in Two-Player Extensive-Form Games
Authors: Junkang Li, Bruno Zanuttini, Vรฉronique Ventos
JAIR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the complexity of computing the pure maxmin value for such games, i.e. the maximum reward that a player can guarantee by playing a pure strategy, whatever their opponents play. We focus on two-player and two-team games and perform a systematic study depending on the degree of imperfect information of each player or team: perfect information, perfect recall, or perfect recall for each agent in a team (which we call multi-agent perfect recall). For each combination, we settle the complexity of deciding whether the maxmin value is at least as high as a given threshold. We give a complete complexity picture for three orthogonal settings: games represented explicitly by their game tree; games represented compactly by game rules, for which we propose two new formalisms; games in which the set of strategies of the opponents is restricted to a known set of opponent models. |
| Researcher Affiliation | Collaboration | Junkang Li EMAIL Nukk AI, Paris, France Universit e Caen Normandie, ENSICAEN, CNRS, Normandie Univ, GREYC UMR6072, F-14000 Caen, France Bruno Zanuttini EMAIL Universit e Caen Normandie, ENSICAEN, CNRS, Normandie Univ, GREYC UMR6072, F-14000 Caen, France V eronique Ventos EMAIL Nukk AI, Paris, France |
| Pseudocode | Yes | Algorithm 1: Polynomial-time algorithm for verifying that a ๐-tuple (๐1, . . . , ๐๐) is reachable under some pure strategy of MAX against the ๐OMs. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code, nor does it provide any links to code repositories for the methodology described in this work. |
| Open Datasets | No | The paper is theoretical and focuses on computational complexity. It uses mathematical problem formulations (like Subset Sum or Tiling problems for reductions) but does not involve empirical studies with specific datasets. Therefore, no information on public dataset access is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical studies using datasets. Therefore, there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and focuses on computational complexity; it does not describe any experiments that would require specific hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and focuses on computational complexity; it does not describe any experiments that would require specific software dependencies with version numbers. Therefore, no software dependency details are provided. |
| Experiment Setup | No | The paper is theoretical and focuses on computational complexity; it does not describe any experiments that would require specific setup details like hyperparameters or training configurations. Therefore, no experimental setup details are provided. |