A polynomial time algorithm for computing the nucleolus for a class of disjunctive games with a permission structure
Recently, applications of cooperative game theory to economic allocation problems have gained popularity. In many such allocation problems there is some hierarchical ordering of the players. In this paper we consider a class of games with a permission structure describing situations 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 provide a polynomial time algorithm for computing the nucleolus of the restricted games corresponding to a class of games with a permission structure which economic applications include auction games, dual airport games, dual polluted river games and information market games.
|Keywords||Algorithm, Complexity, Game with permission structure, Information market game, Nucleolus, Peer group game, TU-game|
|Publisher||Physica-Verlag, Heidelberg / Vienna|
|Note||Article in press - dd November 2010|
van den Brink, R, Katsev, I, & van der Laan, G. (2010). A polynomial time algorithm for computing the nucleolus for a class of disjunctive games with a permission structure. Physica-Verlag, Heidelberg / Vienna. Retrieved from http://hdl.handle.net/1765/21374