On June 29, eighteen years ago, the world saw the publication of the first book in a series that changed the reading habits of children around the world. The first book, called Harry Potter and the Philosopher’s Stone written by then an unknown author, JK Rowling, came out on this date.

The seven-book series, now a cultural icon, has been translated into over 60 languages and even forced the New York Times to start a separate best-seller list for children’s literature in 2000.

The word Muggles meaning (in the series) non-magical folk like us, now finds a place in the OED, meaning a person who has no magical power or more generally lacks a certain skill or skills.

The plot The series is a classic tale of good versus evil set in an enchanted world of wizards and witches that co-exists with our world.

It is at the same time a coming of age story set in the Hogwarts School of Witchcraft and Wizardry where Harry and his friends hone their wizarding skills and use them to prevent the Dark Lord, Voldemort, and his evil coterie from taking over the world.

The book is full of many magical devices that will resonate with readers, such as the Anti-Cheating Quill that prevents students from cheating in exams and the Cloak of Invisibility which renders its wearer invisible.

Our favourite is a tattered old hat called the Sorting Hat which assigns students to one of the four Houses at Hogwarts when they first arrive there.

Finding the right house The Hogwarts School was founded thousands of years ago by four great wizards and witches of the time, Godric Gryffindor, Rowena Ravenclaw, Helga Hufflepuff and Salazar Slytherin. The school has four Houses named after its founders and the job of the Sorting Hat is to put new students into one of these Houses.

Gryffindor House is for those who are brave at heart. The Ravenclaws are the smartest of the lot. Slytherin is for those who are cunning and great leaders, and does not admit anyone with Muggle blood in their lineage.

Hufflepuff “accepts all the rest”. It doesn’t mean Hufflepuffs are stupid. They are extremely loyal, goodnatured and kind at heart.

But the Hat’s task is not that simple — it also takes the preferences of the students into account when assigning them to a House.

For instance, Draco Malfoy, Harry’s arch-enemy, is sorted into Slytherin before the Hat barely touches his head. Malfoy’s qualities match Slytherin’s ideal candidate so much that the Hat does not even have to think.

On the other hand, the Hat speaks to Harry saying he would go on to achieve great things in Slytherin. Harry, knowing Slytherin House’s reputation for turning out evil wizards and witches, does not want to belong in Slytherin.

Taking Harry’s choice into account along with his various qualities, the Hat eventually sorts him into Gryffindor.

Thus, the Sorting Hat is a smart hat that plays a key role in matching students to Houses that will nurture them the best and make them better witches and wizards, i.e., an efficient allocation of resources.

Studying matching Economics is about allocating scarce resources in an efficient manner. Usually the prices do a good job of solving this problem bringing together buyers and sellers who then trade at the price that satisfies both sides.

Yet, sometimes, legal or ethical concerns may not allow for prices making efficient allocation tricky. In a short paper, Douglas Gale and Lloyd Shapley (Nobel Prize, 2012) tackled this problem using a simple scenario that we can all identify with.

They called it the “marriage problem” where an identical set of men and women are seeking partners. Women have a ranking over the set of men and vice versa. They then devised a simple algorithm to solve this problem which laid the foundation for studying matching.

The algorithm The Gale-Shapley algorithm as this is also known works as follows. In the first round, each man proposes to the woman who is his first choice. Each woman rejects all unacceptable proposals if more than one acceptable proposal is received, says “maybe” to the most preferred among those.

In the next round, each man proposes to the most preferred woman he has not yet proposed to. Each woman follows the same rule as in the first round. Notice that the proposal allows women to trade up by rejecting a man she had tentatively accepted in a previous round in favour of a better mate.

The algorithm stops when no proposals are rejected and each woman is matched to the man she had tentatively accepted.

Observe that in the end there cannot be a man or woman without a mate, since the man would have proposed to this woman at some point and if she rejected him, she would have found a better partner. Moreover, these matches are stable.

Suppose Chacha and Chachi have found mates different from each other. If Chacha prefers Chachi to his current mate, then he would have proposed to her before proposing to his current mate.

If she prefers him over her current mate she would have consented to Chacha’s proposal. Thus, no more gains from trade are possible!

Applications Matching theory has many applications. It can range from matching individuals to rooms in a hostel called one-sided matching since the rooms really do not have preferences over their occupants, to matching workers to firms or schools students to houses called two-sided matching.

Matching was most famously used by Al Roth (Nobel Prize, 2012) in the US to match graduates from medical schools who have to complete residency to hospitals. It is also used to match students to public schools in the Boston and New York saving parents lots of worry.

Perhaps most important is the application in one-sided matching, where an algorithm called top-trading cycle is used to design complicated swaps among patients for organ transplants.

The idea is that while you may not be able to donate a kidney for your own kin, you may have a better match with someone else, who may have a better match with yet another person who can donate a kidney to your loved one. New research is afoot to do the same for other organs such as lungs.

The time is perhaps right to think about implementing such algorithms in India.

These are days when parents are harried and children are anxious: all kinds of exams results and college cut-off marks are out. Students are seeking admission to engineering/medical programmes, or into degree programs in universities.

Such algorithms would go a long way towards making everyone’s life more zen.

Acharya is a Harry Potter aficionado who ultimately plans to be a doctor. Sarangi teaches microeconomics and game theory at Virginia Tech.

Related Topics