Computational time constraints in applied cooperative games: the inductive nucleolus

In cooperative game theory important primitives are often taken as given in order to focus on the distribution of the benefits of cooperation among all players. Even under such ideal circumstances, the computation of a solution may be time-consuming as for instance the nucleolus or the Shapley value become increasingly hard to determine as the number of agents increases. In applications of cooperative games computing the worth of a coalition may involve solving an NP-hard problem, and there are exponentially many worths to be determined. Under this triple curse of dimensionality, we deal with the situation that a solution may be required before all primitives are known. An inductive nucleolus is determined on a series of auxiliary games. First, the worth of the grand coalition is determined which (by assumption) is always possible. While the time constraint is not met, the worths for all coalitions with cardinality 1 are computed, then for those with cardinality 2, and so on. Each time computations of all worths for a certain cardinality are complete, an auxilliary game and its nucleolus are determined. If the computation time reaches the constraint while computing worths for coalitions with cardinality U + 1, the nucleolus of the auxilliary game based on the completed calculations up to U is reported. If the time constraint is not binding, the inductive nucleolus and nucleolus coincide. We show that the inductive nucleolus shares attractive axioms with the nucleolus, while incorporating aspects of fairness for computations under time constraints.