Understanding Optimal Portfolios of Strategies for Solving Two-player Zero-sum Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908671200460800 |
|---|---|
| author | Drabent, Karolina Kubíček, Ondřej Lisý, Viliam |
| author_facet | Drabent, Karolina Kubíček, Ondřej Lisý, Viliam |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_18658 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Understanding Optimal Portfolios of Strategies for Solving Two-player Zero-sum Games Drabent, Karolina Kubíček, Ondřej Lisý, Viliam Computer Science and Game Theory 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. |
| title | Understanding Optimal Portfolios of Strategies for Solving Two-player Zero-sum Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2511.18658 |