Solutions for sharing the cost of a set covering situation

M. Pulido Cayuela, J. Sánchez-Soriano, G. Bergantiños Cid, M. Gómez-Rúa, N. Llorca Pascual

The (weighted) set covering problem is one of the classical problems in discrete location theory. In this problem, a set of customers requires a kind of service which is provided by a set of facilities. Any facility can only serve the subset of customers who are “close enough” to it. A setup cost must be paid for opening a facility and, at the same time, the total cost of locating a set of facilities must be minimized in such a way every customer is covered for at least one facility. In this paper, we focus on the cost sharing situation associated with a set covering problem. Our main goal is to share the optimal cost among all customers. Firstly, we study the corresponding cooperative game and introduce some desirable properties which any rule should accomplish. Secondly, we propose some core-like solutions and bankruptcy-like solutions which are close related to the structure of the set covering situation. Finally, we analyze the properties of those solutions.

Palabras clave: Cost sharing, Set covering problem, Core, Bankruptcy rules

X03.4 Grupo de Teoría de Juegos II
7 de septiembre de 2016  10:00
Aula 21.07

E. Gutiérrez Núñez, N. Llorca Pascual, M. A. Mosquera Rodríguez, J. Sánchez-Soriano

J. Sánchez-Soriano, V. Fragnelli, N. Llorca Pascual

G. Bergantiños Cid, P. Arribillaga

G. Bergantiños Cid, J. J. Vidal Puga