Strategic Behavior in Unbalanced Matching Markets∗

Peter Coles eBay Research Labs

Yannai Gonczarowski Hebrew University

Ran Shorrer Harvard University and Harvard Business School

February 2014

Abstract
In this paper we explore how the balance of agents on the two sides of a matching market impacts their potential for strategic manipulation. Coles and Shorrer [5] previously showed that in large, balanced, uniform markets using the Men-Proposing Deferred Acceptance Algorithm, each woman’s best response to truthful behavior by all other agents is to truncate her list substantially. In fact, the optimal degree of truncation for such a woman goes to 100% of her list as the market size grows large. Recent ﬁndings of Ashlagi et. al. [2] demonstrate that in unbalanced random markets, the change in expected payoﬀs is small when one reverses which side of the market “proposes,” suggesting there is little potential gain from manipulation. Inspired by these ﬁndings, we study the implications of imbalance on strategic behavior in the incomplete information setting. We show that the “long” side has signiﬁcantly reduced incentives for manipulation in this setting, but that the same doesn’t always apply to the “short” side. We also show that risk aversion and correlation in preferences aﬀect the extent of optimal manipulation.
1 Introduction
A great success story in economic theory is the application of the Deferred Acceptance Algorithm (DAA), proposed by Gale and Shapley [10], to real world two-sided matching markets. The DAA and its variants have been used extensively in school choice settings [1], and most famously in the National Resident Matching Program [20]. The advantages of mechanisms using DAA over other mechanisms have been discussed extensively (See for example [19]). Importantly, it was shown that while no stable matching mechanism is strategy proof, mechanisms applying the DAA have truthful reporting as a dominant strategy for the proposing side [6, 18]. The choice of the proposing side has received some attention in the public domain and in the literature [20], but the general message that has emerged from this body of literature is that the choice of the proposing side has a small eﬀect over agents’ utilities [20, 11, 13, 14, 2, 4].
∗We thank Itai Ashlagi, Nicole Immorlica, Jacob Leshno, Yashodhan Kanoria, Assaf Romm and Al Roth for helpful discussions. We are especially grateful to Jeno˝ Pa´l for his contributions to this paper. Shorrer thanks Microsoft Research for their hospitality while most of the paper was written. The authors can be contacted at rshorrer@hbs.edu.
1

This paper takes a diﬀerent perspective on this issue. We look for the (exact) best responses of agents, and consider the degree of manipulation expected in the market. To do this, we restrict attention to truncation strategies, which are endowed with a natural metric for measuring the extent of manipulation (how many acceptable partners were declared unacceptable). This class of strategies was shown to be optimal in symmetric low-information settings [21, 7]. We derive comparative statics on the extent of manipulation as a function of risk aversion and correlation, and show that more risk averse agents submit longer lists (so they are “more truthful”) and that correlation in preferences also reduces the incentives to manipulate. These results are similar to the ﬁndings of Coles and Shorrer [5], but they are more general as we do not assume that the markets are balanced.
The main innovation in this paper is inspired by the results of Ashlagi, Kanoria and Leshno [2]. In contrast to the ﬁndings of Roth and Peranson [20] regarding the “large core” of markets when agents have long preference lists, and the related ﬁndings of Pittel [16], Ashlagi et. al. [2] show that if the number of agents on each side of the market is not balanced, the core becomes small in the typical case. So while the gap between men (women) expected partner ranks under the men and women proposing versions of the DAA is high in a balanced marked, even a slight imbalance “shrinks” this gap signiﬁcantly. In light of this ﬁnding we ask: What are the eﬀects of imbalance on the incentives to misrepresent one’s preferences? The answer is: it depends! Under the men-proposing version of the DAA, if there are more women than men, women optimally submit “long” lists. When the sides of the market are balanced, a woman facing truthful opponents should submit a short list; asymptotically she truncates 100% of her list. When women are over demanded (on the short side), we provide simulation evidence that extreme truncation is still optimal. We also show that truncation is “safe” when women are on the short side, but not when they are on the long side of the market. To summarize, the extent of optimal truncation may crucially depend on whether the strategic agents (the ones not on the proposing side) are on the long side or the short side of the market.
A market designer may prefer that agents submit either long or short lists. She may be concerned about the incentives for truthfulness for several reasons. For one, she may wish to advise participants that being truthful will not harm them, so as to “level the playing ﬁeld” between savvy and naive agents [15, 9]. The number of matched agents and the (ex-post) stability of the match may also be aﬀected [8]. An additional reason why designers may want to induce truthful reporting is that the submitted proﬁles may provide a signal as to the desirability of agents on the two sides of the market. In school choice settings, for example, truthful reporting allows school districts to learn about the actual desirability of diﬀerent schools.
But market designers may also have reasons to favor shorter lists. From a computational perspective, running the DAA on shorter lists is faster. More importantly, the designer may think that there is a cost (actual or mental) to the system or to participants on one side of the market for generating a long preference list. For example, a school may be required to give each applicant a tour, paperwork may be required for each school that appears on an applicant’s list, and a student may simply ﬁnd it hard to compare his 100th and 101st choices. We take no stand on whether ensuring truthfulness or promoting short lists is more desirable, but merely wish to provide advice to the market designer given objectives regarding list length.
2

2 Preliminaries
We begin by setting out the basic model of matching. Following Coles and Shorrer [5], and in contrast to some of the well-known papers in the ﬁeld of matching, we endow agents with cardinal rather than ordinal preferences.

2.1 Marriage Markets and Stability

In this paper, only one-to-one two sided matching markets will be considered. We call these markets marriage markets for short, and label one side on the market as men M, and the other as women W.

Both men and women are referred to as agents.
The preferences of man m ∈ M are given by a von Neumann-Morgenstern utility function um ∶ W ∪ {m} → R. um(w) is the utility that man m derives from being matched with woman w with certainty, and um(m) is his utility from being unmatched. For simplicity, we assume that um is one-

to-one, so that there are no indiﬀerences. Preferences for women are deﬁned similarly. We denote by

u

=

Π
i∈M ⊍

W ui

the

proﬁle

of

agents

preferences.

Since we have assumed that agents’ preferences are one-to-one, they induce strict preference orderings

on all possible partners and the possibility of remaining unmatched. For a man m ∈ M we denote by

Pm the preference list over W ∪ {m} that is induced by um. For example, Pm ranks w3 higher than w1

if um (w4) > um (w1). We say that w ∈ W is acceptable for m if um(w) > um(m), so m prefers being

matched with w over remaining single. We sometimes omit unacceptable mates from m’s preference list

for notational convenience. Preference lists for women are deﬁned similarly, and we denote by P the

proﬁle of all preference lists.
A matching µ is a mapping from M ∪ W to itself, such that for each m ∈ M we have that µ(m) ∈ W ∪ {m}, for each w ∈ W we have µ(w) ∈ M ∪ {w} and for each x ∈ M ⊍ W µ2(x) = x. When µ(x) = x we say that x is single or unmatched under the matching µ. Otherwise, we refer to µ(w) as w’s husband and µ(m) as m’s wife under the matching µ. We also use the terms partner and mate. The preferences over

partners induce natural preference order over matchings, where each agent ranks the matchings according

to the partner that is assigned to him.
A matching is individually rational if for every x ∈ M ⊍ W, the agent x weakly prefers µ(x) to remaining single. A matching is blocked by a pair (w, m) ∈ W × M if both w prefers m to µ(w) and m prefers w to µ(m). A matching is stable if it is individually rational and not blocked by any pair. There

always exists a stable matching in a market, but in general there may be more than one [10]. For given

preferences, we say that a woman w is achievable for a man m if there exists a stable matching µ such that µ(w) = m. A symmetric deﬁnition applies to womens’ achievable mates.

2.2 The Men-Proposing Deferred Acceptance Algorithm
To prove that every marriage market has a stable matching, Gale and Shapley [10] proposed the MenProposing Deferred Acceptance Algorithm (MP-DA). It takes as an input a proﬁle of preferences P of a set of agents M ⊍ W and outputs a stable matching µM [P ]. When P is clear form the contexts, we

3

sometimes omit it and write µM instead of µM [P ]. The following is a description of the algorithm.
 Step 1. Each man proposes to the ﬁrst woman on his preference list. Each woman then considers her oﬀers, rejects all men deemed unacceptable, and if any others remain, rejects all but her most preferred mate.
 Step k . Each man who was rejected in step k−1 makes an oﬀer to the next woman on his preference list. If his preference list is exhausted, or if he prefers bachelorhood to the next woman on his list, he makes no oﬀer. Each woman behaves as in step 1, considering oﬀers in hand (including any man she has retained from the previous step) and rejects all but her most preferred acceptable suitor.
 Termination. If in any step k, no man makes an oﬀer, the algorithm terminates. Each woman is paired with her current mate and this matching is ﬁnal.
Gale and Shapley show that this algorithm must terminate in ﬁnite time, and they provide a remarkable characteristic of the resulting outcome.
Theorem. (Gale-Shapley) The matching µM resulting from MP-DA is stable. Furthermore, for any other stable matching µ, every man weakly prefers µM to µ and every woman weakly prefers µ to µM .
Since there is no actual content to gender (it is just a label), it is clear that the women-proposing version of the algorithm (WP-DA) has identical but reversed properties. We denote its output given an input P by µW [P ].
As discussed by Roth [19], stability is a desirable property for a matching mechanism. But the theorem illustrates a particular feature of the stable matching produced by the MP-DA (WP-DA); it is the most desirable stable matching for men (women), and the least desirable for women (men). This paper focuses on the strategic incentives that emerge from this property under incomplete information, and their eﬀects on the realized matchings given strategic reporting.
2.3 The Preference List Submission Problem
We now turn to study the incentive properties of stable matching mechanism which use the MP-DA. In a setting where agents are asked to report preferences lists to the mechanism, we consider if they have an incentive to report truthfully, or to submit a diﬀerent preference list.
Consider a set of agents M ⊍ W. Agent i ∈ M ⊍ W with preferences ui must submit a preference list Pˆi to MP-DA, where Pˆi is chosen from the set of i ’s possible preference lists Pi. The agent’s beliefs about what preference lists others will report are represented by the random variable P˜−i, which takes as its range P−i, the set of all possible preference list proﬁles for others. Note that since ui is a von Neumann-Morgenstern utility function, agent i may compare outcomes in this incomplete information setting.
Agent i solves the Preference List Submission Problem:
max E[ui(µM [Pˆi, P˜−i](i))].
Pˆi∈Pi
4

Dubins and Freedman [6] and Roth [18] have shown that for any man m with preferences um and beliefs P˜−m, it is optimal for m to submit his true preference list Pm (which corresponds to um).
Theorem. (Dubins and Freedman; Roth) In the Preference List Submission Problem,
Pm ∈ arg max E[um(µM [Pˆm, P˜−m](m))].
Pˆm∈Pm
This is not the case for women, as they may misrepresent their preferences and get preferable outcomes in some settings [18]. A natural way to misrepresent one’s preferences is by submitting a truncated preferences list. A truncated preference list is identical to the original one, except that some acceptable partners are declared unacceptable. Denote by Pwk the preference list which includes in order only w’s k most preferred men, and call this the k-truncation of her true preference list Pw. If fewer than k men are acceptable to w, then Pwk ≡ Pw. Truncation generates a simple tradeoﬀ which is described by the following proposition:
Proposition. Let P be the preference list proﬁle of all agents in M ⊍ W. Then µM [Pwk, P−w](w) is w’s least preferred achievable mate under P with rank ≤ k. Should no such mate exist, µM [Pwk, P−w](w) = w.
The proposition implies that when others’ submitted preferences lists are known with certainty it is easy to ﬁnd a truncation strategy that would match the woman with her most preferred achievable partner, but also that when there exists uncertainty about others’ submitted lists truncation may yield each of the three possible results relative to truthful reporting:
1. No eﬀect - when woman w has truncated below her least preferred achievable mate
2. Improvement - when woman w truncates above her least preferred achievable mate, and is matched with her least preferred achievable mate above the point of truncation
3. Turning unmatched - when woman w has an achievable mate, but has over-truncated by truncating above her most preferred achievable mate
Since the realized outcome depends on the realized proﬁle that others submit, each truncation yields a lottery given the beliefs P˜−w, and the problem of choosing the optimal truncation corresponds to choosing the most preferable lottery.
2.3.1 Optimality of Truncation
Truncation is not the only possible misrepresentation of preferences. A woman could reverse two men in her preference list, list men as acceptable who are in fact unacceptable, drop men from the middle of her list, or use some combination of these. However, under some conditions, truncation is optimal.
The next proposition states that under certainty, women can do no better than to truncate [22].
Proposition. (Roth and Vande Vate) Suppose woman w has preferences uw and knows others will report preference lists P−w to MP-DA. Then truncating such that µW (w) is the last acceptable partner on her list is an optimal strategy for w.
5

Perhaps surprisingly, when a woman has very little information about the preference lists others might
report, she again can do no better than to truncate. In order to gain from non-truncation misrepresen-
tations, such as swapping the positions of two men in her reported preference list, a woman must have
very speciﬁc information about the preference lists others report. Without such information, it is best
to leave the men in their correct order. Roth and Rothblum [21] demonstrate this principle using the following framework.1
Let woman w’s beliefs about reported preference lists of others be represented by P˜−w, a random variable taking on values in P−w. If P−w is a preference list proﬁle for agents −w, deﬁne P−mw↔m′ to be the preference list proﬁle in which m and m′ swap preference lists, and all women swap the positions of m and m′ in their lists. We say that woman w’s beliefs are (m, m′)-symmetric if Pr(P˜−w = P−w) = Pr(P˜−w = P−mw↔m′) for all P−w ∈ P−w. For a subset M′ ⊆ M, beliefs P˜−w are M′-symmetric if they are (m, m′)-symmetric for all m, m′ ∈ M′.
Theorem. (Roth and Rothblum) Suppose w’s beliefs about reported preference lists of others are Msymmetric. Then any preference list Pˆw she might submit to MP-DA is weakly Pw-stochastically dominated by some truncation of her true preference list.2
Hence, when w is certain about reported preference lists of her opponents, or when she has extreme,
symmetric uncertainty, truncation is optimal.

2.3.2 The Truncation Problem

Even when truncation is not optimal, we may sometimes wish to restrict the choice set for women to
truncations of her true preference list. We deﬁne the Truncation Problem for woman w with preferences uw and beliefs P˜−w on others’ submitted preference lists as

max
k∈{0,...,N

}

E[uw

(µM

[Pwk

,

P˜−w

](w))].

3 Optimal Truncation in Unbalanced Markets

Following Coles and Shorrer [5] and Ashlagi et. al. [2] we consider a setting where each agent draws independently uniformly at random a complete preference list (so that all mates are acceptable).3 We assume further that for each agent i, ui (⋅) is linear in the rank of i’s match, where being unmatched is

treated as rank one below the lowest ranked mate. For a balanced uniform market with N men and N

women, deﬁne

k∗(N

)

≡

max

⎛ ⎝ka∈r{g0,m...,aNx}

E[uw (µM

[Pwk ,

P˜−w](w))]⎞⎠

.

1Ehlers [7] provides weaker conditions, in the same spirit, under which truncation is still optimal. 2Pˆw is Pw-stochastically dominated by Pˆw′ iﬀ for any vNM utility function that corresponds to Pw, the expected utility from submitting Pˆw′ is at least as great as the expected utility from submitting Pˆw. 3While this assumption is not very realistic for real markets, it may serve as an approximation for the behavior of the
top tiers in a tiered market. For example, it may be the case that everyone agrees about the composition of the top tier of
schools and students, but personal tastes causes the orderings to vary [2].

6

k∗(N ) describes woman w ’s optimal point of truncation, given that the other women submit their true preference lists. If there are multiple optima, we conservatively select that which involves the least
truncation. Coles and Shorrer [5] prove the following theorem.

Theorem 1. Let woman w have uniform beliefs and preferences linear in rank (or any strictly increasing,

convex

transformation

of

such

preferences).

Then

lim
N →∞

k∗(N ) N

= 0.

Theorem 1 states that for balanced markets, as the market size grows large, the fraction of the list

that an individual woman optimally truncates goes to 100%. The intuition behind this theorem can be

gleaned from statistical facts about the most and least preferred achievable mates for women. In large

balanced markets where preferences are uniform, the expected rank of the most preferred achievable mate

of a woman (which is the same as the expected rank of her mate under WP-DA) is very low relative to

the length of her list; it asymptotes to log N [16]. This suggests that a woman may safely truncate a

large fraction of her list with little risk of becoming unmatched. Furthermore, the expected rank of a

woman’s

match

under

MP-DA

is

signiﬁcantly

worse,

asymptoting

to

N log N

[16].

In fact,

for

large

markets,

Pittel [17] proved that the worst-oﬀ wife will be matched with a husband at the bottom of her list with

probability approaching 1. This large gap in a woman’s expected most and least preferred achievable

mates suggests that not only is it safe to truncate a large fraction of one’s list in large markets, but that

a woman will also generate gains from such a truncation.

Figure 1 presents simulation results for balanced markets of size 10, 100, 1,000 and 10,000. It is clear

from the ﬁgures that, when all other agents are truthful, the best response of a strategic woman is to

submit a (very) short list. It also appears that the gains from truncation may be signiﬁcant. In a market

of size 10,000, the partner rank could potentially be reduced by about 1,000 in expectation (10% of the

market size).

The recent paper by Ashlagi et. al. [2] implies that the large gap between the best and worst stable

partners is a knife-edge case. When markets are even slightly unbalanced, under any stable matching the

rank of the mates that an agent on the over demanded side of the market gets is approximately log N in

expectation, while the other side can expect approximately

N log N

.4

Intuitively, these results imply that

unbalanced matching markets typically have a “small core.” In turn this suggests that submitting a long

list may constitute an optimal strategy in unbalanced uniform markets. In light of their ﬁndings, we

inspect strategic behavior in the unbalanced setting.

3.1 The Case of More Women Than Men
Given L ≥ 0, for a market with N men and N + L women deﬁne k∗(N, L) ≡ min ⎧⎪⎪⎨⎪⎪⎩⎛⎝ka∈r{g0,m...,aNx} E[uw(µM [Pwk, P˜−w](w))]⎞⎠⎫⎪⎪⎬⎪⎪⎭ .
4The approximations calculated by [2] involve multiplicative constants and describe expected payoﬀs conditional on an agent being assigned a partner.

7

Expected Payoff for w

N = 10
10 9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9 10
Truncation Point for Woman w

N = 1,000

1000 900 800 700 600 500 400 300 200 100
0 0

100 200 300 400 500 600 700 800 900 1000
Truncation Point for Woman w

Expected Payoff for w

Expected Payoff for w

N = 100
100 90 80 70 60 50 40 30 20 10 0
0 10 20 30 40 50 60 70 80 90 100
Truncation Point for Woman w

N = 10,000

10000 9000 8000 7000 6000 5000 4000 3000 2000 1000
0 0

1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
Truncation Point for Woman w

Expected Payoff for w

Figure 1: Simulation Results for Truncation Payoﬀs. The graphs display (N + 1)− an individual woman’s expected partner rank from truncating her list at each point k ∈ {0, . . . , N } and submitting these preferences to MP-DA. Preference lists of the other agents
are uniformly random, selected from the set of all possible full length preference list proﬁles,
and payoﬀs are averaged over 100,000 draws. Markets are of size 10, 100, 1,000 and 10,000.

k∗(N, L) describes woman w ’s optimal point of truncation, given that the other women submit their true preference lists. If there are multiple optima, we conservatively select that which involves the most truncation. Note that for L = 0, k∗(N, 0) ≤ k∗(N ) so the results of Theorem 1 apply to k∗(N, 0). We now have the following theorem, which constitutes a partial converse of Theorem 1. The theorem shows
that the intuition from Ashlagi et. al. [3] extends to the incomplete information setting when women are
over demanded.

Theorem 2. Given L > 0, consider a market with N men and N + L women. Let woman w have

uniform beliefs and preferences linear in rank (or any strictly increasing, concave transformation of such

preferences).

Then

k∗(N,L) N

≥

L L+1

so

lim
N →∞

k∗(N,L) N

≥

L L+1

.

In

particular

k∗(N,L) N

≥

1 2

and

lim
N →∞

k∗(N,L) N

≥

1 2

.

Proof. Recall that a truncation by woman w could lead to one of three results: 1. No eﬀect: woman w has truncated below her least preferred achievable mate

8

100 100

Expected payoff for women w

Expected payoff for women w

80 80

60 60

40 40

20 20

00 20 40 60 80 100 00 20 40 60 80 100

Truncation point of women w

Truncation point of women w

(a) 101 women

(b) 99 women

100 100

Expected payoff for women w

Expected payoff for women w

80 80

60 60

40 40

20 20

00 20 40 60 80 100 00 20 40 60 80 100

Truncation point of women w

Truncation point of women w

(c) 105 women

(d) 95 women

100 100

Expected payoff for women w

Expected payoff for women w

80 80

60 60

40 40

20 20

00 20 40 60 80 100 00 20 40 60 80 100

Truncation point of women w

Truncation point of women w

(e) 110 women

(f ) 90 women

Figure 2: Simulation Results for Truncation Payoﬀs. The graphs display 101– an individual woman’s expected partner rank from truncating her list at each point k ∈ {0, . . . , 100} and submitting these preferences to MP-DA. Preference lists of the other agents are uniformly random, selected from the set of all possible full length preference list proﬁles,
and payoﬀs are averaged over 100,000 draws. All markets have 100 men, and the number of
women varies between 90, 95, 99, 101, 105 and 110. 9

2. Improvement: woman w truncates above her least preferred mate, and is matched with her least

preferred achievable mate above the point of truncation

3. Becoming unmatched: woman w has an achievable mate, but has over-truncated, truncating above

her most preferred achievable mate

In a balanced market, truncation worsened a woman’s outcome only when MP-DA terminated with one

man exhausting his list. But when women outnumber men, truncation may cause MP-DA to terminate

when a previously unmatched woman receives an oﬀer. Note that when agents are truthful, at least one

woman will have received no proposals prior to the truncation. Of course improvement upon truncation

is possible only if w does not end up single.

Using the principle of deferred decisions, it is easy to see that conditional on a truncation making

a

diﬀerence,

the

probability

of

improvement

is

less

than

1 L+1

≤

1 2

.

To

show

this,

recall

that

unmatched

women have not received any proposals. Hence, it follows from the principle of deferred decisions and

symmetry that, following truncation, any future proposal is at least as likely to be directed at these

women as to w. The algorithm terminates only when such a proposal happens.

Now consider the marginal beneﬁt to w from omitting the lowest-ranked man from a list of length

m+1. The most w can hope for is an improvement in her match of m ranks (from m+1 to the top).5 If this

omission instead leaves her unmatched, she drops N −m ranks (from m+1 to N +1). Since the probability

of

becoming

unmatched

conditional

on

truncation

having

any

eﬀect

is

at

least

L 1+L

≥

1 2

,

the

expected

gain

cannot

be

positive

if

m<

L L+1

N

.

Hence,

the

optimal

list

length

for

w

is

at

least

L L+1

N

≥

1 2

N

.

The left panels of Figure 2 illustrate our ﬁndings. We simulated markets with 100 men and 99, 95 and 90 women. In each market we generate independently and at random a full preference list for each agent. We then calculate an individual woman’s payoﬀ, given that all other agents submit their true lists, for each possible level of truncation. Payoﬀs are depicted by 101 – partner rank, and we report the average result over 100,000 iterations.
The simulations support the ﬁndings of Theorem 2, as the optimal list length in all three markets is greater than 50. Indeed, the optimal list lengths are higher than 50, 84 and 91, the respective lower bounds the theorem indicates. In contrast to Figure 1, the balanced market case, it is almost impossible to detect the peak of the graphs. That is, not only should women submit long lists, but there is little to gain by truncating optimally. Note that as one would expect, women do worse as the competition on their side increases.
A few points related to Theorem 2 deserve attention. First, under uniform beliefs, Roth and Rothblum’s optimality theorem applies whether the market is balanced or not. This implies that the truncation strategies described in Theorems 1 and 2 are the best overall strategies, not just the optimal truncation strategies. Hence, we have a natural metric for the “distance” between the optimal strategy and truthfulness. The importance of Theorem 1 is in showing that the best response to straightforward behavior of others could be “far” from truthful, and so provides an important qualiﬁcation to the literature which ﬁnds truthful reporting to be close to optimal [20, 11, 13, 14, 2]. Theorem 2 qualiﬁes this previous ﬁnding. We show that our example relies heavily on the fact that the number of women is not larger than the

5In

fact,

the

gain

is

m+1 2

in

expectation

-

the

expected

rank

of

the

remaining

partners.

10

number of men.

A second point worth noting is instead chosen to state the theorem ing ties in favor of less truncation

autshsiainntgtokhu∗er(Ndche,ﬁoLinc)iet≡ioomnf akox∗f(⎧⎪⎪⎨⎪⎪⎩kN⎛⎝∗,k(aL∈Nr{g)0),m.w,..,aaaNxsn}daE[tcuhowen(stµehrMevoa[rPteiwvmke,

P˜o−nwe].(wW)e)]c⎞⎠o⎫⎪⎪⎬⎪⎪⎭u,ldbrheaavkewould of course still

hold (since k∗(N, L) ≥ k∗(N, L) by deﬁnition).

Finally, in contrast to most of the results in this strand of the literature, our theorem is not a “large

market result”; our result holds for any N and L. That is, manipulation opportunities are minimal

(in the sense of distance from truthful submission) whenever women outnumber men, for unbalanced

markets of any size. However, a simple corollary of our result is that as imbalance in a market increases,

manipulation opportunities vanish altogether.

Corollary 1. Given a sequence {LN } with limLN = ∞ and a sequence of uniform markets with N men

and

N + LN

women,

if

woman

w

has

N
uniform

beliefs

and

preferences

linear

in

rank

(or

any

strictly

increasing, concave transformation of such preferences), then Nli→m∞k∗(N, LN ) = 1.

The simulation results presented in Figure 2 are consistent with the results of Ashlagi et. al. [2]. In

contrast to the relatively large gain that a woman may be able to realize by truncating in a balanced

market, when there are more women than men the graph of the expected payoﬀ is much ﬂatter between

the optimum and truthful reporting. It is also true that in this case truncation is relatively risky. One can

see from Figure 2 that, for example, in a market with 101 women and 100 men, submitting a list of length

30 exposes a woman to a signiﬁcant risk of remaining unmatched. The following theorem formalizes this

observation by providing a lower bound on the probability of becoming unmatched following a relatively

conservative truncation.

Theorem 3. Fix L>0 and δ ∈ (0, 1). For N large enough, in a uniform market with N men and N + L

women, if all other agents report truthfully and woman w submits a truncation list of length less than

δN ,

she

will

be

unmatched

with

probability

at

least

.49+L N +L

.

Proof. From Pittel [17, Theorem 6.2] we know that in a balanced uniform market of size N , the probability

that the worst-oﬀ woman gets a mate ranked worse than δN approaches 1. This probability only increases

when there are more women than men [12]. Now consider a woman truncating her list shorter than δN

while all other agents are truthful. From Pittel’s theorem, for large N the probability that this truncation

makes

a

diﬀerence

is

at

least

N

1 +L+1

.

For

large

enough

N,

this

expression

is

greater

than

.999 N

.

Conditional

on the truncation making a diﬀerence, using the principle of deferred decisions, the resulting chain of

rejections is at least as likely to terminate with a proposal to a woman that did not receive any proposals

until w divorced her partner, as it is to return to w. This implies that even in the event that w is matched

when she (and all others) report truthfully, by truncating her list to a size smaller than δN she raises

her

probability

of

being

unmatched

by

at

least

L 1+L

×

.999 N

>

.49 N

.

Multiplying

both

sides

of

the

inequality

by the probability of w being matched if she reports truthfully, and adding the probability of w being

unmatched if she reports truthfully, produces the lower bound:

N

L +

L

+

1

−

N

L +

L

.49 N

=

L + .49 N +L

.

11

Symmetry

implies

that

w

will

remain

unmatched

with

probability

L N +L

no

matter

what

(full)

list

she reports. We are interested in the increase in probability of being left unmatched relative to truthful

reporting

.49 N +L

.

While the increase does not appear to be large at ﬁrst glance, several facts must

be taken into account. First, this is a lower bound, and there is no good reason to suspect that it is

tight. Moreover, the lower bound for the increase in probability is of the same order of magnitude as the

probability of remaining unmatched under truthful reporting. Second, the degree of truncation of w may

be minimal. The theorem allows w to submit 99% of her list and the results will still hold. A third point

is that these results should be compared with the opposite case, where men outnumber women. This is

exactly what we do in the next section.

But before we move on, we state a conjecture. Let a uniform market be the setting in which each

agent is equally likely to have any full preference list. Additionally, agent utility depends on partner

rank, agents on each side of the market identically value a match with their rth ranked choice and have

identical value to being unmatched. Coles and Shorrer [5] showed that:6

Theorem 4. In uniform markets, there exists a symmetric equilibrium ((σm)N , (σw)N ) where men each use the strategy σm of truthful reporting and women each use the strategy σw, which is a mixture over truncation strategies.

In an imbalanced market were individual women have an incentive to submit long lists, we conjecture that submission of long lists is also optimal in equilibrium.

Conjecture. Fix L>2. In a large uniform markets with N men and N + L women, where MP-DA is

used,

there

exists

a

symmetric

equilibrium

where

all

women

submit

truncated

lists

longer

than

N 2

.

3.2 The Case of Fewer Women Than Men
The results of Ashlagi et. al. [2] regarding the small core apply regardless of the direction of the imbalance. That is, no matter the size or direction of the imbalance, the expected potential improvement is small. One might therefore suspect that when men outnumber women, an analog to Theorem 2 would apply and room for manipulation would again be small. This, however, does not appear to be the case. The simulation results presented in the right panel of Figure 2 indicate that when there are fewer women than men, the optimal level of truncation may still be signiﬁcant.
The ﬁgure depicts truncation payoﬀs for men in simulated markets with 100 men and 101, 105 and 110 women. In contrast to the case where women outnumber men, in this case the peaks of all three graphs involve lists of length shorter than 31.
Comparing the right and left panels of Figure 2, three additional facts stand out. The ﬁrst is that women do much better when the balance tips slightly in their favor: payoﬀs with 99 women and 100 men are much higher than when there are 101 women. This diﬀerence becomes starker as the imbalance increase. This corroborates the ﬁndings of Ashlagi et. al. [2] in the case when w reports truthfully.
6In fact, their proof was for the balanced case, but the same proof would work for general uniform markets.

12

Also salient is that even though optimal truncation may be far from the truth, such a manipulation increases payoﬀs only minimally. This too could be deduced from their paper. The third salient feature is not a direct consequence of their ﬁndings (though is related to techniques used in their proofs). The simulations suggest that truncation is “safer” for women when they are over-demanded. That is, when there are more men then women, women may submit relatively short lists without facing a large risk of becoming unmatched, even if there is little gain from doing so.
The next theorem shows that this third fact holds more generally.

Theorem 5. Fix L ≥ 0. For a uniform market with N + L men and N women, a woman that submits

a truncation containing more than L + (2 + a) log2 N men will be matched with probability at least 1 −

O

N −c(a) , where c(a) = 2a

3

+

(4a

+

9)

1 2

−1
.

In particular a women that submits a truncated list of

more than L + 10 log2 N men will be unmatched with probability at most O

1 N2

.

Proof. For notational simplicity we provide the proof for the case of L+10 log2 N , but analogous arguments

would apply for all other cases. The proof has two steps. First, recall that in a market that uses MP-

DA, adding men to the market makes the other men weakly worse-oﬀ and women weakly better-oﬀ

[12]. Second, from Pittel [17, Theorem 6.1] we know that in a balanced market of size N , submitting a

truncated list with 10 log2 N men ensures being matched with probability 1 − O

1 N2

. In a market with

all the women and an arbitrary subset of the men containing N agents, by submitting a truncated list

with L + 10 log2 N men, a woman submits a list containing, at least, her most preferred 10 log2 N men

in the subset in order. By Pittel’s theorem, this ensures that the woman is matched with probability at

least 1 − O

1 N2

.

But the ﬁrst point ensures that by adding the other L men to the market all women

are weakly better-oﬀ. In particular, no woman that would have been matched in the smaller market can

become unmatched.

Remark. The statement of Theorem 5 is intentionally silent on the strategies of women -w. The proof shows that the statement holds when all other women are truthful. But the proof also holds whenever other women use truncation strategies, or any anonymous strategies. The logic is simple: truncation by other women only increases w’s probability of being matched given any list she submits.

Intuition for Theorem 5 may come from considering markets with large imbalances. Consider, for example, uniform markets with N women and (1 + λ) N men, for positive λ. In these markets, MP-DA

terminates only after λN men have proposed to all of the women. Since preferences are independent,

this implies (using the “principle of deferred decisions”) that even in the men optimal stable matching, a

woman is matched with a man high on her list with high probability (her expected partner rank is lower

than

N λN

=

1 λ

).

Rather than being an analog, Theorem 5 stands in sharp contrast to Theorem 3. The ratio between

the length of the lists described in Theorem 5 and the ones described in Theorem 3 approaches 0 as

N grows large (since the lists from Theorem 5 are much shorter). Yet the ratio of the increases in the

probability of becoming unmatched approaches inﬁnity if the (short) list in the setting of Theorem 5 is chosen to be suﬃciently long (e.g. 11 log2 N ).

13

To illustrate Theorem 5, we present additional simulation evidence. We simulated a market with 1000 men and 999 women, and estimated the returns to truncation for a woman w given that all other agents are truthful, reporting average results over 100,000 iterations. The results are summarized in the left panel of Figure 3. While diﬃcult to observe with the naked eye, the maximum is attained at 89, so that in terms of list length, the best response is still “far” from truthful reporting.

1000 1000

Expected payoff for women w Expected payoff for women w

800 800

600 600

400 400

200 200

00

200 400 600

800 1000

00

200 400 600 800 1000

Truncation point of women w

Truncation point of women w

(a) 999 women

(b) 1001 women

Figure 3: Simulation Results for Truncation Payoﬀs. In markets with 1000 men and
999 or 1001 women, the graph displays 1001– an individual woman’s expected partner rank from truncating her list at each point k ∈ {0, . . . , 1000} and submitting these preferences to MP-DA. Preference lists of the other agents are selected, uniformly at random, from the set
of all possible full length preference list proﬁles, and payoﬀs are averaged over 100,000 draws.

4 Other Aspects Impacting the Optimal Level of Truncation
Coles and Shorrer [5] provide several comparative statics for the optimal level of truncation in the case of balanced markets. We demonstrate that these hold in the unbalanced case as well.
4.1 Truncation and Risk Aversion
As discussed previously, truncation is a risky strategy. Compared to truthful reporting, truncation may oﬀer some beneﬁt, but over-truncating can lead to large losses depending on the proﬁle of preferences that is submitted by others. One might expect agents with more conservative attitudes toward risk to shy away from this proposition. In this section, we formalize this intuition.
We consider a general setting, with arbitrary preferences for woman w and beliefs about reported preferences of others. Let ψ(⋅) be any strictly increasing, concave transformation. We claim that for any beliefs about others, woman w with preferences uw(⋅) will truncate more than a woman wψ who has identical beliefs, but preferences given by ψ(uw(⋅)).

14

We ﬁx w′s preferences to be uw(⋅), and deﬁne the shorthand

v(k, P−w) ≡ uw(µM [Pwk, P−w](w)),

w’s payoﬀ from submitting truncated preference list Pwk. Now deﬁne

vψ(k, P−w) ≡ ψ(uw(µM [Pwk, P−w](w)),

the payoﬀ from submitting truncated preference list Pwk for a woman wψ with preferences ψ(uw(⋅)). The following theorem states that if w prefers truncating less to more, then wψ deﬁnitely prefers
truncating less to more.

Theorem 6. Let P˜−w be any random variable distributed over P−w. Then ∀k ∈ {1, . . . , N − 1}, ∀t ∈

{1, . . . , N − k} we have

E v(k, P˜−w) ≤ E v(k + t, P˜−w)

⇒

E vψ(k, P˜−w) ≤ E vψ(k + t, P˜−w) .

Furthermore, if i) ψ(⋅) is strictly concave, and ii) under P˜−w, each man is achievable for w with positive probability, then the second inequality is strict.

We can now use Theorem 6 to sort optimal truncation points based on degree of concavity.

Corollary 2. Let kil be the minimum optimal truncation point (by rank) and let kih be the maximum optimal truncation point for woman i ∈ {w, wψ}. Then kwl ≤ kwl ψ and kwh ≤ kwhψ . Furthermore, if conditions i) and ii) from Theorem 6 hold, then kwh ≤ kwl ψ .
We omit the proofs, as they are straightforward analogs of the proofs of Theorem 5 and Corollary 1 in Coles and Shorrer [5]. The key insight in the analysis is the interpretation of truncation as a risky lottery, and then mapping the additional risk associated with incremental truncation to an extra lottery a woman must face. If a woman doesn’t like to face the extra lottery, then certainly a woman with more concave preferences will not want to face it. Note that despite pertaining to risk aversion, the results in this section do not restrict the structure of uw(⋅) in any way. For example, we do not require uw(⋅) to be “concave.” Rather, it is the relative concavity that is crucial.
This result can oﬀer advice to a market designer. If she wishes to see long lists, for example since her objective is to maximize the number of matches, a market designer may wish to choose the less risk averse side to be the “proposers” in the Deferred Acceptance Algorithm. If the two sides of the market are identical in all regards except for their risk preferences, the more risk averse side will be less likely to truncate, even if manipulations increase their expected partner rank. Lower levels of truncation will increase the number of realized matches, and consequently, reduce the number of participants left unmatched. However, in making this choice, the market designer should take other market features into consideration as well, as we demonstrate in the next section.

15

4.2 Truncation and Correlated Preferences

Coles and Shorrer [5] provided theoretical and empirical evidence that, in the balanced setting, correlation in preferences of agents on one side of the market reduces their incentive to truncate. In this section, we show that their ﬁndings generalize to unbalanced markets.
We consider ﬁrst the case of perfectly correlated preferences on womens’ side of the market. In this case, there exist a unique stable matching, and so women have no incentive to truncate their lists at all when all others report truthfully. If women are uncertain about mens’ preferences, truncation may only lead them to a worse outcome, provided that others are truthful.
While perfect correlation and independence are easy to model, partial correlation may appear in many forms. In this paper, we focus on one simple such form. Consider the Preference List Submission Problem for woman w with preferences uw and beliefs P˜−w about reported preference lists of opponents. Let p(⋅, ⋅) be the probability mass function for w’s beliefs. That is,

p(PM, PW {w})

gives the likelihood that the men will report preference lists PM and women W {w} will report preference lists PW {w}. Deﬁne the marginal probability over mens’ preference proﬁles by pM (⋅).
Given p(⋅, ⋅), deﬁne beliefs pC(⋅, ⋅) by

pC (PM, PW

{w}) ≡ ⎧⎪⎪⎨⎪⎪⎩

pM (PM) 0

if Pwˆ = Pw ∀wˆ ∈ W {w} . otherwise

pC(⋅, ⋅) is the distribution that preserves the marginal distribution over men’s preferences pM (⋅), but
where the other women share the preferences of w.
Deﬁne beliefs pα(⋅) by pα(P−w) ≡ (1 − α)p(P−w) + αpC (P−w).

Hence, as α varies from 0 to 1, pα ranges from p to pC. The marginal distribution over men’s preferences

remains ﬁxed, while the correlation of women’s preferences steadily increases (the distribution remains constant if p = pC).

The set of optimal truncation points for woman w with preferences uw and beliefs indexed by α is

given by

k∗(α, p, uw) ≡ arg max Epα[v(k, P˜−w)].
k∈{0,...,N }

Notice that since the choice set is ﬁnite, k∗(⋅, ⋅) will be non-empty. Let kh(α, p, uw) = max[k∗(α, p, uw)] and kl(α, p, uw) = min[k∗(α, p, uw)], the optimal choices involv-

ing the least and most truncation respectively.

The following proposition states that for any preferences uw and beliefs p, as we increase the degree of correlation α, woman w should truncate less.

Proposition 1. Let α, α′ ∈ [0, 1] with α′ > α. Then kl(α′, p, uw) ≥ kl(α, p, uw) and kh(α′, p, uw) ≥ kh(α, p, uw).

16

The proof of the proposition is analogous to the proof of Proposition 2 in Coles and Shorrer [5], and is therefore omitted.
The anticipated level of correlation in the environment might inﬂuence the advice a market designer can oﬀers participants. If correlation is high, the designer can safely advise participants to report truthfully, and it is in their best interest to do so. With low correlation (suﬃciently heterogeneous preferences), players may anticipate gains from truncation, which if acted on, could lead to unstable matching.
5 Conclusion
In this paper, we study optimal strategic behavior in unbalanced one-to-one matching markets, where matchings are determined by the Deferred Acceptance Algorithm and agents have incomplete information about the preferences of others. We focus on truncation strategies, which are attractive for agents as they are simple and always weakly increase the probability of being matched with more-preferred mates. From a computational perspective, this reduces signiﬁcantly the dimensions of the strategy space, allowing us to use simulations to pinpoint optimal behavior. This restriction also produces a natural metric on the extent of manipulation: the shorter the lists submitted, the further they are from truthfulness. This allows us to make relative statements about optimal list lengths.
The main innovation of this paper is in studying the eﬀect of imbalance in the number of agents on the two sides of a market on their potential for manipulation. We study a stylized setting which we term a uniform market, and ﬁnd that the degree of manipulation observed in this setting critically depends on the direction of the imbalance. When women are on the long side of the market (there are more women than men), we ﬁnd that the incentives for women to manipulate are signiﬁcantly diminished compared to a balanced market. This ﬁnding is consistent with the intuition of Ashlagi et. al. [2], who ﬁnd that the expected gap between an agent’s highest and lowest achievable mates is small in unbalanced uniform markets.
By contrast, when men outnumber women, we provide evidence that a woman’s best response to truthful behavior by others involves a signiﬁcant degree of truncation. This ﬁnding qualiﬁes results that suggest opportunities for manipulation in such settings are minimal (e. g. in terms of potential gain in utility [14]). We further show that truncation is safe when women are on the short side (more men than women) but not when they are on the long side.
We also provide comparative statics regarding the extent of manipulation, regardless of the direction of size of a market imbalance. When women are more risk averse, they should be less aggressive in their degree of truncation. Correlation in womens’ preferences also reduces their incentive to truncate.
Matching mechanisms based on the Deferred Acceptance Algorithm are used extensively in a variety of entry level labor markets [19] and in school choice [15]. One advantage of DAA is that it induces truthful reporting as a dominant strategy for one side of the market [18, 6]. This alone is an argument market designers have used to decide which side will be the “proposing” one [19].
In addition to shedding light on strategic behavior in unbalanced markets generally, our paper introduces a new factor that might be considered when selecting the proposing side: direction of imbalance. By selecting the over-demanded side to propose, potential for strategic manipulation is minimized. Selecting
17

the over-demanded side to receive oﬀers leaves room for signiﬁcant, safe manipulation. While simplistic and stylized in many respects, our result is a ﬁrst eﬀort to extend the logic market designers rely on in choosing the proposing side. Future work should ﬁnd more general environments in which the extent of manipulation may be compared, and explore the interaction between the diﬀerent forces that determine the incentives to manipulate.
References
[1] Atila Abdulkadiro˘glu, Parag A Pathak, and Alvin E Roth. The new york city high school match. American Economic Review, pages 364–367, 2005. 1
[2] Itai Ashlagi, Yashodhan Kanoria, and Jacob D Leshno. Unbalanced random matching markets. In ACM Conference on Electronic Commerce, pages 27–28, 2013. (document), 1, 3, 3, 3, 4, 3.1, 3.1, 3.2, 5
[3] Itai Ashlagi and Flip Klijn. Manipulability in matching markets: Conﬂict and coincidence of interests. Social Choice and Welfare, 39:23–33, 2012. 3.1
[4] Eduardo M Azevedo and Jacob D Leshno. A supply and demand framework for two-sided matching markets. In MATCH-UP 2012: the Second International Workshop on Matching Under Preferences, page 124, 2012. 1
[5] Peter Coles and Ran Shorrer. Optimal truncation in matching markets. Technical report, Nota di Lavoro, Fondazione Eni Enrico Mattei, 2013. (document), 1, 2, 3, 3.1, 4, 4.1, 4.2, 4.2
[6] L.E. Dubins and D.A. Freedman. Machiavelli and the gale-shapley algorithm. American Mathematical Monthly, 88(7):485–494, 1981. 1, 2.3, 5
[7] Lars Ehlers. In search of advice for participants in matching markets which use the deferredacceptance algorithm. Games and Economic Behavior, 48(2):249–270, 2004. 1, 1
[8] Clayton Featherstone and Muriel Niederle. School choice mechanisms under incomplete information: an experimental investigation. Harvard Business School, Unpublished manuscript, 2011. 1
[9] Clayton R. Featherstone and Eric Mayefsky. Stability and deferred acceptance: Strategic behavior in two-sided matching. working paper, 2010. 1
[10] D. Gale and L.S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9–15, 1962. 1, 2.1, 2.2
[11] Nicole Immorlica and Mohammad Mahdian. Marriage, honesty, and stability. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005. 1, 3.1
[12] Jr. Kelso, Alexander S. and Vincent P. Crawford. Job matching, coalition formation, and gross substitutes. Econometrica, 50(6):pp. 1483–1504, 1982. 3, 3.2
18

[13] Fuhito Kojima and Parag Pathak. Incentives and stability in large two-sided matching markets. American Economic Review, 99:608–627, 2009. 1, 3.1
[14] SangMok Lee. Incentive compatibility of large centralized matching markets. working paper, 2011. 1, 3.1, 5
[15] Parag A Pathak and Tayfun Sonmez. Leveling the playing ﬁeld: Sincere and sophisticated players in the boston mechanism. The American Economic Review, 98(4):1636–1652, 2008. 1, 5
[16] B. Pittel. The average number of stable matchings. SIAM J. Discret. Math., 2(4):530–549, November 1989. 1, 3
[17] Boris Pittel. On likely solutions of a stable marriage problem. The Annals of Applied Probability, 2(2):pp. 358–401, 1992. 3, 3, 3.2
[18] Alvin E. Roth. The economics of matching: Stability and incentives. Mathematics of Operations Research, 7:617–628, 1982. 1, 2.3, 5
[19] Alvin E Roth. New physicians: a natural experiment in market organization. Science, 250(4987):1524–1528, 1990. 1, 2.2, 5
[20] Alvin E. Roth and Elliot Peranson. The redesign of the matching market for american physicians: Some engineering aspects of economic design. American Economic Review, 89(4):748–780, 1999. 1, 3.1
[21] Alvin E. Roth and Uriel G. Rothblum. Truncation strategies in matching markets - in search of advice for participants. Econometrica, 67:21–43, 1999. 1, 2.3.1
[22] Alvin E. Roth and John H. Vande Vate. Incentives in two-sided matching with random stable mechanisms. Economic Theory, 1(1):31–44, 1991. 2.3.1
19