Matching in closed-form: equilibrium, identification, and comparative statics

This paper provides closed-form formulas for a multidimensional two-sided matching problem with transferable utility and heterogeneity in tastes. When the matching surplus is quadratic, the marginal distributions of the characteristics are normal, and when the heterogeneity in tastes is of the continuous logit type, as in Choo and Siow (J Polit Econ 114:172–201, 2006), we show that the optimal matching distribution is also jointly normal and can be computed in closed form from the model primitives. Conversely, the quadratic surplus function can be identified from the optimal matching distribution, also in closed-form. The closed-form formulas make it computationally easy to solve problems with even a very large number of matches and allow for quantitative predictions about the evolution of the solution as the technology and the characteristics of the matching populations change.

Authors and Affiliations

1. Department of Economics, École polytechnique, Route de Saclay, 91128, Palaiseau, France

   Raicho Bojilov

2. Economics Department, Courant Institute, New York University, 19 W 4th Street, New York, NY, 10012, USA

   Alfred Galichon

3. Economics Department, Sciences Po., Paris, France

   Alfred Galichon

Corresponding author

Correspondence to Alfred Galichon.

Date: January 12, 2016. A preliminary version of this paper containing the main results was first presented in September 2012 under the title “Closed-Form Formulas for Multivariate Matching”. We would like to thank Nicholas Yannelis, the Editor, and two anonymous referees, as well as Arnaud Dupuy, Bernard Salanié and seminar participants at CREST and the 2013 Search and Matching Conference in Paris for helpful comments. Galichon’s research has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC grant agreements no 313699, and from FiME, Laboratoire de Finance des Marchés de l’Energie. Bojilov’s work is supported by a grant of the French National Research Agency (ANR), “Investissements d’Avenir” (ANR-11-IDEX-0003/Labex Ecodec/ANR-11-LABX-0047).

Appendix: Matrix differentiation

The Kronecker product and the vectorization operation are extremely useful when it comes to studying asymptotic properties involving matrices. The idea is that matrices \(m\times n\), where m stands for the number of rows and n for the number of columns, can be seen as \(mn\times 1\) vectors in \( R^{mn}\), and linear operation on such matrices can be seen as higher order matrices. To do this, the fundamental tool is the vectorization operation, which vectorizes a matrix by stacking its columns. Introduce \(\tau _{mn}\) a collection of invertible maps from \(\left\{ 1,\ldots ,m\right\} \times \left\{ 1,\ldots ,n\right\} \) onto \(\left\{ 1,\ldots ,mn\right\} \), such that \(\tau _{mn}\left( i,j\right) =m\left( j-1\right) +i\).

Definition 1

For \(\left( M\right) \) a \(m\times n\) matrix, \(\mathrm{vec}\left( M\right) \) is the vector \(v\in \mathbb {R}^{mn}\) such that \(v_{\tau _{mn}\left( i,j\right) }=M_{ij}\).

Next, we introduce the transposition tensor \(\mathbb {T}_{m,n}\) as the \( mn\times mn\) matrix such that

The matrix operator \(T_{m,n}\) is a permutation matrix with zeros and a single 1 on each row and column. Note that \(\mathbb {T}_{m,n}=\mathbb {T}_{n,m}^{-1}\), so \(\mathbb {T}_{m,n}\mathbb {T}_{n,m}\mathrm{vec}\left( M\right) =\mathrm{vec}\left( M\right) .\) Furthermore, \(\mathbb {T}_{m,n}=\mathbb {T}_{n,m}^{*}\). The next definition deals with Kronecker product, which is closely related to vectorization.

Definition 2

Let A be a \(m\times p\) matrix and B an \(n\times q\) matrix. One defines the Kronecker product \(A\otimes B\) as the \(mn\times pq\) matrix such that

The following fundamental property characterizes the Kronecker product.

Fact 1

For all \(q\times p\) matrix X,

The following important basic properties follow.

Fact 2

Let A be a \(m\times p\) matrix and B an \(n\times q\) matrix. Then:

1. 1.

   (Associativity) \(\left( A\otimes B\right) \otimes C=A\otimes \left( B\otimes C\right) .\)

2. 2.

   (Distributivity) \(A\otimes \left( B+C\right) =A\otimes B+A\otimes C.\)

3. 3.

   (Multilinearity) For \(\lambda \) and \(\mu \) scalars, \(\lambda A\otimes \mu B=\lambda \mu \left( A\otimes B\right) \)

4. 4.

   For matrices of appropriate size, \(\left( A\otimes B\right) \left( C\otimes D\right) =\left( AC\right) \otimes \left( BD\right) \).

5. 5.

   \(\left( A\otimes B\right) ^{*}=A^{*}\otimes B^{*}\).

6. 6.

   If A and B are invertible, \(\left( A\otimes B\right) ^{-1}=A^{-1}\otimes B^{-1}\).

7. 7.

   For vectors a and \(b, a^{\prime }\otimes b=ba^{\prime }\) (in particular, \(aa^{\prime }=a^{\prime }\otimes b\)).

8. 8.

   If A and B are square matrices of respective size m and n,

   $$\begin{aligned} \det \left( A\otimes B\right) =\left( \det A\right) ^{m}\left( \det B\right) ^{n}. \end{aligned}$$
9. 9.

   \(\mathrm{Tr}\left( A\otimes B\right) =\mathrm{Tr}\left( A\right) \mathrm{Tr}\left( B\right) \).

10. 10.

    \(\mathrm{rank}\left( A\otimes B\right) =\mathrm{rank}\left( A\right) \mathrm{rank}\left( B\right) \).

11. 11.

    The singular values of \(A\otimes B\) are the product of the singular values of A and those of B.

Let f be a smooth map from the space of \(m\times p\) matrices to the space of \(n\times q\) matrix. Define \(\frac{df\left( A\right) }{dA}\) as the \(\left( nq\right) \times \left( mp\right) \) matrix such that for an \(m\times p\) matrix X,

We use the notation \(A^{-*}\) for \(\left( A^{*}\right) ^{-1}\).

Fact 3

Let A be a \(m\times p\) matrix and B an \(n\times q\) matrix. Then:

1. 1.

   \(\frac{\mathrm{d}\left( AXB\right) }{\mathrm{d}X}=B^{*}\otimes A\).

2. 2.

   \(\frac{\mathrm{d}A^{*}}{dA}=\mathbb {T}_{m,p}\).

3. 3.

   \(\frac{\mathrm{d}A^{-1}}{\mathrm{d}A}=-\left( A^{-*}\otimes A^{-1}\right) \).

4. 4.

   \(\frac{\mathrm{d}A^{2}}{\mathrm{d}A}=I\otimes A+A^{*}\otimes I\)

5. 5.

   For A symmetric, \(\frac{\mathrm{d}A^{1/2}}{\mathrm{d}A}=\left( I\otimes A^{1/2}+A^{1/2}\otimes I\right) ^{-1}\).

Reprints and permissions