Abstract
Combinatorial optimization games form an important subclass of cooperative games. In recent years, increased attention has been given to the issue of finding good cost shares for such games. In this paper, we define a very general class of games, called integer minimization games, which includes the combinatorial optimization games in the literature as special cases. We then present new techniques, based on row and column generation, for computing good cost shares for these games. To illustrate the power of these techniques, we apply them to traveling salesman and vehicle routing games. Our results generalize and unify several results in the literature. The main underlying idea is that suitable valid inequalities for the associated combinatorial optimization problems can be used to derive improved cost shares.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bauer P.: The circuit polytope: facets. Math. Oper. Res. 22, 110–145 (1997)
Bläser M., Shankar Ram L.: Approximately fair cost allocation in metric traveling salesman games. Theory Comput. Syst. 43, 19–37 (2008)
Bondareva O.N.: Some applications of linear programming to cooperative games. Problemy Kibernetiki. 10, 119–139 (1963)
Bramel J., Simchi-Levi D.: Set-covering-based algorithms for the capacitated VRP. In: Toth, P., Vigo, D. (eds) The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications SIAM, Philadelphia (2002)
Dantzig G.B., Wolfe P.: Decomposition principle for linear programs. Oper. Res. 8, 101–111 (1960)
de Aragaõ M.P., Uchoa E.: Integer program reformulation for robust branch-and-cut-and-price. In: Wosley, L. (eds) Annals of Mathematical Programming in Rio, pp. 56–61. Búzios, Brazil (2003)
Deng X., Ibaraki T., Nagamochi H.: Algorithmic aspects of the core of combinatorial optimization games. Math. Oper. Res. 24, 751–766 (1999)
Edmonds J.: Maximum matching and a polyhedron with 0,1-vertices. J. Res. Natl. Bur. Stand. 69, 125–130 (1965)
Faigle U., Fekete S.P., Hochstättler W., Kern W.: On approximately fair cost allocation for the Euclidean traveling salesman problem. OR Spektrum 20, 29–37 (1998)
Fekete, S.P., Pulleyblank, W.R.: A note on the traveling preacher problem. Report No. 98.331, Angewandte Mathematik und Informatik, Universität zu Köln (1998)
Fukasawa, R., Lysgaard, J., de Aragão, M.P., Reis, M., Uchoa, E., Werneck, R.F.: Robust branch-and-cut-and-price for the capacitated vehicle routing problem. In Nemhauser, G., Bienstock, D. (eds.) Integer Programming and Combinatorial Optimization 10, pp. 1–15. Lecture Notes in Computer Science 3064, Berlin, Springer (2004)
Gillies D.B.: Solutions to general non-zero-sum games. In: Tucker, A.W., Luce, R.D. (eds) Contributions to the Theory of Games, vol. 4, pp. 47–85. Princeton University Press, Princeton (1959)
Goemans, M.X.: Private communication (2004)
Goemans M.X., Skutella M.: Cooperative facility location games. J. Algorithms 50, 194–214 (2004)
Göthe-Lundgren M., Jörnsten K., Värbrand P.: On the nucleolus of the basic vehicle routing game. Math. Program. 72, 83–100 (1996)
Granot D., Huberman G.: Minimum cost spanning tree games. Math. Program. 21, 1–18 (1981)
Grötschel M., Lovász L., Schrijver A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)
Grötschel M., Padberg M.W.: On the symmetric travelling salesman problem I: inequalities. Math. Program. 16, 265–280 (1979)
Grötschel M., Padberg M.W. et al.: Polyhedral theory. In: Lawler, E.L. (eds) The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, Chichester (1985)
Grötschel M., Pulleyblank W.: Clique tree inequalities and the symmetric travelling salesman problem. Math. Oper. Res. 11, 537–569 (1986)
Gouveia L.: A result on projection for the vehicle routing problem. Eur. J. Opl. Res. 85, 610–684 (1995)
Houck D.J., Picard J.-C., Queyranne M., Vemuganti R.R.: The travelling salesman problem as a constrained shortest path problem: theory and computational experience. Opsearch 17, 93–109 (1980)
Jain K., Mahdian M.: Cost sharing. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds) Algorithmic Game Theory, Cambridge University Press, Cambridge (2007)
Letchford A.N., Eglese R.W., Lysgaard J.: Multistars, partial multistars and the capacitated vehicle routing problem. Math. Program. 94, 21–40 (2002)
Letchford A.N., Salazar Gonzalez J.J.: Projection results for vehicle routing. Math. Program. 105, 251–274 (2006)
Naddef D.: Polyhedral theory and branch-and-cut algorithms for the symmetric TSP. In: Gutin, G., Punnen, A. (eds) The Traveling Salesman Problem and Its Variations, Kluwer, Dordrecht (2001)
Naddef D., Rinaldi G.: The symmetric traveling salesman polytope and its graphical relaxation: composition of valid inequalities. Math. Program. 51, 359–400 (1991)
von Neumann J., Morgenstern O.: Theory of Games and Economic Behaviour. Princeton University Press, Princeton (1947)
Okamoto Y.: Traveling salesman games with the Monge property. Discr. Appl. Math. 138, 349–369 (2004)
Padberg M.W., Rao M.R.: Odd minimum cut-sets and b-matchings. Math. Oper. Res. 7, 67–80 (1982)
Pal, M., Tardos, E.: Group strategy proof mechanisms via primal-dual algorithms. In: Proceedings of the 44th annual IEEE symposium on foundations of computer science (FOCS 2003), pp. 584–593 (2003)
Peleg B., Sudholter P.: Introduction to the Theory of Cooperative Games. Kluwer, Dordrecht (2003)
Potters J.A.M., Curiel I.J., Tijs S.H.: Traveling salesman games. Math. Program. 53, 199–211 (1992)
Seymour P.D.: Sums of circuits. In: Bondy, J.A., Murty, U.S.R. (eds) Graph Theory and Related Topics, pp. 341–355. Academic Press, London (1979)
Shapley L.S.: On balanced sets and cores. Nav. Res. Log. Quart. 14, 453–460 (1967)
Shapley L.S., Shubik M.: The assignment game I: the core. Int. J. Game Theory 1, 111–130 (1972)
Shubik, M.: Game theory models and methods in political economy. In Arrow, K.J., Intriligator, M.D. (eds.) Handbook of Mathematical Economics, vol. I. North-Holland, pp. 285–330 (1981)
Tamir A.: On the core of a traveling salesman cost allocation game. Oper. Res. Lett. 8, 31–34 (1988)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Caprara, A., Letchford, A.N. New techniques for cost sharing in combinatorial optimization games. Math. Program. 124, 93–118 (2010). https://doi.org/10.1007/s10107-010-0357-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-010-0357-7
Keywords
- Cooperative games
- Optimal cost shares
- Combinatorial optimization games
- Valid inequalities
- Traveling salesman game
- Vehicle routing game