Mullat, Joseph E. (2010): How to arrange a Singles Party.

PDF
MPRA_paper_24821.pdf Download (209Kb)  Preview 
Abstract
The study addresses important question regarding the computational aspect of coalition formation. Almost as well known to find payoffs (imputations) belonging to a core, is prohibitively difficult, NPhard task even for modern supercomputers. In addition to the difficulty, the task becomes uncertain as it is unknown whether the core is nonempty. Following Shapley (1971), our Singles Party Game is convex, thus the presence of nonempty core is fully guaranteed. The article introduces a concept of coalitions, which are called nebulouses, adequate to critical coalitions, Mullat (1979). Nebulouses represent coalitions minimal by inclusion among all coalitions assembled into a semilattice of sets or kernels of "Monotone System," Mullat (1971,1976,1995), Kuznetsov et al. (1982). An equivalent property to convexity, i.e., the monotonicity of the singles game allowed creating an effective procedure for finding the core by polynomial algorithm, a version of PNP problem. Results are illustrated by MS Excel spreadsheet.
Item Type:  MPRA Paper 

Original Title:  How to arrange a Singles Party 
Language:  English 
Keywords:  stability conditions; game theory; coalition formation 
Subjects:  C  Mathematical and Quantitative Methods > C7  Game Theory and Bargaining Theory > C71  Cooperative Games C  Mathematical and Quantitative Methods > C6  Mathematical Methods; Programming Models; Mathematical and Simulation Modeling > C63  Computational Techniques; Simulation Modeling C  Mathematical and Quantitative Methods > C6  Mathematical Methods; Programming Models; Mathematical and Simulation Modeling > C62  Existence and Stability Conditions of Equilibrium 
Item ID:  24821 
Depositing User:  Joseph E. Mullat 
Date Deposited:  08. Sep 2010 16:19 
Last Modified:  19. Feb 2013 21:43 
References:  1. Berge, C. (1958). Théorie des Graphes et ses Applications, Dunod, Paris. Теория Графов и её Применения, перевод с французского А. А. Зыкова под редакцией И. А. Вайнштейна, Издательство Иностранной Литературы, Москва 1962, in Russian. 2. Cormen, Leiserson, Rivest, and Stein. (2001). Introduction to Algorithms, Chapter 16, "Greedy Algorithms.” 3. Dumbadze, M.N. (1990). Classification Algorithms Based on Core Seeking in Sequences of Nested Monotone Systems, Automation and Remote Control 51, 382387. 4. Edmonds, J. (1970). Submodular functions, matroids and certain polyhedra, in Guy, R.; Hanani, H.; Sauer, N. et al., Combinatorial Structures and Their Applications, New York: Gordon and Breach, pp. 69–87. 5. Kuznetsov, E. N. and I. B. Muchnik I. B. (1982). Analysis of the Distribution of Functions in an Organization, Automation and Remote Control 43, 13251332. 6. Kuznetsov, E.N., Muchnik I.B. and L.V. Shvartsev (1985). Local transformations in monotonic systems. I. Correcting the kernel of monotonic system, Automation and Remote Control 46, 15671578. 7. Mullat, J.E. (1971). On a certain maximum principle for certain setvalued functions, Tr. Tallin. Politech. Inst., Ser. A, No. 313, 3744, (in Russian); (1976). Extremal subsystems of monotone systems. I, Automation and Remote Control, 130139; (1979). Stable Coalitions in Monotonic Games, Automation and Remote Control 40, 1469 1478; (1995). A Fast Algorithm for Finding Matching Responses in a Survey Data Table, Mathematical Social Sciences 30, 195205. 8. Narens, L. and R.D. Luce (1983). How we may have been misled into believing in the Interpersonal Comparability of Utility, Theory and Decisions 15, 247–260. 9. Nemhauser G.L, Wolsey L.A. and. Fisher M.L. (1978). An analysis of approximations for maximizing submodular set functions I., Math. Progr., No.14, 265294. 10. Owen, G. (1968). Game Theory, W.B. Saunders Company, Philadelphia, London, Toronto. 11. Petrov, A. and V. Cherenin. (1948). An improvement of train gathering plans design´s methods, Zheleznodorozhnyi Transport 3 (1948) (in Russian). 12. Rawls, John A. (1971). A Theory of Justice, Revised edition, 2005, Belknap Press of Harvard University. 13. Shapley L.S. (1971). Cores of convex games, International Journal of game Theory, vol. 1, no.1,pp.11–26. 14.Veskioja, T. (2005). Stable Marriage Problem and College Admission, Thesis on Informatics and System Engineering, Faculty of Information Technology, Department of Informatics Tallinn Univ. of Technology, 80p. 15. Võhandu, L.V. (2010). Kõrgkooli vastuvõttu korraldamine stabiilse abielu mudeli rakendusena, Õpetajate Leht, reede, veebruar 2010, nr.7/7, in Estonian. 
URI:  http://mpra.ub.unimuenchen.de/id/eprint/24821 