0
$\begingroup$

I have a set $F$ of $n_1$ families, a set $C$ of $n_2$ children ($n_1<n_2$) and a set $M$ of feasible one-to-one matchings of the families with the children. All the children have the same preference list over the families, but the families have different preference lists.

Our objective is to select from the set $M$ a stable matching. It is clear that the family with rank 1 will be matched with the child she ranks the best among those that is matched with them in $M$, the family with rank 2 will be matched with the child she ranks the best among those that is matched with them in the matchings selected for family 1 and so on.

When the preference lists are fixed, the constraint can be modeled as follows:

$ 1 \leq \sum\limits_{j'\in J^{\leq}_{C_j^i}(i)}x_{ij'} + \sum\limits_{i'\in F^{\leq}_{i}}x_{i'C_j^i} $; $i \in F$, $j=1,\ldots,i$

with

  • $x_{ij}$ equals one if family $i$ is matched with rank $j$.
  • $C_j^i$ is the child with rank $j$ for family $i$.
  • $ J^{\leq}_{s}(i)$ is the set of children that family $i$ ranks at the same level or better than child $s$.
  • $C^{\leq}_{i}$ is the set of families that are at the same level or better than family $i$.

How to modify this constraint to take into account the changes in the preference lists?

$\endgroup$
2
  • $\begingroup$ Your constraints already allow arbitrary preference lists. $\endgroup$ Apr 25, 2020 at 14:13
  • $\begingroup$ these constraints can produce a solution that is not in $M$, so after assigning a child to a family $i$, we need to change the preference list for family $i+1$ to ensure that the selected matching is in $M$ $\endgroup$
    – Farah Mind
    Apr 25, 2020 at 14:16

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.