Abstract
We consider the theoretical properties of a model which encompasses bipartite matching under transferable utility on the one hand and hedonic pricing on the other. This framework is intimately connected to tripartite matching problems (known as multi-marginal optimal transport problems in the mathematical literature). We exploit this relationship in two main ways; first, we show that a known structural result from multi-marginal optimal transport can be used to establish an upper bound on the dimension of the support of stable matchings. Next, assuming the distribution of agents on one side of the market is continuous, we identify a condition on their preferences that ensures purity and uniqueness of the stable matching; this condition is a variant of a known condition in the mathematical literature, which guarantees analogous properties in the multi-marginal optimal transport problem. We exhibit several examples of surplus functions for which our condition is satisfied, as well as some for which it fails.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
This paper considers the theoretical properties of a general model, which encompasses both the transferable utility matching model of Shapley and Shubik (1971) and Becker (1973), extended to continuous type spaces by Gretsky et al. (1992), and the hedonic model of Rosen (1974), whose theoretical properties (in a continuous, multi-dimensional setting) were studied by Ekeland (2010), Ekeland (2005) and Chiappori et al. (2010).
In the hedonic model, agents on two sides of a market (e.g., buyers and sellers) are matched together according to their preferences to exchange certain goods, assuming they are indifferent to which partner they do business with. Letting X and Y be spaces of buyers and sellers, respectively, and Z the set of goods that can feasibly be produced, we assume that agents’ preferences are encoded respectively by functions u(x, z) and v(y, z), expressing the utilities of buyer \(x \in X\) and seller \(y \in Y\) if they purchase or produce a product of type \(z \in Z\), respectively. The main problem is then to determine which buyers match with which sellers, which goods they exchange and the prices they exchange for them, in equilibrium.
In the matching model, agent x (respectively y) has a preference u(x, y) [respectively v(x, y)] to match with agent y (respectively x). Together, a match between x and y generates a joint utility, or surplus, \(s(x,y)=u(x,y) +v(x,y)\). Utility can then be transferred in the form of a payment from one agent to the other; by this mechanism, the total surplus s(x, y) can be divided in any way between the two agents. Here the good z to be exchanged (or the nonmonetary terms of the contract) does not affect agents’ preferences.
Recently, Dupuy et al. (2015) formulated a hybrid model in which agents have preferences which depend on both their partners and the product under exchange. In that paper, x and y represent agents on different sides of a marriage market, and z the location where they would agree to settle; however, as was noted by the authors, the model has much wider potential applicability. In family economics, for instance, when a couple match together, there are many conditions of the match which can affect the surplus generated. In addition to location, a couple may choose to marry or to live together without marrying, and to have one or more children, for example. These decisions affect the surplus differently depending on the couple; see, for example, Mourifie and Siow (2014). When considering buyers and sellers, it also seems natural in many scenarios to allow consumers’ preferences to depend on both the producer he does business with and the good he receives. For example, consumers often exhibit brand loyalty; they may be willing to pay more (for the same good) when dealing with one company rather than another. On the other hand, producers’ preferences can also depend on the consumers they sell to; for example, mortgage lenders often offer better rates to clients with higher credit scores, reflecting the fact that they prefer to do business with more creditworthy borrowers. Another example occurs in insurance models like the one of Rothschild and Stiglitz (1976); insurance companies offer the same policy at different prices to different consumers depending on how their characteristics influence the risk of a claim.
The theoretical properties of these hybrid models do not seem to have received much attention. In this paper, we study this model when the type spaces X and Y and the space of feasible contracts Z are all continuous. In both the classical matching problem, and the hedonic problem, conditions are well known which ensure that the equilibrium, or stable matching, is unique and pure. In the matching problem, this condition is known as the twist, or generalized Spence–Mirrlees condition. Purity means that the matching (which is a measure on the product space \(X \times Y \times Z\)—see Sect. 2) concentrates on a graph [\(\{x,F_Y(x),F_Z(x)\}\) over the first variable; economically, this means that all buyers of type x choose to buy a good of type \(z=F_Z(x)\) from a buyer of type \(y=F_Y(x)\)].
One natural question in the present setting is to identify conditions on the joint surplus function (which is now a function of x, y and z, without any specific form) in the more general model which ensure purity and uniqueness of the stable match.
Both the strict matching and hedonic problems have well-established connections to a variational problem known as optimal transportation; economically, this is exactly the social planner’s problem of matching the agents in order to maximize their average surplus (a detailed introduction to this subject can be found in the books of Galichon 2016; Santambrogio 2015; Villani 2009). The generalized model studied here turns out to have natural connections to both the classical optimal transport problem, and variant of it where there are three (rather than two) measures to be matched (known in the mathematics literature as a multi-marginal optimal transport problem). Our main contribution here is to establish and exploit these connections to uncover insights into matching patterns for this generalized matching-hedonic model. As immediate applications of the multi-marginal optimal transport point of view, we establish existence of stable matchings, under quite general conditions, and an upper bound on the dimension of their supports (which are measures on the product space \(X \times Y \times Z\)) in terms of the signature of the off-diagonal part of the Hessian of s. We then find conditions on the functions u and v, and the measures \(\mu \) and \(\nu \) ensuring uniqueness and purity of equilibria. Our condition here is a weaker variant of the twist on splitting sets condition, which is known to ensure purity and uniqueness in the multi-marginal optimal transport problem; we will call the condition for the hybrid matching problem the twist onz-trivial splitting sets.
In addition, due to recent work of Chiappori et al. (2010), it is now clear that the hedonic problem is actually equivalent to a matching problem, with a surplus equal to the maximum possible joint utility for buyers and sellers, among all possible goods; we often refer to the analogous maximized surplus \(\bar{s}(x,y)\) [see (6)] in our setting as the reduced surplus, as we have reduced the number of variables from three to two (that is, \(\bar{s}\) depends only on x and y). This equivalence persists in our setting. In this simplified but equivalent bipartite matching setting, the twist condition on the maximal surplus (6) ensures the uniqueness and purity of the stable match. It is desirable then, to understand when the twist condition on the surplus (6) holds; we show that, under certain conditions, this is essentially equivalent to our twist on z-trivial splitting sets condition on s. I am not aware of any nontwisted surplus s(x, y) for which purity holds for general measures \(\mu \) and \(\nu \); therefore, the equivalence described above suggests that, in the hybrid problem, twist on z-trivial splitting sets may be a necessary condition for purity. The equivalence also lets us adapt known results from two marginal optimal transport to derive conditions under which stable matchings are unique, but not necessarily pure.
In the next section, we outline the model under consideration and establish some of its basic properties. In Sect. 3, we use the connection with multi-marginal optimal transport to establish a result on the local structure (i.e., the dimension of the support) of stable matchings. In Sect. 4, we develop our sufficient condition for purity and uniqueness of stable matchings, while Sect. 5 is devoted to the reformulation of our problem as a strict matching problem (with a reduced surplus function) and the demonstration that the classical twist condition of \(\bar{s}\) is equivalent to our twist on z-trivial splitting sets condition on the surplus s. Section 6 presents some examples, while we offer a brief conclusion in the final section.
Short, simple proofs of mathematical results are included within the body of the paper; longer or more involved mathematical arguments are relegated to an “Appendix”, to avoid interrupting the flow of the paper.
2 The general model and basic properties
We consider heterogeneous distributions of buyer and seller types, encoded respectively by compactly supported Borel probability measures \(\mu \) on \(X \subseteq \mathbb {R}^{n_x}\) and \(\nu \) on \(Y \subseteq \mathbb {R}^{n_y}\), and a set of feasible goods, parameterized by \(Z \subseteq \mathbb {R}^{n_z}\). The sets X, Y and Z will be the closures of open and bounded sets \(X^0,Y^0\) and \(Z^0\), respectively, with smooth boundaries. Each buyer will buy exactly one good; each seller will produce and sell exactly one good.Footnote 1
The preference of a buyer of type x to purchase a good of type z from a seller of type y will be given by a function u(x, y, z), while the preference of a seller of type y to sell a good of type z to a buyer of type x is given by v(x, y, z). We will assume throughout the paper that u and v are uniformly Lipschitz; stronger regularity hypotheses will be adopted at various specific points. Utilities will be quasilinear, so that the utility derived by a buyer purchasing a good of type z from a seller of type y for a price p will be
and similarly, the utility derived by a seller selling a good of type z to a buyer of type x for a price p will be
We will denote by s(x, y, z) the total, or joint, surplus generated when a buyer of type x purchases a good of type z from a seller of type y:
As the utility can freely be transferred from one partner to another, the analytical properties of s, rather than u and v separately, are most relevant in determining the purity and uniqueness of equilibrium.
We define a matching as a probability measure \(\gamma \) on \(X \times Y \times Z\) whose first marginal is \(\mu \) and whose second marginal is \(\nu \); that is
for all Borel \(A \subseteq X\), \(B \subseteq Y\). This represents an assignment of the agents in the sets X and Y into pairs and assigns to each pair a good from the set Z to be exchanged. We will denote by \(\varGamma _{XYZ}(\mu ,\nu )\) the set of all matchings of \(\mu \) and \(\nu \) on \(X \times Y \times Z\).
We will say that a mapping \(T:X \rightarrow Y\)pushes\(\mu \)forward to\(\nu \), and write \(\nu =T_{\#}\mu \) if \(\mu (T^{-1}(B)) =\nu (B)\) for all Borel \(B \subseteq Y\).
For a given measure \(\gamma \) on \(X \times Y \times Z\), we denote by \(\gamma _{XY}\) its projection onto \(X \times Y\), a measure on \(X \times Y\) defined by \(\gamma _{XY}(C) =\gamma (C \times Z)\) for any \(C \subset X \times Y\). The measures \(\gamma _{XZ}\) and \(\gamma _{YZ}\) are defined analogously. Note that \(\gamma _{XY} = (P_{XY})_\# \gamma \), where \(P_{XY}: X \times Y \times Z \rightarrow X\times Y\) is the projection map, \(P_{XY}(x,y,z) :=(x,y)\). It is also worth noting that if \(\gamma \) is a matching of \(\mu \) and \(\nu \), then \(\gamma _{XY}\) has marginals \(\mu \) and \(\nu \).
Given a matching \(\gamma \), functions U(x) and V(y) are called payoff functions for \(\gamma \) if
for \(\gamma \) almost every (x, y, z). For any matching, points in the supportFootnote 2\(spt(\gamma )\) of \(\gamma \) (and hence in the equality set \(\{U(x)+V(y) = u(x,y,z) + v(x,y,z)\}\) for payoff functions U and V) represent buyer–seller pairs who are matched together by \(\gamma \), together with the good they exchange. Payoff functions then represent a division of the surplus between matched pairs. Given such a triple \((x,y,z) \in spt(\gamma )\) and payoffs U(x) and V(y), the priceFootnote 3 that y charges x in exchange for the good z is given
The matching is called stable if there exist payoff functions U(x) and V(y) such that
for all (x, y, z).
The condition (2) ensures stability of the matching in the sense that no pair of unmatched agents would both prefer to leave their current partners and match together. If (2) failed, so that \(U(x)+V(y) < u(x,y,z) + v(x,y,z)\) for some unmatched buyer–seller–good triple (x, y, z) [that is, \((x,y,z) \notin spt(\gamma )\)], then buyer x and seller y would be incentivized to exchange good z for a price p such that
resulting in increased payoffs \(\bar{U}(x) := u(x,y,z)-p >U(x)\) and \(\bar{V}(y) := v(x,y,z)+p >V(y)\) for both x and y.
Finally, we turn our attention to purity of matchings. There are several relevant notions of purity here, corresponding to various relationships between buyers, sellers, and goods.
Definition 1
A matching \(\gamma \) is called buyer–seller pure if its projection \(\gamma _{XY}\) onto \(X \times Y\) is concentrated on a graph over X; that is, if there exists a function \(F_Y: X \rightarrow Y\) such that \(\gamma _{XY}=(Id,F_Y)_\# \mu \). We say \(\gamma \) is buyer–good pure if its projection \(\gamma _{XZ}\) onto \(X \times Z\) is concentrated on a graph over X; that is, if there exists a function \(F_Z: X \rightarrow Z\) such that \(\gamma _{XZ}=(Id,F_Z)_\# \mu \).
We will call \(\gamma \)buyer–(seller, good) pure (or simply pure) if it is both buyer–seller and buyer–good pure, which means that \(\gamma \) is concentrated on a graph over X. In other words, there exist functions \(F_Y: X \rightarrow Y\) and \(F_Z: X \rightarrow Z\) such that \(\gamma =(Id,F_Y,F_Z)_\# \mu \).
Note that one could analogously define several other notions of purity (seller–buyer, good–seller, etc). The economic interpretation of, for instance, buyer–seller purity is that there is no randomness in each buyer x’s choices of the seller \(y=F_Y(x)\) he works with; buyers of the same type will (almost) always buy goods from sellers of the same type.
One of our main contributions in this paper is to identify a condition on the surplus that ensures full, buyer–(seller, good) purity; as we will see, the same condition will guarantee uniqueness of the stable matching as well.
2.1 Variational interpretation
Much like the classical matching and hedonic problems, the problem of finding stable matchings in our setting has a variational formulation. Consider the problem of maximizing
over the set \(\varGamma _{XYZ}(\mu ,\nu )\) of all matchings of \(\mu \) and \(\nu \) (that is, maximizing the total surplus of all agents).
Theorem 1
A matching \(\gamma \) is a stable matching if and only if it is optimal in (3).
This result is well known in the classical matching case of Gretsky et al. (1992), when the surplus s (and hence the matching measures \(\gamma \) as well) depends only on x and y. For general hybrid surplus functions, s(x, y, z), the result is proven in the discrete case by Dupuy et al. (2015). The proof here requires no new ideas but is included in an “Appendix” in the interest of completeness.
By standard arguments, Theorem 1 implies existence of a stable matching.
Corollary 1
There exists at least one stable matching \(\gamma \).
Proof
The proof is by continuity and compactness and is completely standard.
Continuity of s immediately implies continuity of
with respect to weak convergence of measures. The Riesz–Markov theorem identifies the dual of the set \(C( X \times Y \times Z)\) of continuous functions on \(X \times Y \times Z\) with the set \(\mathcal M( X \times Y \times Z)\) of regular Borel measures on \(X \times Y \times Z\), with norm given by total variation (which is total mass, for positive measures). The Banach–Alaoglu theorem then asserts that the closed unit ball in \(\mathcal M(X \times Y \times Z)\) is compact. The set \(\varGamma _{XYZ}(\mu ,\nu )\) is clearly a weakly closed subset of this unit ball, and therefore is itself compact. The existence of a maximizer of (3) over the set \(\varGamma _{XYZ}(\mu ,\nu )\), and hence a stable matching by Theorem 1, then follows immediately. \(\square \)
2.2 Connection to tripartite matching
Problem (3) is closely related to a tripartite matching problem (also known, in the mathematical literature, as the multi-marginal optimal transport problem), where in addition to prescribing the distributions of agents \(\mu \) on X, \(\nu \) on Y, one fixes the distribution \(\alpha \) on Z.Footnote 4 Finding a stable matching in this problem is equivalent to the following maximization:
where the maximum is over the set \(\varGamma _{XYZ}(\mu ,\nu ,\alpha )\) of positive measures on \(X \times Y \times Z\) whose marginals are \(\mu , \nu \) and \(\alpha \). The underlying relationship between tripartite matching and our present problem is that the variational problem (3) (and therefore the equivalent hybrid matching-hedonic problem) is equivalent to maximizing \(T(\mu ,\nu ,\alpha )\) over the set of all probability measures \(\alpha \) on Z.
There is a growing mathematical and economic literature on tripartite (or, more generally, multipartite) matching, which will be useful in what follows, as some of the results there can be translated to the present setting. In particular, an immediate application is an upper bound on the dimension on the support of the stable matching, which is presented in the next section. In addition, conditions ensuring purity and uniqueness in (4) have been identified by Kim and Pass (2014). In a subsequent section, we use this as a guide to develop a similar condition for problem (3); our condition here is somewhat weaker than the one of Kim and Pass (2014), as we do not require purity in (4) for every choice of \(\alpha \); we require it only for those which maximize\(\alpha \mapsto T(\mu ,\nu ,\alpha )\).
3 Dimension of the support of matching measures
Even when the conditions for purity and uniqueness developed in the next section fail, there are results known about the local structure of the optimizer in (4); as any stable matching \(\gamma \) maximizes (4), taking \(\alpha \) to be its z marginal, these results immediately apply to stable matchings as well.
More specifically, for a \(C^2\) surplus function, the theorem below provides a bound on the Hausdorff dimension of the support of \(\gamma \) in terms of the off-diagonal part of the Hessian of s. Consider the symmetric \((n_x+n_y+n_z) \times (n_x+n_y+n_z) \) matrix
where the three diagonal 0 blocks are \(n_x \times n_x\), \(n_y \times n_y\) and \(n_z \times n_z\), respectively, \(D^2_{xy}s:=\Big ( \frac{\partial ^2 s}{\partial x_i \partial y_j} \Big )_{ij}\) is the \(n_x \times n_y\) matrix of mixed second-order partial derivatives with respect to the components of x and y, and the other nonzero blocks are defined similarly.
Recall that the signature\((\lambda _+,\lambda _-,\lambda _0)\) of a symmetric \(N \times N\) matrix is an ordered triple representing the numbers \(\lambda _+, \lambda _-\) and \(\lambda _0=N-\lambda _+-\lambda _-\) of positive, negative and zero eigenvalues, respectively.
Theorem 2
Assume that \(s \in C^2(X \times Y \times Z)\) and that at some point \((x_0,y_0.z_0) \in X \times Y \times Z\), the signature of G is \((\lambda _+, \lambda _-, n_x +n_y+n_z-\lambda _+-\lambda _-)\). Then, there is a neighborhood U of \((x_0,y_0,z_0)\) in \(X \times Y \times Z\) such that \(spt(\gamma ) \cap U\) is contained in a Lipschitz submanifold of \(X \times Y \times Z\) of dimension \(n_x+n_y+n_z-\lambda _-\).
The result is known for optimizers of (4) (Pass 2011, 2012), and that result immediately implies this one. Note that the dimension \(n_x+n_y+n_z-\lambda _-\) is the number of nonnegative eigenvalues of G; in fact, if \(spt(\gamma )\) is a differentiable manifold at \((x_0,y_0,z_0)\), then \(v^TGv \ge 0\) for any v in the tangent space of \(spt(\gamma )\) (Pass 2011, 2012). It is worth noting that, unlike the purity results in the subsequent section, this theorem does not require any regularity assumptions on the marginals \(\mu \) and \(\nu \).
The following proposition, also established by Pass (2011), asserts that when the dimensions are all equal, the signature can be determined from the symmetric part of the product \( D^2_{zy}s[ D^2_{xy}s]^{-1} D^2_{xz}s\).
Proposition 1
If \(n_x=n_y=n_z=:n\), and the matrices \( D^2_{xy}s, D^2_{xz}s\) and \( D^2_{yz}s\) are all invertible, then the signature of G is given by \((\lambda _+,\lambda _-, \lambda _0) = (n+r_-,n+r_+,n-r_--r_+)\) where \(r_+\ (\)respectively \(r_-)\) is the number of positive (respectively negative) eigenvalues of the \(n \times n\) symmetric matrix
In particular, if \(n_x=n_y=n_z=1\) and \(\frac{\partial ^2s }{\partial z \partial y}[\frac{\partial ^2s }{\partial x \partial y}]^{-1}\frac{\partial ^2s }{\partial x \partial z}>0\), then \((r_+,r_-) =(1,0)\) in the proposition above and so the proposition together with Theorem 2 assert that any stable matching is concentrated on a 1-dimensional Lipschitz submanifold; that is, a curve. We will see later on that for an absolutely continuous \(\mu \), the same condition ensures purity and uniqueness.
In higher (but still equal) dimensions, the situation is more subtle. For a bilinear surplus function \(s(x,y,z) = x^TAy +x^TBz + y^TCz +f(x) +g(y)+h(z)\), as in Example 2 below, the condition
together with absolute continuity of \(\mu \) implies purity (see Example 2), but for more general forms of s, one can have solutions which concentrate on n dimensional sets but are not pure. Consider, for example, the surplus on \(\mathbb {R}^2 \times \mathbb {R}^2 \times \mathbb {R}^2\) studied by Moameni and Pass (2017)
For this surplus, a straightforward calculation Moameni and Pass (2017) verifies that the product \(D^2_{zy}s[ D^2_{xy}s]^{-1} D^2_{xz}s +D^2_{zx}s[ D^2_{yx}s]^{-1} D^2_{yz}s\) is a scalar multiple of the identity, and the results above then imply that the signature of G is (2, 4, 0). Every stable matching for this surplus therefore concentrates on sets of no more than 2 dimensions.
However, stable matchings may not be pure. It is straightforward to check that \(s(x,y,z) \le 0\) for all (x, y, z), with equality on the set
It follows that any \(\gamma \) concentrated on S is stable (we can take \(U=V=0\) as the payoff functions). This set is two dimensional, as predicted by the calculations above, but not concentrated on a graph, and so the matching is not pure.
4 Conditions for purity and uniqueness
We now turn our attention to the purity and uniqueness of stable matchings. For the sake of comparison, we first recall known purity and uniqueness results for the simpler, strict matching and hedonic problems. The twist or generalized Spence–Mirrlees condition plays a fundamental role in that setting:
Definition 2
Given a differentiable function, say s(x, y), of two variables, we say u is \(x-y\)twisted if for each \(x \in X\), the mapping
is injective. Here, \(D_x\) represents the gradient of s with respect to the x variable.
We will use the same terminology for functions of several variables, when all but one are held fixed. That is, we say s(x, y, z) is \(x-z\)twisted if for each \(x \in X, y \in Y\), the mapping
is injective.
4.1 Classical matching and hedonic problems
We first review a purity result in the straight matching case, \(s=s(x,y)\).
Theorem 3
(Matching problems) Assume that \(u=u(x,y)\) and \(v=v(x,y)\) depend only on x and y. Assume that \(\mu \) is absolutely continuous with respect to Lebesgue measure and \(s(x,y) =u(x,y) +v(x,y)\) is \(x-y\) twisted. Then, any stable matching is buyer–seller pure and its projection \(\gamma _{XY}\) onto \(X \times Y\) is uniquely determined; that is, if \(\gamma \) and \(\bar{\gamma }\) are stable matchings, \(\gamma _{XY} =\bar{\gamma }_{XY}\).
This result is well known; a proof can be found in the work of Chiappori et al. (2010). Indeed, in the mathematics literature, comparable results regarding the equivalent optimal transport problem were established, in various levels of generality, by Brenier (1987), Gangbo (1995), Levin (1999), Gangbo and McCann (1996) and Caffarelli (1996).
Note that in our terminology, stable matchings are measures on \(X \times Y \times Z\), whereas in the literature the strict matching problem is usually formulated instead in terms of measures on \(X \times Y\), as the good z plays no role in the surplus function. In our formulation, we would not have full uniqueness; any measure on \(X \times Y \times Z\), whose projection onto \(X \times Y\) is \(\gamma _{XY}\) is a stable matching, as both agents x and y are indifferent to the superfluous good z.
We now turn to the fully hedonic case, where agents’ preferences \(u=u(x,z)\) and \(v=v(y,z)\) depend on goods but not on their partners.
Theorem 4
(Hedonic problems) Assume that agents’ preferences \(u=u(x,z)\) and \(v=v(y,z)\) depend only on (x, z) and (y, z), respectively, and that \(\mu \) is absolutely continuous with respect to Lebesgue measure. Then:
-
1.
If u is \(x-z\) twisted, the stable matching is buyer–good pure and it’s projection \(\gamma _{XZ}\) onto \(X \times Z\) is uniquely determined.
-
2.
If in addition, v is \(z-y\) twisted, and, for each fixed x, y, every maximum of the mapping \(z \mapsto u(x,z) +v(y,z)\) over Z occurs on the interior of Z, the stable matching measure is buyer–(seller, good) pure and unique.
The proof of part 1 can be found in the work of Ekeland (2005), while the proof of the second assertion requires a minor additional argument.
Proof (of assertion 2)
Using part 1), we have the existence of a unique map \(F_Z:X \rightarrow Z\) such that, for \(\gamma \) almost every (x, y, z), \(z=F_Z(x)\). Now, by a result of Chiappori et al. (2010), we also have for \(\gamma \) almost every (x, y, z) that z maximizes \(z' \mapsto u(x,z') +v(y,z')\), so that
or
The \(z-y\) twist condition then ensures that there is only one y satisfying this equation. That is, \(y=:F_Y(x)\) is uniquely determined by x ; i.e., the matching is pure. Therefore, the stable matching \(\gamma \) takes the form \(\gamma =(Id, F_Y , F_Z)_\# \mu \), and as \(F_Z\) is unique by part 1, and \(F_Y\) is uniquely determined from (5) by \(F_Z\), \(\gamma \) is unique. \(\square \)
4.2 Fully mixed problems
Our condition for purity and uniqueness will require a couple of definitions. The first is borrowed from Kim and Pass (2014).
Definition 3
(Splitting sets) For a fixed \(x \in X\), a set \(S_x \subset Y \times Z\) is a splitting set atx if there exist functions V(y) and W(z) such that
with equality whenever \((y,z) \in S_x\).
The particular case when \(W(z)=0\) in the above definition is especially relevant for this paper:
Definition 4
(z-trivial splitting sets) For a fixed \(x \in X\), a set \(S_x \subset Y \times Z\) is a z-trivial splitting set atx if there exists a function V(y) such that
with equality whenever \((y,z) \in S_x\).
It is clear that any z-trivial splitting set is a splitting set. The role of z-trivial splitting sets in the matching problem (3) is fairly transparent; for a given buyer x, the collection of all seller-contract pairs (y, z) achieving equality in (2) (and hence potentially matching with x in equilibrium) is a z-trivial splitting set at x. As was observed by Kim and Pass (2014), splitting sets play a similar role in the tripartite matching problem (4).
Remark 1
It is worth noting that \(S_x\) is a z-trivial splitting set at x if and only if \(\bar{z}\) maximizes \(z \mapsto s(x,\bar{y},z)\) for each \((\bar{y}, \bar{z}) \in S_x\).
Definition 5
(Twist on splitting sets) A differentiable surplus s(x, y, z) is twisted on splitting sets [or (TSS) for short], if whenever \(S_x \subseteq Y \times Z\) is a splitting set at x and \(p \in \mathbb {R}^{n_x}\), there is at most one \((y,z) \in S_x\) such that
Kim and Pass (2014) showed that the (TSS) condition implies purity in the multi-agent matching model (4). Here, we introduce a variant, replacing splitting sets with z-trivial splitting sets, which will play an analogous role in (3) and the related matching problem.
Definition 6
(Twist onz-trivial splitting sets) A differentiable surplus s(x, y, z) is twisted on z-trivial splitting sets [or (TzSS) for short], if whenever \(S_x \subseteq Y \times Z\) is a z-trivial splitting set at x and \(p \in \mathbb {R}^{n_x}\), there is at most one \((y,z) \in S_x\) such that
We are now ready to state our main theoretical result on the purity of matchings.
Theorem 5
Suppose s is twisted on z-trivial splitting sets, and \(\mu \) is absolutely continuous with respect to Lebesgue measure. Then any stable matching \(\gamma \) is pure.
The proof of this result is fairly standard; it involves applying the envelope theorem with respect to x on the equality set in (2) to equate the gradients of U and s (with respect to x), and then using the (TzSS) condition to infer the resulting equation can have only one solution. There is one technical difficulty, which is also standard in problems of this type; the payoff function U(x) may not be differentiable. We use a (well known) convexification trick to get around this, replacing U with a Lipschitz (and hence differentiable almost everywhere, by Rademacher’s theorem) payoff function, \(\bar{U}\). The proof can be found in “Appendix”.
A standard argument now implies uniqueness of the stable matching.
Corollary 2
Under the conditions in the preceding theorem, the stable matching is unique.
Proof
Suppose \(\gamma \) and \(\bar{\gamma }\) are stable matchings; by Theorem 5, we know that both \(\gamma \) and \(\bar{\gamma }\) are pure, \(\gamma =(Id, F)_{\#} \mu \) and \(\bar{\gamma }=(Id , \bar{F})_{\#} \mu \) for \(F, \bar{F}:X \mapsto Y \times Z\), and, by Theorem 1, both are also maximizers of (3). It is then easy to see that \(\gamma _{1/2} :=\frac{1}{2}[\gamma +\bar{\gamma }] \in \varGamma _{XYZ}(\mu ,\nu )\). It is therefore also optimal in (3), as the functional is linear. By Theorem 5 again, \(\gamma _{1/2}\) too must then be supported on the graph of some function; on the other hand, it is clear that it is supported on the union of the graphs of F and \(\bar{F}\), which then implies that \(F(x) =\bar{F}(x)\) almost everywhere, and so \(\gamma =\bar{\gamma }\), yielding uniqueness.
As any z-trivial splitting set is a splitting set [one needs only to take \(W(z) =0\) in the definition], any surplus which is twisted on splitting sets is twisted on z-trivial splitting sets. Therefore, we also have the following Corollary:
Corollary 3
Suppose s is twisted on splitting sets, and \(\mu \) is absolutely continuous with respect to Lebesgue measure. Then, the stable matching \(\gamma \) is unique and pure.
The preceding corollary is potentially useful, as several examples of surplus functions satisfying the twist on splitting sets condition are known, as well as general sufficient differential conditions ensuring it (Kim and Pass 2014; Pass 2015). Some of these will be discussed in Sect. 6.
Remark 2
(Uniqueness is the absence of purity) In our arguments above, uniqueness of the stable matching is derived as a consequence of purity. It is natural to ask whether there are conditions under which the stable matching is unique, but not pure. In the two marginal optimal transport setting, corresponding to the classical stable matching problem, a fair bit of research has been devoted to this question, and conditions ensuring uniqueness but not purity have been developed by Chiappori et al. (2010), McCann and Rifford (2016) and Ahmad et al. (2011).
Relatively little is known about the corresponding question in multi-marginal optimal transport. Joint work with Moameni identifies certain specialized conditions on s which can sometimes be used to deduce uniqueness of solutions to multi-marginal problem (Moameni and Pass 2017, Theorem 4.1, Examples 4.2 and 4.4), and these can use to construct unique, nonpure examples in the hybrid matching-hedonic problem in the same way.
Finding more general sufficient conditions for uniqueness of solutions to multi-marginal optimal transport problems is an interesting, but seemingly quite challenging, open problem. Somewhat surprisingly, this question is easier to address for the hybrid-matching-hedonic problem. We will see in the next section (Corollary 5) that conditions from the classical matching problem can be used to derive corresponding conditions for the hybrid problem.
4.3 Other notions of purity
In this paper, we have mostly focused on buyer–(seller, good) purity; as noted above, one can define other notions of purity, and ask under which conditions they hold. As the roles of buyer x and seller y are completely symmetric in our model, it follows immediately that interchanging the roles of x and y in the twist on z-trivial splitting sets condition yields a condition under which any equilibrium is seller–(buyer, good) pure. We also note that two distinct, appropriate relaxations of the (TzSS) condition will individually imply buyer–seller or buyer–good purity, but not full buyer–(seller, good) purity. For instance, if we require that whenever \(S_x\) is a z-trivial splitting set at x, \((y,z),(\tilde{y}, \tilde{z}) \in S_x\), and \(D_xs(x,y,z) =D_xs(x,\tilde{y},\tilde{z})\), we must have \(y =\tilde{y}\), then any stable matching must be buyer–seller pure. The proof of this is almost identical to the proof of Theorem 5.
Turning our attention to matchings which concentrate on graphs over z, we note the following, known result on good–(buyer, seller) purity for strictly hedonic problems.
Proposition 2
For a strictly hedonic surplus, \(s(x,y) =u(x,z) +v(y,z)\)
-
1.
If u is \(z-x\) twisted, then any stable matching is good–buyer pure.
-
2.
If v is \(z-y\) twisted then any stable matching is good–seller pure.
-
3.
Consequently, it u is \(z-x\) twisted and v\(z-y\) twisted, the stable matching is good–(buyer, seller) pure.
A proof of this result (in fact, of a more general version), can be found in work of (Pass 2015, Proposition 2.3.4.2).Footnote 5 The proof, however, relies on the hedonic form of s in a crucial way, and it is not clear whether a version of the result can be extended to hybrid models.
5 Reformulation as a bipartite matching problem
Here, we provide a different, but equivalent, formulation of the problem, following Chiappori et al. (2010), as a binary matching, or two marginal optimal transport, problem. We define the reduced surplus by:
The meaning of \(\bar{s}(x,y)\) is clear; it expresses the maximum joint surplus (among all possible contracts) that can be generated by the partnership of x and y. The classical two marginal optimal transport problem is to maximize
over the set \(\varGamma _{XY}(\mu ,\nu )\) of probability measures on \(X \times Y\) with X (respectively Y) marginal \(\mu \) (respectively \(\nu \)). This optimization problem is equivalent to the classical strict stable matching problem under transferable utility, with surplus \(\bar{s}\) (Gretsky et al. 1992; Chiappori et al. 2010).
For each x, y, choose \(\bar{z}(x,y) \in \mathrm{argmax}_z [u(x,y,z) +v(x,y,z)]\); note that \(\bar{z}\) then defines a function \(\bar{z}: X \times Y \rightarrow Z\). Due to compactness, one can choose this selection to be Borel measurable.
Proposition 3
Suppose a measure \(\sigma \) is optimal in (7). Then \((Id, Id, \bar{z})_{\#}\sigma \) is optimal for (3). Conversely, if \(\gamma \) is optimal in (3), then \(\gamma _{XY}=(P_{XY})_{\#}\gamma \) is optimal in (7), where \(P_{XY}(x,y,z) =(x,y)\).
The proof of this result is almost identical to the proof of the analogous result of Chiappori et al. (2010) and can be found in “Appendix”.
As the well-known generalized Spence–Mirrlees condition on \(\bar{s}\) is known to imply purity and uniqueness of maximizers in (7), it is natural to look for conditions on s which ensure it. We show that the twist on z-trivial sets for s is equivalent to the classical generalized Spence–Mirrlees condition on \(\bar{s}\) (under an extra condition on s). Note that this, combined with the preceding proposition and Theorem 3 yields an alternative proof of the buyer–seller aspects of the purity and uniqueness results in the last section (that is, buyer–seller purity and uniqueness of \(\gamma _{XY}\)).
Theorem 6
Assume that both s and \(\bar{s}\) are everywhere differentiable with respect to x. If s satisfies the twist on z-trivial splitting sets condition, then \(\bar{s}\) satisfies the twist condition.
Conversely, assume that s is \(x-z\) twisted. Then, if \(\bar{s}\) satisfies the twist condition, s satisfies the twist on z-trivial splitting sets condition.
The proof is relegated to an “Appendix”.
Remark 3
From inspection of the proof, it is clear that in fact slightly more is true.
If we assume that \(\bar{s}\) is twisted, but remove the \(x-z\) twist assumption on s, the argument in the proof of the second implication still yields that if \((y_0,z_0)\) and \((y_1,z_1)\) are in any splitting set \(S_x\) at x, and \(D_xs(x,y_0,z_0)= D_xs(x,y_1,z_1)\) then \(y_0=y_1\) (although possibly \(z_0 \ne z_1\)). This then implies that any stable matching is buyer–seller pure, and that its projection onto \(X \times Y\) is uniquely determined (as can also be proven using the twistedness of \(\bar{s}\) in combination with Theorem 3).
Remark 4
If s is either Lipschitz or semi-convex, one can show by a standard argument that \(\bar{s}\) is also Lipschitz or semi-convex, respectively, and it is well known that functions satisfying either one of these criteria are differentiable almost everywhere. In fact, a version of the twist condition implying purity and uniqueness can be formulated under either of these assumptions (in place of everywhere differentiability) (Chiappori et al. 2010), and our proof in “Appendix” adapts easily to this setting. It follows that one can remove the assumption of differentiability on \(\bar{s}\) in the preceding theorem; we present the version with the differentiability assumption on \(\bar{s}\) here for simplicity.
Proposition 3 also has the following immediate corollary relating uniqueness of solutions to problems (3) and (7).
Corollary 4
The solution \(\gamma \) to (3) is unique if and only if the solution to \(\sigma \) (7) is unique and, for \(\sigma \) almost every (x, y), \(z \mapsto s(x,y,z)\) has a unique maximizer.
The subtwist condition on \(\bar{s}(x,y) =s(x,y,\bar{z}(x,y))\), introduced by Chiappori et al. (2010), requires that for each fixed \(y_0\) and \(y_1\), the function
has no critical points, except for possibly one global maximum and one global minimum (note that having no critical points at all is equivalent to the twist condition). This condition implies that solutions to (7) are unique, but not necessarily pure [in fact, solutions concentrate on sets with a certain special structure—see Theorem 5.1 of Ahmad et al. (2011) and Theorem 3 of Chiappori et al. (2010)]. Combined with the preceding Corollary, this yields a condition under which solutions to (3) are unique, but not necessarily pure.
Corollary 5
Assume that for each \((x,y) \in X \times Y\), \(z \mapsto s(x,y,z)\) has a unique maximizer, \(\bar{z}(x,y) \in Z\), and that \(s(x,y,\bar{z}(x,y))\) satisfies the subtwist condition. Then, the solution \(\gamma \) to (3) is unique.
Proof
As \(\bar{s}(x,y) =s(x,y,\bar{z}(x,y))\) is subtwisted by assumption, the solution to (7) is unique. Corollary 4 then implies uniqueness of the solution to (3). \(\square \)
6 Examples
While the twist on z-trivial splitting sets condition looks complicated, it is possible to verify it on several classes of examples. We present here three types of examples:
-
1.
Examples satisfying the more restrictive twist on splitting sets condition (and hence the twist on z-trivial splitting sets condition introduced here as well). A wide variety of examples of this type are already known in the mathematical literature.
-
2.
Examples violating the twist on splitting sets condition, but satisfying twist on z-trivial splitting sets.
-
3.
An example violating twist on z-trivial splitting sets, together with an explicit nonpure stable matching.
6.1 Surpluses satisfying twist on splitting sets
As mentioned above, a variety of examples satisfying the twist on splitting sets condition (and therefore also the twist on z-trivial splitting sets condition), as well as general differential conditions on s which imply them, are known (Kim and Pass 2014). As the differential conditions are somewhat complicated, we do not state them here; instead, we present a couple of examples which seem potentially relevant in economics
Example 1
(One dimensional problems) Suppose \(X,Y,Z \subset \mathbb {R}\) are all real intervals. Then, s is twisted on splitting sets provided the compatibility condition, \(\frac{\partial ^2s }{\partial x \partial y}[\frac{\partial ^2s }{\partial z \partial y}]^{-1}\frac{\partial ^2s }{\partial z \partial x}>0\), holds for all \((x,y,z) \in X \times Y \times Z\). In particular, this holds when s is supermodular in each pair of its arguments.
The next example is similar to the model of Tinbergen (1956), augmented to include direct buyer–seller interactions.
Example 2
(Bilinear utilities) Suppose \(X,Y,Z \subset \mathbb {R}^n\) are convex and
for nonsingular \(n \times n\) matrices A, B and C. Then, s is twisted on splitting sets provided the symmetric matrix \(C^TA^{-1}B +B^T(A^T)^{-1}C\) is positive definite.
Note that the positive definiteness assumption on \(C^TA^{-1}B +B^T(A^T)^{-1}C\) forces each of the matrices A, B and C to be invertible. Proofs of the (TSS) property for the surplus functions in both of the examples in this subsection can be found in joint work with Kim (Kim and Pass 2014).
Remark 5
As we will see below, the sufficient conditions for purity and uniqueness considered here (twist on splitting sets) are substantially stronger than the twist on z-trivial splitting sets, and so, when studying purity and uniqueness in the hybrid matching-hedonic model, the motivation for considering the multi-marginal coupling between buyers, sellers and (prescribed) goods and the related twist on splitting sets condition may seem questionable. However, there are at least two concrete advantages to doing so.
First, the twist on splitting sets condition is often easier to check. For instance, in one dimension, the compatibility condition in Example 1 is essentially equivalent to twist on splitting sets and hence is an easy to check sufficient condition for twist on z-trivial splitting sets; if compatibility fails, twist on z-trivial splitting sets may still hold, but establishing this typically requires more delicate arguments.
Secondly, the twist on splitting sets condition has some flexibility not shared by the twist on z-trivial splitting sets; namely, if s(x, y, z) is twisted on splitting sets, then so is \(s(x,y,z) +F(z)\) for any function z. This fact may make it easier to check on certain examples.
6.2 Surplus satisfying the twist on z-trivial splitting sets (but violating twist on splitting sets)
The (TzSS) condition is strictly weaker than the (TSS) condition. We demonstrate this here by presenting two examples which do not satisfy the twist on splitting sets condition, but do satisfy the weaker variant, twist on z-trivial splitting sets.
Example 3
(Strictly hedonic utilities) Assume that the utilities of both consumers and producers depend only on goods, \(u(x,y,z) =u(x,z)\) and \(v(x,y,z) =v(y,z)\), and that for each fixed x and y, all maxima of the function \(z \mapsto u(x,z) +v(y,z)\) occur on the interior of Z. Then \(x-z\) twistedness on u and \(z-y\) twistedness on v suffice to ensure the twist on z-trivial splitting sets condition on \(s(x,y,z) =u(x,z) +v(y,z)\).
The proof of this assertion can be found in “Appendix”.
Remark 6
The conditions in Example 3do not imply the twist on splitting sets condition, and as a result it is possible for the solution to the tripartite matching problem (4) with surplus \(s(x,y,z)=u(x,z) +v(y,z)\) to be nonunique and nonpure. Suppose, for example, \(\alpha =\delta _{z_0}\) is concentrated at a point. Then if a probability measure \(\gamma \) on \(X \times Y \times Z\) is in \(\varGamma _{XYZ}(\mu ,\nu ,\alpha )\) (i.e., has marginals \(\mu ,\nu \) and \(\alpha \)) we have \(z=z_0\), \(\gamma \) almost surely, so that
As the last expression does not depend on \(\gamma \), any\(\gamma \in \varGamma _{XYZ}(\mu ,\nu ,\alpha )\) maximizes the total surplus and is therefore stable.
We close this subsection by revisiting the Tinbergen (1956) type surplus functions from Example 2. We show that the twist on z-trivial splitting sets holds in much greater generality that the twist on splitting sets (although we specialize slightly here, by replacing the general function h(z) with a concave quadratic \(z^tDz\)).
Example 4
Suppose \(X,Y,Z \subseteq \mathbb {R}^n\) are convex, and let
with \(D+D^T <0\). Then, s is twisted on z-trivial splitting sets provided C is invertible and
is nonsingular.
Proof
Given a z-trivial splitting set \(S_x\) at x, we note that if \((y,z) \in S_x\), maximality of \(s(x,y,\cdot )\) at z (recall Remark 1) implies
so \(y = -(C^T)^{-1}[B^Tx+(D+D^T)z]\). For a given p, we will show that only one point of the form \((y,z) =(-(C^T)^{-1}[B^Tx+(D+D^T)z],z)\) can satisfy the condition
Indeed, the mapping
is affine and injective by assumption. This completes the proof. \(\square \)
Remark 7
In the model above, if A is also invertible, we have
If in addition, we have \(C^TA^{-1}B +B^T(A^T)^{-1}C>0\), then the surplus is twisted on splitting sets, according to Example 2. Twist on z-trivial splitting sets is much weaker, requiring only invertibility of \([C^TA^{-1}B-(D+D^T)]\) rather than positivity of its symmetric part, which is implied by the condition \(C^TA^{-1}B +B^T(A^T)^{-1}C>0\) in Example 2.
Furthermore, the matrices B and A in this example are not required to have full rank; in particular, this model incorporates low dimensional buyer–seller interactions, where preferences of buyers/sellers for their partners are dependent on only some of their characteristics (for instance, if all the entries of A are 0 except the upper left-hand corner \(A_{11}\), partners’ preferences depend only on the first characteristics, \(x_1\) and \(y_1\)). In its general form, the model interpolates between the strictly hedonic case, where \(A=0\), and the case with strong, full dimensional interactions between buyers and seller, when A has full rank.
6.3 A surplus violating twist on z-trivial splitting sets, and a nonpure solution
Here, we exhibit an example of a surplus violating the twist on z-trivial splitting sets condition, and demonstrate explicitly that in this case, matching equilibria may not be pure.
We let X, Y, Z be intervals in \(\mathbb {R}\); the consumers’ and sellers’ surplus are given respectively by \(u(x,y,z) = xy+xz\) and \(v(x,y,z)=-yz-z^2/2\), so that \(s(x,y,z) =xy+xz-yz-z^2/2\). It seems reasonable to interpret this surplus economically as a toy model for the effects of ethical business practices. The variable \(x \in X\) will represent the income of a consumer and \(z \in Z\) the quality of a good. Firms will be differentiated according to a variable \(y \in Y\) which we may think of as reflecting the ethicality of their business practices (as perceived by consumers); for example, firms with large values of y may provide their workers with better working conditions. Consumers’ preferences then have two supermodular terms, reflecting separately their preferences to buy higher quality goods and to purchase them from more ethical businesses (the supermodularity of xy may be interpreted as consumers with more disposable income having stronger preferences for ethically produced goods than their lower income counterparts). Producers’ preferences are independent of consumers, but their costs \(yz+z^2/2\) include a quadratic term in good quality and also a supermodular term yz, meaning more ethical firms have higher marginal production costs (for instance, producing a higher quality good may take more hours of labor than a lower quality good—the resulting difference in cost will be higher for a firm paying higher wages).
Now note that for \(U(x) =\frac{x^2}{2}\) and \(V(y) =\frac{y^2}{2}\), we have
with equality when \(x=y+z\). Then taking \(\gamma \) to be uniform measure on the set \(X\times Y \times Z \cap \{x=y+z\}\), we immediately get that \(\gamma \) is a stable matching measure for its marginals \(\mu =(P_X)_\# \gamma \) and \(\nu =(P_Y)_\# \gamma \), with payoff functions U and V. This matching is certainly not pure; each consumer x is indifferent among a continuum of choices of producers y.
We note that when consumer x and producer y match together, they exchange product \(z =x-y\), for price \(p_{x,y,z} =u(x,y,z)-U(x) =x(y+z) -x^2/2 =x^2/2\). A y varies, increasing favourability of the firm y to the consumer x is exactly offset by the decreasing quality of the good \(z=x-y\) they exchange, and the price remains constant.
Remark 8
By example (4), the surplus function \(s(x,y,z) =xy+xz-yz-az^2\)is twisted on z-trivial splitting sets for any constant aother than \(a=\frac{1}{2}\), indicating that the previous example is highly nongeneric.
7 Conclusion
This paper studies a general hybrid matching-hedonic model where agents match according to their preferences for both their partners and the good or contract they exchange. In contrast to strict matching and strict hedonic problems, these mixed models do not seem to have received much theoretical attention yet, but are quite natural in a variety of settings.
The hybrid problem has a natural connection with tripartite matching, or multi-marginal optimal transport; specifically, being a stable matching in the hybrid model is equivalent to solving a less constrained variant of the corresponding optimal transport problem. This variational interpretation implies the existence of stable matchings under quite general conditions. In addition, this observation, together with known results on multi-marginal optimal transport, can be exploited to reveal information on the structure of matching patterns. In particular, locally, the dimension of the support of a stable matching measure is controlled in terms of the mixed second-order partial derivatives of the surplus; this result holds without any conditions on the distributions \(\mu \) and \(\nu \) of agents. In addition, if \(\mu \) is absolutely continuous, the twist on splitting sets condition is known to imply purity and uniqueness of stable matchings in multi-marginal optimal transport and therefore immediately implies the same for the hybrid problem. It can also be used as a guide to develop a weaker variant, twist on z-trivial splitting sets, which implies purity and uniqueness in the hedonic-matching problem but not in the more general tripartite matching problem.
Notes
It would be straightforward to enhance the model to allow for unequal numbers of buyers and sellers, and to allow both to decline to participate in any match; this can be done as in Chiappori et al. (2010), by augmenting the measures \(\mu \) and \(\nu \) with Dirac masses, representing null buyers and sellers. As this is tangential to our main purpose here, we work instead with the simpler model in which all agents participate.
The support of \(\gamma \) is the smallest closed set \(spt(\gamma ) \subset X \times Y \times Z\) with full mass, \(\gamma (spt(\gamma ))=1\).
In contrast to the strict hedonic problem, one cannot hope for a market clearing pricing function p(z) which is independent of x and y here; it is possible that the same good may be exchanged between different pairs of buyers and seller for different prices.
In these tripartite matching problems, the variables are typically interpreted differently; economically, they model problems where three agents are required to form a match (think, for example, of firms hiring simultaneously both CEOS and CFOS, drawn from separate distributions). The distributions of all three types of agents (firms, CEOs and CFOs) are then known, and finding a stable match is equivalent to maximizing (4) [see Carlier and Ekeland (2010)].
We note that when \(-\,u\) and \(-\,v\) are proportional to the squared distance on either \(X,Y,Z \subseteq \mathbb {R}^n\) or a Riemannian manifold, the third marginal \(\gamma _Z\) of the matching measure \(\gamma \) coincides with the displacement interpolant of \(\mu \) and \(\nu \), and the purity follows from the Mather Shortening lemma [see Theorem 8.5 in the book of Villani (2009) or Lemma 5.3 of Cordero-Erausquin et al. (2001)]; the proof of Pass (2015) relies on the same ideas.
References
Ahmad, N., Kim, H.K., McCann, R.J.: Optimal transportation, topology and uniqueness. Bull. Math. Sci. 1(1), 13–32 (2011). https://doi.org/10.1007/s13373-011-0002-7
Becker, G.: A theory of marriage. Part I. J. Polit. Econ. 81, 813–846 (1973)
Brenier, Y.: Decomposition polaire et rearrangement monotone des champs de vecteurs. CR Acad. Sci. Pair Ser. I Math. 305, 805–808 (1987)
Caffarelli, L.: Allocation maps with general cost functions. In: Partial Differential Equations and Applications, Lecture Notes in Pure and Applied Math, vol. 177, pp. 29–35. Dekker, New York (1996)
Carlier, G., Ekeland, I.: Matching for teams. Econ. Theory 42(2), 397–418 (2010). https://doi.org/10.1007/s00199-008-0415-z
Chiappori, P.A., McCann, R., Nesheim, L.: Hedonic price equilibria, stable matching and optimal transport; equivalence, topology and uniqueness. Econ. Theory 42(2), 317–354 (2010). https://doi.org/10.1007/s00199-009-0455-z
Cordero-Erausquin, D., McCann, R.J., Schmuckenschläger, M.: A Riemannian interpolation inequality a la Borell, Brascamp and Lieb. Invent. Math. 146(2), 219–257 (2001)
Dupuy, A., Galichon, A., Zhao, L.: Migration in China: to work or to wed? Working paper. https://feb.kuleuven.be/drc/Economics/misc/seminars/papers2015/Paper_Dupuy.pdf. Accessed 8 Jan 2017 (2015)
Ekeland, I.: An optimal matching problem. ESAIM Control Optim. Calc. Var. 11(1), 57–71 (2005)
Ekeland, I.: Existence, uniqueness and efficiency of equilibrium in hedonic markets with multidimensional types. Econ. Theory 42(2), 275–315 (2010). https://doi.org/10.1007/s00199-008-0427-8
Galichon, A.: Optimal Transport Methods in Economics. Princeton University Press, Princeton (2016)
Gangbo, W.: Habilitation thesis, Universite de Metz. http://people.math.gatech.edu/~gangbo/publications/habilitation.pdf. Accessed 8 Jan 2017 (1995)
Gangbo, W., McCann, R.: The geometry of optimal transportation. Acta Math. 177, 113–161 (1996)
Gretsky, N., Ostroy, J., Zame, W.: The nonatomic assignment model. Econ. Theory 2(1), 103–127 (1992). https://doi.org/10.1007/BF01213255
Kim, Y.H., Pass, B.: A general condition for Monge solutions in the multi-marginal optimal transport problem. SIAM J. Math. Anal. 46, 1538–1550 (2014)
Levin, V.: Abstract cyclical monotonicity and Monge solutions for the general Monge–Kantorovich problem. Set-Valued Anal. 7(1), 7–32 (1999)
McCann, R.: Polar factorization of maps on Riemannian manifolds. Geom. Funct. Anal. 11, 589–608 (2001)
McCann, R.J., Rifford, L.: The intrinsic dynamics of optimal transport. J l’École Polytech. Math. 3, 67–98 (2016). https://doi.org/10.5802/jep.29
Moameni, A., Pass, B.: Solutions to multi-marginal optimal transport problems concentrated on several graphs. ESAIM Control Optim. Calc. Var. (2017). 23(2), 551–567 https://doi.org/10.1051/cocv/2016003
Mourifie, I., Siow, A.: Cohabitation versus marriage: marriage matching with peer effects, working paper (2014)
Pass, B.: Structural results on optimal transportation plans. Ph.D. thesis, University of Toronto. https://sites.ualberta.ca/~pass/thesis.pdf. Accessed 8 Jan 2017 (2011)
Pass, B.: On the local structure of optimal measures in the multi-marginal optimal transportation problem. Calc. Var. Partial Differ. Equ. 43, 529–536 (2012). https://doi.org/10.1007/s00526-011-0421-z
Pass, B.: Regularity properties of optimal transportation problems arising in hedonic pricing models. ESAIM Control Optim. Calc. Var. 19(3), 668–678 (2013). https://doi.org/10.1051/cocv/2012027
Pass, B.: Multi-marginal optimal transport: theory and applications. ESAIM Math. Model. Numer. Anal. 49(6), 1771–1790 (2015). https://doi.org/10.1051/m2an/2015020
Rosen, S.: Hedonic prices and implicit markets: product differentiation in pure competition. J. Polit. Econ. 82(1), 34–55 (1974). http://www.jstor.org/stable/1830899
Rothschild, M., Stiglitz, J.: Equilibrium in competitive insurance markets: an essay on the economics of imperfect information. Q. J. Econ. 90(4), 629–649 (1976)
Santambrogio, F.: Optimal Transport for Applied Mathematicians. Birkhäuser, Basel (2015)
Shapley, L., Shubik, M.: The assignment game i: the core. Int. J. Game Theory 1(1), 111–130 (1971). https://doi.org/10.1007/BF01753437
Tinbergen, J.: On the theory of income distribution. Weltwirtschaftliches Archiv 77, 155–175 (1956). http://www.jstor.org/stable/40435398
Villani, C.: Topics in Optimal Transportation. Graduate Studies in Mathematics, vol. 58. American Mathematical Society, Providence (2003)
Villani, C.: Optimal Transport: Old and New, Grundlehren der Mathematischen Wissenschaften, vol. 338. Springer, New York (2009)
Author information
Authors and Affiliations
Corresponding author
Additional information
The author is pleased to acknowledge the support of a University of Alberta start-up grant and National Sciences and Engineering Research Council of Canada Discovery Grant Number 412779-2012.
Appendices
Appendices
1.1 Appendix A Proofs
1.1.1 A.1 Proof of variational formulation: Theorem 1
The proof requires the following lemma, expressing a duality result for the linear maximization (3).
Lemma 1
where the infimum on the right-hand side is taken over the set of continuous functions \(U \in C(X)\) and \(V \in C(Y)\) satisfying \(U(x) +V(y) \ge s(x,y,z)\) throughout \(X \times Y \times Z\). Furthermore, the infimum on the right-hand side is attained.
We will refer to the minimization on the right-hand side as the dual problem to (3). The lemma is a variant of the standard, optimal transport duality theorem, and it’s proof is a straightforward adaptation of the proof of that result (Villani 2003, Theorem 1.3).
Proof
The Riesz representation theorem implies that the dual of \(C(X\times Y \times Z)\) is the set \(M( X\times Y \times Z)\) of signed regular Borel measures on \(X \times Y \times Z\). We define the functionals F and G on \(C(X\times Y\times Z)\) by
and
Fenchel–Rockafellar duality [see, for example, Theorem 1.9 of Villani (2003)] then asserts that
where \(F^*\) and \(G^*\) are the Legendre–Fenchel transforms of F and G, respectively. It is easy to check that the infimum above coincides with the infimum in (9). On the other hand, we compute
Now, if \(\gamma \) is not a positive measure, the infimum above is clearly \(-\,\infty \), while if it is a positive measure, the infimum is attained at \(f=s\). So we have
Similarly,
where \(\gamma _X =(P_X)_\#\gamma \) and \(\gamma _Y =(P_Y)_\#\gamma \) are the projections of \(\gamma \) onto X and Y, respectively. The integrals inside the supremum are clearly 0 for each choice of U, V if \(\gamma \) has \(\mu \) and \(\nu \) as its X and Y marginals, respectively, and so the supremum is 0 in this case. If the marginals of \(\gamma \) are not \(\mu \) and \(\nu \), then the supremum is clearly \(+\infty \), so we have
Noting that, if \(\gamma \) is a signed measure, \(\gamma \in \varGamma _{XYZ}(\mu ,\nu )\) is equivalent to \(\gamma \) being nonnegative and having \(\mu \) and \(\nu \) as it X and Y marginals, it is then straightforward to see that the supremum in (10) is exactly the supremum in (9).
To obtain existence in the dual problem, note that for any U, V such that \(U(x) +V(y) \ge s(x,y,z)\), we have
and then
Now, as s is assumed Lipschitz, \(U^s\) and \(U^{ss}\) are Lipschitz with the same constant C, by a now classical argument of McCann (2001, Lemma 2). By shifting \(U^s \rightarrow U^s +a\) and \(U^{ss} \rightarrow U^s -a\), we may also assume that \(U^s(\bar{x}) =0\) for some fixed \(\bar{x}\); together with the Lipschitz condition and compactness, this implies that \(|U^s|,|U^{ss}| \le K\) for some fixed K.
Noting that we have \(U^{ss}(x) +U^s(y) \ge s(x,y,z)\), and \(\int _XU^{ss}(x) \text {d}\mu (x)+\int _YU^s(y)\text {d}\nu (y) \le \int _XU(x) \text {d}\mu (x)+\int _YV(y)\text {d}\nu (y)\), we may take the minimization in the dual problem over functions which in addition to the constraint \(U(x) +V(y) \ge s(x,y,z)\) are Lipschitz with uniform constant C and bounded by the uniform constant K. This set is compact with respect to uniform convergence, by the Arzela–Ascoli theorem, which implies existence of a minimizer. \(\square \)
The preceding lemma can be used to prove Theorem 1; the solutions U and V to the dual problem turn out to be exactly the payoff functions.
Proof
Given a stable matching \(\bar{\gamma }\) on \(X \times Y \times Z\), and associated payoff functions U(x) and V(y), we integrate the inequality (2) against any other matching \(\gamma \in \varGamma _{XYZ}(\mu ,\nu )\) to obtain
On the other hand, the stability of \(\bar{\gamma }\) means that we have equality in (2) \(\bar{\gamma }\) almost everywhere, so we have equality in the preceding argument when \(\gamma =\bar{\gamma }\). This means the stable matching \(\bar{\gamma }\) is optimal in (3).
On the other hand, if \(\bar{\gamma }\) solves (3), let U and V be solution to the dual problem, guaranteed to exist by the lemma above. Then, we have \(s(x,y,z) \le U(x) +V(y)\) everywhere by definition, and so
However, the duality lemma states that we actually have equality, \(\int _{X \times Y \times Z} s(x,y,z)\text {d}\bar{\gamma }(x,y,z) =\int _{X } U(x) \text {d}\mu (x) +\int _{Y }V(y) \text {d}\nu (y)\), which is possible only if \(s(x,y,z) = U(x) +V(y)\), \(\bar{\gamma }\) almost everywhere. Thus, U and V are payoffs for \(\bar{\gamma }\), and so \(\bar{\gamma }\) is stable. \(\square \)
1.1.2 A.2 Proof the twist on z-trivial splitting sets implies purity: Theorem 5
Proof
Let \(\gamma \) be a stable equilibrium and U, V the corresponding payoff functions. Let \(S \subseteq X\times Y \times Z\) be the set where equality is attained in (2); as \(spt(\gamma )\subseteq S\), it suffices to show that for \(\mu \) almost all x, the set \(S_x:=\{(y,z): (x,y,z) \in S\}\) is a singleton. Note that, as an immediate consequence of the definition, \(S_x\) is a z-trivial splitting set.
We first set \(V^s(x) =\sup _{(y,z) \in Y \times Z}s(x,y,z) -V(y)\). It is known that the fact that s is Lipschitz in x implies that \(V^s\) is in fact Lipschitz as well (McCann 2001), and hence differentiable Lebesgue almost everywhere by Rademacher’s theorem. In addition, for a fixed x, (2) implies \(s(x,y,z) -V(y) \le U(x)\) for every choice of (y, z), and so taking supremum over (y, z) yields
Therefore, for all (x, y, z), we have the following string of inequalities
Furthermore, as the first and last terms are equal on S, we must have equality throughout this set; in particular,
on S. Now, for every x at which \(V^s\) is differentiable, and \(y,z \in S_x\), the envelope theorem implies
However, as \(S_x\) is a z-trivial splitting set at x, the (TzSS) condition implies that this uniquely determines y and z. That is, the splitting set \(S_x\) is a singleton. This holds for each x where \(V^s\) is differentiable, which is Lebesgue almost every x, and hence \(\mu \) almost every x, by the absolute continuity of \(\mu \). For each such x, we define \((F_Y(x),F_Z(x))\) to be the unique (y, z) satisfying (12); \(\gamma \) is then concentrated on the graph of \((F_Y,F_Z)\), and is therefore pure. This completes the proof. \(\square \)
1.1.3 A.3 Proof of equivalence between the hybrid matching-hedonic problem and the reduced matching problem: Proposition 3
Proof
Let \(\gamma \) be a maximizer in (3) and set \(\sigma =\gamma _{XY} =(P_{XY})_\#\gamma \). Then clearly \(\sigma \in \varGamma _{XY}(\mu ,\nu )\); we will show that it maximizes (7). For any other \(\tilde{\sigma }\in \varGamma _{XY}(\mu ,\nu )\), set \( \tilde{\gamma }=(Id, Id, \bar{z})_\# \tilde{\sigma }\) and note that \(\tilde{\gamma }\in \varGamma _{XYZ}(\mu ,\nu )\).
We have
As \(\tilde{\sigma }\in \varGamma _{XY}(\mu ,\nu )\) was arbitrary, it follows that \(\sigma \) is optimal in (7).
On the other hand, let \(\sigma \) be any maximizer in (7) and \(\gamma =(Id , Id , \bar{s})_\# \sigma \). It is clear that \(\gamma \in \varGamma _{XYZ}(\mu ,\nu )\); we need to show that it maximizes (3). For any other \(\tilde{\gamma }\in \varGamma _{XYZ}(\mu ,\nu )\), we set \(\tilde{\sigma }= (P_{XY})_\#\tilde{\gamma }\) and observe \(\tilde{\sigma }\in \varGamma _{XY}(\mu ,\nu )\). We then have, by reasoning similar to the above,
This yields optimality of \(\gamma \) in (3) and completes the proof. \(\square \)
1.1.4 A.4 Proof of equivalence between twistedness of \(\bar{s}\) and twistedness on z-trivial splitting sets of s: Theorem 6
Proof
First suppose s is twisted on z trivial splitting sets. Fix x, set \(V(y)=\bar{s}(x,y)\) and
Then \(S_x\) is a z-trivial splitting set for s at x, with splitting function V, as for any y, z we have by definition
with equality whenever \((y,z) \in S_x\).
Now, choose \(y_0,y_1\) satisfying
we want to show \(y_0 = y_1\). We can choose \(z_0 \in \mathrm{argmax}_z (s(x,y_0,z))\) and \( z_1\in \mathrm{argmax}_z (s(x,y_1,z))\), so that \((y_0,z_0), (y_1,z_1) \in S_x\). By the envelope condition, we have
and
Combined with (13), this implies that \(D_xs(x,y_0,z_0) = D_xs(x,y_1,z_1) \). As \((y_0,z_0)\) and \( (y_1,z_1)\) both belong to the z- trivial splitting set S, the twist on z-trivial splitting sets hypothesis now implies \((y_0,z_0)=(y_1,z_1)\); in particular, \(y_0 =y_1\) as desired.
Conversely, assume \(\bar{s}\) is twisted, and suppose that \((y_0,z_0), ( y_1, z_1) \in S_x\), where \(S_x\) is a z-trivial splitting set at x, such that
we need to show \((y_0,z_0) =(y_1, z_1)\). Let V be the splitting function for \(S_x\); then
for all z, with equality for \(z=z_0\). As the left-hand side is independent of z, this tells us that \(z_0 \in \mathrm{argmax}_z s(x,y_0,z)\) and so \(\bar{s}(x,y_0) =s(x,y_0,z_0)\). The envelope theorem then yields
An identical argument implies
and so we have \(D_x \bar{s}(x,y_0) =D_x \bar{s}(x,y_1)\). The twist condition then gives us \(y_0 =y_1=:y\). It remains to verify that \(z_0=z_1.\) To this end, note that (14) now becomes
and so the \(x -z\) twist condition implies \(z_0=z_1\), completing the proof. \(\square \)
1.1.5 A.5 Proof that strictly hedonic surpluses are twisted on z-trivial splitting sets: assertion in Example 3
This result actually follows by combining Theorem 6 with a result of Pass (2013), which asserts that the reduced surplus \(\bar{s}\) corresponding to a strictly hedonic surplus s is twisted (under the assumptions in Example 3); however, we feel it is enlightening to provide a direct proof as well.
Proof
Let \(S_x\) be a z-trivial splitting set at x, with splitting function V(y). Assume \(D_xs(x,y_0,z_0) = D_xs(x, y_1, z_1)\) for \((y_0,z_0), ( y_1, z_1) \in S_x\); we need to show \((y_0,z_0)=( y_1, z_1)\). Note that the form of s implies
the \(x - z\) twist condition on u then implies that \(z_0=z_1\).
It remains to show \(y_0 =y_1\). Now, \( z \mapsto u(x,z) +v(y_0,z)- V(y_0)\) is maximized at \(z=z_0\), and so its derivative vanishes there (note \(z \in Z^0\) by assumption):
or
Similarly,
which, as \(z_0= z_1\), combines with the above to yield \(D_zv(y_0,z_0)=D_zv( y_1, z_0)\). The \(z -y\) twistedness of v then yields \(y_0=y_1\), which completes the proof. \(\square \)
Rights and permissions
About this article
Cite this article
Pass, B. Interpolating between matching and hedonic pricing models. Econ Theory 67, 393–419 (2019). https://doi.org/10.1007/s00199-018-1126-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00199-018-1126-8
Keywords
- Matching under transferable utility
- Hedonic pricing
- Optimal transport
- Multi-marginal problems
- Purity
- Uniqueness