Inductive Shapley values in cooperative transportation games

Reinoud Joosten*, Eduardo Lalla-Ruiz

*Corresponding author for this work

Research output: Working paper

153 Downloads (Pure)


The Shapley value (Sh) gives each player in a cooperative game his marginal contribution to the H(art &)M(as-Colell)-potential of the grand coalition. For cooperative transportation games, computing the worth of a coalition may involve solving a traveling salesman or a vehicle routing problem which are known to be NP-hard. Moreover, the computation of Sh is NP-hard itself. We take into account that in applications a solution, i.e., an allocation of savings or profits, may be required before all worths of the coalitions, necessary for the computation of Sh have been established. An inductive Shapley value (ISh) gives each player in a cooperative game his marginal contribution to an inductively approximated HM-potential of the grand coalition. First, the worth of the grand coalition is determined which (by assumption) is always possible. As long as the constraint is not met, the worths of all coalitions with cardinality 1 are computed, followed by those for all coalitions with cardinality 2, and so on. Simultaneously, the HM-potential of the game restricted to the coalition at hand is determined, as well as an auxiliary function based on all HM-potentials found until then. If the computation time reaches the constraint at cardinality U+1, the auxiliary functions determine the inductive HM-potential of the grand coalition and all coalitions with one member missing, based on the completed calculations for cardinalities smaller than or equal to U. If the constraint is not binding, the ISh coincides with the standard Shapley value. ISh satisfies efficiency, linearity, but also the balanced contributions property (a fairness property) in general. ISh is sensitive up to cardinality U and insensitive beyond cardinality U, i.e., it depends on and only on information that has been computed, and therefore not on factors unrelated to verifiable properties of the game. JEL-codes: C71. Keywords: Inductive Hart & Mas-Colell potentials, inductive Shapley values, cooperative transportation games
Original languageEnglish
PublisherUniversity of Twente
Publication statusPublished - 12 Jul 2019


Dive into the research topics of 'Inductive Shapley values in cooperative transportation games'. Together they form a unique fingerprint.

Cite this