Geodesic
How to arrange a singles’ party: coalition formation in matching game
Contributions to game theory and management, Tome 7 (2014), pp. 221-238.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{CGTM_2014_7_a19,
     author = {Joseph E. Mullat},
     title = {How to arrange a singles{\textquoteright} party: coalition formation in matching game},
     journal = {Contributions to game theory and management},
     pages = {221--238},
     publisher = {mathdoc},
     volume = {7},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CGTM_2014_7_a19/}
}
TY  - JOUR
AU  - Joseph E. Mullat
TI  - How to arrange a singles’ party: coalition formation in matching game
JO  - Contributions to game theory and management
PY  - 2014
SP  - 221
EP  - 238
VL  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CGTM_2014_7_a19/
LA  - en
ID  - CGTM_2014_7_a19
ER  - 
%0 Journal Article
%A Joseph E. Mullat
%T How to arrange a singles’ party: coalition formation in matching game
%J Contributions to game theory and management
%D 2014
%P 221-238
%V 7
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CGTM_2014_7_a19/
%G en
%F CGTM_2014_7_a19
Joseph E. Mullat. How to arrange a singles’ party: coalition formation in matching game. Contributions to game theory and management, Tome 7 (2014), pp. 221-238. http://geodesic.mathdoc.fr/item/CGTM_2014_7_a19/

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

[2] Arrow K. J., “Rational Choice functions and orderings”, Economica, 26:102 (1959), 121–127 | DOI

[3] Berge C., Théorie des Graphes et ses Applications, Dunod, Paris, 1958 | MR

[4] Chernoff H., “Rational selection of decision functions”, Econometrica, 22:3 (1984), 422–443 | MR

[5] Cormen T. H., Leiserson C. E., Rivest R. L., Stein C., “Greedy Algorithms”, Introduction to Algorithms, Chapter 16, 2001 | MR

[6] Dumbadze M. N., “Classification Algorithms Based on Core Seeking in Sequences of Nested Monotone Systems”, Automation and Remote Control, 51 (1990), 382–387 | MR | Zbl

[7] Edmonds J., “Submodular functions, matroids and certain polyhedral”, Combinatorial Structures and Their Applications, eds. Guy R., Hanani H., Sauer N., et al., Gordon and Breach, New York, NY, 1970, 69–87 | MR

[8] Gale D., Shapley L. S., “College Admissions and the Stability of Marriage”, American Mathematical Monthly, 69 (1962), 9–15 | DOI | MR | Zbl

[9] Kempner Y., Levit V. E., Muchnik I. B., “Quasi-Concave Functions and Greedy Algorithms”, Advances in Greedy Algorithms, ed. W. Bednorz, I-Tech., Vienna, Austria, 2008, 586–XX pp.

[10] Kuznetsov E. N., Muchnik I. B., “Analysis of the Distribution of Functions in an Organization”, Automation and Remote Control, 43 (1982), 1325–1332 | MR | Zbl

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

[12] Malishevski A. V., Qualitative Models in the Theory of Complex Systems, Nauka. Fizmatlit, M., 1998 (in Russian) | Zbl

[13] Mullat J. E., “A Fast Algorithm for Finding Matching Responses in a Survey Data Table”, Mathematical Social Sciences, 30 (1995), 195–205 | DOI | MR | Zbl

[14] Mullat J. E., “Stable Coalitions in Monotonic Games”, Aut. and Rem. Control, 40 (1979), 1469–1478 | Zbl

[15] Mullat J. E., “Extremal subsystems of monotone systems, I”, Aut. and Rem. Control, 5 (1976), 130–139 | MR | Zbl

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

[17] Narens L., Luce R. D., “How we may have been misled into believing in the Interpersonal Comparability of Utility”, Theory and Decisions, 15 (1983), 247–260 | DOI | Zbl

[18] Nemhauser G. L., Wolsey L. A., Fisher M. L., “An analysis of approximations for maximizing submodular set functions, I”, Math. Progr., 14 (1978), 265–294 | DOI | MR | Zbl

[19] Owen G., Game Theory, 2nd ed., Academic Press, Inc., San Diego, CA, 1982 | MR | Zbl

[20] Petrov A., Cherenin V., “An improvement of train gathering plans design's methods”, Zheleznodorozhnyi Transport, 3 (1948) (in Russian)

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

[22] Roth A. E., Sotomayor M., Two-sided Matching: A Study in Game-Theoretic Modeling and Analysis, Cambridge University Press, New York, NY, 1990 | MR | Zbl

[23] Shapley L. S., “Cores of convex games”, International Journal of Game Theory, 1:1 (1971), 11–26 | DOI | MR | Zbl

[24] Sen A. K., “Choice functions and revealed preference”, Rev. Econ. Stud., 38:115 (1971), 307–317 | DOI | Zbl

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

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