The Fast and the Furious: Market Design and Operations Research

Sepehr Ramyar

by Sepehr Ramyar

Sep

Have you ever lined up in front of a store for several hours on a Black Friday? Have you ever wondered why professional Wall Street (high-frequency) traders spend billions of dollars on IT infrastructure just to get their bids processed before everyone else. The reason for both these situations is fundamentally no different. In situations like these, there is value in being the first one in line. This is the same reason that prompted the ‘Sooners’ in the early 19th century to jump the gun in the race for registering land claims in Oklahoma. But what can you do when you have so many eager participants and limited resources? Or how do you optimize the performance of a system in presence of different constraints? Beginning to sound like operations research jargon?

It turns out that operations research concepts make up the machinery behind many of our everyday market transactions. From calling Uber on your smartphone, to the ads displayed on the webpages you visit every day, or even in decisions for high school admissions in many urban areas. In all such marketplaces, the market designer aims to achieve the best performance as fast as possible. The definition of performance, however, depends on the context. For instance, in the case of online ads, the best performance means choosing the most valuable ads (i.e. those with the highest willingness-to-pay) while for high school admissions, the mutual satisfaction of students and schools with the allocations probably makes the most sense. But how can this be achieved?

The primary objective of a market designer is to process the orders of participants as fast and safely as possible. Speed is important because it enables participation of more customers in the market. This is why Amazon and Airbnb have been able to obtain a larger pool of customers than traditional retailers and hotels: they provide a faster means of browsing through items and choosing the one you like most. Safety is also important. It means the customer (or the seller) would not have to worry about the other party ‘gaming’ the system. Here’s where operations research comes in.

Operations research can help us design rules for marketplaces to make them safe for everyone to participate. In the online ad market, as mentioned earlier, the desired outcome is to have each ad slot allocated to the highest bidder. But does that mean choosing the highest bidder and charging them what they bid? This is in fact the mechanism that was in place in the early days of online ads and led to ‘bidding wars’ where everyone would bid their least affordable price and minimally increasing them with competing bids.  This was not safe for the market. First, it strained the market operator’s system as competitors would continuously place bids in very short intervals. Second, it did not guarantee whether the winner would be paying equivalent of their true value for the item. The solution came from operations research: an auction where the highest bidder wins but pays the second-highest bid also known as ‘Second-Price’ auction. The second price auction guarantees ‘truth-telling’ in the sense that no participant would have an incentive to misreport their value for the item by overbidding or underbidding. The introduction of generalized second price auctions significantly improved the performance in online ad markets that are considered the cash cows of giant tech companies like Google. Later, around 2008, these auctions were optimized with ‘reserve’ prices and further boosted online ad revenues (Wurman, Wellman & Walsh, 2001; Roughgarden, 2016).

The idea of second-best choice, however, is not always the solution. In fact, for school admissions, a source of instability of the market has chronically been students and families misreporting their list of preferred schools in hopes of maximizing their chances of getting into the second-best school; because they figure listing their favorite school (which is too hard to get into) on top of the list would lower their chances of getting into the second-best school, so they list their second-best as their first choice. This leads to undesired market outcomes with some schools ending up with empty seats and some others withholding their capacity and assigning their seats based on other criteria. The solution, again, comes from game theory and operations research community: the well-known deferred acceptance (DA) algorithm. In this algorithm, students and schools both list their choices from most to least preferred and then submit it to a ‘clearing house’. The market clearing house would then match the most preferred student (by the school) to the most preferred school (by the student) given the capacity of the school. The result is astonishing: no assigned student would want to go to another school (with available capacity) and no school with full capacity would want to exchange one of its students (because that student would prefer to stay in the same school). Here, too, the mechanism is ‘incentive-compatible’ (or truthful) in the sense that students would have no incentive to misreport their list of preferred school. This algorithm was originally proposed by Lloyd Shapley and David Gale for a hypothetical ‘marriage market’ in 1962 and has since been improved and built on for many applications (Roughgarden, 2016).

Almost any market these days is run on algorithms that facilitate participation and improve efficiency of the marketplace. From kidney exchanges (Priority Pairwise Kidney Exchange algorithm) to stock exchange (Double Auction), these algorithms help operate markets in a fast and secure way that scales to the level of computation and performance required for today’s marketplaces with millions of participants and billions of transactions every day; and operations research is at the heart of what makes all these markets work.

* This article has largely been inspired by the book “Who Gets What - and Why” by Alvin Roth, a Nobel laureate in Economics that got his Ph.D. in ‘operations research’. This is a great read for anyone who is interested in learning about market design and matching markets.

 [1] Wurman, Peter R., Michael P. Wellman, and William E. Walsh. "A parametrization of the auction design space." Games and economic behavior 35.1-2 (2001): 304-338.

 [2] Roughgarden, Tim. Twenty lectures on algorithmic game theory. Cambridge University Press, 2016.