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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

The Two-Stage Stochastic Facility Location Game

  • Xiaoyun Tian,
  • Mengzhen Li,
  • Chenchen Wu,
  • Dachuan Xu

摘要

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.