Strongly essential coalitions and the nucleolus of peer group games
Most of the known efficient algorithms designed to compute the nucleolus for special classes of balanced games are based on two facts: (i) in any balanced game, the coalitions which actually determine the nucleolus are essential; and (ii) all essential coalitions in any of the games in the class belong to a prespeci ed collection of size polynomial in the number of players.We consider a subclass of essential coalitions, called strongly essential coalitions, and show that in any game, the collection of strongly essential coalitions contains all the coalitions which actually determine the core, and in case the core is not empty, the nucleolus and the kernelcore.As an application, we consider peer group games, and show that they admit at most 2n - 1 strongly essential coalitions, whereas the number of essential coalitions could be as much as 2n-1. We propose an algorithm that computes the nucleolus of an n-player peer group game in O(n2) time directly from the data of the underlying peer group situation.
(This abstract was borrowed from another version of this item.)
Volume (Year): 33 (2005)
Issue (Month): 3 (09)
|Contact details of provider:|| Web page: http://www.springer.com|
|Order Information:||Web: http://www.springer.com/economics/economic+theory/journal/182/PS2|
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Arin, J. & Feltkamp, V., 1994.
"The nucleolus and kernel of veto-rich transferable utility games,"
1994-40, Tilburg University, Center for Economic Research.
- Vincent Feltkamp & Javier Arin, 1997. "The Nucleolus and Kernel of Veto-Rich Transferable Utility Games," International Journal of Game Theory, Springer;Game Theory Society, vol. 26(1), pages 61-73.
- Solymosi, Tamas & Raghavan, T. E. S. & Tijs, Stef, 2005. "Computing the nucleolus of cyclic permutation games," European Journal of Operational Research, Elsevier, vol. 162(1), pages 270-280, April.
- Le Breton,Michel & Owen,Guillermo & Weber,Shlomo, 1991.
"Strongly balanced cooperative games,"
Discussion Paper Serie A
338, University of Bonn, Germany.
- Maschler, M & Potters, J A M & Tijs, S H, 1992. "The General Nucleolus and the Reduced Game Property," International Journal of Game Theory, Springer;Game Theory Society, vol. 21(1), pages 85-106.
- D. Granot & F. Granot & W. R. Zhu, 1998. "Characterization sets for the nucleolus," International Journal of Game Theory, Springer;Game Theory Society, vol. 27(3), pages 359-374.
- Reijnierse, Hans & Potters, Jos, 1998. "The -Nucleolus of TU-Games," Games and Economic Behavior, Elsevier, vol. 24(1-2), pages 77-96, July.
- Maschler, M. & Potters, J.A.M. & Tijs, S.H., 1992. "The general nucleolus and the reduced game property," Other publications TiSEM ab187dab-1b5b-40c3-a673-8, Tilburg University, School of Economics and Management.
- Brânzei, R. & Fragnelli, V. & Tijs, S.H., 2002.
"Tree-connected peer group situations and peer group games,"
Other publications TiSEM
f4601b66-2e29-4969-85ca-0, Tilburg University, School of Economics and Management.
- Brânzei, R. & Fragnelli, V. & Tijs, S.H., 2000. "Tree-connected Peer Group Situations and Peer Group Games," Discussion Paper 2000-117, Tilburg University, Center for Economic Research.
- Brânzei, R. & Fragnelli, V. & Tijs, S.H., 2000. "On the computation of the nucleolus of line-graph peer group games," Other publications TiSEM fd889ce3-d034-47a2-9f6b-2, Tilburg University, School of Economics and Management.
When requesting a correction, please mention this item's handle: RePEc:spr:jogath:v:33:y:2005:i:3:p:447-460. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Sonal Shukla)or (Rebekah McClure)
If references are entirely missing, you can add them using this form.