How to arrange a Singles' Party (pdf)

Joseph E. Mullat, independent researcher, without affiliation

The study addresses important issues relating to computational aspects of coalition formation. Almost as well known, to find payoffs (imputations) belonging to the core is, even for modern supercomputers, an overly complex, NP-hard problem. In addition to the difficulty, the task becomes uncertain as 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 non-dominant outcomes induced by coalitions minimal by inclusion among special coalitions, which constitute a join semi-lattice of sets (kernels), Mullat [1971-1995], Kempner et al. [2008], Kuznetsov et al. [1982]. We claim that monotone property of outcomes equivalent to convexity of characteristic function, Shapley [1971], leads to effective procedure for finding the quasi-core by polynomial algorithm – a version of P-NP problem. Results are illustrated by Excel spreadsheet.