1
$\begingroup$

I'm dealing with a slight variation on a classic matching problem on sets $A$ and $B$), where:

  • Set $A$ has an incomplete set of preferences (not all of $B$ is included)
  • Set $B$ has no preferences whatsoever.

I want to find an $A$-optimal matching (e.g, for any $(a_1 \rightarrow b_1), (a_2 \rightarrow b_2)$, then either $b_2$ is lower than $b_1$ or does not appear in $a_1$'s preferences, and likewise for $a_2$) between $A$ and $B$, respecting $A$'s preference lists, and where ties between members of $A$ are broken randomly. I've been trying to apply the Gale Shapely algorithm to this problem, with random preferences for B, but it appears to have degenerate cases where the above criterion is violated.

A pre-rolled solution to this problem seems to be somewhat elusive, potentially because it's so obvious. There's a related SO question, Stable marriage problem with only one side having preferences, which states the no-preference issue, but the answers only cover how to check for a perfect matching, which does not necessarily guarantee the optimality of the result with respect to $A$'s preferences. Is there an algorithm that produces an $A$-optimal matching?

Improve this question
$\endgroup$
9
  • $\begingroup$ What happens in the following case? Both $a_1$ and $a_2$ prefer $b_1$ to $b_2$. There seems to be no $A$-optimal matching in this case. Perhaps you meant "either $b_2$ is lower than $b_1$ in $a_1$'s preferences or $b_1$ is lower than $b_2$ in $a_2$'s preferences", where we put unmentioned $b$'s at the bottom of the preference lists. $\endgroup$
    – Yuval Filmus
    Aug 22, 2017 at 13:13
  • $\begingroup$ That's a good point, though I would think that in the case where $a_1$ and $a_2$ prefer $b_1$ to $b_2$ there would then be two $A$-optimal matchings. I have fixed the issue with the conjunction, thanks for pointing it out. This does seem a lot like an instance of the assignment problem with clever weights now. $\endgroup$
    – ckfinite
    Aug 22, 2017 at 13:19
  • $\begingroup$ If my interpretation is correct, you can use the following iterative algorithm. Start with any matching. While there is a pair $(a_1,a_2)$ such that $a_1$ prefers $a_2$'s partner and $a_2$ prefers $a_1$'s partner, switch their partners. This improves the matching (in the sense that the sum of the positions of matches decreases), and so this algorithm terminates after at most $n^2$ rounds. $\endgroup$
    – Yuval Filmus
    Aug 22, 2017 at 13:19
  • $\begingroup$ You have to define your problem formally. Otherwise we can't help you, since we don't know what problem you're trying to solve. $\endgroup$
    – Yuval Filmus
    Aug 22, 2017 at 13:20
  • 1
    $\begingroup$ @j_random_hacker There are $n$ elements of $A$ to match, and each has a preference order over the $n$ elements of $B$, in this scenario. Since each swap in the worst case will increase an assignment of an $a$ to a $b$ by one step, the worst case for each $a$ is that it takes $n$ swaps to reach the optimum case, and since there are $n$ $a$s, it follows that worst case running time is $O(n^2)$, $\endgroup$
    – ckfinite
    Aug 22, 2017 at 14:20

1 Answer 1

Reset to default
1
$\begingroup$

We can suppose without loss of generality that the elements of $A$ have complete sets of preferences (if an element of $A$ is indifferent to some elements of $B$, we put them at the bottom of the element's preference list).

Our goal would be to match elements of $A$ and elements of $B$ such that the resulting matching is stable in the following sense. For any two elements $a_1,a_2 \in A$, either $a_1$ prefers its current match to that of $a_2$, or $a_2$ prefers its current match to that of $a_1$.

Here are two different algorithms for solving the problem. The first uses a greedy approach. Order the elements of $A$ arbitrarily: $A = a_1,\ldots,a_n$. Let $a_1$ choose its top pick, let $a_2$ choose the top available pick, and so on. This results in a stable matching since if $i < j$ then $a_i$ prefers its current match to that of $a_j$.

A different approach, more similar to the Gale-Shapley algorithm, is iterative. Start with an arbitrary matching $f$. If there is a pair $a_1,a_2$ in which $a_1$ prefers $f(a_2)$ over $f(a_1)$ and $a_2$ prefers $f(a_1)$ over $f(a_2)$, then switch $f(a_1)$ and $f(a_2)$. This decreases the objective function $\Phi$ which is the sum over $i$ of the index of $f(a_i)$ in $a_i$'s preference list. Since $n \leq \Phi \leq n^2$ and $\Phi$ is an integer, we deduce that this algorithm terminates in $O(n^2)$ rounds.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.