Stability in Labour Market Games

by Katarína Cechlárová, Robert W. Irving, and David F. Manlove

Scientists from P.J. Šafárik University and the University of Glasgow have investigated a new form of stability in labour markets. This has produced some unexpected results and some challenging open problems.

Labour markets are typical examples of games. On one side, firms seek the best possible employees, and on the other side each prospective employee wishes the best possible job. Various criteria to be satisfied by a matching of workers to firms have been proposed. David Gale and Lloyd Shapley introduced the notion of stability in their paper published in 1962 and indeed, many years later Alvin Roth discovered in 1984 that exactly this notion forms the basis of a large centralised scheme for allocating medical students to hospitals in the USA, called the National Resident Matching Program (NRMP), which has been in use since 1952. Through an ongoing collaboration, motivated by practical matching schemes, we have investigated a new form of stability in labour markets, namely exchange-stability.

The simplest case of a labour market arises when each firm has just one vacant position. Gale and Shapley adopted an amusing name and description for this version of the problem. An instance of the so-called 'Stable Marriage Problem' (SM) involves a set of n men and a set of n women. Each person has a preference list in which he/she ranks all the members of the opposite sex in strict order. A matching M is a one-one correspondence between the men and women. If (m,w)ŒM for some man m and woman w, then m is the mate of w and vice versa. We say that a (man,woman) pair (m,w) is a blocking pair of M if each of m and w prefers the other to his/her mate in M. A matching that admits no blocking pair is said to be stable. Stability ensures that a matching cannot be undermined by two people who could form a private arrangement to their mutual benefit.

Figure 1: An instance of the stable marriage problem and two of its matchings.

An example instance of SM is given by the preference lists in Figure 1 (the entries are shown in decreasing order of preference). The reader may verify that, here, matching M1 admits several blocking pairs, including (m1, w2) and (m2, w1), whilst matching M2 is stable. Gale and Shapley showed in their seminal paper that every instance of SM admits at least one stable matching, and they gave an efficient algorithm for finding such a matching. Their algorithm is as amusing as the problem name, since it simulates a courtship process between the men and women.

When applied to labour markets in practice, the basic Stable Marriage problem has many generalisations. For example, in the context of the NRMP, a given hospital will have many positions in general. Furthermore, the Scottish counterpart of the NRMP, called the 'Scottish PRHO Allocation scheme' (SPA), has to take into account the fact that typically a student seeks two posts that are to be allocated in different half-years. However the stability concept can be generalised to extensions such as these. Moreover, efficient algorithms exist for finding stable matchings in such settings. In applications of this kind, typically the number of participants is very large (30,000 per year for the NRMP), so it is of great interest to analyse the computational complexity of proposed algorithms.

In 1995, an alternative notion of stability, so-called exchange-stability, was introduced by José Alcalde. A matching M in an instance of SM is exchange-stable if there is no exchange-blocking pair. This is a pair of participants of the same sex, each of whom prefers the other participant's mate in M to his/her own mate in M. In contrast to classical Gale-Shapley stability, there are instances of SM that do not admit an exchange-stable matching, such as the one in Figure 2. The reader may verify that, here, matching M1 admits the exchange-blocking pair {w1,w2}, whilst matching M2 admits the exchange-blocking pair {m1,m2}.

Figure 2: An instance of the stable marriage problem with no exchange-stable matching.

In a recent collaboration (funded by Slovak Agency for Science contract 'Combinatorial Structures and Complexity of Algorithms', by Engineering and Physical Sciences Research Council grant GR/R84597/01, and by Nuffield Foundation award NUF-NAL-02), we have shown that, somewhat surprisingly, the problem of deciding whether an instance of SM admits an exchange-stable matching is NP-complete. That is, there is no polynomial-time algorithm for this problem unless P=NP. However, for a weaker form of exchange-stability, so-called man-exchange-stability, in which exchange-blocking pairs are only permitted to contain two men, every instance of SM admits at least one man-exchange-stable matching, and such a matching may be found efficiently. Analogously, one may define woman-exchange-stability, with similar results.

Some practical motivation for considering exchange-stability may be drawn from the following real-life scenario. Recently, two students participating in the SPA scheme discovered that, if they could have exchanged their assigned hospitals with each other, then they would each have ended up with a more favourable assignment. Naturally the hospitals to which the students were matched would not have permitted the exchange (for if they were to have agreed, it would have implied that the original matching contained a blocking pair with respect to classical stability, whereas the primary consideration of SPA is to produce a matching that is stable in the classical sense). However when such a situation arises, it can adversely affect the level of confidence that the participants have in the fairness of the matching scheme.

We therefore close with the following problem linking classical stability and exchange-stability: it is an open question as to whether the problem of finding a stable matching that is man-exchange-stable is solvable in polynomial time.

Links:
http://www.nrmp.org/about_nrmp/how.html

Please contact:
Katarína Cechlárová
P.J. Šafárik University/SRCIM
E-mail cechlarovascience.upjs.sk

Rob Irving, David Manlove
Department of Computing Science,
University of Glasgow, UK
E-mail {rwi,davidm}dcs.gla.ac.uk