Matchings with Interval Order Preferences: Efficiency vs Strategy-proofness

Procedia Computer Science. 2014. Vol. 31. P. 807–813.

Sofya Kiselgof

We investigate models of two-sided matching markets without transfers. Examples of such markets include marriage market, universities-applicants market and others. Gale and Shapley in 1962 first introduced this kind of problems in the literature. They considered one-to-one and one-to-many markets, where preferences of individuals on the one side over individuals on the other side were strict.

In this paper we analyze a modification of the classical Gale-Shapley admission problem, where preferences of universities are considered to be interval orders. Interval order allows a specific form of indifference in the preference relation. Imagine, each alternative is described with an interval [l, u], and one alternative dominates another if and only if intervals do not overlap and lower bound of the first interval is greater than upper bound of the second interval. Preferences with such property may occur in the cases, when applicants’ scoring system (interview, exam or sum of points) is not exactly accurate.

In the previous paper we have shown the existence of a stable matching and provided the criteria of applicant Pareto-optimality of a stable matching, based on Stable Improvement Cycles.

However, the Pareto-efficient stable mechanism is not (in general) strategy-proof for applicants. We provide a strategy-proof applicant-proposing deferred acceptance with tie-breaking, where tie-breaking procedure is organized in a special way. This special tie-breaking allows to lower chances of an applicant-inefficient stable matching (in comparison to that with random-tie breaking).

Keywords: matchings, Pareto optimality, interval orders, stable matchings

Publication based on the results of: Theoretical and numerical study of advanced mathematical models in the social, economic, political and financial fields (2014)