Stable matching in preference relationships

Abstract

It is the aim of this paper to review some of the work done on stable matching, and on stable marriage problems in particular.

Variants of the stable marriage problem will be considered, and the similarities and differences from a mathematical point of view will be highlighted. The correlation between preference and stability is a main theme, and the way in which diluted or incomplete preferences affect stability is explored.

Since these problems have a wide range of practical applications, it is of interest to develop useful algorithms for the derivation of solutions. Time-complexity is a key factor in designing computable algorithms, making work load a strong consideration for practical purposes. Average and worst-case complexity are discussed.

The number of different solutions that are possible for a given problem instance is surprising, and counter-intuitive. This leads naturally to a study of the solution sets and the lattice structure of solutions that emerges for any stable marriage problem. Many theorems derive from the lattice structure of stable solutions and it is shown that this can lead to the design of more efficient algorithms.

The research on this topic is well established, and many theorems have been proved and published, although some published proofs have omitted the detail. In this paper, the author selects some key theorems, providing detailed proofs or alternate proofs, showing the mathematical richness of this field of study.

Various applications are discussed, particularly with relevance to the social sciences, although mention is made of applications in computer science, game theory, and economics.

The current research that is evident in this subject area, by reference to technical papers in periodicals and on the internet, suggests that it will remain a key topic for some time to come.