Computer scientists and economists will perhaps disregard this post as pretentious. But I think that the Stable Matching problem is really cool and easily formulated, so I am going to go ahead with it anyway.
Assume, for whatever reason, that you are holding a grand ball-dancing event in which you invite 'n' men and 'n' women. Each man has a strict preference ordering over the women and analogously, every woman has a strict preference ordering over the men. Your objective is to match men with women such that the pairing has a certain 'stability' quality. For the sake of this problem, assume that you have been sent back about twenty years in time and the main pairing mechanism is still heterosexual). A given pairing is said to be unstable if there exist two pairs (Amit, Puja) and (John, Alice) say, such that Amit prefers Alice to Puja and Alice prefers Amit to John (so that both Amit and Alice have incentive to cheaton their partners). Given the fickle and uncompromising nature of men, clearly instability is an undesirable property and you would like to avoid the anguish it ensues at all cost. So your task as a match maker is to pair up men and women, one on one such that the resulting pairing is stable in the sense that there are no unstable pairs. It is interesting to note that it is not sufficient for Amit to prefer Alice to Puja to make the pairing unstable. In other words, Alice must reciprocate this bias for instability.
The first question that you might be interested in is, do stable matchings always exist?
Answer: Yes (was shown by Gale and Shapley in 1962).
Caveat: The proof breaks down for mixed (homosexual + heterosexual) preferences.
The next question that you would like to resolve, given that you are organizing this ball is whether there is some easy (efficient) way in which you can determine this matching. In other words, you are interested in an efficient algorithm that computes a stable matching. The solution (also given by Gale and Shapley in 1962) is a simple and elegant one.
Here is the algorithm. Imagine that the men and women are standing at either end of the room. The algorithm is the Men Propose, Women Reject algorithm (much like the real world).
It proceeds in rounds. In the first round, every man proposes to his most desired woman. Among the proposals that a woman receives in this round (she might receive none), she (temporarily) accepts her most desired man, and rejects everyone else. In subsequent rounds, each unpaired man (and hence one who was rejected in the previous round) proposes to the most desired woman who has not yet rejected him. In case a woman, currently matched with John receives a proposal from a man she prefers to John, she rejects John (after having led him on initially by saying yes to him in an earlier round!) and accepts this other man. The algorithm terminates when all men are paired. And this works and produces a stable matching! How much it resembles real world dynamics in a modern day society - I leave to your imagination!
PS (thanks to Vivek for pointing this out): It turns out that the Men Propose, Women Reject algorithm is optimal for men in the following sense: the algorithm produces a matching in which every man lands up with the best possible woman he could have been with in any stable matching.
Moral of the story: Always hit on the best girl even if you don't have the confidence, get ditched a few times, until you settle with the best possible woman you could possibly get.
Gale-Shapley algorithm
Stable Marriage Problem
