We Study Strategic Issues In The Gale Shapley Stable Marriage ...
Gale-Shapley Stable Marriage
Problem Revisited: Strategic Issues
and Applications
Chung-Piaw Teo • Jay Sethuraman • Wee-Peng Tan
Department of Decision Sciences, Faculty of Business Administration, National University of Singapore,
FBA 1-15 Law Link, Singapore 117591
Department of Industrial Engineering and Operations Research, Columbia University,
New York, New York 10027
Department of Decision Sciences, Faculty of Business Administration, National University of Singapore,
FBA 1-15 Law Link, Singapore 117591
fbateocp@nus.edu.sg • jay@ieor.columbia.edu
We study strategic issues in the Gale-Shapley stable marriage model. In the first part
of the paper, we derive the optimal cheating strategy and show that it is not always
possible for a woman to recover her women-optimal stable partner from the men-optimal
stable matching mechanism when she can only cheat by permuting her preferences. In fact,
we show, using simulation, that the chances that a woman can benefit from cheating are
slim. In the second part of the paper, we consider a two-sided matching market found in
Singapore. We study the matching mechanism used by the Ministry of Education (MOE) in
the placement of primary six students in secondary schools, and discuss why the current
method has limited success in accommodating the preferences of the students, and the spe-
cific needs of the schools (in terms of the “mix” of admitted students). Using insights from
the first part of the paper, we show that stable matching mechanisms are more appropriate
in this matching market and explain why the strategic behavior of the students need not be
a major concern.
(Stable Marriage; Strategic Issues; Gale-Shapley Algorithm; Student Posting Exercise )
1.
Introduction
matching mechanism (a complete description appears
This paper is motivated by a study of the mech-
in §4). In fact, two well-known stable matching
anism used to assign primary school students in
mechanisms—the students-optimal stable mechanism,
Singapore to secondary schools. The current assign-
and the schools-optimal stable mechanism—appear to
ment process requires that the primary school stu-
be natural candidates; however, neither of these
dents submit a rank-ordered list of six schools to the
mechanisms (nor any other stable matching mech-
Ministry of Education. Students are then assigned to
anism) is capable of eliciting truthful participation
secondary schools based on their preferences, with
from all of the participants. Our main purpose is to
priority given to those with higher examination scores
show that the students have very little room to mis-
in the Primary School Leaving Examination (PSLE).
represent their preferences, under either mechanism.
The current matching mechanism is plagued by sev-
While the strategic issues facing the students under
eral problems. We argue that a satisfactory resolu-
the students-optimal mechanism are well understood,
tion of these problems necessitates the use of a stable
the insights under the schools-optimal mechanism
Management Science © 2001 INFORMS
0025-1909/01/4709/1252$5.00
Vol. 47, No. 9, September 2001 pp. 1252–1267
1526-5501 electronic ISSN
TEO, SETHURAMAN, AND TAN
Gale-Shapley Stable Marriage Problem Revisited
appear to be new. The most suitable stable match-
be complete, and no one is to be declared as unac-
ing mechanism for the Singapore Posting Exercise
ceptable. A matching is just a one-to-one mapping
will ultimately be a variant of these two well-known
between the two sexes such that a man m is mapped
matching mechanisms, as local issues and features
to a woman w if and only if w is mapped to m,
have to be incorporated. However, our results on sim-
and m and w are acceptable to each other. (In the
ulation experiments under the students-optimal and
economics literature, this is defined as an individually
schools-optimal mechanisms suggest that, regardless
rational matching.) A matching
is said to be unstable
of the choice of the stable matching mechanism, the
(under either model) if there is a man-woman pair,
students have little incentive to misrepresent their
who both prefer each other to their partners in
; this
preferences. This addresses one of the major concerns
pair is said to block the matching
, and is called
of the participants in the Singapore Posting Exercise.
a blocking pair for
. A stable matching is a match-
A distinguishing feature of our model is that the
ing that is not unstable. The significance of stability
participants are required to submit complete preference
is best highlighted by a system where acceptance of
lists. Strategic issues in the stable marriage problem
the proposed matching is voluntary. In such a setting,
have been explored in settings that allow incomplete
an unstable matching cannot be expected to remain
preference lists; but, to the best of our knowledge,
intact, as the blocking pair(s) may discover that they
no systematic study has been made when complete
could both improve their match by joint action: The
preference lists are required. As we shall see, such a
man and woman involved in a blocking pair could
requirement imposes a severe restriction on the strate-
just “divorce” their respective partners and “elope.”
gic choices available to the participants, resulting in
In addition to formulating several versions of the
substantially reduced incentives to cheat. To study the
stable matching problem, Gale and Shapley (1962)
immunity of the schools-optimal mechanism to cheat-
described a simple algorithm that always finds a sta-
ing by the students, we need to first determine the
ble matching for any instance of the stable marriage
optimal cheating strategy in the classical stable mar-
problem. This elegant result sparked the interest of
riage model where the participants are only allowed
many researchers, resulting in a thorough investiga-
to cheat by reversing the true preference order of
tion of the structural properties of the stable mar-
acceptable partners; They are not allowed to truncate
riage model. A property that is especially relevant to
the preference list, as is the case usually considered
our study is that the set of all stable matchings for
in the literature. The main result of this paper shows
an instance of the stable marriage problem forms a
that this problem can be solved in polynomial time,
lattice, with the extremal elements being the so-called
using a simple extension of the classical Gale-Shapley
“men-optimal” and “women-optimal” stable match-
algorithm.
ings. In fact, the algorithm of Gale and Shapley (1962)
Preliminaries. Stable matching problems were first
that established the existence of a stable marriage con-
studied by Gale and Shapley (1962). In a stable mar-
structs a men-optimal stable matching. This algorithm
riage problem there are two finite sets of participants:
is commonly known as the men-propose algorithm
the set of men (M) and the set of women (W ). We
because it can be expressed as a sequence of “pro-
assume that every member of each sex has strict pref-
posals” from the men to the women. Note that the
erences over the members of the opposite sex. In the
Gale-Shapley algorithm can be easily adapted to yield
model that allows rejection, the preference list of a
a women-optimal stable matching by simply inter-
participant can be “truncated” in the sense that par-
changing the roles of men and women; this is com-
ticipants have the option of declaring some others
monly called the women-propose algorithm. All of the
as unacceptable; in this model, we also include the
results in this paper will be stated under the assump-
possibility that a participant may be unmatched, i.e.,
tion that the men-optimal stable matching mechanism
the participant’s assigned partner in the matching is
is used; by interchanging the role of men and women,
himself/herself. In contrast, in the Gale-Shapley model,
analogous results can be derived for the women-
the preference lists of the participants are required to
optimal mechanism.
Management Science/Vol. 47, No. 9, September 2001
1253
TEO, SETHURAMAN, AND TAN
Gale-Shapley Stable Marriage Problem Revisited
Strategy. Consider a market in which men and
choices, and the ministry pads each list by ranking
women submit their preference lists to a centralized
the remaining schools using location as the only cri-
agency that matches the participants by computing
terion (schools close to the student’s home are ranked
the men-optimal stable matching. An important dif-
higher). All assignments are done in a centralized
ficulty that arises is that this matching mechanism is
manner, and no student is allowed to approach the
manipulable by the women: Some women can inten-
schools privately for admission purposes.
tionally submit false preferences and obtain better
However, such passive roles for the schools
partners. Such (strategic) questions have been stud-
will change in the near future. In preparation
ied for the stable marriage problem by mathemati-
for a knowledge-based economy, the ministry has
cal economists and game theorists, with the goal of
reiterated its intention to shift from the current
quantifying the potential gains of a deceitful par-
examination-oriented system to one that focuses on
ticipant. An early result in this direction is due to
ability-driven education. In line with this goal, the
Roth (1982), who proved that when the men-optimal
ministry intends to give the schools administrative
mechanism is used, none of the men benefits by
and professional autonomy. Student assessments will
submitting false preferences, regardless of how the
also be reviewed to meet the objective of develop-
other participants report their preferences. By sub-
ing creative independent learners. The new university
mitting a false preference list, a man can, at best,
admissions system to be implemented from 2003 will
obtain his (true) optimum stable partner, which he
not rely solely on the GCE A-level exam results,
obtains anyway by submitting his true preference list.
but instead make a holistic evaluation of a student’s
In game-theoretic parlance, stating true preferences
potential. The current assignment process of students
is a dominant strategy for the men. However, Gale
to schools is not consistent with this new focus of
and Sotomayor (1985b) showed that the women can
the ministry. Furthermore, the design of the current
still force the men-optimal mechanism to return the
assignment process has also given rise to several
women-optimal solution. The optimal cheating strat-
operational problems (see §4), and our purpose is to
egy in this case is simple: Each woman w submits a
argue that a centralized stable matching mechanism
preference list that is the same as her true preference
of the type proposed by Gale and Shapley is supe-
list, except that she declares men who rank below her
rior. Our goal, in the end, is to convince the read-
women-optimal partner as unacceptable. Our main
ers that regardless of whether the students-optimal or
goal in this paper is to study the analogous question
schools-optimal mechanism is used, there is no sig-
in the Gale-Shapley model, in which all the partici-
nificant incentive for the students or the schools to
pants are required to submit complete preference lists.
strategize and exploit the system.
We emphasize that we consider only a centralized
There is an obvious relation between the MOE
problem and the stable marriage problem introduced
market that computes the men-optimal matching, and
earlier: In the MOE problem, the students play the
all the men and women can only manipulate the out-
role of “women” and the secondary schools play the
come by permuting their preference lists. We do not
role of “men.” Observe that there is also a crucial dif-
consider a decentralized market, where manipulation
ference: In the MOE problem, many “women” (stu-
possibilities are richer, nor do we consider other ways
dents) can be assigned to the same “man” (secondary
of manipulating the outcome.
school), whereas in the stable marriage model we
Motivation. The motivation for studying strategic
require that the matching be one-to-one. Since the
questions in the Gale-Shapley model is the Singapore
students (schools) in this setting are not allowed
school admissions problem (referred to hereafter as
to declare any school (student) as unacceptable, the
the MOE (Ministry of Education) problem) briefly
MOE problem can be modeled as a many-to-one
described earlier. Currently, the schools are merely
matching problem with complete preference lists.
seen as resources by the ministry to be allocated
The issues of strategic manipulation in the sta-
to students. Furthermore, for ease of implementa-
ble marriage model with rejection are well under-
tion, each student is only allowed to submit six
stood (cf. Roth and Sotomayor 1991 and the references
1254
Management Science/Vol. 47, No. 9, September 2001
TEO, SETHURAMAN, AND TAN
Gale-Shapley Stable Marriage Problem Revisited
therein). However, little is known in the case of
Roth and Rothblum (1999). In a centralized many-to-
stable marriage models (one-to-one and many-to-
one market (with rejection allowed) operating under
one) without rejection, which, as we discussed, is
the schools-optimal mechanism, Roth and Rothblum
a more suitable representation of the MOE prob-
consider the strategic issues facing the students. In a
lem; a notable exception is the recent work of
low information environment, where preferences of
Tadenuma and Toda (1998), in which they consider
the other participants are not known with certainty,
the implementation question, and show that no sta-
they conclude that stating preferences that reverse the
ble matching correspondence can be implemented in
true preference order of two acceptable schools is not
Nash equilibrium as long as M = W > 2. (Stronger
beneficial to the students, while submitting a trunca-
nonimplementability results hold for the rejection
tion of the true preferences may be. Our simulation-
model, see Kara and Sonmez 1996.)
based experimental results in this paper suggest that
this observation is valid even in the perfect informa-
Results and Structure of the Paper. To derive
tion setting, i.e., knowing the reported preferences of
insights into the strategic behavior of the participants
all the other participants may still not allow one to
in the MOE problem, we first consider the one-to-one
benefit from cheating, if one is only allowed to reverse
model, and study the following question: In the sta-
the order of the schools, but not allowed to submit a
ble marriage model with complete preferences, with
truncated list.
the men-optimal mechanism, is there an incentive for
Finally, we note that the strategic issues facing the
the women to cheat? If so, what is an optimal cheat-
schools, under the schools-optimal mechanism, is a
ing strategy for a woman? Can a woman always force
nontrivial problem: Roth (1985) showed that, contrary
the mechanism to return her women-optimal part-
to the one-to-one case, the schools-optimal match-
ner? In §2 we present the main result of this paper:
ing need not even be weakly-Pareto optimal for the
An optimal cheating strategy can be constructed in
schools, and there is no stable matching mechanism
polynomial time. A related issue concerns the robust-
that makes it a dominant strategy for all the schools
ness of the men-optimal mechanism. In the rejection
to state their true preferences. We shall see in §4 why
model, it is well known that the women can easily
this is not an important issue in the MOE problem.
manipulate the men-optimal mechanism, and, in fact,
almost all the women will submit false preferences. In
sharp contrast, our results for the Gale-Shapley model
2.
Optimal Cheating in the
in §3 provide evidence that the men-optimal mecha-
Gale-Shapley Model
nism is fairly robust, and that there is very little incen-
Our standing assumption in this paper is that woman
tive for the women to cheat. In particular, restricting
w is the only deceitful participant and she knows
the strategic choices of the women drastically reduces
the reported preferences of all the other partici-
their benefits from cheating, thereby reducing the pos-
pants, which remain fixed throughout. We shall show,
sibility that a woman will cheat. Armed with this the-
eventually, that cheating opportunities for woman w
oretical understanding of the Gale-Shapley model, we
are uncommon, in spite of the assumption that she
prescribe some recommendations in §4 to improve the
has perfect information. We consider only a central-
current “matching mechanism” used in the Singapore
ized market, although the algorithm is phrased as a
MOE Secondary School Posting Exercise. In particu-
sequence of proposals from the men to the women.
lar, we argue that a stable matching mechanism is
We visualize the deceitful woman as running this
more appropriate for the MOE problem, and that
algorithm in her head and submitting the optimal
some of the other difficulties inherent in the present
cheating strategy thus computed as her preference list
system can be effectively addressed by a stable match-
to the centralized market.
ing mechanism.
We shall begin by considering the following ques-
It is instructive to compare our results to some
tion: Consider a centralized market in which the men-
recent results obtained in a very interesting study by
propose algorithm is literally used to compute the
Management Science/Vol. 47, No. 9, September 2001
1255
TEO, SETHURAMAN, AND TAN
Gale-Shapley Stable Marriage Problem Revisited
men-optimal matching. Suppose woman w has no
preference lists is the women-optimal solution (with
knowledge of the preferences of any of the other partic-
respect to the original preference lists). To prove our
ipants, and that she is the only deceitful participant.
result, however, we have to show that when a woman
Suppose also that she is allowed to reject proposals.
unilaterally declares all the men as unacceptable, this
Is it possible for her to identify her women-optimal
is enough to induce her optimal partner to propose to
partner by just observing the sequence of proposals
her in the course of executing the men-propose algo-
she receives? Somewhat surprisingly, the answer is
rithm. Furthermore, we need to show that no higher-
yes! If w simply rejects all the proposals made to
ranked man on her list will propose to her even after
her, then the best (according to her true preference
she rejects the proposal from her optimal partner.
list) man among those who propose to her is her
Proof of Theorem 1.
Let
w denote the women-
women-optimal partner. Our algorithm for finding the
optimal partner for w. We modify w’s preference list
optimal cheating strategy in the Gale-Shapley model
by inserting the option to remain single in the list,
builds on this insight: Woman w rejects as many pro-
immediately after
w . (We declare all men that are
posals as possible, while remaining engaged to some
inferior to
w as unacceptable to w.) Consequently,
man who proposed earlier in the algorithm. Using a
in the men-propose algorithm, all proposals inferior
backtracking scheme, she uses the matching mecha-
to
w will be rejected. Nevertheless, since there is
nism repeatedly to find her optimal cheating strategy.
a stable matching (with respect to the original prefer-
Given our standing assumption that woman w has
ences) with w matched to
w , our modification does
complete knowledge of the reported preferences of
not destroy this solution, i.e., this solution remains
the other participants, and that she is the only agent
stable with respect to the modified list. It is also
acting strategically, it is clear what she would do: She
well known that in any stable matching instance, the
would run the algorithm to find her optimal cheating
set of people who are single is the same for all sta-
strategy privately and submit this (optimal) prefer-
ble matchings (cf. Roth and Sotomayor 1990, p. 42).
ence list to the centralized market.
Thus, w must be matched in all stable matchings
with respect to the modified preference list. The men-
2.1.
Finding Your Optimal Partner
optimal matching for this modified preference list
We first describe Algorithm OP—an algorithm to
must match w to
w , since
w is now the worst
compute the women-optimal partner for w using the
partner for w with respect to the modified list. In par-
men-propose algorithm. (Recall that we do this under
ticular,
w must have proposed to w during the exe-
the assumption that woman w is allowed to remain
cution of the men-propose algorithm. Note that until
single.)
w proposes to w, the men-propose algorithm for
the modified list runs exactly in the same manner as
Algorithm OP
in Step 1 of OP. The difference is that Step 1 of OP will
1. Run the men-propose algorithm, and reject all
reject the proposal from
w , while the men-propose
proposals made to w. At the end, w and a man, say
algorithm for the modified list will accept the pro-
m, will remain single.
posal from
w , as w prefers
w to being single.
2. Among all the men who proposed to w in Step 1,
Hence, clearly
w is among those who proposed to
let the best man (according to w) be m .
w in Step 1 of OP, and so m ≥w w .
Suppose m >w
w . Consider the modified list in
Theorem 1.
m is the women-optimal partner for w.
which we place the option of remaining single imme-
Remark.
Gale and Sotomayor (1985b) showed that
diately after m . We run the men-propose algorithm
when each woman declares all the men inferior to
with this modified list. Again, until m proposes to w,
her women-optimal partner as unacceptable, then the
the algorithm runs exactly the same as in Step 1 of
men-optimal mechanism will be forced to return
OP, after which the algorithm returns a stable partner
the women-optimal stable matching. This is because
for w who is at least as good as m according to w
the only stable matching solution for the modified
(under both the original and the modified lists, since
1256
Management Science/Vol. 47, No. 9, September 2001
TEO, SETHURAMAN, AND TAN
Gale-Shapley Stable Marriage Problem Revisited
we have not altered the order of the men before m
under the Gale-Shapley model. The reason is that this
on the list). The matching obtained is thus stable with
greedy improvement technique does not allow for the
respect to the original list. This contradicts our ear-
possibility of rejecting the current best partner, in the
lier assumption that
w is the best stable partner
hope that this rejection will trigger a proposal from a
for w.
better would-be partner. Our algorithm in this paper,
Suppose w is allowed to modify her preference list
which is described next, does precisely that. An illus-
after each run of the men-propose algorithm, and the
trative example appears soon after the description of
algorithm is to be repeated until w concludes that
the algorithm.
she has found her best possible partner. Theorem 1
Let P w = m m
m
1
2
n be the true preference
essentially says that knowing the set of proposals
list of woman w, and let P m w be a preference list
woman w receives is enough to allow her to con-
for w so that the men-propose algorithm will return
struct her optimal cheating strategy, if she is allowed
m as her men-optimal partner. In the case that man m
to declare certain men as unacceptable; she need not
cannot be obtained by w as her men-optimal partner
know the preferences of any of the other participants
for any preference list, we set P m w to be the null
involved, as long as they behave truthfully. In the next
list, as a matter of convention. Our algorithm con-
section, we shall use this insight to construct an opti-
structs P m w (if man m is attainable by woman w)
mal cheating algorithm for w, under the additional
or determines whether P m w is the null list (if man
restriction that she is not allowed to declare any man
m is not attainable by woman w) iteratively, and con-
as unacceptable.
sists of the following steps:
1. Run the men-propose algorithm with the true
2.2.
Cheating Your Way to a Better Marriage
preference list P w for woman w. Keep track of all
Observe that the procedure of §2.1 only works when
men who propose to w. Let the men-optimal partner
woman w is allowed to remain single throughout the
for w be m, and let P m w be the true preference
matching process. Suppose the central planner does
list P w .
not give the woman an option to declare any man as
2. Suppose m
unacceptable. How do we determine her best attain-
j proposed to w in the men-propose
algorithm. By moving m
able partner by manipulation? This is essentially a
j to the front of the list
P m w , we obtain a preference list for w such that
restatement of our original question: Who is the best
the new men-optimal partner (after running the men-
stable partner woman w can have when the men-
propose algorithm on this modified list) is m
optimal mechanism is used and when she can lie only
j . Let
P m
by permuting her preference list. Note that the prefer-
j w
be this altered list. We say that mj is a
ences of the remaining participants (except woman w)
potential partner for w.
are fixed throughout.
3. Repeat Step 2 to obtain a preference list for every
A natural extension of Algorithm OP is for woman
man (other than m) who proposed to woman w in the
w to: (i) accept a proposal first, and then reject
algorithm; after this, we say that we have exhausted
all future proposals; (ii) from the list of men who
man m, the men-optimal partner obtained with the
proposed to her but were rejected, find her most
preference list P m w . All potential partners of w
preferred partner; repeat the men-propose algorithm
that come from running the men-propose algorithm
until the stage when this man proposes to her;
using the list P m w have been found.
(iii) reverse the earlier decision and accept the pro-
4. If a potential partner for w, say man u, has not
posal from this most preferred partner, and continue
been exhausted, run the men-propose algorithm with
the men-propose algorithm by rejecting all future
P u w as the preference list of w. Identify new poten-
proposals; and (iv) repeat (ii) and (iii) until w can-
tial partners. Repeat Steps 2–3 with u in place of m.
not obtain a better partner from all other proposals.
5. Repeat Step 4 until all potential partners of w are
Unfortunately, this simple strategy does not always
exhausted. Let N denote the set of all potential (and
yield the best stable partner a woman can achieve
hence exhausted) partners for w.
Management Science/Vol. 47, No. 9, September 2001
1257
TEO, SETHURAMAN, AND TAN
Gale-Shapley Stable Marriage Problem Revisited
6. Among the men in N let ma be the man woman
exhausted after this. No new potential partner is
w prefers most. Then P ma w is an optimal cheating
found, and so the algorithm terminates.
strategy for w.
Remark.
Example 1 shows that woman 1 could
The men in the set N at the end of the algorithm
cheat and get a partner better than her men-optimal
have the following crucial properties:
partner. However, her women-optimal partner in this
• For each man m in N , there is an associated pref-
case turns out to be Man 1. Hence Example 1 also
erence list for w such that the men-propose algorithm
shows that Woman 1 cannot always assure herself
returns m as the men-optimal partner for w with this
of her women-optimal partner through cheating, in
list.
contrast to the case when rejection is allowed in the
• All other proposals in the course of the men-
cheating strategy.
propose algorithm come from other men in N . (Oth-
We conclude this section by stating and proving the
erwise, there will be some potential partners who are
main result. Recall that ma is the best man according
not exhausted.)
to w’s true preference list among the men in set N
With each run of the men-propose algorithm, we
constructed by the algorithm.
exhaust a potential partner, and so this algorithm
executes at most n men-propose algorithms before
Theorem 2.
= P ma w is an optimal strategy for
termination.
woman w.
Example 1.
Consider the following stable marriage
Proof (by contradiction).
We use the convention
problem:
that r m = k if man m is the kth man on woman
1 2 3 4 5 1
1 1 2 3 5 4
w’s true preference list. Let ∗ = mp m
m
1
p2
pn
2 3 4 5 1 2
2 2 1 4 5 3
be a preference list that gives w her best stable part-
3 5 1 4 2 3
3 3 2 5 1 4
ner when the men-optimal mechanism is used. Let
4 3 1 2 4 5
4 4 5 1 2 3
this man be denoted by mpb, and let woman w strictly
5 1 5 2 3 4
5 5 1 2 3 4
prefer mpb to ma (under her true preference list), i.e.,
True Preferences of
True Preferences of
r mpb < r ma . Observe that the order of the men
the Men
the Women
who do not propose to woman w is irrelevant and
does not affect the outcome of the men-propose algo-
We construct the optimal cheating strategy for
rithm. Furthermore, men of rank higher than r m
Woman 1 using the algorithm described earlier.
pb
do not get to propose to w, otherwise we can cheat
Step 1 Run the men-propose algorithm with the
true preference list for Woman 1; her men-optimal
further and improve on the best partner for w, con-
partner is Man 5. Man 4 is the only other man who
tradicting the optimality of
∗. Thus we can arbitrar-
proposes to her during the men-propose algorithm.
ily alter the order of these men, without affecting the
So P(Man 5, Woman 1) = 1 2 3 5 4 .
outcome. Without loss of generality, we may assume
Steps 2–3
Man 4 is moved to the head of
that 1 = r mp < 2 = r m
< · · · < b = r m
1
p2
pb . Since
Woman 1’s preference list; i.e., P(Man 4, Woman 1)
r mpb < r ma ma will appear somewhere after mpb
= 4 1 2 3 5 . Man 5 is exhausted, and Man 4 is a
in
∗: thus, ma can be any of the men in the list
potential partner.
mp b+ m
m
1
p b+2
pn.
Step 4 As Man 4 is not yet exhausted, we run the
Now, we modify
∗ such that all men who (numer-
men-propose algorithm with P(Man 4, Woman 1) as
ically) rank lower than ma but higher than mpb
the preference list for Woman 1. Man 3 is identified
(under true preferences) are put in order accord-
as a new possible partner, with P(Man 3, Woman 1) =
ing to their ranks. This is accomplished by moving
3 4 1 2 5 . Man 4 is exhausted after this.
all these men before ma in
∗. With that alteration,
Repeat Step 4 As Man 3 is not yet exhausted, we run
we obtain a new list ˜ = mq m
m
1
q2
qn
such
the men-propose algorithm with P(Man 3, Woman 1)
that:
as the preference list for Woman 1. Man 3 will be
(i) 1 = r mq < 2 = r m
< · · · < s = r m
1
q2
qs .
1258
Management Science/Vol. 47, No. 9, September 2001
TEO, SETHURAMAN, AND TAN
Gale-Shapley Stable Marriage Problem Revisited
(ii) mq = m
m
1
p1
qb = mpb, where the position
3.
Strategic Issues in the
of
those
men
who
rank
higher
than
mpb is
Gale-Shapley Problem
unchanged.
By requiring the women to submit complete pref-
(iii) r ma = s + 1 ma ∈ mq s+ m
m
1
q s+2
qn .
erence lists, we are clearly restricting their strategic
(iv) The men in the set
mq s+ m
m
1
q s+2
qn
options; thus many of the strong structural results
retain their relative position with respect to one
known for the rejection model may not hold for the
another under
∗.
Gale-Shapley model. This is good news, for it reduces
Note that the men-optimal partner of w under ˜
the incentive for a woman to cheat. In this section, we
cannot come from the set mq s+ m
m
1
q s+2
qn .
present several examples to show that the strategic
Otherwise, since the set of men who proposed
behavior of the women can be very different under
in the course of the algorithm must come from
the models with and without rejection.
mq s+ m
m
1
q s+2
qn , and since the preference list
∗ retains the relative order of the men in this
3.1.
The Best Man (Obtained by Cheating)
set, the same partner would be obtained under
∗.
May Not Be Women-Optimal
This leads to a contradiction as
∗ is supposed to
In the two-sided matching model with rejection, it is
return a better partner for w. Hence, we can see
not difficult to see that the women can always force
that under ˜ , we already get a better partner than
the men-optimal mechanism to return the women-
under
.
optimal solution (for instance, each woman declares
Now, since the preference list
returns ma with
as unacceptable those men who are inferior to her true
r ma = s + 1, we may conclude that the set N
women-optimal partner). In the Gale-Shapley model,
(obtained from the final stage of the algorithm)
which forbids rejection, the influence of the women
does not contain any man of rank lower than
is far less, even if they collude. A simple example is
s + 1. Thus N ⊆ mq s+ m
m
1
q s+2
qn . Suppose
when each woman is ranked first by exactly one man.
mq s+ m
m
1
q s+2
qw do not belong to the set N ,
In this case, there is no “conflict” among the men,
and mq w+ is the first man after m
1
qs who belongs to
and in the men-optimal solution, each man is matched
the set N . By construction of N , there exists a per-
to the woman he ranks first. In this case, the algo-
mutation ˆ with mq w+ as the stable partner for w
1
rithm will terminate with the men-optimal matching,
under the men-optimal mechanism. Furthermore, all
regardless of how the women rank the men in their
of those who propose to w in the course of the
lists. So ruling out the strategic option of remaining
algorithm are in N , and hence they are no better
single for the women significantly affects their ability
than ma to w. Furthermore, all proposals come from
to change the outcome of the game by cheating.
men in mq w+ m
m
,
1
q w+2
qn , since N ⊆ mq s+1
By repeating the above analysis for all the other
mq s+
m
2
qn .
women in Example 1, we conclude that, by cheating
By altering the order of those who did not pro-
unilaterally, the best possible partners for Women 1,
pose to w, we may assume that ˆ takes the follow-
2, 3, 4, and 5 are, respectively, Men 3, 1, 2, 4, and 3.
ing form: mq m
m
m
1
q2
q s−1
qs
mqw mq w+1
An interesting observation is that Woman 5 cannot
, where the first qw + 1 men in the list are identi-
benefit by cheating alone (she can only get her men-
cal to those in ˜ . But, the men-optimal stable solution
optimal partner no matter how she cheats). However,
obtained using ˆ must also be stable under ˜ , since
if Woman 1 cheats using the preference list (3, 4, 1,
w is match to mq w+ , and the set of men she strictly
1
2, 5), Woman 5 will also benefit by being matched to
prefers to mq w+ is identical in both ˆ and ˜ . This
1
Man 5, who is first in her list.
is a contradiction as ˜ is supposed to return a men-
optimal solution better than ma.
3.2.
Does Cheating Pay?
This implies that
∗ does not exist, and so
is opti-
Roth (1982) shows that under the men-optimal mech-
mum and ma is the best stable partner w can get by
anism, the men have no incentive to alter their true
permuting her preference list.
preference lists. In the rejection model, however, Gale
Management Science/Vol. 47, No. 9, September 2001
1259
TEO, SETHURAMAN, AND TAN
Gale-Shapley Stable Marriage Problem Revisited
and Sotomayor (1985a) show that a woman has an
represents the men-optimal and women-optimal part-
incentive to cheat as long as she has at least two dis-
ners of each participant. For instance, Man 1 and
tinct stable partners. From Pittel (1989), we know that
Woman 1 have preference lists “64782351” (i.e., Man 1
the average number of stable matchings is asymptot-
prefers Woman 6 to Woman 4 to Woman 7, etc., and
ically n log n /e, and with high probability, the rank
similarly Woman 1 prefers Man 6 to Man 4 to Man 7,
of the women-optimal and men-optimal partners for
etc.). Under the men-optimal mechanism, Man 1 is
the women are, respectively, log n and n/ log n .
matched to Woman 6, and Woman 1 is matched to
Thus, in typical instances of the stable marriage game
Man 7. Thus the women-optimal partner for Woman 1
under the rejection model, most of the women will
is Man 6 (from symmetry), and so she has an incen-
not reveal their true preferences.
tive to lie about her preferences. In fact, this exam-
Many researchers have argued that the troubling
ple shows that 6 out of the 8 women benefit from
implications from these studies are not relevant in
cheating in the rejection model. The situation for the
practice, as the model assumes that the women have
Gale-Shapley model is very different: given that the
complete knowledge of all the other participants, as
women can only misrepresent their preferences by
well as their preference lists. For the Gale-Shapley
order reversals, no woman can benefit from cheating.
model we consider, it is natural to ask whether it
We ran the algorithm on 1,000 instances, with pref-
pays (as in the rejection model) for a typical woman
erences of each individual generated uniformly at
to solicit information about the preferences of the
random, for n = 8. The number of women who benefit
remaining participants in the game.
from cheating is tabulated in Table 1.
Example 2.
We have designed a Visual Basic pack-
Interestingly, the number of women who benefit
age for the stable marriage problem with complete
from cheating is surprisingly low. In fact, in 74%
preference lists. The following example, in one of the
of the instances, the men-optimal solution is their
simulation experiments, illustrates the dramatic dif-
only option, no matter how they cheat. The average
ference in the behavior of the women in the models
percentage of women who benefit from cheating is
with and without rejection:
merely 5.06.
In the example, the men and women are labelled
To look at the typical strategic behavior on larger
from 1 to 8. Both man i and woman i have identical
instances of the stable marriage problem, we ran the
preference lists. The number next to the list in Figure 1
heuristic on 1,000 random instances for n = 100. The
cumulative plot is shown in Figure 2. In particular,
in more than 60% of the instances at most 10 women
Figure 1
Stable Marriage Model with Rejection Versus One Without
(out of 100) benefited from cheating, and in more than
Rejection
96% of the instances at most 20 women benefited from
cheating. The average number of women who bene-
fited from cheating is 9.515%. Thus, the chances that
a typical woman can benefit from acquiring perfect
information (i.e., knowing the preferences of the other
participants) is slim in the Gale-Shapley model.
We have performed similar experiments for large
instances of the Gale-Shapley model. Because of com-
putational requirements, we can only run the exper-
iment on 100 random instances of the problem with
Table 1
Number of women who benefited
0
1
2
3
4 5 6 7 8
Number of observations
740 151 82 19 7 1 0 0 0
1260
Management Science/Vol. 47, No. 9, September 2001
TEO, SETHURAMAN, AND TAN
Gale-Shapley Stable Marriage Problem Revisited
Figure 2
Benefits of Cheating
500 men and women. The insights obtained from the
solution is more appropriate, and how some of the
100 by 100 cases carry over: the number of women
problems under the current system can be addressed
who benefit from cheating is again not more than 10%
using a stable matching mechanism.
of the total number of the women involved. In fact,
the average was close to 6% of the women popula-
4.1.
Current Assignment Process
tion in the problem. This suggests that the number
Prior to taking their Primary School Leaving Exam-
of women who benefit from cheating in the Gale-
ination (PSLE), the students are required to submit
Shapley model with n women grows at a rate slower
(around August) their rank ordering of schools to
than a linear function of n. A detailed probabilistic
the MOE, which oversees the posting exercise. In the
analysis of this phenomenon is a challenging problem,
option form, each student is required to list six sec-
which we leave for future research.
ondary schools she would like to attend, in order of
decreasing desirability. The students (rather, their par-
4.
Singapore MOE Posting Exercise
ents) are advised by the MOE to make realistic choices
The admission to secondary schools in Singapore is
because the preference list, once submitted, cannot
centrally controlled. A distinguishing feature of the
be changed. After the PSLE results are announced,
Singapore school admissions problem (MOE problem)
the top ten percent performers are given a second
is that the students are not allowed to remain unas-
option to indicate their preferences for the Indepen-
signed at the end of the posting exercise, and that the
dent schools and the Special Assistance Plan (SAP)
schools are not allowed to reject any students if there
schools. These are the elite schools in Singapore that
are still places available. In what follows, we first
admit only the top students.
present a summary of the current matching mecha-
The posting of students to secondary schools is
nism, along with a brief description of its shortcom-
(partially) computerized. All students are ranked
ings in §4.1. In §4.2, we explain why a stable matching
according to their aggregate PSLE scores regardless of
Management Science/Vol. 47, No. 9, September 2001
1261
TEO, SETHURAMAN, AND TAN
Gale-Shapley Stable Marriage Problem Revisited
their choices. Currently, the assignment of students to
release of the PSLE scores. Knowing that many good
schools is conducted in multiple phases, which are as
students will be applying to the good schools, parents
follows:
cannot afford to reveal their true preferences. If they
Phase 1
Consider the top students who have
were to list down just the ideal top six schools as their
applied to the independent schools in the second
six choices, they run the risk of being rejected by all
option, and assign them to these schools.
these six schools—this happens if their child performs
Phase 2
Consider the top students who have
below their expectations in the PSLE and fails to qual-
applied to SAP schools in the second option, and
ify for these schools. Worse, this may actually result
assign them to SAP schools.
in their child getting into a school that is completely
Phase 3 For historical and administrative reasons,
out of their consideration, as manual posting would
certain secondary schools have affiliated primary
then be carried out. The parents are thus forced to be
schools. This is to foster closer collaboration between
more “realistic” when choosing the schools for their
the primary and secondary schools. Students who
child. Consequently, the parents are faced with the
opt to go to the affiliated secondary schools will
difficult problem of optimally utilizing the six options
be given higher priority. Consider all students who
provided by the MOE.
have selected their affiliated secondary school as their
The MOE has tried to simplify matters for the par-
top choice, and assign them to the affiliated schools
ents by providing them with information such as the
(subject to availability of places).
schools’ cut-off points for the previous year to help
Phase 4 Consider the remaining students one by
them make rational decisions. In recent years, the
one, and match them to the schools according to the
MOE has also provided a rating of all the schools in
choices they made in August.
Singapore so that the parents will be better informed
Note that in the process of assigning the students
of the schools’ strengths and weaknesses. However,
to schools, a student who ranks his affiliated sec-
this still does not address the parents’ major concern
ondary school as his first choice is given priority for
in formulating their choices: they have to submit their
that school. In this way, the current assignment pro-
choices before their children take the examination! In
cess has managed to incorporate some of the schools’
fact, one parent lamented on a national newspaper:
selection criterion, which actually place more impor-
“How do we choose when we do not know how they
tance on “affiliation” than on performance in the
will do at the national level?” (The Straits Times, 17
PSLE; not all students, however, can gain admis-
August 1996). A good matching mechanism should allow
sion to their affiliated secondary schools because such
admissions are subject to vacancies in these schools.
the students to submit their true ranking list, without the
When a student fails to get admission to any of
need to strategize based on their PSLE results.
the schools of her choice, she is assigned (manually)
We note that it is not possible for the Ministry
to a school (in nearby postal districts) that still has
to solicit the students’ options after the release of
vacancies. If there is no such school available, the
the examination results, due to the tight time span
student is assigned (manually) to a school in some
between the release of results and the start of the new
other postal district that still has vacancies. The stu-
school term.
dents are notified of the schools they are assigned
Problem 2 Another problem with the current assign-
to by late December, just in time for the new school
ment process is that other than affiliation, the gen-
semester, which starts early January. The current sys-
uine preferences of the schools are not considered.
tem is plagued with several problems, some of which
The schools have to accept the students assigned
are as follows.
to them under the process. Furthermore, the num-
Problem 1 Decision making by the parents is com-
ber of places available in the school is also largely
plicated by the fact that (i) parents are only given
determined by the MOE. To attract the desired stu-
limited options to express their preferences, and
dents, many schools, especially the newer ones, resort
(ii) parents have to make their decisions prior to the
to advertising campaigns such as organizing open
1262
Management Science/Vol. 47, No. 9, September 2001
TEO, SETHURAMAN, AND TAN
Gale-Shapley Stable Marriage Problem Revisited
houses, sending brochures to parents, and conduct-
Although a substantial number (30%) of respon-
ing talks at primary schools. Though such market-
dents think that distance to school is important, and
ing efforts help, schools still depend significantly on
hence they have no reason to worry about this cri-
the ST School 100 ranking (provided by the MOE)
terion under the current assignment process, it is
to attract their desired students. However, since the
interesting to note that 70% of respondents do not
ST ranking is decided mainly by the schools’ per-
consider distance to school as an important factor in
formance in the GCE “O”-level examination, over-
their ranking of schools. The current system are not
reliance on the ranking could induce the schools to
able to cater to these people in its assignment. A good
overemphasize the importance of academic results.
assignment process should match all students to schools
This is clearly an undesirable repercussion as it actu-
according to the true preferences of the students.
ally impedes the Singapore government from achiev-
Problem 4 Finally, since the examination results are
ing the “Thinking Schools, Learning Nation” vision.
released only in late November, the MOE can only
A good matching mechanism should allow the schools to
obtain the second option form not earlier than early
rank the students using different criteria, depending on
December. As such, the entire assignment process is
the strength and areas of excellence the schools wish to
conducted only in a span of two weeks as the assign-
emphasize.
ments have to be made known to the students by
Problem 3 A third problem lies in the logic of the
the third week of December. An unfortunate event
current assignment process at Phase 4 of the exercise.
developed in December 1997 when the Ministry had
When all the six choices are exhausted, the students
to publicly apologize for an administrative error:
are then assigned to schools in nearby postal districts.
It has been discovered that there were some dis-
However, according to a 1992 survey (The Straits
crepancies in the posting of pupils within the Nor-
Times, 19 August 1992), only 30% of the respondents
mal (academic) course; 3,278 pupils out of a total of
think that the distance to school is an important factor
9,417 are affected. The ministry is re-posting the 3,278
in their selection of schools. While this is a nonnegli-
pupils (The Straits Times, December 1997).
gible fraction of the respondents, it is distressing that
The ministry apologized for the error and said that
several other factors, considered more important by the
the error occurred when wrong data was entered
respondents, were completely ignored in the current
into its computers during the assignment process. The
assignment process. The major factors identified in
human error was discovered only when “the min-
the survey are:
istry checked again and the parents gave feedback.”
Average Score
This ultimately led to some resentment and confu-
Which Factors Matter Most
(out of 10)
sion among the students and parents, as some of them
had already bought the books and met the teachers in
Quality of O-level passes
7 5
Percentage of O-level passes
7 4
their previously assigned secondary school. The fact
Entry cut-off points
6 6
that the re-assignment was made barely a week before
Value-added
6 6
the commencement of the new school term aggra-
Percentage of students accepted
6 1
vated the seriousness of the human errors. As far as
ECA performance
4 9
possible, the matching mechanism should be fully auto-
mated to mitigate the chances of human errors and reduce
Other factors considered
Percentage of
the time taken to post students to schools.
very important
decision makers
Quality of teachers
88%
4.2.
Benefits of Stable Matching Mechanisms
School discipline
82%
The current posting method is appropriate for the old
Quality of principal
58%
paradigm in which the schools are all alike and, thus,
School reputation
50%
Range of school facilities
35%
are viewed as resources to be allocated to the stu-
Distance from school
30%
dents. Also, assigning the students to schools accord-
Friends in the school
30%
ing to merit is a simple and convenient way to solve
Management Science/Vol. 47, No. 9, September 2001
1263
TEO, SETHURAMAN, AND TAN
Gale-Shapley Stable Marriage Problem Revisited
the matching problem. However, in recent years, this
the MOE to prevent the schools from misrepresenting
problem has assumed a new dimension as it is gen-
their preferences. For instance, by working with the
erally recognized that examination results alone are
schools to determine their strengths and core compe-
not a good way of assessing the merit of the students.
tence, the MOE can specify the profile of the prospec-
Thus, elaborate mechanisms are now being put in
tive students that would fit into the schools’ curricu-
place to assess the students in an all-round fashion. In
lum. This can be used to rank the students according
the future, it will no longer be possible to have a sin-
to the various criteria listed down by the schools. This
gle list that ranks all the students according to merit.
eliminates the need for the schools to submit a rank-
Also, given that the schools are being encouraged to
ing list of individual students, thus giving them less
develop their own identity and strength, it is highly
scope for strategic manipulation.
debatable whether the schools will all rank the stu-
Schools-Optimal Mechanism. As in the case of the
dents in the same way. Currently, besides affiliation,
students-optimal matching mechanism, the danger of
the assignment process cannot handle school-specific
schools manipulating the assignment process can be
criteria. By moving to a new paradigm in which
eliminated by appropriate management control. Note
schools are allowed to devise their own criteria to
that even with the schools-optimal mechanism, it is
rank the students, and assigning the students to
known that truth revelation is not a dominant strategy
schools via a stable matching mechanism, we can
for the schools, and so proper management control is
address some of the problems outlined in §4.1. Under
still required to ensure that the schools do not mis-
this new mechanism, the limit on the number of
represent their preferences. However, it is still possi-
choices each student is entitled to should be removed,
ble that some of the students will benefit from lying.
since this is one of the root causes for the problems
In the rest of this section, we examine the extent to
faced by the students in the current system. Although
which the students benefit by misrepresenting their
this will lead to an additional burden on the sys-
preferences. We use the algorithm described in §2.2 to
tem (data collection and processing), the benefits that
obtain some insights into this problem.
accrue will be well worth the effort.
We designed an experiment with n = 60 students,
With these changes, we can have a fully automated
and k schools each with 60/k places, for k = 1,
matching mechanism that can capture the true pref-
3 5 10 20. The preferences of the schools and the
erences of the students, and allow the schools to turn
students are generated randomly in the many-to-one
from passive to active participants in the assignment
model. We then convert the problem into a one-to-one
process. This immediately addresses Problems 2–4
model, with each school represented as k individuals
outlined in §4.1. We argue next that in a stable match-
in the new model. All individuals corresponding to
ing mechanism implementation, it is unlikely that the
the same school will have identical preference lists.
students will benefit significantly from misrepresent-
Also, for the students in the new model, the prefer-
ing their preference lists. In particular, we analyze
ence list is generated so that the individuals corre-
the strategic issues under the students-optimal and
sponding to the same school are clustered together in
schools-optimal mechanisms.
the students’ preference list, capturing the fact that
Students-Optimal Mechanism. It follows from
in the many-to-one model, the students basically pro-
classical results in stable matching (cf. Roth 1982)
vide the preference lists for the schools only. In this
that, in this model, the students have no incentive to
new one-to-one model (where students correspond to
misrepresent their preferences. However, the strategic
women and schools correspond to men), the prefer-
behavior of the schools is not well understood. In fact,
ence lists are thus generated in a special manner. We
to the best of our knowledge, the question of finding
next report the extent to which the women (i.e., stu-
the optimal cheating strategy for the schools is still
dents) can cheat in this new one-to-one model, under
open and appears to be a difficult problem. For the
the men-optimal mechanism. Note that the number of
MOE problem, however, this is less of a concern, since
women who can benefit by cheating in this case is not
proper management mechanisms can be instituted by
directly equivalent to the number of students who can
1264
Management Science/Vol. 47, No. 9, September 2001
TEO, SETHURAMAN, AND TAN
Gale-Shapley Stable Marriage Problem Revisited
benefit by cheating in the many-to-one model, since
5.
Concluding Remarks
the one-to-one problem contains artificial strict pref-
Our study here focused on two main areas: In the
erences over slots of the same school. Nevertheless,
first part, we studied the theoretical aspects of the
the numbers reported consititue an upperbound on
stable marriage problem. Specifically, we addressed
the number of students who can benefit by cheating
the strategic issues in the Gale-Shapley model (i.e.,
in the many-to-one model.
a one-to-one matching model in which each partic-
For each set of parameters, we ran 1,000 experi-
ipant submits complete preference lists)—very little
ments. The following table shows the average number
was known about the strategic issues for this model
of women who benefited by cheating.
prior to our work. Assuming that the men-optimal
mechanism is used, we derived an optimal cheating
k
1
3
5
10
20
strategy for the women. We also showed that the
Percentage of
strategic behavior of the women can be very different
women who benefit
by cheating
8.77 11.00 11.09 10.22 4.675
under the models with and without rejection. We saw
that in our model, an optimal cheating strategy for a
The cumulative distribution of the number of
woman did not always guarantee her women-optimal
women who benefited by cheating is shown in
partner. Moreover, in sharp contrast to the rejection
Figure 3.
model, we showed that the chances of a woman ben-
For each value of k, the y axis shows the cumula-
efitting by cheating are small.
tive number of women who can benefit from cheat-
The second part of our study emphasized the
ing. For instance, for k = 1, in close to 900 out of 1,000
importance of adopting stable matching mechanisms
experiments, at least one woman benefits from cheat-
in the context of the Singapore Secondary School post-
ing. Note that in the many-to-one model with only
ing exercise. There is an enormous amount of litera-
one school, clearly the students cannot benefit from
ture on the college admissions problem, which sheds
cheating. This number drops to slightly over 800 for
light on the viability of the matching mechanisms
k = 3, slightly over 700 for k = 5, slightly over 500 for
we proposed. For instance, a variant of the student-
k = 10, and finally to around 200 for k = 20. Interest-
propose mechanism suggested here has recently been
recommended to be the official posting method to
ingly, the number of times that no women benefit by
assign interns to hospitals in the United States (Roth
cheating (i.e., optimal strategy is for all the women to
and Peranson 1997). The high participation rate in this
tell the truth) seems to increase as k increases (From
interns/hospitals market, despite the fact that partic-
100 for k = 1 to 800 for k = 20). Translated to the
ipation is voluntary, shows the relevance and impor-
many-to-one model, it indicates that, for instance, in
tance of ensuring stability. For the Singapore posting
the case k = 20 (i.e. 20 schools and 60 students), the
exercise, however, participation rate is not the cen-
chances that no students can benefit from cheating
tral theme of the problem, since the students do not
is at least 80%. It indicates that if there are relatively
have a choice in participation. Interestingly, exploiting
many schools in the many-to-one model compared
this unique feature of the problem (that the student
to the total number of students, cheating becomes
cannot say “no”), we showed that a stable match-
increasingly impossible.
ing mechanism is still appropriate in this context.
The simulation experiments also showed a interest-
The current assignment process used by the MOE
ing feature: The proportion of women who can benefit
seems to place undue emphasis on the parents mak-
from cheating hovers around 10% for all choices of
ing intelligent, “realistic” choices; this is troublesome
k, even though the preference lists are generated in
for the parents, especially because they have to make
a special manner. The numbers are similar to those
their decisions before their children appear for the
in the earlier experiment when the preference lists
primary school leaving examination. We argued that
for the one-to-one model are generated in a random
adopting a stable matching mechanism results in a
fashion.
better system. We showed further that regardless of
Management Science/Vol. 47, No. 9, September 2001
1265
TEO, SETHURAMAN, AND TAN
Gale-Shapley Stable Marriage Problem Revisited
Figure 3
Cheating in the Many-to-One Model
the particular stable matching mechanism used (the
To summarize, our analysis of the strategic issues
students-optimal or the schools-optimal mechanism),
suggests that stable matching mechanisms can be
there is no significant incentive for the students to
used to address most of the shortcomings of the cur-
cheat, under the perfect information scenario. Since
rent assignment process. In particular, it can be used
the students have little reason to cheat in the two
to address the key concern of most parents: “How
extremal stable matching mechanisms, it is natural to
do I choose the schools if I do not know my child’s
suspect that this result carries over to all the “inter-
standing at the national level?” The answer to that,
mediate” stable matchings as well; we leave this as a
regardless of the stable matching mechanism used, is:
challenging problem for future research.
“Just tell the truth.”
As for the strategic behavior of the schools, the
adoption of any stable matching mechanism would
Acknowledgments
give incentives for some schools to falsify their prefer-
The authors thank the editor and the two anonymous referees
ences or even to falsify the number of places available
for pointing many errors and omissions in earlier versions of this
(see Sonmez 1997 on how the schools can manipu-
paper. In particular, the referees made several suggestions that
late capacities to obtain a better match under both
improved the paper significantly, both in form and substance. This
research was supported by the National University of Singapore
students-optimal and schools-optimal mechanisms).
under grant RP 3970021 and a fellowship from the Singapore-MIT
In the Singapore context, however, the latter is rela-
Alliance program.
tively unimportant as the schools are tightly regulated
by the government, and the number of places avail-
able are determined by the Ministry. Furthermore, the
ranking of the students, according to the schools, is
References
usually done by some broad selection criteria (e.g.,
Dubins, L.E., D.A. Freedman. 198l. Machiavelli and the Gale-
Shapley algorithm. Amer. Math. Monthly 88 485–494.
examination results, affiliation, etc.) rather than at an
Gale, D., L.S. Shapley. 1962. College admissions and the stability of
individual level. Hence the issues of manipulation
marriage. Amer. Math. Monthly 69 9–15.
(both rank and capacity) on the schools’ part is less
, M. Sotomayor. 1985a. Some remarks on the stable matching
of a concern in this context.
problem. Discrete Appl. Math. 11 223–232.
1266
Management Science/Vol. 47, No. 9, September 2001
TEO, SETHURAMAN, AND TAN
Gale-Shapley Stable Marriage Problem Revisited
,
. 1985b. Ms Machiavelli and the stable matching
. 1984b. Stability and polarization of interests in job match-
problem. Amer. Math. Monthly 92 261–268.
ing. Econometrica 52 47–57.
Gardenfors, P. 1975. Match making: Assignments based on bilateral
. 1985. The college admissions problem is not equivalent to
preferences. Behavioural Sci. 20 166–173.
the marriage problem. J. Econom. Theory 36 277–288.
Gusfield, D., R.W. Irving. 1989. The Stable Marriage Problem: Struc-
. 1990. New physicians: A natural experiment in market
ture and Algorithms. MIT Press, Cambridge, MA.
organization. Science 250 1524–1528.
Irving, R.W. 1994. Stable marriage and indifference. Discrete App.
, E. Peranson. 1997. The effects of the change in the
Math. 48 261–272.
NRMP matching algorithm. J. Amer. Medical Assoc. 278
Kara, T., T. Sonmez. 1996. Nash implementation of matching rules.
729–732.
J. Econom. Theory 68 425–439.
, U. Rothblum. 1999. Truncation strategies in matching mar-
Knuth, D.E. 1976. Marriages Stables. Les Presses de l’Unversite’de
kets: In search of advice for participants. Econometrica 67
Montreal, Montreal, Canada.
(January), 21–43.
McVitie, D.G., L.B. Wilson. 1970. Stable marriage assignments for
, M. Sotomayor. 1991. Two-sided Matching: A Study in Game-
unequal sets. BIT 10.
theoretic Modeling and Analysis. Cambridge University Press,
,
. 1971. The stable marriage problem. Comm. ACM 10
Cambridge, MA.
486–490.
Sonmez, Tayfun. 1997. Manipulation via capacities in two-sided
Pittel, B. 1989. The average number of stable matchings. SIAM
matching markets. J. Econom. Theory 77 197–204.
J. Discrete Math. 530–549.
Tadenuma, K., M. Toda. 1998. Implementable stable solu-
Roth, A.E. 1982. The economics of matching: Stability and incen-
tions to pure matching problems. Math. Social Sci. 35(2)
tives. Math. Oper. Res. 7 617–628.
121–132.
. 1984a. The evolution of the labor market for medical
Teo, C.P., J. Sethuraman. 1998. The geometry of fractional
interns and residents: A case study in game theory. J. Political
stable matching and its applications. Math. Oper. Res. 23(4)
Econom. 92 991–1016.
874–891.
Accepted by Bruce L. Golden; received January 1999. This paper was with the authors 10 months for 2 revisions.
Management Science/Vol. 47, No. 9, September 2001
1267
