E

OData support
Supervisor:
Dr. Fleiner Tamás
Department of Computer Science and Information Theory

The analysis of stable matchings in one-sided matching markets:

Matching markets naturally occur in any field of life, most relevant examples including the admission of pupils to schools or matching patients with kidney failure to appropriate donors. It is common that the allocation is undertaken by a central scheme, a mechanism that yields an equitable, optimal matching. For instance, the Hungarian university admission system is based on such considerations.

Applications modelled by a two-sided matching market usually involve preferences that agents on either side of the market form about the counter-market party. The goal is to determine a stable matching. The classical showpieces in the field are the high school and university admission systems. The standard representation of the matching problem is a bipartite graph which encodes pupils and universities into vertices and an edge links a pupil and a university if and only if the pupil actually applies to the institution in question. While pupil-side preferences are determined by the application order, the preferences of the universities are implicitly determined by the score of applicants from their previous studies. The aim is to centrally compute a matching, where university quotas are filled such that no pupil is rejected from a highly ranked university unless all the accepted applicants possess a higher score. This property is called stability.

One-sided markets attempt to pair up agents of a single object-space with stability in mind. A typical application in the flesh is the dormitory quota-distribution system used by the Technion Israel Institute of Technology. Students within the same living facility are paired up into rooms based on their personal preferences about each other. The very name of this market problem, the Stable Roommates problem, originates from this example. The goal is to achieve a matching, in which there are no two students that were not paired up, yet they mutually prefer each other to the assigned partners.

Fair, optimal stable matchings:

In the roommates-problem, the mean rank of partners taken over all agents may well differ among stable matchings. The aim of our research was to select an optimal, or so called, egalitarian solution from the possible stable matchings. Notwithstanding the fact that the task is proven to be NP-hard, there are significant results concerning approximation algorithms, which, by definition, compute efficiently an almost optimal solution. Our main purpose is the enhancement of such algorithms by designing new techniques. By the end of the work, we will manage to improve the well-founded 2-approximation in general case to a 9/7-approximation in a special case, where the length of lists are limited.

Downloads

Please sign in to download the files of this thesis.