Matching models with nontransferable utility

Alfred Galichon (NYU+ScPo)

'math+econ+code' masterclass on equilibrium transport and matching models in economics

With python code examples

© 2018-2022 by Alfred Galichon. Past and present support from NSF grant DMS-1716489, ERC grant CoG-866274 are acknowledged, as well as inputs from contributors listed here.

If you reuse material from this masterclass, please cite as:
Alfred Galichon, 'math+econ+code' masterclass on equilibrium transport and matching models in economics, June 2021. https://github.com/math-econ-code/mec_equil

References

Textbooks

Papers

Setting up the model

Populations

Preferences

Representing the model

Let's first load the libraries we will need.

We create the NTU_market class to encompass that information and store it in a convenient way:

The following print_prefs method prints the ordinal preferences of the agents:

We simulate such a market and print the corresponding preferences:

The following example is taken from [RS90], example 2.17

Stable matchings

We shall see two notions of stable matchings with non-transferable utility (NTU):

Stability in the Gale-Shapley sense

Assume that there is one individual per type:
$n_x = 1$ and $m_y = 1$ for all $x\in\mathcal{X}$ and $y\in\mathcal{Y}$.

As before, $\mu_{xy}\in\{0,1\}$ will be a dummy variable equal to 1 iff $x$ is matched with $y$,
and $u_x$ and $v_y$ are the payoffs of worker $x$ and firm $y$ at equilibrium.

Definition. $(\mu,u,v)$ is a stable outcome in the Gale-Shapley sense if:

(i) Population constraints are satisfied
$\left\{ \begin{array}[l] ~\sum_{y} \mu_{xy} + \mu_{x0} = n_{x}=1 \\ \sum_{x}\mu_{xy} + \mu_{0y} = m_{y}=1 \end{array} \right.$

(ii) There is no blocking pair and all individuals are rational:
$ \max \{ u_x - \alpha_{xy},v_y - \gamma_{xy} \} \geq 0$, and
$u_x \geq 0$ and $v_y \geq 0$

(iii) Strong complementarity:
$\mu_{xy}>0$ implies $u_x = \alpha_{xy}$ and $v_y = \gamma_{xy}$
$\mu_{x0}>0$ implies $u_x = 0$
$\mu_{0y}>0$ implies $v_y = 0$

Remark

The following function detects stable matchings.

Let's go back to example 2.17 in [RS90], and let's check the stability of the following matching:

Let's try again with the following alternative matching:

Some useful functions

Let's construct some useful functions that will be useful later.

Deferred acceptance: Gale and Shapley's algorithm

The reference for this section is [GS62].

Principle: Workers make offers to firms that have not rejected them yet. Define:

For $B \subseteq \mathcal{X} \times \mathcal{Y}$, we introduce the following notations:

Deferred acceptance algorithm of Gale and Shapley.

At time $t=0$, all firms are avaiable to anyone $A^{0} =\mathcal{X} \times \mathcal{Y}$.

Iterate over $t$:

$ \left\{ \begin{array}{l} P^{t}=\left\{ xy\in \mathcal{X}\times \mathcal{Y}:y\in \arg \max_{y\in A^{t}\left( x\right) \cup \left\{ 0\right\} }\left\{ \alpha _{xy}\right\} \right\} \\ E^{t}=\left\{ xy\in \mathcal{X}\times \mathcal{Y}:x\in \arg \max_{x\in P^{t}\left( y\right) \cup \left\{ 0\right\} }\left\{ \gamma _{xy}\right\} \right\} \\ A^{t+1} =A^{t} \backslash \left\{ P^{t} \backslash E^{t} \right\} \end{array} \right. $

Repeat until $P^{t} =E^{t} $, i.e. no offer is rejected.

Let's implement as follows:

Test on our example:

We investigate a bit more systematically:

Deferred acceptance revisited: Adachi's algorithm

The reference for this section is [A00] and [GL21].

Adachi's algorithm.

Set initially $v^0_y$: say $v^0_y < \min_{x\in \mathcal{X}_0} \left\{ \gamma_{xy} \right\}$.

Iterate over t:

$\left\{ \begin{array}{l} u_{x}^{t+1}=\max \left\{ \max_{y\in \mathcal{Y}}\left\{ \alpha _{xy}:\gamma _{xy}\geq v_{y}^{t}\right\} ,\alpha _{x0}\right\} \\ v_{y}^{t+1}=\max \left\{ \max_{x\in \mathcal{X}}\left\{ \gamma _{xy}:\alpha _{xy}\geq u_{x}^{t+1}\right\} ,\gamma _{0y}\right\} \end{array} \right. $

until $u^{t+1} = u^{t}$.

We now implement Adachi's algorithm. It will be based on a pair of functions uo_from_vo and vo_from_uo which implement the maximization problem above, namely:
$\max \left\{ \max_{y\in \mathcal{Y}}\left\{ \alpha _{xy}:\gamma_{xy}\geq v_{y}\right\} ,\alpha _{x0}\right\}$, and
$\max \left\{ \max_{x\in \mathcal{X}}\left\{ \gamma _{xy}:\alpha _{xy}\geq u_{x}\right\} ,\gamma _{0y}\right\}$.

Adachi's algorithm iterates the loop above:

We try it on running_mkt:

Next, we investigate a bit more Adachi's algorithm similarly to what we did above with Gale and Shapley's algorithm, and in comparison with the latter:

Testing an alternative representation of Adachi

In this section, we show experimentally that Adachi's algorithm can equivalently be expressed by the following formulation, see [GL21]:

Adachi Bis algorithm.

Set initially $v^0_y$: say $v^0_y < \min_{x\in \mathcal{X}_0} \left\{ \gamma_{xy} \right\}$.

Iterate over t:

$\left\{ \begin{array}{l} u_{x}^{t+1}=\max \left\{ \max_{y\in \mathcal{Y}}\left\{ \alpha _{xy}:\gamma _{xy}\geq v_{y}^{t}\right\} ,\alpha _{x0}\right\} \\ v_{y}^{t+1}=\max \left\{ \max_{x\in \mathcal{X}}\left\{ \gamma _{xy}:\alpha _{xy}= u_{x}^{t+1}\right\} ,\gamma _{0y}\right\} \end{array} \right. $

until $u^{t+1} = u^{t}$.

Reformulating Adachi and Gale-Shapley coordinate updates algorithm

[GL21] reformulate Adachi's and Gale-Shapley algorithms as a variants of the (blockwise) Gauss-Seidel coordinate update algorithm.

As usual, change the sign of $u_{x}$ take $p=\left( u,-v\right) $ and define
$\left\{ \begin{array}{l} Q_{x}\left( p\right) =p_{x}-\max_{y\in \mathcal{Y}}\left\{ \alpha _{xy}:p_{y}\geq -\gamma _{xy},0\right\} ,x\in \mathcal{X} \\ Q_{y}\left( p\right) =p_{y}-\min_{x\in \mathcal{X}}\left\{ -\gamma _{xy}:\alpha _{xy}\geq p_{x},0\right\} ,y\in \mathcal{Y}% \end{array}% \right.$

Adachi as Gauss-Seidel

[GL21] reformulate Adachi's algorithm as a (blockwise) Gauss-Seidel algorithm.

Start by $p_{x}^{0}=\max_{y\in \mathcal{Y}_{0}}\left\{ \alpha _{xy}\right\} $ and $p_{y}^{0}=\max_{x\in \mathcal{X}_{0}}\left\{ -\gamma _{xy}\right\} $, which are such that $e\left( p\right) \geq 0$.

Adachi reinteprets as a blockwise Gauss-Seidel algorithm
$\left\{ \begin{array}{l} p_{x}^{t+1}:Q_{x}\left( p_{x}^{t+1},\left( p_{y}^{t}\right) _{y}\right) =0, \\ p_{y}^{t+1}:Q_{y}\left( p_{y}^{t+1},\left( p_{x}^{t+1}\right) _{x}\right) =0.% \end{array}% \right.$

We test numerically that Adachi and Gauss-Seidel coincide:

Gale-Shapley as damped Gauss-Seidel

[GL21] reformulate Gale and Shapley's algorithm as a damped blockwise Gauss-Seidel algorithm.

Gale and Shapley's proposal step reformulates as
$\left\{ \begin{array}{l} p_{x}^{t+1}=decr_{x}\left( p_{x}^{t}\right) \text{ if }Q_{x}\left( p_{x}^{t+1},\left( p_{y}^{t}\right) _{y}\right) >0\text{, } \\ p_{x}^{t+1}=incr_{x}\left( p_{x}^{t}\right) \text{ if }Q_{x}\left( p_{x}^{t+1},\left( p_{y}^{t}\right) _{y}\right) <0 \\ p_{x}^{t+1}=p_{x}^{t}\text{ if }Q_{x}\left( p_{x}^{t+1},\left( p_{y}^{t}\right) _{y}\right) =0, \\ p_{y}^{t+1}:Q_{y}\left( p_{y}^{t+1},\left( p_{x}^{t+1}\right) _{x}\right) =0% \end{array}% \right.$
where
$decr_{x}\left( p\right) =\max_{y\in \mathcal{Y}_{0}}\left\{ \alpha _{xy}:\alpha _{xy}<p\right\} $ is the next value below $p$ (in terms of the $\alpha _{xy}$'s), and
$incr_{x}\left(p\right) =\min_{x\in \mathcal{X}_{0}}\left\{ \alpha _{xy}:\alpha _{xy}>p\right\} $ is the next value above $p$.

We test numerically that Gale and Shapley and damped Gauss-Seidel coincide:

Comparing running times

We build a wrapper that keeps track of the times.

Enumeration of stable matchings

The following algorithm, described in [RS] p. 62, enumerates all stable matchings.

First, we implement a convenient method that returns a list of matched pairs.

The following method returns the matchings (as designed by the payoff vectors) that are immediately above (or below) a given matching.

Let's run an example:

The following method lists all stable matchings, starting with the lattice upper bound for side $\mathcal{X}$.

Aligned preferences

Following [NY09], we define aligned preferences as the situation when $\alpha_{xy}=\gamma_{xy}=\varphi_{xy}$.

We setup a derived class for this called Aligned_NTU_market:

The MaxMaxLex algorithm was proposed in [GGH21] to look for a stable matching in this type of markets. It looks for the pair $xy$ that maximizes $\varphi_{xy}$, matches $x$ and $y$, and removes them from the available individuals. We implement into:

We compare the MaxMaxLex algorithm with Adachi:

Aggregate stable matchings

The reference for this section are [GH19] and [GHS21].

Aggregate stability

We now allow for the possibility that there are more than one individual per type:
$n_x$ and $m_y$ don't need to be equal to one for all $x\in\mathcal{X}$ and $y\in\mathcal{Y}$.

As in the previous lecture, $\mu_{xy}$ is the mass of $xy$ pairs at equilibrium,
and $u_x$ and $v_y$ are the payoffs of worker $x$ and firm $y$ at equilibrium.

Definition. $(\mu,u,v)$ is an aggregate stable outcome if:

(i) Population constraints are satisfied
$\left\{ \begin{array}[l] ~\sum_{y} \mu_{xy} + \mu_{x0} = n_{x} \\ \sum_{x}\mu_{xy} + \mu_{0y} = m_{y} \end{array} \right.$

(ii) There is no blocking pair and all individuals are rational:
$ \max \{ u_x - \alpha_{xy},v_y - \gamma_{xy} \} \geq 0$, and
$u_x \geq 0$ and $v_y \geq 0$

(iii) Strong complementarity:
$\mu_{xy}>0$ implies $ \max \{ u_x - \alpha_{xy},v_y - \gamma_{xy} \} = 0$
$\mu_{x0}>0$ implies $u_x = 0$
$\mu_{0y}>0$ implies $v_y = 0$

We implement the distance-to-frontier function in this NTU matching setting as:

The following function detects aggregate stable matchings:

A first example

Consider the following example:

Solve this using Gale and Shapley into:

It is interesting to note that while u_x= [0.6 0.3 0. ] and v_y= [0.3 0.3] are stable, one can decrease utility of some agents and remain stable (in the aggregate sense).

A second example: one car, two passengers

In the next example we have one car and two passengers of the same type.

The sensible solution consists in matching the car to one of the passengers, and leave the other passenger unmatched. However, it is not a stable solution.

However, the above solution is aggregate stable if $u=1$ for the car and $v=0$ for both passengers.

Deferred acceptance with aggregate stable matchings

The DARUM algorithm is an aggregate version of deferred acceptance. It is based on the specification of aggregate choice functions $C_{\mathcal{X}}$ and $C_{\mathcal{Y}}$ on each sides of the market:

The DARUM algorithm is then:

Initialization: $\mu _{xy}^{A,0}=\min \left( n_{x},m_{y}\right) $

Repeat:

Until $| \mu ^{P,t}-\mu ^{D,t} |$ becomes below tolerance.

We implement the DARUM algorithm generically as follows -- we'll have to specify our aggregate choice functions later:

The function aggregateChoice above has not been defined yet; it will be a wrapper function to various aggregate choice functions.

We shall implement the case with no heterogeneity (heterogeneity = 'none') first, and the logit case later.

Case with no heterogeneity

We have in that case:
$\begin{array}{l} C_{\mathcal{X}}\left( \overline{\mu }\right) =\arg \max_{\mu \geq 0} &\left\{ \sum_{xy}\mu _{xy}\alpha _{xy}\right\} \\ s.t.~ &\sum_{y\in \mathcal{Y}}\mu _{xy}\leq n_{x} \\ ~ &\mu _{xy}\leq \overline{\mu }_{xy} \end{array}$
and
$\begin{array}{l} C_{\mathcal{y}}\left( \overline{\mu }\right) =\arg \max_{\mu \geq 0} &\left\{ \sum_{xy}\mu _{xy}\gamma _{xy}\right\} \\ s.t.~ &\sum_{x\in \mathcal{X}}\mu _{xy}\leq m_{y} \\ ~ &\mu _{xy}\leq \overline{\mu }_{xy} \end{array}$

We build this into:

We verify that in the case when there is one agent per type, DARUM coincides with Gale and Shapley at every step.

Aggregate stable matching with heterogeneity

Logit case

We next implement the logit case, in which:
$\begin{array}{l} C_{\mathcal{X}}\left( \overline{\mu }\right) =\arg \max_{\mu \geq 0} &\left\{ \sum_{xy}\mu _{xy}\alpha _{xy} - \sum_{xy}\mu _{xy} \log \mu _{xy} \right\} \\ s.t.~ &\sum_{y\in \mathcal{Y}}\mu _{xy}\leq n_{x} \\ ~ &\mu _{xy}\leq \overline{\mu }_{xy} \end{array}$

The solution to the above problem has

$\mu _{xy}=\min \left\{ \mu _{x0}e^{\alpha _{xy}},\overline{\mu }% _{xy}\right\} $

where $\mu _{x0}$ solves

$\mu _{x0}+\sum_{y\in \mathcal{Y}}\min \left\{ \mu _{x0}e^{\alpha _{xy}},% \overline{\mu }_{xy}\right\} =n_{x}$

We build this into:

Run it on the one car example, for which we have:
$\left\{ \begin{array}{l} \mu_{x0}+\min\{\mu_{x0},\mu_{0y} \} e = 1 \\ \mu_{0y}+\min\{\mu_{x0},\mu_{0y} \} e = 2 \end{array}\right. $
thus $\mu_{0y}=\mu_{x0}+1$, so
$\mu_{x0} = (1+e)^{-1}$, $\mu_{0y} = (2+e)/(1+e)$
and $u_x = \log(1+e)$ and $v_y =\log(1+e) - \log(1+e/2)$.

Solution using IPFP

As shown in the previous lecture, one can solve the problem using IPFP = Gauss-Seidel algorithm, as done in [GKW19].

This consists of iterately:
a. solving in $\mu_{x0}$ the equation
$\mu_{x0}+\sum_y \min \left\{ \mu _{x0}e^{\alpha _{xy}}, \mu _{0y}e^{\gamma _{xy}} \right\}=n_x,$
and:
b. solving in $\mu_{0y}$ the equation
$\mu_{0y}+\sum_x \min \left\{ \mu _{x0}e^{\alpha _{xy}}, \mu _{0y}e^{\gamma _{xy}} \right\}=m_y.$
until the update become below tolerance.

The solution is given by
$\mu_{xy} = \min \left\{ \mu _{x0}e^{\alpha _{xy}}, \mu _{0y}e^{\gamma _{xy}} \right\}.$

We build this into:

We run the IPFP on the one-car example:

On the running_mkt example:

Interestingly, in this example, the steps taken by both algorithms are exactly the same.

However, this is far from being the case in general. This is not surprising given that IPFP is a Gauss-Seidel algorithm, while DARUM is a deferred acceptance algorithm. See for example: