Primal-Dual-Based Approximation Algorithms for the Two-Stage Stochastic Facility Location Game and Its Variant

This study investigates a two-stage stochastic facility location game (2-SFLG), in which clients collaboratively share the combined costs of facility opening and client connection. As strategic players, the clients aim to minimize the total cost through jointly decisions on which facilities to open and how to assign connections in the most cost-effective way. We focus on designing cross-monotonic cost-sharing strategies that incentivize client cooperation by revealing their true value. To this end, an approximation method utilizing the primal-dual technique is developed, which achieves a 6-approximation cost-sharing ratio, effectively balancing cost distribution and cooperation incentives. Furthermore, we introduce a novel variant, the 2-SFLG with penalties (2-SFLGP), which generalizes both the FLGP and the 2-SFLG. Crucially, our cost-sharing method for the 2-SFLGP preserves the same approximation guarantee while demonstrating competitive performance.