On the number of blocks required to access the core

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

Abstract

For any transferable utility game in coalitional form with 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 less than or equal to n(n-1)/2, where n is the cardinality of the player set. This number considerably improves the upper bounds found so far by Koczy (2006) and Yang (2010). Our result relies on an altered version of the procedure proposed by Sengupta and Sengupta (1996). The use of the Davis-Maschler reduced-games is also pointed out.

• Item Type: MPRA Paper
• Language: English
• Keywords: Core; excess function; dominance path; Davis-Maschler reduced-game
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games

References

[1] R. J. Aumann and M. Maschler, "The Bargaining Set for Cooperative Games", Annals of Mathematical Studies 53 (1963), pp. 443–476.

[2] S. Béal, J. Durieu and P. Solal, "Farsighted Coalitional Stability in TU-games", Mathematical Social Sciences 56 (2008), pp. 303–313.

[3] M. S.-Y. Chwe, "Farsighted Coalitional Stability", Journal of Economic Theory 63 (1994), pp. 299–325.

[4] M. Davis and M. Maschler, "The Kernel of a Cooperative Game", Naval Research Logistics Quarterly 12 (1965), pp. 223–259.

[5] D. B. Gillies, "Some Theorems on n-Person Games", Ph.D. dissertation, Princeton University, Department of Mathematics, 1953.

[6] J. C. Harsanyi, "An Equilibrium Point Interpretation of Stable Sets and a Proposed Alternative Definition", Management Science 20 (1974), pp. 1472–1495.

[7] M. Justman, "Iterative Processes with “Nucleolar” Restrictions", International Journal of Game Theory 6 (1977), pp. 189–212.

[8] L. Kóczy," The Core can be Accessed with a Bounded Number of Blocks", Journal of Mathematical Economics 43 (2006), pp. 56–64.

[9] M. Manea, "Core Tâtonnement", Journal of Economic Theory 133 (2007), pp. 331–349.

[10] F. Maniquet, "A Characterization of the Shapley Value in Queueing Problems", Journal of Economic Theory 109 (2003), pp. 90–103.

[11] B. Peleg, "On the Reduced Game Property and its Converse", International Journal of Game Theory 15 (1986), pp. 187–200.

[12] D. Schmeidler, "The Nucleolus of a Characteristic Function Game", SIAM Journal of Applied Mathematics (1969), 17, pp. 1163–1170.

[13] A. Sengupta and K. Sengupta, "A Property of the Core", Games and Economic Behavior 12 (1996), pp. 266–273.

[14] L. S. Shapley, "The Solutions of a Symmetric Market Game", Contribution to the Theory of Games IV, vol 40, Annals of Mathematics Studies (A. W. Tucker and R. Luce, éds.), Princeton University Press, 1959, pp. 145–162.

[15] R. E. Stearns, "Convergent Transfer Schemes for N-person Games", Transactions of the American Mathematical Society 134 (1968), pp. 449–459.

[16] J. von Neumann and O. Morgenstern, The Theory of Games and Economic Behavior, 3rd edition, Princeton University Press, Princeton, 1953.

[17] Y.-Y. Yang, "On the Accessibility of the Core", Games and Economic Behavior 69 (2010), pp. 194–199.