The Two-Stage Stochastic Facility Location Game
摘要
This paper investigates a two-stage stochastic facility location game in which customers pay the incurred costs by sharing the costs, including facility opening and customer connection costs. The players in this game are the customers, and the aim is to minimise the total cost by deciding which facilities to open and how to connect customers in the most cost-effective way. The model is inherently cross-monotonic. We are interested in developing cross-monotonic cost-sharing strategies to encourage customers to cooperate by revealing their true value. To this end, we propose an approximation method based on the primal-dual technique. Subsequently, we prove that our proposed algorithm can achieve 6-approximation cost-sharing.