On some approximately balanced combinatorial cooperative games

A model of taxation for cooperative n-person games is introduced where proper coalitions are taxed proportionally to their value. Games with non-empty core under taxation at rate • are •-balanced. Sharp bounds on • in matching games on (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.