Ensuring Stable Marriages: The Gale-Shapley Algorithm
By Ishan Kashyap Hazarika
At its heart, economics is the study of choices, of institutions and how they are arranged. From markets to elections and laws to crime, economists have pushed the boundary of the field far and wide, and to every topic, they have touched, they have tried to introduce the formal rigor with which they revolutionized the study of markets in the late nineteenth century. With economists have traveled their concerns— does the system reach an equilibrium? Can central policies make it better or is it efficient on its own? How can the concern of efficiency be balanced with other normative concerns?
Does such a dichotomy even exist?
The study of perfect commodity markets reached its zenith in the mid-twentieth century— with the landmark proofs by Arrow, Debreau, and others of the existence of an equilibrium, of the efficiency of the equilibrium (the First Welfare Theorem) and the independence (in at least one sense) of the issues of efficiency and equality (the Second Welfare Theorem). The study of the more general social choice problem— can individual ordinal preferences be ever satisfactorily combined into one aggregate social preference ordering— led to an impossibility (the Arrow’s Impossibility Theorem). This led to the questioning of many systems that tried to do so— such as popular elections. The journey continued.
One very interesting class of systems is constituted by the “two-sided markets”. Think about it, in a commodity market, every buyer has preferences over the commodities, but the commodities do not have any preferences over the buyers— they cannot have, they are not sentient beings, they are just “things”. Let us informally call it a “one-sided market”. But what if both sides have preferences over each other? While for commodity markets this may be impossible, in certain other important institutions, this is the obvious case— such as traditional marriages (for the sake of simplicity, I consider only monogamous heterosexual marriages here, leaving other marriages to future articles). Here, all the males have preferences over the females, and all the females have preferences over the males too. It is a challenge to determine if a “stable allocation” akin to the commodity-market equilibrium always exists in these institutions, and if it does, how can we attain it? For theory-minded people like me, this speculation is enough to raise curiosity. But even for the more practically minded people— this is an important problem, as the problem appears equally prominently in many human-organ donation systems, in the allocation of doctors to hospitals, and also in the resource allocation of crucial computing systems (I leave the question of “how” for the readers to ponder). The existence of “stable allocations” in these systems is the famous “Stable Marriage Problem” in Cooperative Game Theory and the solution is the famous ‘Gale-Shapley Algorithm’. So let us dive into it.
Let us characterize the problem in a more detailed manner first. For the sake of simplicity, let us assume that the number of males is equal to the number of females (dropping this and some other assumptions lead to the ‘Rural Hospital Theorem’ which we shall discuss in a future article). Every male, in his mind, has a preference-ordering over the females, for example, his most preferred ‘future-bride’ is Miss A, and the next preferred is Miss E, then Miss C and so on until all the females are ranked. This preference ordering can be different for different males, or the same. Similarly, every female has a preference ordering over the males— the most preferred is Mr. X, then Mr. Y, and so on. A marriage-allocation then is a set of ordered pairs, which tells us which male will get married to which female.
Before defining a stable marriage, let me first provide an example of an unstable marriage. Say, Raju is married to Sakhi, and Santosh is married to Rani. But, Raju prefers Rani over his current wife Sakhi and Rani also prefers Raju over her current husband Santosh. This is an ‘unstable allocation’ because Raju and Rani can leave their respective spouses to marry each other instead— it is beneficial for both of them. Thus, an unexploited mutually beneficial contract exists in this case. In some allocations, however, such mutually beneficial contracts do not exist, that is, it is never the case that any two people (out of all the males and females) prefer each other instead of their current spouses— such an allocation is called a ‘stable allocation’. The question we seek to answer is, given any possible set of preference-orderings and any number of males and females, is it always possible to find a stable allocation, and how?
Gale-Shapley Algorithm.
In the beginning, we call all the males and females “free”. Then, in the algorithm, every woman proposes her most preferred male. If a male has received multiple proposals, he accepts the proposal from his most-preferred female out of the proposals he has received. If a female’s proposal gets accepted, she and the male she proposed become temporarily ‘engaged’. If a female’s proposal gets rejected, which means she remains free, in the next round, she would propose her second most-preferred male. Now, in the first round, all the males were free. But in this second round, a male may be free or engaged. A free male will accept the proposal from the most preferred female of his out of the ones who proposed to him. For an engaged male, if all the new proposals he has received in this round are inferior to him than his fiancé from the previous round, he will reject all the new proposals. But if some new proposals turn out to be more preferred than his current fiancé, he will switch to the new most-preferred female. The old fiancé will newly become free. In the third round, just like the second round, all the free females (including those whose proposals have never been accepted and the ones who have recently got dis-engaged) would propose to their third-most preferred males and the algorithm continues.
Note these observations— once engaged, a female can become free again, but not the male. In every round, a male either remains engaged with the previous fiancé or switches to a more preferred fiancé. This means that every successive round becomes better or stays equally good than the previous round for each male.
Also note, that for females, in each round, conditions can get only worse or stay the same. This is because every female starts from the most preferred male and either remains engaged or successively has to switch to less preferred males.
From this, we know that the algorithm will not continue ad-infinitum because there are a finite number of males and females. At worst, a female would have to propose the least-preferred male, but she must stop after that.
I claim, that when the Gale-Shapley Algorithm ends, whichever marriage-allocation we find is a stable allocation. Now let us prove this.
We prove this by contradiction. Assume to the contrary, that there exist two males X and Y and two females A and B by the end of the Gale-Shapley Algorithm, such that X is engaged to B and Y is engaged to A, but X prefers A more than B and A also prefers X more than Y.
The impossibility of this situation is evident—we have already made the observation that in each successive round, the condition of the females worsens or stays the same, but does not become better and for males, in each successive round, the condition improves or stays the same. Because every female proposes successively less preferred males (most-preferred to second-best to third best and so on), and because A is engaged to Y, she must have in one previous round each, proposed every male she prefers more than Y. But X is more preferred to Y, therefore in some previous round, she must have proposed X. When she would have proposed to X, only two things might have happened, either X accepted the proposal then or rejected it. If X accepted the proposal then, he was at least for that round, engaged to A. But then after a few rounds, he could not have ended up marrying B, because B is less preferred than A, and in each successive round, the condition of the males improves or remains the same, but does not deteriorate. It is thus impossible for X’s fate to deteriorate from once being engaged with A to being married to B. The other possibility is that when A proposed X in that previous round, A rejected. But that means, that at least at that round, A was engaged to someone who was preferred even more than A. But then again, in the future rounds, A’s fate could not have deteriorated to getting engaged to B, because, as already explained, the condition of males under this algorithm either improves in each successive round or stays the same, but does not deteriorate. Because both the scenarios contradict our true observation, the allocation cannot be unstable. Therefore, it must be stable.
This is a very simple algorithm, as we see, but a very powerful one. This entire business of proposing and rejecting, of course, need not be done by the prospective brides and grooms, a social planner with a computer can run the algorithm on it. It can even be done using plain old pen and paper, if the number of males and females is less or if the planner is a fast implementer. The complexity of the algorithm is simply O(n-square).
What is interesting for many Economics readers perhaps is not how and on which device the algorithm is run, but that a stable allocation exists, no matter how “bizarre” the preferences are, and that we know exactly how to find one. This, as we see, is a very important result, both theoretically and practically. As described, the algorithm is currently being used to assign graduating medical students to their first hospital (a different problem but same solution) and to connect internet users to servers, etc. In 2012, Lloyd Shapley and Alvin Roth received the Nobel Prize in Economics “for the theory of stable allocations and the practice of market design”.
Ishan is a student of Economics from Hansraj College, University of Delhi. He is interested in behavioral economics, decision theory, and the emergent properties of systems.