Abstract
In cooperative game theory we often take important primitives as given by some `oracle' in order to focus on the distribution of the benefits of cooperation among all players. Even under such ideal circumstances, the computation of an actual solution may be time-consuming as for instance the nucleolus, the Shapley value or the core become increasingly hard to determine as the number of agents increases.
In cooperative transportation games (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. We therefore deal with the situation that a solution for a CTG may be required before the `oracle' has determined all primitives.
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, and this worth is taken equal for all auxiliary games. 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 as the inductive nucleolus of the game. If the time constraint is not binding, the inductive nucleolus coincides with the nucleolus.
We show that the inductive nucleolus shares attractive axioms with the nucleolus, while incorporating aspects of fairness for computations under time constraints.
JEL-codes: C71
Keywords: Inductive nucleolus, cooperative transportation games
In cooperative transportation games (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. We therefore deal with the situation that a solution for a CTG may be required before the `oracle' has determined all primitives.
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, and this worth is taken equal for all auxiliary games. 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 as the inductive nucleolus of the game. If the time constraint is not binding, the inductive nucleolus coincides with the nucleolus.
We show that the inductive nucleolus shares attractive axioms with the nucleolus, while incorporating aspects of fairness for computations under time constraints.
JEL-codes: C71
Keywords: Inductive nucleolus, cooperative transportation games
| Original language | English |
|---|---|
| Number of pages | 30 |
| Publication status | Unpublished - 23 May 2025 |