Stable matchings, generating functions, and optimal transport


(24 Feb 2019)

Left to do here:

  1. Explain why quasi-linear utilities are called “transferable”
  2. Clean up the discussion of the basic model
  3. Prove the first proposition
  4. Prove the second proposition
  5. Discussion about what could happen in the non quasi-linear case
  6. Add references

The Stable Matching model

In an idealized (that is, simplified) labor market situation, each worker chooses among all firms which would be the best for them to work, conversely, each firm chooses which workers would be the best for them to hire. The Stable Matching Model is used by economists to model such a situation. The stable model is not exclusive to employment markets, it is used to model any situation where you have two types of agents deciding whether to pair up according to what partner is best for each of them. What is the essential for the model is the assumption that agents make rational decisions and have definite and complete information about the utility of each of their possible choices.

This as much detail about the model I can give without using more notation. So let’s get to it. It will be helpful to keep using the interpretation of a labor market, so I will be referring to the two types of agents as workers and firms, even if all what follows will apply to many other situations. I will deal only with the continuum setting, and simply note here that most (if not all) of what I say here extends in some way or another the discrete setting. Lastly, a simplifying assumption in this model is that each worker chooses just one firm, and each firm chooses just one worker.

The basic assumptions of the model are:

$\bullet$ A set $X \subset \mathbb{R}^p$, representing workers.

$\bullet $ A set $Y \subset \mathbb{R}^q$, representing firms.

$\bullet$ A utility function given by $G:X\times Y \times \mathbb{R}\to \mathbb{R}$, which is assumed to be continuous. The meaning of $G(x,y,v)$ is the following: if worker $x$ works for firm $y$ and produces for them a utility of $v$, then $x$ gets a utility of $G(x,y,v)$. Lastly, the function $G$ is strictly decreasing with respect to the variable $v$.

Definition: The fac that $G$ is strictly decreasing in $v$ means that for each $x,y$ the function $v\to G(x,y,v)$ is invertible and has a unique inverse which is also decreasing. This defines a function $H(x,y,u)$, which can be easily be seen to be continuous (thanks to the continuity assumption on $G$). In particular,

\[G(x,y,H(x,y,u)) = u \text{ and } H(x,y,G(x,y,v)) = v.\]

Since $H(x,y,\cdot)$ is defined as an inverse to $G(x,y,\cdot)$ it is easy to see that it represents the following: if firm $y$ hires worker $x$ and gives them a utility of $u$, then $y$ will get a utility of $H(x,y,u)$.

The utility functions $G$ and $H$ is how we will encode the assumption that each worker and each firm has, as I said earlier, ‘‘definite and complete information’’. Each worker and each firm knows how much utility they will get based on who they match with and what utility transfer takes place (respectively, $G(x,y,v)$ and $H(x,y,u)$).

Now, how does the model work? It does not concern with the extended process by which workers and firms choose one another and choose how much utility they are willing to transfer (i.e. how much a worker wants to make, how much a firm wants a worker to pruduce), but instead studies a final matching of workers and agents. This means each worker has decided on $u(x)$, the utility they would be willing to work for, and conversely each firm $y$ has decided on $v(y)$, the utility they would be willing to hire someone for. So we have a pair of scalar functions

\[u:X\to\mathbb{R},\; v:Y\to\mathbb{R},\]

moreover, each worker $x$ has chosen a firm $T(x)$ and each firm $y$ has chosen a worker $S(y)$. This means that $u,v$ and the functions $T(x)$ and $S(y)$ satisfy the functional equations

\[u(x) = G(x,T(x),v(T(x))),\; v(x) = H(S(y),y,u(S(y)))\]

This leads to the following definition.

Definition: A matching or outcome is a pair of scalar functions $u,v$ and a pair of maps $T,S$

\[u:X\to\mathbb{R},\;v:Y\to\mathbb{R},\;T:X\to Y,\; S:Y\to X,\]

all such that for every $x\in X$ and every $y\in Y$ we have

\[u(x) = G(x,T(x),v(T(x))),\; v(x) = H(S(y),y,u(S(y)))\]

A matching is stable if no worker or firm would be better off if they switched their respective choices.

Therefore, we see that stable matchings are the same as matchings where the utility functions form are conjugate.

Proposition: A matching $(u,v,T)$ is stable if and only if $u= v^* $ and $v = u^*$.


\[T(x) \in \partial u(x) \text{ for every } x \in X\]

Perfectly transferable utilities

The case that has been studied most widely is the case of perfectly transferable utilities. In this case the respective generating function $G(x,y,v)$ is quasi-linear, that is linear in the $v$-variable, so

\[G(x,y,v) = b(x,y)-v,\]

for some function $b:X\times Y\to\mathbb{R}$.

The central planner problem

Then, the planner is interested in maximizing the total welfare

\[\int_{X\times Y} b(x,y) \;d\pi(x,y)\]

The dual problem

The problem is now to minimize

\[\int_{X}u(x)\;d\mu(x) + \int_{Y}v(y)\;d\nu(y)\]

among all pairs $(u,v)$ satisfying the pointwise constraint

\[u(x)+v(y) \geq b(x,y)\]

Proposition: There is at least one pair $(u,v)$ minimizing the dual functional, moreover

\[u = v^* \text{ and } v = u^*.\]

The dual problem is, as its name suggests, closely related to the central planner problem.

Theorem: The optimal solution to the dual problem agrees with the solution to the central planner problem

\[\max \int_{X\times Y} b(x,y) \;d\pi(x,y) = \min \int_{X\times Y} b(x,y) \;d\pi(x,y)\]

Moreover, any solution $\pi$ to the Central Planner problem and any solution $(u,v)$ to the Dual Problem must satisfy the relation

\[u(x)+v(y) = b(x,y) \;\;\text{ for}\;\pi\text{-a.e. } (x,y)\]

A corollary of this theorem is that for quasi-linear utilities there is always at least one stable outcome: a triad $(u,v,T)$ resulting from the theorem.

When utilities are not quasi-linear