Abstract
A model of taxation for cooperativen-person games is introduced where proper coalitions Are taxed proportionally to their value. Games with non-empty core under taxation at rateɛ-balanced. Sharp bounds onɛ in matching games (not necessarily bipartite) graphs are estabLished. Upper and lower bounds on the smallestɛ in bin packing games are derived and euclidean random TSP games are seen to be, with high probability,ɛ-balanced forɛ≈0.06.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bondareva ON (1963) Some applications of linear programming methods to the theory of cooperative games. Problemy Kibernet 10:119–139 (in Russian)
Claus A, Kleitman DJ (1973) Cost allocation for a spanning tree. Networks 3:289–304
Faigle U, Kern W (1993) unpublished
Goemans M, Bertsimas D (1991) Probabilistic analysis of the Held and Karp lower bound for the euclidean TSP. Math of OR 16:72–89
Kern W (1989) On the rate of convergence of some stochastic processes. Math of OR 14:275–280
Lovász L, Plummer MD (1986) Matching theory. North Holland Math Studies 121, North Holland, Amsterdam
Owen G (1975) The core of linear production games. Math Programming 9:358–370
Potters JAM, Curiel IJ, Tijs SH (1992) Traveling salesman games. Math Progr 53:199–211
Rhee WT, Talagrand M (1989) A sharp deviation for the stochastic TSP. Ann Probab 17:1–8
Shapley LS (1967) On balanced sets and cores. Naval Res Logist Quaterly 14:453–460
Shapley LS, Shubik M (1966) Quasi-cores in a monetary economy with nonconvex preferences. Econometrica 34:805–827
Shapley LS, Shubik M (1972) The assignment game I: The core. Intern J Game Theory 1:111–130
Steele M (1990) Probabilistic and worst case analyses of classical problems of combinatorial optimization in euclidean space. Math of OR 15:749–770
Tamir A (1989) On the core of a traveling salesman cost allocation game. OR Letters 8:31–34
Tamir A (1991) On the core of network synthesis games. Math Programming 50:123–135
Tijs SH, Driessen TSH (1986) Extensions of solution concepts by means of multiplicativeɛ-tax games. Math Social Sciences 12:9–20
Wolsey LA (1980) Heuristic analysis, Linear programming and branch and bound. Math Programming Study 13:121–134
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Faigle, U., Kern, W. On some approximately balanced combinatorial cooperative games. ZOR - Methods and Models of Operations Research 38, 141–152 (1993). https://doi.org/10.1007/BF01414210
Issue Date:
DOI: https://doi.org/10.1007/BF01414210