Home / Opinion / Online-views /  Opinion | The Gale-Shapley algorithm and the future of work

The World Economic Forum ‘Future of Jobs Report 2018’ presents a picture of a world gearing up for its fourth industrial revolution. While the first three revolutions were powered by the steam engine, electric power, and digital technologies, the fourth revolution will be powered by technology breakthroughs in fields such as artificial intelligence, the Internet of Things, 3-D printing, and energy storage.

The good news is that there is a net positive outlook for jobs, with the growth of new jobs outstripping the elimination of old functions. However, there is likely to be a geographic repositioning of jobs based on skill availability and not just labour costs. There is also likely to be an increased level of structural unemployment as a large proportion of workers will have to adapt and pick up skills in the course of changing jobs, rather than through training programmes conducted within companies. By 2022, 54% of all employees will require significant re- and upskilling. Besides full-time staff, companies will rely on an extended talent ecosystem of external contractors, temporary staff and freelancers to address skills gaps.

A change in workplaces will be accompanied by the changing mindset of the worker. With millennials, those born from the 1980s to the early 2000s, becoming a dominant part of the workforce, workers will exhibit shifting preferences towards an improved work-life balance with a heightened focus on individual advancement, and close relationships, including with supervisors. Thus, attrition levels seem set to rise, driven not just by employer needs but also worker preferences. Does game theory offer any tools that could help with the changing contours of the job market?

In the early 1960s, the mathematician David Gale sent game theorist Lloyd Shapley a puzzle in the mail: Given a set of N men and N women, each with preferences regarding the other gender, is there always a ‘stable matching’—a set of pairings of men and women that would be proof against elopement? In other words, can we form couples in a way that no man and woman would run away together on account of preferring each other over their assigned partners? By return mail, Shapley gave his answer. Yes, a stable matching always exists. Further, there exists an algorithm that would allow us to find such a matching.

Think of the job market as a polygamous or polyandrous marriage game, with one employer hiring multiple workers. The challenge is to assign workers to employers such that no worker-employer pair likes each other more than the employer or worker with whom they are paired. With such an assignment, there would be no attrition.

In the context of the job market, the algorithm proposed by Shapley involves putting workers in the driver’s seat. Think of a cluster of call centres run by Amazon, Flipkart and Google, where attrition rates are at a stratospheric level. Instead of the current paradigm of ‘I poach yours while you poach mine’, companies would participate in a centralized process where each would first make a pitch to all the job seekers. Next, each worker would be free to apply to companies one by one, in the order of their preferences. If rejected by one company, they could apply to their next choice. In this way, the process would continue till all workers were placed. No formal job offers would be made till the end. Gale and Shapley prove that this would result in a stable matching, in which the workers would be placed in the highest ranked company possible for them in any stable matching.

In the world we live in, such an algorithm is not acceptable to companies. Fuelled by testosterone, each believes that it is the workplace of choice and stands to gain from job market choppiness. They have no time for initiatives like no-poach agreements, and certainly not for centralized hiring processes. Further, while the Gale-Shapley algorithm gives workers their best possible employment, it gives the passive side, the employers, their worst set of employees relative to what they would get in any stable matching. Why should companies accept this?

Let us divide the job market into an external job market, which represents the interface of the company with potential employees, and an internal job market, which represents the movement of workers to new roles within the company. Given the transformations of the workplace, both markets are likely to become highly relevant. For internal movement, the Shapley-Shubik algorithm certainly offers an efficient design to allow employees to gravitate to roles that suit them best, while keeping the interests of the company in mind at the same time (remember, employees are not paired to their top choice of role but to the best one possible in a stable matching).

For external roles as well, the gains to stability, in terms of lower attrition, saved costs of training, and increased banks of implicit knowledge, outweigh the potential loss of a star employee to a rival company. If we look at the way the job market functions today, it is very similar to the Gale-Shapley algorithm, except that workers are actually hired by companies they ‘propose to’, instead of companies waiting till a stable matching emerges through the entire process of proposals and rejections. In this situation, it may not be difficult to convince companies as well as competition regulators that there is a better way, and that the Gale-Shapley algorithm offers useful tips for designing the labour markets of the future.

With inputs from Anurag Sinha, student at MDI Gurgaon

Rohit Prasad is a professor at MDI, Gurgaon, and author of Blood Red River. Game Sutra is a fortnightly column based on game theory.

Comments are welcome at

Catch all the Business News, Market News, Breaking News Events and Latest News Updates on Live Mint. Download The Mint News App to get Daily Market Updates.
More Less
Subscribe to Mint Newsletters
* Enter a valid email
* Thank you for subscribing to our newsletter.

Recommended For You

Edit Profile
Get alerts on WhatsApp
Set Preferences My ReadsWatchlistFeedbackRedeem a Gift CardLogout