How to arrange a singles’ party: coalition formation in matching game

Joseph E. Mullat<sup>ab

a</sup> Tallinn Technical University, Faculty of Economics, Estonia
^b Byvej 269, 2650 Hvidovre, Denmark

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.

Language: English