An optimal bound to access the core in TU-games

Béal, Sylvain and Rémila, Eric and Solal, Philippe (2012): An optimal bound to access the core in TU-games.

Abstract

For any transferable utility game in coalitional form with a nonempty core, we show that that the number of blocks required to switch from an imputation out of the core to an imputation in the core is at most n-1, where n is the number of players. This bound exploits the geometry of the core and is optimal. It considerably improves the upper bounds found so far by Koczy (2006), Yang (2010, 2011) and a previous result by ourselves (2012) in which the bound was n(n-1)/2.

• Item Type: MPRA Paper
• Language: English
• Keywords: Core ; Block ; Weak dominance relation ; Strong dominance relation ; Davis-Maschler reduced games
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games

References

S. Béal, E. Rémila and P. Solal. "On the number of blocks required to access the coalition-structure core", MPRA Paper No. 29755, 2011.

S. Béal, E. Rémila and P. Solal. "On the number of blocks required to access the core", Discrete Applied Mathematics 160 (2012), p. 925-932.

M. S.-Y. Chwe. "Farsighted coalitional stability", Journal of Economic Theory 63 (1994), p. 299-325.

M. Davis and M. Maschler. "The Kernel of a cooperative game", Naval Research Logistics Quarterly 12 (1965), p. 223-259.

D. B. Gillies. "Some theorems on n-person games", Ph.D. Dissertation, Princeton University, Department of Mathematics, 1953.

J. C. Harsanyi. "Equilibrium point interpretation of stable sets and a proposed alternative definition", Management Science 20 (1974), p. 1472-1495.

L. A. Koczy. "The core can be accessed with a bounded number of blocks", Journal of Mathematical Economics 43 (2006), p. 56-64.

B. Peleg. "On the reduced game property and its converse", International Journal of Game Theory 15 (1986), p. 187-200.

A. Schrijver. "Polyhedral Combinatorics", in Handbook of Combinatorics (Graham, Grotschel, Lovasz (eds)), Elsevier Science B.V., Amsterdam, 1995.

A. Sengupta and K. Sengupta. "A property of the core", Games and Economic Behavior 12 (1996), p. 266-273.

L. S. Shapley. "Cores of convex games", International Journal of Game Theory 1 (1971), p. 11-26.

J. von Neunamm and O. Morgenstern. The theory of games and economic behavior, Princeton University Press, Princeton, 1953.

Y.-Y. Yang. "On the Accessibility of the Core", Games and Economic Behavior 69 (2010), p. 194-199.

Y.-Y. Yang. "accessible outcomes versus absorbing outcomes", Mathematical Social Sciences 62 (2011), p. 65-70.