Allocating costs in set covering problems

Bergantiños, Gustavo and Gómez-Rúa, María and Llorca, Natividad and Pulido, Manuel and Sánchez-Soriano, Joaquin (2019): Allocating costs in set covering problems.

Abstract

This paper deals with the problem of allocating costs in set covering situations. In particular, we focus on set covering situations where the optimal covering is given in advance. Thus, we take into account only the facilities that have to be opened and look for rules distributing their cost. We define a cooperative game and study the core and the nucleolus. We also introduce two new rules: the equal split rule on facilities and the serial rule. We axiomatically characterize the core, the nucleolus, and the two rules. Finally, we study several monotonicity properties of the rules.

• Item Type: MPRA Paper
• Language: English
• Keywords: set covering problems; cost sharing rules; cooperative games
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games

References

Balcan, M.-F., Krehbiel, S., Piliouras, G., & Shin, J. (2011). Near optimality in covering and packing games by exposing global information. arXiv:1109.3606 [cs.GT].

Beasley, J.E., & Jørnsten, K. (1992). Enhancing an algorithm for set covering problems. European Journal of Operational Research, 58(2), 293-300.

Bergantiños, G., Gómez-Rúa, M., Llorca, N., Pulido, M., & Sánchez-Soriano, J. (2014). A new rule for source connection problems. European Journal of Operational Research, 234(3), 780-788.

Bergantiños, G., & Lorenzo-Freire, S. (2008). "Optimistic" weighted Shapley rules in minimum cost spanning tree problems. European Journal of Operational Research, 185(1), 289-298.

Bergantiños, G., & Vidal-Puga, J.J. (2007). A fair rule in minimum cost spanning tree problems. Journal of Economic Theory, 137, 326-352.

Berge, C. (1957). Two theorems in graph theory. Proceedings of the National Academy of Sciences, 43(9), 842-844.

Bird, C. (1976). On cost allocation for a spanning tree: a game theoretic approach. Networks, 6, 335-350.

Borm, P., Hamers, H., & Hendrickx, R. (2001). Operations research games: A survey. TOP, 9, 139-216.

Caprara, A., & Letchford, A. (2010). New techniques for cost sharing in combinatorial optimization games. Mathematical Programming, 124, 93-118.

Cardinal, J., & Hoefer, M. (2010). Non-cooperative facility location and covering games. Theoretical Computer Science, 411, 1855-1876.

Claus, A., & Kleitman, D.J. (1973). Cost allocation for a spanning tree. Networks, 3, 289-304.

Deng, X., Ibaraki, T., & Nagamochi, H. (1999). Algorithms aspects of the core of combinatorial optimization games. Mathematics of Operations Research, 24(3), 751-766.

Devanur, N. R., Mihail, M., & Vazirani, V. V. (2005). Strategyproof cost-sharing mechanisms for set cover and facility location games. Decision Support Systems, 39, 11-22.

Escoffier, B., Gourves, L., & Monnot, J. (2010). On the impact of local taxes in a set cover game. In B. Patt-Shamir, & T. Ekim (Eds.), Structural Information and Communication Complexity. SIROCCO 2010. In Lecture Notes in Computer Science: 6058 (pp. 2-13). Springer.

Fragnelli, V., & Gagliardo, S. (2013). Open problems in cooperative location games. International Game Theory Review 15(3): 1340015.

García, S., & Marín, A. (2015). Covering location problems. In G. Laporte, S. Nickel, & F. Saldanha da Gama (Eds.), Location Science (pp.93-114). Springer.

Gillies, D.B. (1953). Some theorems on n-person games. PhD thesis, Princeton University, Princeton.

Goemans, M. X., & Skutella, M. (2004). Cooperative facility location games. Journal of Algorithms, 50(2), 194-214.

Granot, D. (1987). The role of cost allocation in locational models. Operations Research, 35, 234-248.

Kalai, E., & Zemel, E. (1982). Totally balanced games and games of flow. Mathematics of Operations Research, 7, 476-478.

Karp, R.M. (1972). Reducibility among combinatorial problems. In R. E. Miller, J. W. Thatcher, & J.D. Bochlinger (Eds.), Complexity of computer computations (pp. 85-103). Springer

Li, X.Y., Sun, Z., \& Wang, W. (2005). Cost Sharing and Strategyproof Mechanisms for Set Cover Games. In: Diekert V., Durand B. (eds) STACS 2005. Lecture Notes in Computer Science 3404:218-230. Springer.

Li, X.-Y., Sun, Z., Wang, W., & Lou, W. (2010). Cost sharing and strategyproof mechanisms for set cover games. Journal of combinatorial optimization, 20(3), 259-284.

Moulin, H., & Shenker, S. (1992) Serial cost sharing. Econometrica, 60(5), 1009-1037.

Owen, G. (1975). On the core of linear production games. Mathematical Programming, 9, 358-370.

Piliouras, G., Valla, T., & Végh, L. A. (2015). LP-based covering games with low price of anarchy. Theory of Computing Systems, 57(1), 238-260.

Puerto, J., Garcia-Jurado, I., & Fernandez, F.R. (2001). On the core of a class of location games. Mathematical Methods of Operations Research, 54, 373-385.

Sanchez-Soriano, J. (2003). The pairwise egalitarian solution. European Journal of Operational Research, 150(1), 220-231.

Sanchez-Soriano, J. (2006). Pairwise solutions and the core of transportation situations. European Journal of Operational Research, 175(1), 101-110.

Schmeidler, D. (1969). The nucleolus of a characteristic function game. SIAM Journal on Applied Mathematics, 17(6), 1163-1170.

Shapley, L. S. & Shubik, S. (1972). The assignment game I: The core. International Journal of Game Theory, 1, 111--130.

Tamir, A. (1992). On the core of cost allocation games defined on location problems. Transportation Science, 27(1), 81-86.

Toregas, C., Swain, R., ReVelle, C., & Bergman, L. (1971). The location of emergency service facilities. Operations Research, 19(6), 1363-1373.