2025/06/02 by Laura Sanità, Sanità, Laura, Lucy Verberk +1 · 1 voice
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #Auction Theory and Applications #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Game Theory and Voting Systems #Transportation Planning and Optimization #cs.DM
paper · pdf · doi:10.48550/arxiv.2506.01509
openalex publication_date 2025/06/02 · arxiv published 2025/06/02 · arxiv updated 2025/06/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.