Content deleted Content added
→Observations: Comment |
|||
Line 30:
If someone could supply useful references for this it would be helpful, something along the lines of how the algo fails or does little when everybody ranks the choices the same. In public school assignments (a variation of H/R), parents tend to adhere to a rigid pecking order, but I haven't seen a metric that describes this aspect of the input.
:The algorithm never "fails", in that it always terminates in finite time and the result is always stable. Using the algorithm, the members of the "suitor" group all get their best possible choice for any stable pairing, and the "suitees" get their worst possible choice for any stable pairing. If all the members of group A have the same preferences, then there is only one stable pairing, which can be produced by the following process: each member of group B, in order of highest to lowest rank (according to group A preferences), chooses the best possible partner from the members of group A not yet chosen. So in the high school example, the highest ranked school would get to choose the students it wanted most, then the next-highest ranked would choose its preferred students from those not chosen by the highest ranked, and so on. [[User:Augurar|Augurar]] ([[User talk:Augurar|talk]]) 07:18, 14 February 2012 (UTC)
== Solutions for constrained problems ==
| |||