Template-Type: ReDIF-Paper 1.0
Series: Tinbergen Institute Discussion Papers
Creation-Date: 2008-10-31
Number: 08-104/1
Author-Name: René van den Brink
Author-Email: jrbrink@feweb.vu.nl
Author-Workplace-Name: VU University Amsterdam
Author-Name: Ilya Katsev
Author-Workplace-Name: St. Petersburg Institute for Economics and Mathematics, Russian Academy of Sciences
Author-Name: Gerard van der Laan
Author-Email: glaan@feweb.vu.nl
Author-Workplace-Name: VU University Amsterdam
Title: An Algorithm for Computing the Nucleolus of Disjunctive Additive Games with An Acyclic Permission Structure
Abstract: A situation in which a finite set of players can obtain certain payoffs by cooperation can be described by a cooperative game with transferable utility, or simply a TU-game. A (single-valued) solution for TU-games assigns a payoff distribution to every TU-game. A well-known solution is the nucleolus. A cooperative game with a permission structure describes a situation in which players in a cooperative TU-game are hierarchically ordered in the sense that there are players that need permission from other players before they are allowed to cooperate. The corresponding restricted game takes account of the limited cooperation possibilities by assigning to every coalition the worth of its largest feasible subset. In this paper we consider the class of non-negative additive games with an acyclic permission structure. This class generalizes the so-called peer group games being non-negative additive games on a permission tree. We provide a polynomial time algorithm for computing the nucleolus of every restricted game corresponding to some disjunctive non-negative additive game with an acyclic permission structure. We discuss an application to market situations where sellers can sell objects to buyers through a directed network of intermediaries.
Classification-JEL: C71
Keywords: TU-game, additive game, acyclic permission structure, disjunctive approach, peer group game, nucleolus, algorithm, complexity
File-Url: https://papers.tinbergen.nl/08104.pdf
File-Format: application/pdf
File-Size: 456700 bytes
Handle: RePEc:tin:wpaper:20080104