Two-stage Stochastic Assignment Games
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910980265476096 |
|---|---|
| author | Sanità, Laura Verberk, Lucy |
| author_facet | Sanità, Laura Verberk, Lucy |
| contents | In this paper, we study a two-stage stochastic version of the assignment game, which is a fundamental cooperative game. Given an initial setting, the set of players may change in the second stage according to some probability distribution, and the goal is to find core solutions that are minimally modified.
When the probability distribution is given explicitly, we observe that the problem is polynomial time solvable, as it can be modeled as an LP. More interestingly, we prove that the underlying polyhedron is integral, and exploit this in two ways.
First, integrality of the polyhedron allows us to show that the problem can be well approximated when the distribution is unknown, which is a hard setting.
Second, we can establish an intimate connection to the well-studied multistage vertex cover problem. Here, it is known that the problem is NP-hard even when there are only 2 stages and the graph in each stage is bipartite. As a byproduct of our result, we can prove that the problem is polynomial-time solvable if the bipartition is the same in each stage. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_01509 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Two-stage Stochastic Assignment Games Sanità, Laura Verberk, Lucy Discrete Mathematics In this paper, we study a two-stage stochastic version of the assignment game, which is a fundamental cooperative game. Given an initial setting, the set of players may change in the second stage according to some probability distribution, and the goal is to find core solutions that are minimally modified. When the probability distribution is given explicitly, we observe that the problem is polynomial time solvable, as it can be modeled as an LP. More interestingly, we prove that the underlying polyhedron is integral, and exploit this in two ways. First, integrality of the polyhedron allows us to show that the problem can be well approximated when the distribution is unknown, which is a hard setting. Second, we can establish an intimate connection to the well-studied multistage vertex cover problem. Here, it is known that the problem is NP-hard even when there are only 2 stages and the graph in each stage is bipartite. As a byproduct of our result, we can prove that the problem is polynomial-time solvable if the bipartition is the same in each stage. |
| title | Two-stage Stochastic Assignment Games |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2506.01509 |