|
Article Excerpt
Baiou and Balinski characterized the stable admissions polytope using a system of linear inequalities. The structure of feasible solutions to this system of inequalities--fractional stable matchings--is the focus of this paper. The main result associates a geometric structure with each fractional stable matching. This insight appears to be interesting in its own right, and can be viewed as a generalization of the lattice structure (for integral stable matchings) to fractional stable matchings. In addition to obtaining simple proofs of many known results, the geometric structure is used to prove the following two results: First, it is shown that assigning each agent their "median" choice among all stable partners results in a stable matching, which can be viewed as a "fair" compromise; second, sufficient conditions are identified under which stable matchings exist in a problem with externalities, in particular, in the stable matching problem with couples.
Key words: stable matching; university admissions; two-sided market; linear programming; randomized rounding; fairness; matching with couples
MSC2000 subject classification: Primary: 90C05, 90C10, 90C35, 91B68; secondary: 90C08, 90C57
OR/MS subject classification: Primary: networks/graphs/matching, programming/linear; Secondary: games
History: Received March 4, 2004; revised February 1, 2005, and January 27, 2006.
1. Introduction. The stable marriage problem and its variants have been studied extensively over the last few decades. Beginning with the pioneering work of Gale and Shapley [17], this problem has captured the attention of researchers and practitioners in several disciplines such as computer science, economics, mathematics, and operations research. The multidisciplinary nature of these problems has led to a thorough understanding of many aspects, such as the design of efficient algorithms to find a stable matching, the structure of all solutions to a given stable matching instance, etc. In fact, by now there are several well-developed approaches to stable matching problems: the combinatorial/algorithmic approach as summarized in the books of Knuth and Goldstein [24] and Gusfield and Irving [18]; the linear programming approach initiated by Vande Vate [39], and further developed by Rothblum [36], Roth et al. [34], Teo and Sethuraman [38], Baiou and Balinski [6], and Fleiner [16]; the fixed-point approach of Subramanian [37] and Feder [12, 13]; an alternative fixed-point approach of Adachi [2]; yet another fixed-point approach due to Fleiner [15]; and a graph-theoretic approach due to Balinski and Ratier [7, 8] and Baiou and Balinski [5].
In addition to its elegant theory, a particularly appealing feature of the stable matching model is its applicability. In fact, starting with the work of Roth [28], applications to the National Resident Matching Program (NRMP) and related labor markets have given rise to interesting questions, resulting in a better understanding of the theory. Moreover, insights from this theory have been useful in the redesign of the stable matching algorithm used by the NRMP (Roth and Peranson [31]). An introduction to the theory of stable matchings with particular emphasis on applications to labor markets is elegantly summarized in Roth and Sotomayor [32]; recent work in this direction includes Roth and Peranson [30, 31], Cantala [11], and Klaus and Klijn [22].
This close interaction between applications and theory continues to this day and is an inspiration for the questions we study, described next.
1.1. Problem description, motivation, and results. It has long been recognized that the (natural) stable matching mechanisms suggested by the "proposal" algorithm of Gale and Shapley [17] are biased, i.e., they compute the best stable matching for one side of the market, which incidentally is also the worst stable matching for the other side of the market. From its inception until 1997, the NRMP used the hospital-optimal matching mechanism as the basis of its allocation. However, increasing pressure from student bodies and others (1) led to the redesign of the matching mechanism in 1998 (Roth and Peranson [30, 31]).
The inequitable treatment of the participants on different sides of the market persists in most known matching mechanisms. This has motivated the need for the design of fair stable matching mechanisms, which do not overtly favor one side of the market over the other. Considerable efforts have been devoted to finding "fair" stable matchings, including the egalitarian solution (minimize the sum of the ranks of the participants) and the minimum-regret solution (maximize the welfare of the participant worst-off in the matching) (Gusfield and Irving [18]). Nevertheless, these approaches are not satisfactory because they focus on socially optimal solutions and ignore the issue of fairness at the individual level.
Motivated by "procedural" fairness considerations, Klaus and Klijn [22] analyze three probabilistic stable matching mechanisms: employment by lotto, proposed by Aldershof et al. [4]; the random order mechanism, proposed by Roth and Vande Vate [35] and Ma [25]; and the equitable random order mechanism, proposed by Romero-Medina [27]. Their analysis shows that the three mechanisms may give completely different outcomes. They also note that the associated probability distribution for each of these mechanisms need not be uniform on the set of stable matchings; in fact, not all stable matchings can arise from these random matching mechanisms. Klaus and Klijn [22] construct an example and showed that a stable matching that constitutes a perfect compromise between contrary preferences on both sides of the market may never result from random matching mechanisms. Curiously, the perfect compromise solution identified there is the median solution (where the agents are assigned to their median stable partners), whose existence had in fact been established earlier in Teo and Sethuraman [38] for the one-to-one stable matching problem. The existence of such a solution is not obvious: Consider the assignment obtained by pairing each agent with his or her median stable partner; that such an assignment should be a matching is itself surprising, so it is quite amazing that the resulting solution is not only a matching but is also stable! In this paper, we establish the existence of such a median solution concept for the many-to-one model, thus proposing a new approach to address the asymmetry often observed in the stable matching problem. This result, as well as the earlier result in Teo and Sethuraman [38], can be viewed as a generalization of an observation first made by Conway (Gusfield and Irving [18]) on the lattice structure of stable matchings. (2)
Several generalizations and extensions of the stable matching problem have been studied in the past because of potential applications to NRMP and other labor markets. Of particular interest is the one in which certain pairs of students ("couples") would like to be assigned to universities that are geographically close together. We identify natural conditions on the preferences under which the couples problem can be handled effectively. Note that, in this case, a stable matching solution may not even exist. Furthermore, Klaus et al. [23] show that in the presence of couples, the current NRMP algorithm may fail to converge to a stable matching!
The common theme underlying our results is a refined understanding of the structure of "fractional" stable matchings. Baiou and Balinski [6] characterize the convex hull of all stable admissions solutions using linear inequalities in the natural assignment variables. We use the Baiou-Balinski formulation to show that the fractional stable admission solutions can be decomposed into convex combination of (integral) stable admission solutions in a simple way. As a by-product, our approach gives a simple visual proof of the integrality of the Baiou-Balinski formulation.
The main results in this paper are derived using a "bin-packing" theorem, obtained by packing a given fractional solution in a particular way. Interestingly, this approach can be viewed as a continuous analog of the bin-packing theorem used by Fleiner [15] to describe the polytope of the more general many-to-many stable matchings. However, in the approach used by Fleiner, the underlying inequalities are obtained through an iterative algorithm; the description of the polytope is thus implicit. The Baiou-Balinski formulation is explicit and is thus a more convenient and natural approach for our goal.
1.2. Organization of the paper. We introduce the stable admissions polytope in [section] 2. In [section] 3, we provide a geometric structure to the fractional stable admissions solutions. Section 4 uses this structure to design a fair stable matching mechanism for the many-to-one stable matching problem. We also describe how the stable matching problem with couples can be addressed using this approach. We end with a brief summary.
2. The stable admissions model. An instance of the stable admissions problem consists of two sets of agents, the set U = {[u.sub.1], [u.sub.2], ..., [u.sub.[absolute value of U]} of "universities" and the set A = {[a.sub.1], [a.sub.2], ..., [a.sub.[absolute value of A]} of "students." Each agent has a strict, transitive, preference ordering of the acceptable agents on the other side of the market, i.e., those agents on the other side of the market that it prefers to remaining unmatched. Let [GAMMA] [subset or equal to] U x A denote the set of acceptable pairs. We assume without loss of generality that (i) u finds a acceptable if and only if a finds u acceptable, and in this case, we say that (u, a) is an acceptable pair; and (ii) university u finds at least [q.sub.u] students acceptable, and each student finds at least one university acceptable. Associated with university u is a positive integer [q.sub.u] representing its quota, the interpretation being university u is allowed to admit up to [q.sub.u] students. Note that we consider the somewhat restrictive model of responsive preferences in which the universities have preferences over individual students, not over groups of students. We refer the reader to Roth and Sotomayor [32, Chapter 6] for interesting discussions on this issue. (3)
A matching [mu] for a stable admissions problem is a subset of [GAMMA] such that each university u appears in at most [q.sub.u] pairs and each student a appears at most once in [mu]. For convenience, we let [mu](a) represent the university that student a is assigned to, and [mu](u) represent the set of students assigned to university u. We let [mu](a) = {a} if student a is unmatched in [mu].
A matching [mu] is stable if there is no incentive for any pair (u, a) to deviate from [mu]. That is, there is no pair (u, a) [member of] [GAMMA] such that student (i) student a prefers university u to [mu](a) and (ii) university u prefers to add student a to its set of students, possibly at the expense of another (less-preferred) student. (If a is unmatched in [mu], then (i) is trivially satisfied.)
By the classical result of Gale and Shapley [17], every instance of the stable admissions problem admits a stable matching. The stable admissions problem with [q.sub.u] = 1 for all u [member of] U is called the stable marriage problem.
2.1. Definitions and notation. The symbols [>.sub.u] and [>.sub.a] will indicate the preference orderings of university u and student a, respectively; in particular, a [>.sub.u] b iff university u prefers student a to student b, and a [[greater than or equal to].sub.u] b iff a [>.sub.u] b or a = b. The shaft, S(u, a), is defined for every (u, a) [member of] [GAMMA] as
S(u, a) = {(u, b) [member of] [GAMMA]: b [[greater than or equal to].sub.u] a}.
The tooth, T(u, a), is defined for every (u, a) [member of] [GAMMA] as
T(u, a) = {(u, a) [member of] [GAMMA]: v [[greater than or equal to].sub.a] u}.
For any set of [q.sub.u] students {a, [a.sub.1], ..., [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]} with [a.sub.i] [>.sub.u] a for all i, the comb C(u, a, [a.sub.1], ..., [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]) is the...
|
