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 epsilon are epsilon-balanced. Sharp bounds on epsilon in matching games on (not necessarily bipartite) graphs are established. Upper and lower bounds on the best epsilon in bin packing games are derived and euclidean random TSP games are seen to be, with high probability, epsilon-balanced for epsilon approx. = 0.06.