TY - UNPB
T1 - Inductive Shapley values in cooperative transportation games
AU - Joosten, Reinoud
AU - Lalla-Ruiz, Eduardo
PY - 2019/7/12
Y1 - 2019/7/12
N2 - 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
AB - 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
M3 - Working paper
BT - Inductive Shapley values in cooperative transportation games
PB - University of Twente
ER -