Inductive Shapley values in cooperative transportation games

Research output: Working paperProfessional

19 Downloads (Pure)

Abstract

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

Fingerprint

Vehicle routing
Profitability

Cite this

@techreport{94a60c5045f44930b569b4ec07b4042d,
title = "Inductive Shapley values in cooperative transportation games",
abstract = "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",
author = "Reinoud Joosten and Eduardo Lalla-Ruiz",
year = "2019",
month = "7",
day = "12",
language = "English",
publisher = "University of Twente",
address = "Netherlands",
type = "WorkingPaper",
institution = "University of Twente",

}

Inductive Shapley values in cooperative transportation games. / Joosten, Reinoud; Lalla-Ruiz, Eduardo.

University of Twente, 2019.

Research output: Working paperProfessional

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 -