Modelling Preference Ties and Equal Treatment Policy

Abstract

The college admission problem (CAP) has been studied extensively in the last 65 years by mathematicians, computer scientists and economists following the seminal paper of Gale and Shapley (1962). Their basic algorithm, the so called deferred acceptance mechanism always returns a student optimal stable matching in linear time, and it is indeed widely used in practice. However, there can be some special features which may require significant adjustments on this algorithm, or the usage of other techniques, in order to satisfy all the objectives of the decision maker. The college admissions problem with ties and equal treatment policy is solvable with an extension of the Gale and Shapley algorithm, but, if there are further constraints, such as lower quotas, there exist no efficient way to find a stable solution. Both of these features are present in the Hungarian higher education matching scheme and a simple heuristic is used to compute the cutoff scores. Integer programming is a robust technique that can provide optimal solutions even when we have multiple requirements. In this paper we develop and test a new IP formulation for finding stable solutions for CAP with ties and equal treatment policy. This formulation is more general than the previously studied ones, and it has better performance, as we demonstrate with simulations, mostly because of its pure binary nature.