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?