Marriage Market with Indifferences: A Linear Programming Approach

Abstract

We study stable and strongly stable matchings in the marriage market with indifference in their preferences. We characterize the stable matchings as integer extreme points of a convex polytope. We give an alternative proof for the integrity of the strongly stable matching polytope. Also, we compute men-optimal (women-optimal) stable and strongly stable matchings using linear programming. When preferences are strict, we find the men-optimal (women-optimal) stable matching.

Appendix

The following example shows how the selection of weights influences the optimal solution reached.

Example 4

Let $M=\left\{ m_{1},m_{2}\right\}$, $W=\left\{ w_{1},w_{2},w_{3},w_{4}\right\}$ and the preference profile R

$$\begin{aligned} \begin{array}{ll} R_{m_{1}}:\left[ w_{1},w_{2}\right] ,w_{3},w_{4}; ~~~~~~ &{} R_{w_{1}}:\left[ m_{1},m_{2}\right] ; \\ R_{m_{2}}:w_{1},w_{3},w_{2}; ~~~~~~ &{} R_{w_{2}}:m_{2}; \\ ~~~~~~ &{} R_{w_{3}}:m_{2}; \\ ~~~~~~ &{} R_{w_{4}}:m_{1}. \end{array} \end{aligned}$$

$S\left( R\right) =\left\{ \mu _{1},\mu _{2}\right\}$ is given by

$$\begin{aligned} x^{\mu _{1}}=\left( \begin{array}{cccc} 1 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 1 &{} 0 \end{array} \right) \mathrm{and} ~~~x^{\mu _{2}}=\left( \begin{array}{cccc} 0 &{} 0 &{} 0 &{} 1 \\ 1 &{} 0 &{} 0 &{} 0 \end{array} \right) . \end{aligned}$$

Both matchings are men-optimal.

   Consider two different selections of weights:

$$\begin{aligned} \alpha = \left( \begin{array}{cccc} 3 &{} 3 &{} 2 &{} 1 \\ 3 &{} 1 &{} 2 &{} 0 \end{array} \right) \mathrm{and}~~\alpha ^{\star }=\left( \begin{array}{cccc} 3 &{} 3 &{} 2 &{} 1 \\ 30 &{} 10 &{} 20 &{} 0 \end{array} \right) . \end{aligned}$$

If we compute the IPS, the solution will be a men-optimal stable matching for any selection of weights. Despite this, the solution of IPS with the weights $\alpha _{i,j}$ will be the stable matching $\mu _{1}.$ Meanwhile, the solution of ${\mathrm{IPS}^\star }$ with the weights $\alpha ^\star _{i,j}$ will be the stable matching $\mu _{2}.$ So, the solution depends on the selection of the weights.

The following example shows that for a marriage market with indifferences, if we change the linear program from a maximization problem to a minimization problem, the new linear program does not compute one of the women-optimal stable matchings.

Example 5

Let $M=\left\{ m_{1},m_{2},m_{3}\right\}$, $W=\left\{ w_{1},w_{2},w_{3}\right\}$ and the preference profile R be such that

$$\begin{aligned} \begin{array}{ll} R_{m_{1}}=\left[ w_{1},w_{2}\right] ,w_{3}; ~~~~~~ &{} R_{w_{1}}=m_{1},m_{2},m_{3}; \\ R_{m_{2}}=\left[ w_{1},w_{2}\right] ,w_{3}; ~~~~~~ &{} R_{w_{2}}=\left[ m_{1},m_{2},m_{3}\right] ; \\ R_{m_{3}}=w_{1},w_{2},w_{3}; ~~~~~~ &{} R_{w_{3}}=m_{1},m_{2},m_{3}. \end{array} \end{aligned}$$

$S\left( R\right) =\left\{ \mu _{1},\mu _{2},\mu _{3}\right\}$ is given by

$$\begin{aligned} x^{\mu _{1}}=\left( \begin{array}{ccc} 1 &{} 0 &{} 0 \\ 0 &{} 1 &{} 0 \\ 0 &{} 0 &{} 1 \end{array} \right) ,~ x^{\mu _{2}}=\left( \begin{array}{ccc} 0 &{} 1 &{} 0 \\ 1 &{} 0 &{} 0 \\ 0 &{} 0 &{} 1 \end{array} \right) ,~ x^{\mu _{3}}=\left( \begin{array}{ccc} 1 &{} 0 &{} 0 \\ 0 &{} 0 &{} 1 \\ 0 &{} 1 &{} 0 \end{array} \right) . \end{aligned}$$

Notice that $\mu _{3}$ is the unique women-optimal stable matching.

Consider the selection of weights:

$$\begin{aligned} \alpha =\left( \begin{array}{ccc} 2 &{} 2 &{} 1 \\ 2 &{} 2 &{} 1 \\ 30 &{} 20 &{} 1 \end{array} \right) . \end{aligned}$$

If we compute the IPS (minimization),

$$\begin{aligned} \begin{array}{ccc} \mathrm{IPS} ~~~~~~ &{} \min &{} \sum \limits _{(i,j)\in A}\alpha _{i,j}x_{i,j} \\ ~~~~~~ &{} \text{ s.t. } &{} x\in C^{*},~x\in \{0,1\}. \end{array} \end{aligned}$$

The solutions of IPS are the stable matchings $\mu _{1}$ and $\mu _{2},$ which are not woman-optimal.