Notes on Who gets what and why by Alvin E. Roth

I have the privilege of interacting daily with many smart colleagues having expertise in fields including machine learning, infrastructure, data science, product design, and with economists specialized in marketplace design. I am at ease discussing all of these but marketplace designs where I often feel like a toddler asking adults for explanations and searching words to efficiently express ideas. I thus asked my colleague Giorgio Martini for a book to get started, and he pointed me to Who Gets What and Why by Alvin E. Roth.

This post is my first step in developing a functional understanding of market design, and this starts with some basic terminology.

Market design terminology

Marketplace

A marketplace matches participants to generate transactions. For example, LinkedIn has a job marketplace matching job seekers with job posters, Uber has a marketplace matching riders with drivers, and school districts have their marketplaces matching students to schools.

While many marketplaces were created by fellow humans, nature also has its own marketplaces. For examples, the marketplace of peacocks searching for mates, or the food chain matching predator and prey in a given region.

Market design

Markets are governed by rules. The goal of market design is to create such rules in the pursuit of a specific goal. A fascinating aspect of markets is that participants will decide whether or not to follow the rules.

We can look at a recent article from The New York Times about tickets sales are resales. Sellers want to limit the number of tickets that are sold in a given transaction to prevent scalping. This rules makes sense, but the scalpers decided to create bot that will buy the tickets automatically as soon as they are available instead of complying with the spirit of the rule.

This is just a simple example among many others. The fact that this practice has been going on for a long time highlights how difficult it is to create a successful marketplace, even for things that should be straightforward.

Match making in a matching market

In a matching market, participants have to meet with each other to transact. A job marketplace is a good example. Job seekers need to apply on individual jobs, job posters need to review each applicant one by one, and a match is made when both meet and agree.

From a computational complexity perspective, an optimal match in a matching market is \(O(n \cdot m)\) where \(n\) and \(m\) are the number of buyers and sellers. Running an optimal matching market becomes harder and harder as we add participants.

Match making in a commodity market

In a commodity market, participants interact through a broker. Uber is a good example of a commodity market. The riders don't get to pick their drivers, they trust Uber to make a safe decision for them. Drivers have a bit more control, but only to the extent that they can accept or reject a match.

A big advantage of commodity markets is that they scale better than matching markets. Assuming that the broker does a good job, the complexity of an optimal match is now \(O(1)\) for the participants. Using Uber would be hell if each rider would need to negotiate with each driver individually.

Clearing house

A clearing house is an institution acting as a broker to facilitate exchanges. They are a useful tool when scaling a matching market to a commodity market.

It was the case for the market matching resident doctors and hospitals. Before the introduction of a national resident clearing house, each resident and hospital had to meet in order to transact. There is now a clearing house where all participants submit their preferences and match making is automated.

Designing and operating a successful clearing house is a difficult endeavor. The book exposes many failed attempts in case you want more details.

Thick and thin markets

Match making can only happen when there are enough participants. A market is thick when most participants can find what they want in it, otherwise it is thin.

If you ever wondered why restaurants would all group together in a food court, or why car dealerships establish in clusters, you now know that it is to create a thick market. Sellers have to compete against each others, but at least they can attract many buyers thanks to the diversity of the offering.

Congestion

Transactions in a market involve many steps. Congestion happens when the delay between steps is so long that it puts the transaction at risk.

Taking a mundane example, eating at restaurant usually involves:

  1. Ask for a table.
  2. Wait to be seated.
  3. Order food.
  4. Wait for food to be served.
  5. Eat.
  6. Pay.

In this simple transaction, congestion can creep in at steps two and four. If any of these becomes too long, the client can choose to leave and transact with another restaurant.

The same can happen when matching a job seeker with a job poster. If the job poster makes an offer to a candidate and this candidate takes five days to refuse it, another good candidate might have accepted a job elsewhere. Roth goes in depth on how congestion was an existential treat for the National Resident clearing house, and how they worked to fix it. I won't repeat it here, but suffice to say that it is complex and participants won't play by the rules of the marketplace when it is not done right.

Trust and safety

Nobody wants to be in harm's way to transact. While it may sound obvious, it is important to internalize when designing a market. A good litmus test to know if a market is safe is to ask:

Are participants sharing enough information for the market to be optimal?

The books have many examples of unsafe markets, but two that stick with me are:

  • Ebay had issue with payments. Some merchants never received the check they were promised and some buyers wouldn't feel comfortable sharing credit card information with random sellers. Ebay thus introduced a rating system and adopted Paypal as their payment system to make the transaction safer.

  • In New-York's school district, parents submitted a ranked list of schools they would like their child to attend. The matching process didn't guarantee the optimal outcome (e.g. if the favorite school was popular, putting it in first might make you not get your second choice because it wouldn't be available anymore when it was time to process the second choices), which lead many parents to submit a ranked list that didn't reflect their true desires.

Safety can mean many things and good marketplace design ensure that participants feel safe sharing crucial information.

Signaling

Signals are information that participants in the marketplace send to one another. In a job marketplace, signals could be about the qualification of the job applicant (e.g. diplomas) and about their interest (e.g. attending a recruiting event, or applying on a job). These signals help the participants make a decision.

From an information theory lens, we want signals to have low entropy, to carry as much information as possible. Bidding on an item on Ebay is an example of a low entropy signal. Money is involved and sending this signal has consequences. Swiping right on someone's Tinder profile is a high entropy signal. Swipes are so cheap that they aren't a good measure of interest and commitment.

Roth presents an experiment on a dating applications. Participants were each given a limited amount of virtual flowers that they could send to matches they really liked. The results was that sending these virtual flowers helped to get reciprocated matches over the traditional swipe. The recipient of such flowers were flattered to receive one of these limited flowers.

Market designers should thus be careful with the type of signal they allow on their market.

Conclusion

Coming from a natural language processing background, a perspective expressed at the end of the book connected with me:

[…] markets are like languages. Both are ancient human inventions. Both are tools we use to organize ourselves, to cooperate and coordinate and compete with one another, and ultimately to figure out who gets what. These two fundamental human artifacts play a role in all the things we do and in everything we make (we can't even make love, let alone war, without them).

The many examples of this book opened my eyes on how marketplaces are everywhere and how we are all participants whether we notice or not. Learning the basic concepts of marketplace design was extremely enjoyable and I am looking forward deepening my understanding of it.

comments powered by Disqus