How to arrange a Singles Party

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

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, NP-hard task even for modern super-computers. In addition to the difficulty, the task becomes uncertain as it is unknown whether the core is non-empty. Following Shapley (1971), our Singles Party Game is convex, thus the presence of non-empty 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 semi-lattice 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 P-NP problem. Results are illustrated by MS Excel spreadsheet.

• Item Type: MPRA Paper
• 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

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, 382-387.

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, 1325-1332.

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, 1567-1578.

7. Mullat, J.E. (1971). On a certain maximum principle for certain set-valued functions, Tr. Tallin. Politech. Inst., Ser. A, No. 313, 37-44, (in Russian); (1976). Extremal subsystems of monotone systems. I, Automation and Remote Control, 130-139; (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, 195-205.

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, 265-294.

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.