Next Article in Journal
Governmental Taxation of Households Choosing between a National Currency and a Cryptocurrency
Next Article in Special Issue
School Choice with Hybrid Schedules
Previous Article in Journal
The Effect of Disclosing Identities in a Socially Incentivized Public Good Game
Previous Article in Special Issue
School Choice in Guangzhou: Why High-Scoring Students Are Protected?
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Stability and Median Rationalizability for Aggregate Matchings

1
Division of the Humanities and Social Sciences, California Institute of Technology, Pasadena, CA 91125, USA
2
Department of Economics, Washington University in St. Louis, St. Louis, MO 63130, USA
3
Department of Economics, Boston College, Chestnut Hill, MA 02467, USA
*
Author to whom correspondence should be addressed.
Submission received: 3 March 2021 / Revised: 22 March 2021 / Accepted: 25 March 2021 / Published: 9 April 2021
(This article belongs to the Special Issue School Choice)

Abstract

:
We develop the theory of stability for aggregate matchings used in empirical studies and establish fundamental properties of stable matchings including the result that the set of stable matchings is a non-empty, complete, and distributive lattice. Aggregate matchings are relevant as matching data in revealed preference theory. We present a result on rationalizing a matching data as the median stable matching.

1. Introduction

Following the seminal work of [1], an extensive literature has developed regarding matching markets with non-transferable utility. This literature assumes that there are agent-specific preferences, and studies the existence of stable matchings in which each agent prefers her assigned partner to the outside option of being unmatched, and there are no pairs of agents that would like to match with each other rather than keeping their assigned partners.
In this paper, we develop the theory of stability for aggregate matchings, which we interpret as a dataset of matchings, and consider its testable implications. In an aggregate matching, agents are classified into types according to their observable characteristics: for example age, employment status, gender, or race. The aggregate matching is then a table, a matrix, that records how many women of each type are matched with men of each type. Our notion of matching data is more general than just deterministic matchings and includes randomized matchings of agents to objects (a probabilistic assignment of children to schools, for example, as in [2,3]) as well. Therefore, our results are also applicable to randomized matching environments.
We assume that preferences are at the type-specific level, rather than the individual-level. In our setting, accommodating individual-level preferences would entail losing all empirical bite. Thus we adopt instead the assumption that the definition of types already carries all the information needed to determine agents’ preferences. This differs from the approach in empirical applications of matching theory, which assume transferable utilities (see, e.g., [4] or [5]), but allow for heterogeneous preferences at the individual-level. When our results are taken to data, one needs to introduce an appropriate error structure that allows for individual-level randomness but without individual-level preference heterogeneity. One way of doing this is via measurement error, as in the classical revealed preference theory for consumption [6,7]. One illustration can be found in [8].
We establish fundamental results on the set of stable matchings in Theorem 1. First of all, there exists a stable matching. Then we introduce two partial orders on matchings using preferences of the two sides of the market and show that for every set of stable matchings there exists the greatest lower bound and the least upper bound with respect to the two partial orders in the set of stable matchings, i.e., the set of stable matchings endowed with either partial order is a complete lattice. Furthermore, we show an additional structural result that this lattice is distributive. (The definition of distributive lattices is given in Section 2). Using the lattice structure on the set of stable matchings, we show that there exists a median stable matching, which assigns each agent the median outcome among all stable matching outcomes (Corollary 1). Theorem 1 also provides other structural results including “polarity of interests”, saying that a stable matching is more preferred for men if and only if it is less preferred for women. Furthermore, the outcomes in two stable matchings are always comparable using the partial orders for an agent. The “rural hospitals theorem”, which states that for each type of agent the number of partners in any two stable matchings are the same, also holds.
Once the stability of matchings is understood, we turn to the main question in the paper: when we interpret an aggregate matching as a table of matching data, and when we do not have access to the agents’ preferences, when can we say that the data is consistent with the theory? This is a revealed preference question that has been addressed by [9] (see also [10,11]). Here we focus on a particular selection of stable matchings—the median stable matching, which is defined for markets with deterministic outcomes. We provide a sufficient condition under which matching is rationalizable as the median stable matching (Theorem 3). We show that the condition is not necessary in Appendix A.
Theorem 1 on the structure of stable matchings generalizes well-known results in the literature to allow for randomization, aggregate matchings, and continuum of agents (see [12] for a review). Proposition 1 establishes the existence of generalized median stable matchings in our environment. For earlier existence results of median stable matchings see [13,14,15,16,17,18]. Revealed preference studies include [9,11,19,20]. The works of [9,20] take aggregate matchings as the source of data, but none of these papers considers the question of median-rationalizability.

2. Preliminary Definitions

2.1. Lattice Theory

If S is a set and ≤ is a partial order on S, we say that the pair ( S , ) is a partially ordered set. We say that x , y S are comparable if x y or y x . A partially ordered set ( S , ) is a lattice if, for every x , y S , the least upper bound and the greatest lower bound of x , y with respect to the partial order ≤ exist in S. We denote the least upper bound of x , y by x y ; and the greatest lower bound of x , y by x y . Similarly, if for every S S , the least upper bound and the greatest lower bound of S exist in S, the lattice ( S , ) is called complete.
We say that a lattice ( S , ) is distributive if the following holds for all x , y , z S :
  • x ( y z ) = ( x y ) ( x z ) , and
  • x ( y z ) = ( x y ) ( x z ) .

2.2. Graph Theory

An (undirected) graph is a pair G = ( V , L ) , where V is a set and L is a subset of V × V . A path in G is a sequence p = v 0 , , v N such that for n { 0 , , N 1 } , ( v n , v n + 1 ) L . We write v p to denote that v is a vertex in p. A path v 0 , , v N connects the vertices v 0 and v N . A path v 0 , , v N is minimal if there is no proper subsequence of v 0 , , v N which is also a path connecting the vertices v 0 and v N . The length of path v 0 , , v N is N.
A cycle in G is a path c = v 0 , , v N with v 0 = v N . A cycle is minimal if for any two vertices v n and v n in c, the paths in c from v n to v n and from v n to v n are distinct and minimal. We call v and w adjacent in c if there is n such that v n = v and v n + 1 = w or v n = w and v n + 1 = v . If c and c are two cycles, and there is a path from a vertex of c to a vertex of c , then we say that c and c are connected.

3. Model

The primitives of the model are represented by a four-tuple M , W , P , K , where
  • M and W are finite and disjoints sets of, respectively types of men, and types of women.
  • P is a preference profile: a list of preferences P m for every type-m man and P w for every type-w woman. Each P m is a linear order over W w 0 , and each P w is a linear order over M m 0 . Here, w 0 and m 0 represent the outside option of being unmatched. The weak order associated with P m is denoted by R m and the weak order associated with P w is denoted by R m .
  • K is a list of non-negative real numbers K m for each m M and K w for each w W . There are K m type-m men and K w type-w women.
We enumerate M as m 1 , , m | M | and W as w 1 , , w | W | . A matching is a | M | × | W | matrix X = ( x m i , w j ) such that x m i , w j + , j x m i , w j K m i for all i, and i x m i , w j K w j for all j. ( + denotes the set of non-negative real numbers.) We denote the mass of single m-agents in X by x m , w 0 , and denote the mass of single w-agents in X by x m 0 , w .
The ith row of a matching X is denoted by X m i , · , and the jth column by X · , w j . When it is not ambiguous, we write X m i , or X i , for X m i , · , and X w j , or X j , for X · , w j . Similarly, we use x i , j for x m i , w j .
Our solution concept is stability:
Definition 1.
A matching X isindividually rationalif x m , w > 0 implies that w P m w 0 and m P w m 0 .
A pair ( m , w ) is ablocking pair forXif there exist m M { m 0 } and w W { w 0 } such that m P w m , w P m w , x m , w > 0 , and x m , w > 0 .
A matching X isstableif it is individually rational and there are no blocking pairs for X.
We denote by S ( M , W , P , K ) the set of all stable matchings in M , W , P , K .
Individual rationality states that if x m , w > 0 , then for type-m men type-w women are more preferred than being unmatched and for type-w women type-m men are more preferred than being unmatched. A pair ( m , w ) is a blocking pair if type-m men have a positive measure of partners who are less preferred than type-w women and type-w women have a positive measure of partners who are less preferred than type-m men.
Two special cases of our model are worth emphasizing: The model of random matching is obtained when K m = 1 for all m, and each K w is a natural number. The interpretation of random matching is that men are “students” and women are “schools”. Students are assigned to schools at random, and each school w has K w seats available for students. In real-life school choice, the randomization often results from indifferences in schools’ preferences over students [3]: Matching theory often requires strict preferences, so a random “priority order” is produced for the schools in order to break indifferences. Random matchings arise in many other situations as well, because random assignment is often a basic consequence of fairness considerations (if two children want the same toy, fairness demands that they flip a coin to determine who gets it).
The second model is that of integral complete matching, where all K m and K w are natural numbers, and all entries of a matching X are natural numbers. The interpretation is that there are K m type-m men and K w type-w women, and that a matching X exhibits in x m , w how many type m men matched to type-w women. This special case captures actual observations in marriage models (see, for example, [8]). We observe that men and women are partitioned into types according to their observable characteristics (age, income, education, etc.); and we are given a table showing how many type-m men married type-w women. These observations are essentially “flow” observations (marriages in a given year), so the integral complete matchings do not have any single agents.

4. Structure of Stable Matchings

In this section, we study the structure of stable matchings. For each m M , define
χ m = x + | W | : 1 j | W | x j K m ,
and a partial order m on χ m by
y m x iff w W { w 0 } , 0 j | W | w j R m w y j 0 j | W | w j R m w x j ,
where x 0 = K m 1 j | W | x j , and y 0 = K w 1 j | W | y j .
Note that m is defined by analogy with the first-order stochastic dominance order on probability distributions. In the case where K m = 1 , vectors x and y in χ m represent probability distributions over the types of women that m may match to. In that case y m x if and only if the lottery induced by y over W { w 0 } is worse than the lottery induced by x, for any von Neumann-Morgenstern utility function that is compatible with R m .
Letting χ w = x + | M | : 1 i | M | x i K w , we define w in an analogous way.
We introduce two partial orders on matchings. Suppose X and Y are matchings, then:
  • X M Y if, for all m M , X m m Y m
  • X W Y if, for all w W , X w w Y w .
Theorem 1.
( S ( M , W , P , K ) , M ) and ( S ( M , W , P , K ) , W ) are nonempty, complete, and distributive lattices; in addition, for X , Y S ( M , W , P , K )
1. 
X M Y if and only if Y W X ;
2. 
for all a M W , either X a a Y a or Y a a X a ;
3. 
for all m, w W x m , w = w W y m , w and for all w, m M x m , w = m M y m , w .
Theorem 1 presents a version, adapted to our model, of the standard results on matching theory. The proof is in Appendix B. Statement (1) is a “polarity of interests” result, saying that a stable matching X is better for men if and only if it is worse for women. Statement (2) says that the outcomes in two stable matchings are always comparable for an agent: note that a is an incomplete preference relation. Statement (3) is the “rural hospitals theorem,” which says that the same number of agents of a given type are matched in any two stable matchings.
Theorem 1 also implies that there are two stable matchings, X M and X W , such that for all stable matchings X,
X W M X M X M , and X M W X W X W .
We refer to X M as the man-optimal (M-optimal) stable matching, and to X W as the woman-optimal (W-optimal) stable matching. We also call X M and X W extremal stable matchings. A matching X is the unique stable matching if S ( M , W , P , K ) = X ; in this case X coincides with the man-optimal and the woman-optimal stable matchings.
Perhaps extremal stable matchings are unlikely to arise because they favor one side of the market over the other. One may instead be interested in matchings that present a compromise. The median stable matching provides such a compromise by assigning each agent a partner who is median ranked amongst all of his/her stable matching partners. Indeed in an experimental study on decentralized market, ref. [21] find that the median stable matching tends to emerge among stable matchings. As such, we may want to test whether an observed matching in field data is rationalizable as a median stable matching.
It is not obvious that median stable matchings exist. We shall first show that median stable matchings exist by only considering integral matchings that have integer entries, and then present a sufficient condition for rationalizability as a median stable matching.
We consider a market M , W , P , K , where all numbers K m , K w , and entries of matchings X are non-negative integers. Consequently, the number of stable matchings is finite, say n. Let S ( M , W , P , K ) = { X 1 , , X n } be the set of stable matchings. For each agent a we consider all stable outcomes and rank them according to a . All the outcomes are comparable by (2) of Theorem 1. More formally, let { X a ( 1 ) , , X a ( n ) } = { X a 1 , , X a n } and X a ( 1 ) a a X a ( n ) . Using these ranked outcomes and (1) of Theorem 1, we construct the matrices Y ( l ) for all l = 1 , , n such that Y m ( l ) = X m ( l ) and Y w ( l ) = X w ( n + 1 l ) . Matrix Y ( l ) assigns each type of men the l t h best outcome, and each type of women the l t h worst outcome among stable matching partners.
Proposition 1.
Y ( l ) is a stable matching.
The proof of Proposition 1 follows from the lattice structure of the set of stable matchings. It is essentially the same as the proofs of Theorem 3.2 in [22] and Theorem 1 of [17].
If n is odd we term Y ( n + 1 2 ) the median stable matching. If n is even we refer to Y ( n 2 ) (or Y ( n 2 + 1 ) ) as the median stable matching (of course the choice is arbitrary).
Corollary 1.
The median stable matching exists.

5. Testable Implications

Suppose that we are given a data of a matching X, and the corresponding M, W and K. Similar to [9], we assume that there are no “singles,” or unmatched agents, and so m K m = w K w , and w x m , w = K m for all m, and m x m , w = K w for all w. We call such a matching in which there are no singles complete. We ask when there are preferences for the different types of men and women such that X is a stable matching or an extremal stable matching (which is shown to exist in Section 4).
Definition 2.
A matching X isrationalizableif there exists a preference profile P = ( ( P m ) m M , ( P w ) w W ) such that X is a stable matching in M , W , P , K . A matching X isM-optimal (W-optimal) rationalizableif there is a preference profile P such that X is the M-optimal (W-optimal) stable matching in M , W , P , K .
We also want to know when a matching can be rationalized as the median stable matching.
Definition 3.
An integral matching X ismedian-rationalizableif there is a preference profile P such that X is the median stable matching in M , W , P , K .
To answer the questions, we define a graph ( V , L ) , where V consists of all the positive entries in X, and there is an edge ( v , v ) L if and only if v and v are either in the same row or in the same column in X. More formally, for each matching X we associate a graph ( V , L ) defined as follows. The set of vertices V is { ( m , w ) : m M , w W such that x m , w > 0 } , and an edge ( ( m , w ) , ( m , w ) ) L is formed for every pair of vertices ( m , w ) and ( m , w ) with m = m or w = w .
A previous study finds that the rationalizability of a matching depends on minimal cycles (defined in Section 2.2) of its associated graph: (The result in [9] is more general than what is stated here.)
Theorem 2
([9]).
1. 
A complete matching X is rationalizable if and only if its associated graph does not contain two connected, distinct, minimal cycles.
2. 
A complete matching X is M-optimal (W-optimal) rationalizable if and only if its associated graph has no minimal cycle.
For example, let matching X be the matrix on the left, with three types of men and women. Its associated graph is depicted on the right:
Games 12 00033 i001
The following two minimal cycles in this graph
Games 12 00033 i002
are connected; thus the matching is not rationalizable.
The rationalizability by stable matchings and extremal stable matchings only depends on whether each number x m , w is positive or 0. However, we find that median rationalizability depends on the value of x m , w as well as whether x m , w is positive or zero.
If v 0 , , v N is a minimal cycle, then N is an even number. We say that a minimal cycle c is balanced if
min { v 0 , v 2 , , v N 2 } = min { v 1 , v 3 , , v N 1 } .
(See the example below for an illustration of this condition.)
Theorem 3.
An integral complete matching X is median-rationalizable if it is rationalizable and if all minimal cycles of ( V , L ) are balanced.
The proof is in Appendix C. It is worth observing that, in our proof, we construct preferences such that the resulting number of stable matchings is odd. Therefore, our results do not depend on the choice of Y ( n 2 ) or Y ( n 2 + 1 ) as the median stable matching when n is even.
To provide some intuition for this result, consider the following example:
  • M = { m 1 , m 2 } ,
  • W = { w 1 , w 2 } ,
  • k m 1 = 6 , k m 2 = 5 , k w 1 = 4 , k w 2 = 7 ,
  • w 2 P m 1 w 1 , w 1 P m 2 w 2 , m 1 P w 1 m 2 , and m 2 P w 2 m 1 ,
where each man prefers all women to being unmatched and each woman prefers all men to being unmatched. In this market, there are five stable matchings as shown in Figure 1. Note that the preferences of each type of agent is shown by an arrow, for example the arrow in the first row represents the preference ranking of m 1 that type- w 2 woman is more preferred to type- w 1 woman. Therefore, the preferences are “clockwise” cyclical. These matchings differ from each other in that, starting with matching A, matchings B-E are formed by clockwise “rotations”—that is, by dissolving two couples { ( m 1 , w 1 ) , ( m 2 , w 2 ) } and repairing them as { ( m 1 , w 2 ) , ( m 2 , w 1 ) } . Given the clockwise preferences, moving from matching A to E, the matchings become increasingly preferred by the men, and at the same time, less preferred by the women.
Hence, matching C is the median stable matching, as the two stable matchings obtained by rotating this matching counterclockwise (i.e., A and B) are more preferred by the women, while the two obtained by rotating clockwise (i.e., D and E) are more preferred by the men. (In addition, one cannot rotate further clockwise beyond E, nor further counterclockwise beyond A, as one “runs out” of pairs in both cases.) Note also that only in the third matching is the cycle balanced: In the minimal cycle there are four vertices with entries 2 , 4 , 3 , 2 and when we take the minimum of the entries of the odd-numbered vertices and the minimum of the entries of the even-numbered vertices for any numbering of vertices preserving the order in which they appear in the cycle we get:
min { 2 , 3 } = 2 = min { 4 , 2 } .
Therefore, the minimal cycle for matching C is balanced. The balancedness condition ensures that one can rotate an equal number of times both in the clockwise direction and in the counterclockwise direction. Furthermore, note that the balancedness condition fails for the other matchings. For example, in matching B, min { 3 , 4 } = 3 1 = min { 3 , 1 } , there the minimal cycle in matching B is not balanced.
Note that the stability and rationalizability of a matching only depend on which entries are zero or positive. Thus if an observed matching X is canonicalized into X C ( x m , w c = 0 if x m , w = 0 , and x m , w c = 1 if x m , w > 0 ), then obviously X is rationalizable if and only if X C is rationalizable. Given the role of canonical matchings in rationalizability, the following corollary is of some interest.
Corollary 2.
A canonicalized matching X C is either not rationalizable or it is median-rationalizable.
Unfortunately, Theorem 3 provides only a sufficient condition for median-rationalizability. Corollary 2 gives a characterization of necessary conditions, but only for the case of canonical matchings. To sketch the boundaries of this result, we present two examples in Appendix A. Example Appendix A.1 shows that there are indeed matchings that are not rationalizable as median stable matchings, so Corollary 2 on canonical matchings does not extend to all aggregate matchings. Example Appendix A.2 shows that the sufficient condition in Theorem 3 is not necessary.

Author Contributions

All authors have equally contributed to all parts of the paper. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Conflicts of Interest

The authors declare no conflict of interest.

Appendix A. Examples

Appendix A.1. Matchings Rationalizable, but Not Median-Rationalizable

A rationalizable aggregate matching that cannot be rationalized as a median stable matching:
Games 12 00033 i003
The only way to rationalize this aggregate matching is to have a cycled preference profile, i.e., if w 1 P m 1 w 2 then m 2 P w 1 m 1 , w 2 P m 2 w 1 , and m 1 P w 2 m 2 . Similarly, if w 2 P m 1 w 1 then the preferences of agents are cycled in the opposite direction. Regardless of the choice, all the feasible aggregate matchings are stable, so there are 5 stable aggregate matchings in total. Therefore, the median aggregate stable matching is the one where each agent is matched to both possible partners twice, which is
Games 12 00033 i004

Appendix A.2. Median-Rationalizability Condition Is Not Necessary

The following example shows that the sufficient condition in Theorem 3 is not necessary. Suppose that there are four types of men, three types of women, and consider an aggregate matching
X = ( 0 0 2 0 2 1 1 3 0 3 1 0 ) .
We choose the preferences such that the graph corresponding to X is as follows. Note that we indicate preference with an arrow, so that for example x i , j x i , h means that w h P m i w j .
Games 12 00033 i005
Note that there is a cycle { ( m 3 , w 1 ) , ( m 3 , w 2 ) , ( m 4 , w 2 ) , ( m 4 , w 1 ) } and that this cycle is not balanced.
By “rotating” the cycle { ( m 3 , w 1 ) , ( m 3 , w 2 ) , ( m 4 , w 2 ) , ( m 4 , w 1 ) } in a clockwise direction we obtain the aggregate matching
( 0 0 2 0 2 1 0 4 0 4 0 0 ) ,
which is better for the men. However, by counterclockwise rotations we obtain the matchings
( 0 0 2 0 2 1 2 2 0 2 2 0 ) , ( 0 0 2 0 2 1 3 1 0 1 3 0 ) , ( 0 0 2 0 2 1 4 0 0 0 4 0 ) ,
which are all better for women than X.
Now, with the rationalization in the arrows above, the following “joint” rotation of the cycle and the upper entries of the matchings is stable as well:
( 0 1 1 0 1 2 0 4 0 4 0 0 ) , ( 0 2 0 0 0 3 0 4 0 4 0 0 ) .
These two matchings are better for the men. In all, then, under the rationalizing preferences as in the arrows, there are 7 stable matchings, and X is the median stable matching.
There is a crucial aspect of the example that makes this possible. Note that, if we are to rotate the upper part of the graph, we need preferences to be as indicated by the arrows. In particular, we must have x 2 , 3 x 1 , 3 for the graph to be rationalizable; then, to accommodate a > 0 entry in x 1 , 2 after the rotation, we must have x 1 , 3 x 1 , 2 , or otherwise we would get a blocking pair ( m 1 , w 3 ) . However, positive entries in x 1 , 3 and in x 3 , 2 imply that we need x 1 , 2 x 3 , 2 (the long dotted arrow in the graph in order to satisfy that x 1 , 3 x 1 , 2 . Now, a modification of X that has a positive entry in x 1 , 2 is only possible if we simultaneously set x 3 , 1 = 0 , as x 3 , 1 x 3 , 2 and x 1 , 2 x 3 , 2 . Hence the rotation of the upper side of the graph is not feasible under any of the modification of X that improve the matches of the women.
There is, therefore, an asymmetry in the graph that allows us to offset the unbalancedness of the number of men and women in the cycle.

Appendix B. Proof of Theorem 1

We split up the proof in short propositions.
Lemma A1.
( χ m , m ) is a complete lattice, with a largest and smallest element.
Proof. 
That ( χ m , m ) is a partially ordered set follows from the definition of m . Take a subset S m of χ m . We need to show that S m has the least upper bound and the greatest lower bound in ( χ m , m ) to complete the proof.
For every x χ m , define x 0 = K m 1 j | W | x j . By definition, for every x χ m , 0 j | W | x j = K m . Assign a new index { ( j ) : j = 0 , 1 , 2 , , | W | } over W { w 0 } such that
w ( 0 ) P m w ( 1 ) P m P m w ( | W | )
Let z ( 0 ) = sup { x ( 0 ) : x S m } . Define z ( i ) inductively as follows: z ( i ) = sup { x ( 0 ) + + x ( i ) : x S m } ( z ( 0 ) + + z ( i 1 ) ) .
Note that z ( j ) 0 and 0 j | W | z ( j ) = K m . We define z as a | W | -vector, ( z 1 , , z | W | ) , with respect to the original index. Clearly, z j 0 and 1 j | W | z j K m , so z χ m .
Claim 1.
zis the least upper bound of S m .
Proof. 
By definition, j = 0 i z ( j ) = sup { x ( 0 ) + + x ( i ) : x S m } which is greater than x ( 0 ) + + x ( i ) for all x S m and 0 i | W | . Therefore, z m x for all x S m , which means that z is an upper bound.
Suppose that z is another upper bound of S m . Therefore, z ( 0 ) + + z ( i ) x ( 0 ) + + x ( i ) for all x S m and 0 i | W | . If we take the supremum of the right hand side, then we get z ( 0 ) + + z ( i ) sup { x ( 0 ) + + x ( i ) : x S m } for all 0 i | W | . On the other hand, z ( 0 ) + + z ( i ) = sup { x ( 0 ) + + x ( i ) : x S m } . The last two impressions imply z ( 0 ) + + z ( i ) z ( 0 ) + + z ( i ) for all i, so z m z . Thus, z is the least upper bound of S m . □
Similarly, we can construct the greatest lower bound of S m as follows: u ( 0 ) = inf { x ( 0 ) : x S m } . Define u ( i ) inductively: u ( i ) = inf { x ( 0 ) + + x ( i ) : x S m } ( u ( 0 ) + + u ( i 1 ) ) . The proof that u is the greatest lower bound of of S m is similar to the proof that z is the least upper bound of S m , so it is omitted. □
For each m, let the choice C m be defined as follows. For a vector x + | W | , let C m ( x ) be the vector in
y χ m : y j x j , j = 1 , , | W |
that is maximal for m . In other words, if x represents the quantities of type of women available for m, C m chooses according to P m from the best choice downwards until filling quota K m . Note that if w 0 P m w j then y j = 0 , and if j : w j P m w 0 y j K m then y 0 = K m j : w j P m w 0 y j . Define C w analogously.
Proposition A1.
( S ( M , W , P , K ) , M ) is a nonempty and complete lattice.
Proof. 
A man pre-matching is a matrix A = ( a m , w ) M × W such that a m , w + and w a m , w K m . A woman pre-matching is a matrix B = ( b m , w ) M × W such that b m , w + and m b m , w K w .
We consider pairs ( A , B ) , where A is a man prematching, and B is a woman prematching, ordered by a partial order ≤. The order ≤ is defined as ( A , B ) ( A , B ) if
m M , w W , ( A m m A m and B w w B w ) .
The order ≤ is a product order of complete lattices by Lemma A1, so that the set of all pairs ( A , B ) ordered by ≤ is a complete lattice.
We define a function C, mapping pairs ( A , B ) of prematchings into pairs of prematchings. Fix ( A , B ) : For a type-m man, the number of type-w women who are willing to match with m at B is θ m , w = K w i : m i P w m b i , w . Let Θ = θ m , w , i.e., the | M | × | W | -matrix such that entry θ m , w is the number of type-w women who are willing to match with type m men at B. Similarly, let Ψ = ( ψ m , w ) be the | M | × | W | -matrix for which entry ψ m , w is the number of type-m men who are willing to match with type-w women at A. Now let C ( A , B ) = ( A ˜ , B ˜ ) where A ˜ m = C m ( Θ m ) and B ˜ w = C w ( Ψ w ) . Note that A ˜ is a man prematching and B ˜ is a woman prematching.
We now prove that C is isotone. Assuming that ( A , B ) ( A , B ) , we prove that C ( A , B ) C ( A , B ) .
Fix m. For any w, we have
i : m i P w m b i , w i : m P w m i b i , w ,
because B w w B w . As a consequence, a type-m man has weakly more women of each type willing to match with him in B than in B: i.e., Θ m Θ m . Thus C m ( Θ m ) m C m ( Θ m ) . Similarly, for a type w woman, C w ( Ψ w ) w C w ( Ψ w ) . It follows that C ( A , B ) C ( A , B ) . By Tarski’s fixed point theorem, there is a fixed point of C, and the set of fixed points of C is a complete lattice when ordered by ≤.
Let ( A , B ) be a fixed point of C, i.e., ( A , B ) = C ( A , B ) . Assume that a m , w > b m , w for some m and w. C w ( Ψ w ) = B w and a m , w > b m , w implies that although a m , w number of type-m men were available, only b m , w of them are chosen by C w . Therefore, all nonnegative entries in B w are at least as good as m with respect to R w . This implies that θ m , w = b m , w . Since b m , w < a m , w , we get θ m , w < a m , w which contradicts A m = C m ( Θ m ) . Therefore, a m , w = b m , w for all m and w. Hence the fixed point has the property that A = B , and they are not only a prematching but a matching as well since a man prematching that is also woman prematching is a matching.
Finally, we prove that the set of fixed points of C is the set of stable matchings. More precisely, ( A , A ) is a fixed point of C if and only if A is a stable matching.
Suppose that a fixed point ( A , A ) of C is not stable. By construction of C m and C w , A is individually rational. Then there is a blocking pair ( m , w ) . By definition of blocking pairs, there exist m M { m 0 } and w W { w o } such that m P w m , w P m w , a m , w > 0 , and a m , w > 0 . Now, the number of type-w women who are willing to match with m at A is
θ m , w = K w i : m i P w m a i , w a m , w + a m , w > a m , w ,
as a m , w > 0 . However, θ m , w > a m , w and a m = C m ( Θ m ) contradicts that there is w with w P m w and a m , w > 0 .
Suppose that A is a stable matching. We fix m and show that a m = C m ( Θ m ) where θ m , w = K w i : m i P w m a i , w . Suppose, for contradiction, that a m C m ( Θ m ) . Denote w j as the most preferred type of women (with respect to R m ) such that a m , j ( C m ( Θ m ) ) j . For all w j preferred to w j , a m , j = ( C m ( Θ m ) ) j . Thus, a m , j > ( C m ( Θ m ) ) j implies either a m , j > θ m , j or j : w j R m w j a m , j > K m , neither of which is possible. On the other hand, a m , j < ( C m ( Θ m ) ) j contradicts that A is stable. Although there are type w j women available more than a m , j , some type m men are matched to less preferred women. Then, there is j such that w j P m w j and a m , j > 0 , so ( m , w j ) is a blocking pair. Similarly, we can show that a w = C w ( Θ w ) , and therefore ( A , A ) = C ( A , A ) . □
Proposition A2.
Suppose that X and Y are stable matchings, then X M Y if and only if Y W X .
Proof. 
Suppose that X and Y are stable matchings such that X M Y , we show that Y W X . The other direction of the claim can be proved analogously.
Consider the construction of C in the proof of Proposition A1: Let Ψ and Ψ correspond to the matrices for X and Y as in the proof. Since X and Y are stable matchings we have C ( X , X ) = ( X , X ) and C ( Y , Y ) = ( Y , Y ) . Since X m Y for all m, Ψ m , w Ψ m , w for all m and w. Therefore, Y w = C w ( Ψ w ) w C w ( Ψ w ) = X w for all w, which implies that Y W X . □
Proposition A3.
Suppose that X and Y are two stable matchings. Then for any men or women type a, either X a a Y a or Y a a X a . Consequently, X a a Y a = max a { X a , Y a } and X a a Y a = min a { X a , Y a } .
Proof. 
We only prove the first part that either X a a Y a or Y a a X a , in three steps depending on whether X and Y have integer, rational, and real entries. The second part follows immediately from the first part.
Case 1 (Integer Entries): We first start with the case when X and Y have integer entries as well as K w and K m . From M , W , P , K , we create a many-to-one matching market (of colleges and students) as follows.
The set of types of men remains the same; interpreted as the set of colleges. A college m has a capacity of K m . Whereas, each type-w woman is split into K w copies, all of which have the same preferences P w over colleges; women types are interpreted as students. On the other hand, m’s preferences P m replace w in P m with her copies enumerated from 1 to K w , in increasing order. Denote w j ’s l t h copy by w j l . So w j l P m w j k if and only if k > l . In addition, each college has responsive preferences over groups of students. The new matching market with | M | colleges and w K w students is a many-to-one matching markets where an outcome for a college is a group of students, and an outcome for a student is either a college or being single.
Now, we construct a new matching, X , in the new market from X. (The new matching is a many-to-one matching, which is not an aggregate matching. Nevertheless, we use the aggregate matching notation to stress the relations between X and X, and Y and Y.) It is enough to describe the matches of students in X . Rank woman w’s outcomes in X in decreasing order according to her preference P w . Let the l t h copy of w j , w j l , match to the l t h highest outcome of w j in X. Similarly, construct Y from Y.
We claim that X and Y are stable matchings in the new market. Suppose for contradiction that X is not a stable matching. Since X is individually rational by construction, there exists a blocking pair ( m , w j l ) . This means that w j l ’s match is worse than m. Similarly, m’s match includes a student worse than w j l : this agent cannot be w j k where k < l by definition of P m , and it cannot be w j k where k > l because by construction w j k ’s match is worse than w j l ’s match with respect to w j . Hence, one of m’s matches is worse than w j l , and not a copy of w j . This means that ( m , w j ) forms a blocking pair in X: A contradiction to the stability of X. Therefore, X must be stable. Similarly, Y is also stable.
Now, by Theorem 5.26 of [12], for any college m the outcomes in X and Y are comparable. This means that the responsive preferences over groups of students inherited from P m , which is equivalent to the first-order stochastic dominance, can compare the outcomes of m in these two stable matchings. Therefore, m can compare the outcomes in X and Y since P m is a coarser order than P m .
An analogous argument shows that w can compare the matching outcomes in X and Y.
Case 2 (Rational Entries): Suppose for now that all entries of X and Y are rational numbers as well as K w and K m . Define a new matching market from M , W , P , K as follows.
M, W, and P are the same. We change the capacities as follows. Find a common factor of denominators in all entries in X and Y, say r, and multiply all capacities by r. Therefore, the new market is M , W , P , r K . Define X = r X and Y = r Y with non-negative integer entries. By the argument above, for any agent a, the matchings in r X and r Y can be compared with respect to a which implies that the outcomes in X and Y can also be compared.
Case 3 (Real Entries): Suppose now that entries of X and Y are real numbers. We construct two sequences of matrices, X ( n ) and Y ( n ) , as follows:
  • X ( n ) and Y ( n ) have rational entries,
  • x i j ( n ) = 0 x i j = 0 and y i j ( n ) = 0 y i j = 0 for all i , j ,
  • the sum of entries in row i and column j is the same for X ( n ) and Y ( n ) , and
  • x i j ( n ) x i j and y i j ( n ) y i j as n for all i , j .
By construction, stability of X and Y imply stability of X ( n ) and Y ( n ) for the same market with adjusted capacities. By the argument above, for each type a, x a ( n ) and y a ( n ) can be compared with respect to a . Take a subsequence { n l } such that the ordering is the same for all entries. Therefore, x a ( n l ) a y a ( n l ) for all l or y a ( n l ) a x a ( n l ) for all l. By taking l to we get that either x a a y a in the former case, or y a a x a in the latter since ( 4 ) implies x · , j ( n ) x · , j and y i , · ( n ) y i , · as n for all i , j . □
We have shown that ( S ( M , W , P , K ) , M ) is a lattice in Proposition A1. Using the proposition above, we show that the lattice, ( S ( M , W , P , K ) , M ) , is distributive.
Proposition A4.
( S ( M , W , P , K ) , M ) is a distributive lattice.
Proof. 
Suppose that X, Y, and Z are stable matchings. We are going to prove that type a has the same matching in X ( Y Z ) and ( X Y ) ( X Z ) for all agent types a:
( X ( Y Z ) ) a = min { X a , max { Y a , Z a } } = max { min { X a , Y a } , min { X a , Z a } } = max { ( X Y ) a , ( X Z ) a } = ( ( X Y ) ( X Z ) ) a ,
where min and max operators are defined with respect to a and where we repeatedly use Proposition A3.
The proof that X ( Y Z ) = ( X Y ) ( X Z ) is analogous. □
Proposition A5.
Suppose that X and Y are stable matchings. Then 1 j | W | x i j = 1 j | W | y i j for all i and similarly 1 i | M | x i j = 1 i | M | y i j for all j.
Proof. 
The proof has the same structure as in the proof of Proposition A3: it has three steps depending on whether X and Y have integer, rational, and real entries.
Case 1 (Integer Entries): We first start with the case when X and Y have integer entries as well as K m for all m and K w for all w. From M , W , P , K , we create a many-to-one matching market and also stable matchings X and Y in this new market as in the proof of Proposition A3.
Now, by Theorem 5.12 of [12], the set of positions filled for any m in X and Y are the same. Therefore, 1 j | W | x i j = 1 j | W | y i j for all i. Similarly, 1 i | M | x i j = 1 i | M | y i j for all j.
Case 2 (Rational Entries): Suppose for now that all entries of X and Y are rational numbers as well as K a for all a. Define a new matching market from M , W , P , K as follows.
M, W, and P are the same. We change the capacities as follows. Find a common factor of denominators in all entries in X and Y, say r, and multiply all capacities by r. Therefore, the new market is M , W , P , r K . Define X = r X and Y = r Y with non-negative integer entries.
By the argument above, 1 j | W | r x i j = 1 j | W | r y i j for all i and 1 i | M | r x i j = 1 i | M | r y i j for all j. The conclusion follows.
Case 3 (Real Entries): Suppose now that entries of X and Y are real numbers. We construct two sequences of matrices, X ( n ) and Y ( n ) , as follows:
  • X ( n ) and Y ( n ) have rational entries,
  • x i j ( n ) = 0 x i j = 0 and y i j ( n ) = 0 y i j = 0 for all i , j ,
  • the sum of entries in row i and column j is the same for X ( n ) and Y ( n ) , and
  • x i j ( n ) x i j and y i j ( n ) y i j as n for all i , j .
By construction, stability of X and Y imply stability of X ( n ) and Y ( n ) for the same market with adjusted capacities. By the argument above, 1 j | W | x i j ( n ) = 1 j | W | y i j ( n ) for all i and 1 i | M | x i j ( n ) = 1 i | M | y i j ( n ) . If we take the limit of these equalities as n , we get the desired equalities. □

Appendix C. Proof of Theorem 3

Let X be a rationalizable integral complete matching. Suppose that all cycles of the associated graph ( V , L ) are balanced. Direct the edges of ( V , L ) such that each cycle is oriented as follows: if v 0 , , v N is a cycle, then the edge ( v n , v n + 1 ) L is oriented such that d ( v n + 1 , v n ) = 1 , which we denote by v n v n + 1 . For each path v 0 , , v N , direct the edges in a similar way. If the matching X is rationalizable, then such an orientation of the edges exists and defines a rationalizing preference profile P (Theorem 2, Part 1). The rationalizing preferences have the property that if x i , j = 0 and x i , j > 0 then w j m i w j if i = i , and m i w j m i if j = j .
First, if X has no cycles, then it is rationalizable as the unique stable matching (Theorem 2, Part 2), so there is nothing to prove, as a unique stable matching is also the median stable matching. Suppose then that X has at least one cycle c = v 0 , , v N . Enumerate the vertexes of the cycle such that v n v n + 1 in the orientation (directed graph) of ( V , L ) above, and v 0 lies in the same row as v 1 . Let
Θ = min v 0 , v 2 , , v N 2 = min v 1 , v 3 , , v N 1 .
Let ε be the set of all | M | × | W | matrices E of integer numbers such that
  • e i , j = 0 if ( i , j ) is not in the cycle c;
  • for all i and j, h e i , h = 0 and l e l , j = 0 ; and
  • | e i , j | Θ .
We want to make two observations about the matrices in ε . First, ( X + E ) i , j > 0 x i , j > 0 , so X + E is a stable matching for all E ε . Second, E ε if and only if E ε ; and E ε is such that X i m i ( X + E ) i if and only if ( X E ) i m i X i . Similarly, E ε is such that X j w j ( X + E ) j if and only if ( X E ) j w j X j .
We need to prove that any stable matching Y X in the resulting market M , W , P , K must be obtained from X through matrices in ε : Then X is a median stable matching.
First, we prove that y i , j x i , j only if x i , j is a vertex in a minimal cycle of X. The number of single agents of each type is the same in X as in Y (Proposition A5; in this case it is zero, as X has no single agents). So, if x i , j < y i , j then there is h j and l i such that y i , h < x i , h and y l , j < x l , j . Similarly, if x i , j > y i , j then there is h j and l i such that y i , h < x i , h and y l , j < x l , j . Hence, we can apply this observation repeatedly, starting from any ( i , j ) with x i , j y i , j and obtain a sequence ( i 1 , j 1 ) , , ( i N , j N ) with ( i 1 , j 1 ) = ( i N , j N ) such that for each n ( mod N ):
  • ( x i n , j n y i n , j n ) ( x i n + 1 , j n + 1 y i n + 1 , j n + 1 ) < 0
  • i n i n + 1 j n = j n + 1 .
Claim 2.
For n = 1 , , N , x i n , j n > 0 .
Proof. 
Suppose for contradiction that 0 = x i 1 , j 1 < y i 1 , j 1 . Without loss of generality, assume that i 1 = i 2 . By definition of the rationalization P, we have that w j 2 P m i 1 w j 1 , as x i 1 , j 1 = 0 and x i 1 , j 2 > y i 1 , j 2 0 . We can now show that if ( i n , j n ) and ( i n + 1 , j n + 1 ) differ in i, then j n prefers m i n + 1 to m i n ; and that if they differ in j, then i n prefers w j n + 1 to w j n . This fact, which we prove in the next paragraph, establishes the contradiction: i N i N 1 , but m i N 1 P w i N m i N by definition of P and because 0 = x i N , j N = x i 1 , j 1 .
To prove the fact, we reason by induction. We have already established that w j 2 P m i 1 w j 1 . Suppose that w j n P m i n w j n 1 . By Property 1 of the sequence ( i n , j n ) n = 1 N , either x i n 1 , j n 1 > 0 and x i n + 1 , j n + 1 > 0 ; or y i n 1 , j n 1 > 0 and y i n + 1 , j n + 1 > 0 (or both hold). Then the stability of X and Y implies that m i n + 1 P w j n m i n . The proof for the case when w i n P w i n m i n 1 is similar. □
The claim implies that the sequence v n = x i n , j n is a cycle in ( V , L ) . Thus a stable matching Y can only differ from X in vertexes that are part of a cycle of ( V , L ) .
Second, we prove that E Y X ε . We established above that e i , j 0 only if x i , j is a vertex in a cycle. We now prove that | e i , j | Θ . Clearly, e i , j x i , j Θ . We show that if e i , j > 0 then there is h such that e i , j + e i , h = 0 .
If e i , j > e i , h for all h i then there is h 1 and h 2 such that some type- m i men of type m i who are married to women of type h 1 and h 2 in X are married to women of type w j in Y. Then we can define two cycles, and x i , j would be a vertex in both of them. The first cycle has ( x i , j , x i , h 1 ) as the first edge, and the remaining edges defined inductively, by the definition of ( i n , j n ) above. The second cycle has ( x i , j , x i , h 2 ) as the first edge, and the remaining edges defined inductively. The resulting two cycles would be connected, which contradicts the hypothesis that X is rationalizable. So there must exist some h with e i , j e i , h . An analogous argument applied to e i , h implies that e i , j e i , h ; so e i , j = e i , h . Then, e i , j Θ , as e i , h Θ .

References

  1. Gale, D.; Shapley, L.S. College Admissions and the Stability of Marriage. Am. Math. Mon. 1962, 69, 9–15. [Google Scholar] [CrossRef]
  2. Abdulkadiroğlu, A.; Pathak, P.; Roth, A.; Sönmez, T. The Boston Public School Match. Am. Econ. Rev. 2005, 95, 368–371. [Google Scholar] [CrossRef] [Green Version]
  3. Abdulkadiroğlu, A.; Pathak, P.A.; Roth, A.E. The New York City High School Match. Am. Econ. Rev. 2005, 95, 364–367. [Google Scholar] [CrossRef] [Green Version]
  4. Choo, E.; Siow, A. Who Marries Whom and Why. J. Political Econ. 2006, 114, 175–201. [Google Scholar] [CrossRef] [Green Version]
  5. Galichon, A.; Salanie, B. Matching with Trade-Offs: Revealed Preferences over Competing Characteristics; Mimeo, Ecole Polytechnique: Paris, France, 2009. [Google Scholar]
  6. Echenique, F.; Lee, S.; Shum, M. The money pump as a measure of revealed preference violations. J. Political Econ. 2011, 119, 1201–1223. [Google Scholar] [CrossRef] [Green Version]
  7. Varian, H.R. Non-Parametric Analysis of Optimizing Behavior with Measurement Error. J. Econom. 1985, 30, 445–458. [Google Scholar] [CrossRef] [Green Version]
  8. Echenique, F.; Lee, S.; Shum, M. Partial identification in two-sided matching models. In Structural Econometric Models; Emerald Group Publishing Limited: Bingley, UK, 2011; pp. 117–139. [Google Scholar]
  9. Echenique, F.; Lee, S.; Shum, M.; Yenmez, M.B. The Revealed Preference Theory of Stable and Extremal Stable Matchings. Econometrica 2013, 81, 153–171. [Google Scholar] [CrossRef] [Green Version]
  10. Chambers, C.; Echenique, F. Revealed Preference Theory; Cambridge University Press: Cambridge, UK, 2016; Volume 56. [Google Scholar]
  11. Echenique, F. What Matchings Can Be Stable? The Testable Implications of Matching Theory. Math. Oper. Res. 2008, 33, 757–768. [Google Scholar] [CrossRef]
  12. Roth, A.; Sotomayor, M. Two-sided Matching: A Study in Game-Theoretic Modelling and Analysis. In Econometric Society Monographs; Cambridge University Press: Cambridge, UK, 1990; Volume 18. [Google Scholar]
  13. Chen, P.; Egesdal, M.; Pycia, M.; Yenmez, M.B. Median stable matchings in two-sided markets. Games Econ. Behav. 2016, 97, 64–69. [Google Scholar] [CrossRef] [Green Version]
  14. Fleiner, T. A Fixed-Point Approach to Stable Matchings and Some Applications. Math. Oper. Res. 2003, 28, 103–126. [Google Scholar] [CrossRef] [Green Version]
  15. Klaus, B.; Klijn, F. Procedurally fair and stable matching. Econ. Theory 2006, 27, 431–447. [Google Scholar] [CrossRef] [Green Version]
  16. Klaus, B.; Klijn, F. Smith and Rawls share a room: Stability and medians. Soc. Choice Welf. 2010, 35, 647–667. [Google Scholar] [CrossRef] [Green Version]
  17. Schwarz, M.; Yenmez, M.B. Median Stable Matching for Markets with Wages. J. Econ. Theory 2011, 146, 619–637. [Google Scholar] [CrossRef]
  18. Teo, C.-P.; Sethuraman, J. The geometry of fractional stable matchings and its applications. Math. Oper. Res. 1998, 23, 874–891. [Google Scholar] [CrossRef]
  19. Chambers, C.P.; Echenique, F. The Core Matchings of Markets with Transfers. Am. Econ. J. Microeconomics 2015, 7, 144–164. [Google Scholar] [CrossRef] [Green Version]
  20. Demuynck, T.; Salman, U. On the Revealed Preference Analysis of Stable Aggregate Matchings; Working Paper; ECARES: Brussels, Belgium, 2020. [Google Scholar]
  21. Echenique, F.; Yariv, L. An Experimental Study of Decentralized Matching; Mimeo, California Institute of Technology: Pasadena, CA, USA, 2012. [Google Scholar]
  22. Klaus, B.; Klijn, F. Median stable matching for college admissions. Int. J. Game Theory 2006, 34, 1–11. [Google Scholar] [CrossRef] [Green Version]
Figure 1. Five stable matchings (matching C is median-stable).
Figure 1. Five stable matchings (matching C is median-stable).
Games 12 00033 g001
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Echenique, F.; Lee, S.; Shum, M.; Yenmez, M.B. Stability and Median Rationalizability for Aggregate Matchings. Games 2021, 12, 33. https://0-doi-org.brum.beds.ac.uk/10.3390/g12020033

AMA Style

Echenique F, Lee S, Shum M, Yenmez MB. Stability and Median Rationalizability for Aggregate Matchings. Games. 2021; 12(2):33. https://0-doi-org.brum.beds.ac.uk/10.3390/g12020033

Chicago/Turabian Style

Echenique, Federico, SangMok Lee, Matthew Shum, and M. Bumin Yenmez. 2021. "Stability and Median Rationalizability for Aggregate Matchings" Games 12, no. 2: 33. https://0-doi-org.brum.beds.ac.uk/10.3390/g12020033

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop