{"ID":2838140,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.18658","arxiv_id":"2511.18658","title":"Understanding Optimal Portfolios of Strategies for Solving Two-player Zero-sum Games","abstract":"In large-scale games, approximating the opponent's strategy space with a small portfolio of representative strategies is a common and powerful technique. However, the construction of these portfolios often relies on domain-specific knowledge or heuristics with no theoretical guarantees. This paper establishes a formal foundation for portfolio-based strategy approximation. We define the problem of finding an optimal portfolio in two-player zero-sum games and prove that this optimization problem is NP-hard. We demonstrate that several intuitive heuristics-such as using the support of a Nash Equilibrium or building portfolios incrementally - can lead to highly suboptimal solutions. These negative results underscore the problem's difficulty and motivate the need for robust, empirically-validated heuristics. To this end, we introduce an analytical framework to bound portfolio quality and propose a methodology for evaluating heuristic approaches. Our evaluation of several heuristics shows that their success heavily depends on the specific game being solved. Our code is publicly available.","short_abstract":"In large-scale games, approximating the opponent's strategy space with a small portfolio of representative strategies is a common and powerful technique. However, the construction of these portfolios often relies on domain-specific knowledge or heuristics with no theoretical guarantees. This paper establishes a formal...","url_abs":"https://arxiv.org/abs/2511.18658","url_pdf":"https://arxiv.org/pdf/2511.18658v1","authors":"[\"Karolina Drabent\",\"Ondřej Kubíček\",\"Viliam Lisý\"]","published":"2025-11-23T23:58:21Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}