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 findings of Ashlagi et. al. [2] demonstrate that in unbalanced random markets, the change in expected payoffs is small when one reverses which side of the market “proposes,” suggesting there is little potential gain from manipulation. Inspired by these findings, we study the implications of imbalance on strategic behavior in the incomplete information setting. We show that the “long” side has significantly 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 affect 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 effect 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 different 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 findings 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 findings of Roth and Peranson [20] regarding the “large core” of markets when agents have long preference lists, and the related findings 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 significantly. In light of this finding we ask: What are the effects 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 field” between savvy and naive agents [15, 9]. The number of matched agents and the (ex-post) stability of the match may also be affected [8]. An additional reason why designers may want to induce truthful reporting is that the submitted profiles 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 different 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 find 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 field 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 indifferences. Preferences for women are defined similarly. We denote by u = Π i∈M ⊍ W ui the profile 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 defined similarly, and we denote by P the profile 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 definition 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 profile 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 first woman on his preference list. Each woman then considers her offers, 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 offer 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 offer. Each woman behaves as in step 1, considering offers 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 offer, the algorithm terminates. Each woman is paired with her current mate and this matching is final. Gale and Shapley show that this algorithm must terminate in finite 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 effects 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 different 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 profiles 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 tradeoff which is described by the following proposition: Proposition. Let P be the preference list profile 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 find 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 effect - 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 profile 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 specific 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 profile for agents −w, define P−mw↔m′ to be the preference list profile 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 define 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, define 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′ iff 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 significantly worse, asymptoting to N log N [16]. In fact, for large markets, Pittel [17] proved that the worst-off 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 figures 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 significant. 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 findings, 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 define 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 payoffs 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 Payoffs. 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 profiles, and payoffs 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 effect: 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 Payoffs. 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 profiles, and payoffs 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 offer. 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 difference, 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 benefit 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 effect 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 findings. 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 payoff, given that all other agents submit their true lists, for each possible level of truncation. Payoffs are depicted by 101 – partner rank, and we report the average result over 100,000 iterations. The simulations support the findings 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 qualification to the literature which finds truthful reporting to be close to optimal [20, 11, 13, 14, 2]. Theorem 2 qualifies this previous finding. 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,fioLinc)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 definition). 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 payoff is much flatter 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 significant 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-off 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 difference is at least N 1 +L+1 . For large enough N, this expression is greater than .999 N . Conditional on the truncation making a difference, 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 first 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 significant. The figure depicts truncation payoffs 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 first is that women do much better when the balance tips slightly in their favor: payoffs with 99 women and 100 men are much higher than when there are 101 women. This difference becomes starker as the imbalance increase. This corroborates the findings 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 payoffs only minimally. This too could be deduced from their paper. The third salient feature is not a direct consequence of their findings (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-off and women weakly better-off [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 first point ensures that by adding the other L men to the market all women are weakly better-off. 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 infinity if the (short) list in the setting of Theorem 5 is chosen to be sufficiently 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 difficult 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 Payoffs. 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 profiles, and payoffs 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 offer some benefit, but over-truncating can lead to large losses depending on the profile 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 fix w′s preferences to be uw(⋅), and define the shorthand v(k, P−w) ≡ uw(µM [Pwk, P−w](w)), w’s payoff from submitting truncated preference list Pwk. Now define vψ(k, P−w) ≡ ψ(uw(µM [Pwk, P−w](w)), the payoff 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ψ definitely 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 offer 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 findings generalize to unbalanced markets. We consider first 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}. Define the marginal probability over mens’ preference profiles by pM (⋅). Given p(⋅, ⋅), define 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. Define 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 fixed, 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 finite, 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 influence the advice a market designer can offers 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 (sufficiently 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 significantly 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 effect 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 find 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 find that the incentives for women to manipulate are significantly diminished compared to a balanced market. This finding is consistent with the intuition of Ashlagi et. al. [2], who find 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 significant degree of truncation. This finding qualifies 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 offers leaves room for significant, safe manipulation. While simplistic and stylized in many respects, our result is a first effort to extend the logic market designers rely on in choosing the proposing side. Future work should find more general environments in which the extent of manipulation may be compared, and explore the interaction between the different 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: Conflict 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 field: 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