Monday, April 01, 2013

[fzivohih] Stable marriage problem inverse

Given a stable matching, determine each person's ranking of the other people.  It is interesting when actions (or lack of the action of desertion in the case of a stable matching) can reveal preferences.

Perhaps we need several stable matchings?  Perhaps subsets matched with other subsets (and assuming the complements of each subset do not exist)?  Can we query certain subsets versus other subsets to an oracle which produces a stable matching?  Can we query certain matchings to an oracle which answers whether or not it is stable?  If not stable, the oracle could return one couple which would desert their assigned partners for each other.

No comments :