How to arrange a Singles' Party: Coalition Formation in Matching Game

Authors

  • Joseph E. Mullat Tallinn Technical University

Abstract

The study addresses important issues relating to computational aspects of coalition formation. However, finding payoffs−imputations belonging to the core−is, while almost as well known, an overly complex, NP-hard problem, even for modern supercomputers. The issue becomes uncertain because, among other issues, it is unknown whether the core is non-empty. In the proposed cooperative game, under the name of singles, the presence of non-empty collections of outcomes (payoffs) similar to the core (say quasi-core) is fully guaranteed. Quasi-core is defined as a collection of coalitions minimal by inclusion among non-dominant coalitions induced through payoffs similar to super-modular characteristic functions (Shapley, 1971). As claimed, the quasi-core is identified via a version of P-NP problem that utilizes the branch and bound heuristic and the results are visualized by Excel spreadsheet.

Keywords:

stability, game theory, coalition formation

Downloads

Download data is not yet available.

References

Aizerman, M. A., and Malishevski, A. V. (1981). Some Aspects of the general Theory of best Option Choice. Automation and Remote Control, 42, 184–198.

Arrow, K. J. (1959). Rational Choice functions and orderings. Economica, 26(102), 121–127.

Berge, C. (1958). Théorie des Graphes et ses Applications. Dunod, Paris.

Chernoff, H. (1984). Rational selection of decision functions. Econometrica, 22(3), 422–443.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2001). Greedy Algorithms. In Introduction to Algorithms, Chapter 16.

Dumbadze, M. N. (1990). Classification Algorithms Based on Core Seeking in Sequences of Nested Monotone Systems. Automation and Remote Control, 51, 382–387.

Edmonds, J. (1970). Submodular functions, matroids and certain polyhedral. In Guy, R., Hanani, H., Sauer, N., et al. (Eds.), Combinatorial Structures and Their Applications (pp. 69–87). New York, NY: Gordon and Breach.

Gale, D., and Shapley, L. S. (1962). College Admissions and the Stability of Marriage. American Mathematical Monthly, 69, 9–15.

Kempner, Y., Levit, V. E., and Muchnik, I. B. (2008). Quasi-Concave Functions and Greedy Algorithms. In W. Bednorz (Ed.), Advances in Greedy Algorithms, (pp. 586–XX). Vienna, Austria: I-Tech.

Kuznetsov, E. N., and Muchnik, I. B. (1982). Analysis of the Distribution of Functions in an Organization. Automation and Remote Control, 43, 1325–1332.

Kuznetsov, E. N., Muchnik I. B., and Shvartser, L. V. (1985). Local transformations in monotonic systems I. Correcting the kernel of monotonic system. Automation and Remote Control, 46, 1567–1578.

Malishevski, A. V. (1998). Qualitative Models in the Theory of Complex Systems. Moscow: Nauka, Fizmatlit, (in Russian).

Mullat, J. E. (1995). A Fast Algorithm for Finding Matching Responses in a Survey Data Table. Mathematical Social Sciences, 30, 195–205.

Mullat, J. E. (1979). Stable Coalitions in Monotonic Games. Aut. and Rem. Control, 40, 1469–1478.

Mullat, J. E. (1976). Extremal subsystems of monotone systems. I. Aut. and Rem. Control, 5, 130–139.

Mullat, J. E. (1971). On a certain maximum principle for certain set-valued functions. Tr. of Tall. Polit. Inst, Ser. A, 313, 37–44, (in Russian).

Narens, L. and Luce, R. D. (1983). How we may have been misled into believing in the Interpersonal Comparability of Utility. Theory and Decisions, 15, 247–260.

Nemhauser G. L., Wolsey L. A., and Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions I. Math. Progr., 14, 265–294.

Owen, G. (1982). Game Theory (2nd ed.). San Diego, CA: Academic Press, Inc.

Petrov, A., and Cherenin, V. (1948). An improvement of train gathering plans design’s methods. Zheleznodorozhnyi Transport, 3 (in Russian)

Rawls, J. A. (2005). A Theory of Justice. Boston, MA: Belknap Press of Harvard University. (original work published in 1971)

Roth, A. E., and Sotomayor, M. (1990). Two-sided Matching: A Study in Game-Theoretic Modeling and Analysis. New York, NY: Cambridge University Press.

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

Sen, A. K. (1971). Choice functions and revealed preference. Rev. Econ. Stud., 38(115), 307–317.

Veskioja, T. (2005). Stable Marriage Problem and College Admission. PhD dissertation on Informatics and System Engineering, Faculty of Information Technology, Department of Informatics Tallinn Univ. of Technology.

Võhandu, L. V. (2010). Kõrgkooli vastuvõttu korraldamine stabiilse abielu mudeli rakendusena. Õpetajate Leht, reede, veebruar, nr.7/7.1 (in Estonian).

Downloads

Published

2022-08-09

How to Cite

E. Mullat, J. (2022). How to arrange a Singles’ Party: Coalition Formation in Matching Game. Contributions to Game Theory and Management, 7. Retrieved from https://gametheory.spbu.ru/article/view/13605

Issue

Vol. 7 (2014)

Section

Articles

License

Articles of "Contributions to Game Theory and Management" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.