Inductive τ-values in cooperative transportation games under computational time constraints

The -value is the efficient convex combination of the ‘minimal-rights’ and ‘utopia’ vectors in a cooperative game. The utopia amount is the player’s marginal contribution to the grand coalition. The remainder for a given player in a certain coalition containing him is the amount left after the sum of the utopia amounts of all other players is subtracted from the coalition’s worth. The player’s minimal-rights amount is then the largest remainder taken over all coalitions containing him. We deal with the problem that a solution for a cooperative transportation game (CTG), e.g., an allocation of profits, may be required before all worths of the coalitions are known. In CTGs computing the worth of a coalition may involve solving a traveling salesman or vehicle routing problem which are NP-hard, and there are exponentially many worths to determine. Finally, computing the -value is NP-hard itself. An inductive-value is the efficient allocation closest to the set of all convex combinations of approximations of the utopia and minimal-rights vectors. First, the worth of the grand coalition is determined which (by assumption) is always possible. As long as 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. The utopia and minimal rights vectors of the game restricted to the cardinality at hand are determined, too. If the computation time reaches the constraint while establishing worths for coalitions with cardinality, the approximations of the utopia and minimal rights vectors based on the completed calculations up to U are used. If the time constraint is not binding, the inductive -value coincides with a natural extension of the -value for hyperplane singular games, and with the -value for quasi-balanced games. We show that the inductive -value satisfies efficiency, symmetry, desirability and two axioms introduced in Joosten & Lalla-Ruiz (Inductive Shapley values in cooperative transportation games, University of Twente, 2019). The latter four axioms incorporate aspects of fairness guaranteed for the computations being based on restricted information.