Institutional Repository

Stable matching in preference relationships

Show simple item record

dc.contributor.advisor Swanepoel, K. (Prof.) en
dc.contributor.advisor Barnard, A. (Prof.) en Philpin, Elizabeth Mary en 2009-08-25T10:46:39Z 2009-08-25T10:46:39Z 2009-08-25T10:46:39Z 2006-11-30 en
dc.identifier.citation Philpin, Elizabeth Mary (2009) Stable matching in preference relationships, University of South Africa, Pretoria, <> en
dc.description.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. en
dc.format.extent 1 online resource (67 leaves)
dc.language.iso en en
dc.subject Stable marriage en
dc.subject Matching algorithms en
dc.subject College admissions problem en
dc.subject.ddc 511.66
dc.subject.lcsh Marriage theorem
dc.subject.lcsh Matching theory
dc.title Stable matching in preference relationships en
dc.type Thesis en
dc.description.department MATHEMATICAL SCIENCES en MSC (MATHEMATICS) en

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search UnisaIR


My Account