On the number of blocks required to access the coalition structure core

Béal, Sylvain and Rémila, Eric and Solal, Philippe (2011): On the number of blocks required to access the coalition structure core.

Abstract

This article shows that, for any transferable utility game in coalitional form with nonempty coalition structure core, the number of steps required to switch from a payoff configuration out of the coalition structure core to a payoff configuration in the coalition structure core is less than or equal to (n*n+4n)/4, where n is the cardinality of the player set. This number considerably improves the upper bound found so far by Koczy and Lauwers (2004).

• Item Type: MPRA Paper
• Language: English
• Keywords: coalition structure core; excess function; payoff configuration; outsider independent domination.
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games

References

[1] R. J. Aumann, "Some non-superadditive games, and their Shapley value, in the Talmud", International Journal of Game Theory 39 (2010), pp. 3–10.

[2] S. Béal, E. Rémila and P. Solal, "On the number of blocks required to access the core", MPRA Paper No. 26578, 2010.

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

[4] J. Greenberg, "Coalition structures", ch. 37 in Handbook of Game Theory with Economic Applications, vol II, (R.J. Aumann and S. Hart eds.), pp. 1305–1307, Elsevier, Amsterdam, 1994.

[5] L. Kóczy, "The core can be accessed with a bounded number of blocks", Journal of Mathematical Economics 43 (2006), pp. 56–64.

[6] L. Kóczy and L. Lauwers, "The coalition structure core is accessible", Games and Economic Behavior 48 (2004), pp. 86–93.

[7] A. Sengupta and K. Sengupta, "Viable proposals", International Economic Review 35 (1994), pp. 347–359.

[8] A. Sengupta and K. Sengupta, "A property of the core", Games and Economic Behavior 12 (1996), pp. 266–273.

[9] L. S. Shapley, "Cores of convex games", International Journal of Game Theory (1971), 1, pp. 11–26.

[10] P. P. Shenoy, "On coalition formation: a game-theoretical approach", International Journal of Game Theory 8 (1979), pp. 133–164.

[11] Y.-Y. Yang, "On the accessibility of the core", Games and Economic Behavior 69 (2010), pp. 194–199.