A Cost-Sharing Scheme for the k-Product Facility Location Game with Penalties

In the k-product facility location game with penalties, each customer must be supplied with k different products or be rejected by paying the penalty cost. The game is considered in this paper. The cost-sharing scheme for this game refers to allocating the costs of the problem to all customers. We present a cross-monotonic and competitive scheme which satisfies 2 and \((\frac{3k}{2}-\frac{3}{2})\) -approximate cost recovery when \(k=2\) and \(k \ge 3\) , respectively. Moreover, the lower bound of the cost-sharing scheme is obtained for the k-product facility location game with penalties.