Market Design is the economic study of designing marketplaces to achieve specific desired outcomes using different mechanisms or rules. Auction Theory, Matching Theory, and Game Theory are related areas of study, with Auction Theory focusing on using prices to influence market outcomes, Matching Theory focusing on finding the maximal outcome of pairs of mutually-interested participants in a market, and Game Theory focusing on optimizing decision-making of independent competing actors. Marketplaces are distinct from centralized planning in that the market participants themselves make the decisions as opposed to a centralized planning system making the decisions. Marketplaces can be seen everywhere in our lives from in nature in how animals mate, to the traditional stock exchange clearinghouse where a buyer and seller are matched at an optimal price point, to auctions like that of radio spectrum to telecom providers, to modern online job boards, websites like Ebay, Amazon, Craigslist, and Airbnb, and gig-economy apps likes DoorDash and Uber.
We’ll go over Market Design and Matching Theory, four historic examples, what causes markets to fail, and finally the principles of good Market Design.
Multi-sided Markets
Market Design historically focused on commodity markets but can be applied both to matching markets and commodity markets - commodity markets focus on batches of a product with price as the primary driver of a transaction (e.g. energy markets, stock markets, e-commerce) whereas matching markets focus on distinct participants each with their own preferences and the best match between them (e.g. vacation homes, gig-economy work, job boards, dating apps). Matching markets are typically more complex and harder to optimize given they have more variables and the pairs of participants require mutual interest in each other. Additionally, matching markets have to deal with more market congestion which we dive into later.
A multi-sided matching marketplace, unlike a typical e-commerce website selling goods for a single merchant to customers, matches two (or more) market participants to generate a mutually-beneficial transaction. Matching Market Design has become an increased topic of interest over the last 25 years as digital platforms have emerged to offer online marketplaces for goods and increasingly for work through gig-economy mobile applications. Online two-sided marketplaces provide the function of Clearinghouse as the broker matching two participants together to generate a transaction. Many markets in our day-to-day lives face failures in their design which incentivize the wrong participant behavior. Matching markets in particular often run astray by requiring participants to strategize to not only consider their own preferences but also the preferences of all other participants and how they might set their preferences accordingly, a form of Game Theory.
The desired outcome for a multi-sided matching market is a Stable Matching - a set of pairings between two sets of elements where there does not exist any pair where both prefer each other to their current pairing. In the classic example of marriages, this would mean there would be no two potential partners in a group of matches who both prefer each other more than their existing partners. This is the optimal solution sought after when designing markets.
History of Market Design and Matching Theory
The invention of money was a monumental market design achievement in that it overcame the problem of a seller having to find a buyer who wanted their goods and who had goods they wanted in return (a “double coincidence”). With money one could simply receive money to spend elsewhere. Matching markets still face this double coincidence challenge of having to find two participants who mutually are interested in the other.
In the 1960’s, David Gale and Lloyd Shapely invented the Gale–Shapley algorithm, also known as the Deferred Acceptance algorithm, to guarantee the solution of a Stable Matching between two equally sized sets of elements in O(n^2) time complexity. The algorithm consists of multiple rounds where in each round unmatched participants in set A are tentatively matched to participants in set B whom they have not yet been matched with previously. Each matching of participants in set B are evaluated sequentially, taking the new match if preferable or otherwise sticking with the existing match. This process repeats in rounds until all participants are matched stably and there are no blocking pairs - matches where the two participants are not optimally matched to each other. The application of this matching algorithm, it’s evolutions, and Deferred Acceptance can be seen in many markets but we’ll focus on three well-documented examples: the National Resident Matching Program (NRMP) in 1999, the New England Program for Kidney Exchange in 2003, and the Boston Public School System (BPS) in 2006. We’ll also discuss a financial non-matching market design example in The Chicago Mercantile Exchange.
Example - The National Residency Matching Program (NRMP)
Residency programs in the US are notoriously competitive, both with residency candidates applying to top programs and for top programs recruiting the top residency candidates. In fact, in the 1940’s most residency candidates were getting locked into residency programs an entire two years before graduation. This caused all sorts of issues and so in the 1950’s, residency candidates and programs collaborated to design a market to manage this matching process more effectively. Both residency candidates and residency programs would submit their ranked preferences and then a set of matches would be generated. This simple market design worked well for 30+ years but began to face issues as times changed and more and more couples/partners were both applying to residency programs simultaneously. Further, preferences were often being set strategically instead of participants setting their true preferences.
Alvin Roth is well known in the fields of market design, matching theory, game theory, and economics, earning a Nobel Prize in Economics in 2013 and instructing as a professor of economics at both Stanford and Harvard. In 1984, Roth published a paper on the National Residency Matching Program (NRMP) proving that a market design built upon the Gale–Shapley Deferred Acceptance algorithm with multiple rounds produced Stable Matchings for unmarried medical students - the problem was with matching couples to residency programs (Random Paths to Stability in Two-Sided Matching, Roth, 1990). Couples on the other hand, would both have to submit their individual preferences separately and strategize on their preferences so they could be matched together. Therefore, in the 1990’s Roth redesigned this market to address the issue with matching partners and having participants set their true preferences. In the new algorithm designed by Alvin Roth, couples entering residency are treated as a single unit and a match is only made if both candidates match with the residency program, further the matches are set through multiple rounds so that a better match can replace a less-optimal match from an earlier round. This design was enticing to both residency candidates and residency programs making the market thick with participants, it made it safe for residents to state their true preferences, and it avoided congestion in waiting too long to learn the results by requesting preferences from all participants up-front and then quickly computing the stable matching result.
The algorithm has been in use since 1999 and today fills more than 20,000 positions for new medical graduates each year. The market design has been further adopted by more than 36 other labor market clearinghouses (The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design, Roth, 1999).
Example - The New England Program for Kidney Exchange
A second example of Market Design and using Deferred Acceptance can be seen in the New England Program for Kidney Exchange. Over 70,000 people require organ transplants every year in the US and there are often long lists of patients waiting with fewer than 20% getting matched successfully. Each organ transplant requires two compatible participants including compatible blood types so a patient’s immune system doesn’t reject the transplanted organ. With live donors, a one-to-one match is required and performed in tandem simultaneously as doing so sequentially could have a participant change their mind whereas creating a legal binding contract would be illegal as it involves organs. If a compatible match could not be made between a donor and patient it left the patient without the organ they needed. Every year, more than 8,000 people would be removed from organ transplant waiting lists due to lack of matches and becoming too sick, while thousands passed away without the treatment they needed.
Alvin Roth was brought in to study and redesign the New England Program for Kidney Exchange. The solution was to create a market with a database of organ donors and design a matching algorithm which supports multi-pair matches over multiple rounds to find the optimal Stable Matching. For example, if a one-to-one match is not possible, a two pairwise exchange may be possible where four participants are involved and both transplants happen simultaneously (four operating rooms). With a large enough number of donors and patients almost all feasible transplants can be accomplished through exchanges among no more than three patient-donor pairs. Larger than a three pairwise exchange is typically considered too complicated and requires too many resources, though up to 12-person exchanges have been performed through this process. This was a huge step forward, expanding the market and enabling matches of more than just 1 pair in a given exchange opened all new matching possibilities and improved the number of organ donor recipients who could successfully be treated. This design has become the standard for kidney exchanges worldwide and is the basis for the new US nationwide kidney exchange (Kidney Exchange, Roth, 2003).
Example - Boston Public Schools (BPS)
The third example of Market Design can be seen in Boston Public Schools (BPS). BPS looked to improve a prior market design used since the 1950’s which had students select their top schools and then weighted higher matches where the school the candidate was qualified for and was their top choice. The design was optimized to give as many students as possible their first choice. This meant it was costly for students to list a first-choice that they would not succeed in getting because other less qualified students marking it their first choice would get higher priority. Strategic students would even consider the capacities and demands of each school when setting their preferences. This in turn incentivized gaming the system and having students strategically select schools they had a higher likelihood of acceptance into as their top choice rather than their true top choices. In 2006, BPS wanted to fix this market design to make the dominant strategy having students state their true preferences. The two major changes to the design included expanding the list of preferences from 3 to 12 and having multiple rounds of matching where in each round matches are marked as only tentative so that in later rounds students with higher scores could still be considered if they are a better match (Deferred Acceptance). This ultimately resulted in a Stable Matching where no student received a less preferred assignment than a lower-priority student for that school; further all students preferred their outcome to any other stable set of matches (Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions, Roth, 2007).
Example - The Chicago Mercantile Exchange
Financial markets have seen a major shift with computers from empirical analysis of stocks and other assets traded infrequently with humans involved into per-millisecond transactions traded automatically by computers running custom financial models. This created an advantage for automated trading software which is located with the quickest digital connection to the trading market as this enables that application to trade an asset before a competitor and influence prices accordingly (“latency arbitrage” or “sniping”). For example, in one scenario a financial institution with latencies of 16ms was cut out of the market by another institution just 3ms faster with 13ms latencies. Some estimates place the value of a speed advantage for an institution at over $5 billion annually. Financial institutions have therefore invested billions of dollars in fiber-optic and microwave telecommunication infrastructure to minimize the latency between them and the financial market. This is ultimately a failure in market design, where traders are incentivized with first-come-first-serve trades and institutions to invest capital into telecommunication speed - competition by speed rather than by price.
The application of Market Design within financial markets can be seen in the proposal submitted to the The Chicago Mercantile Exchange. The proposal suggested a minor change which would restore price competition and remove the speed incentive. Rather than the standard continuous limit orders which most financial exchanges follow, the algorithm proposed using a discrete batch auction instead, where all orders are first collected in 250 millisecond to 1 second batches and then executed together at a single price where the maximum number of orders can be completed. This disincentivizes the ultra-low-latency “arms race” as the winner of a transaction is not solely based on the first party to submit the order with the lowest latency (The High-Frequency Trading Arms Race: Frequent Batch Auctions as a Market Design Response, Budish, 2015).
Why Markets Fail
In the above examples we see several cases where markets were failing and were modified to become successful in achieving their desired outcomes. To summarize, markets fail for the following reasons: Thickness - Not enough participants or volume in the market to quickly or easily match participants (e.g. selling products accessible to few in the world like space launches or hundred-million-dollar properties) Safety - Unsafe to participate in the market or unsafe for participants to state their true preferences (e.g. physical safety, privacy of participants, strategic preference setting) Transparency - Participants with access to vastly different sources of data to inform decision making in the market (e.g. insider trading) Timing - Market time-window is too fast (e.g. first-come-first-serve, not giving participants enough time to participate in the market) Timing - Offer timings are disjointed (e.g. exploding potential match, decisions made without participant weighing all potential matches) Congestion - Getting matches in a timely manner (e.g. waiting days to see if a match was successful, long cycle times)
Principles of Good Market Design
Now that we have read through several examples of Market Design and why markets fail, let’s consider what makes a well designed, well performing marketplace. There are three key elements of a well designed marketplace: Thickness, volume Safety, fairness, transparency Simplicity, speed, low congestion
The first element required for a well functioning market is thickness and volume. Thickness refers to the number of participants active in the market. An optimal matching of market participants can only occur when there are enough participants in the market, otherwise the market is considered “thin” and suboptimal matches result. Thick markets provide participants ease in finding a match to complete a transaction.
The second element is safety, fairness, and transparency. Safety refers not only to physical and digital safety, but also safety for participants to share their true preferences rather than strategizing what information to share or not. The market should evaluate all participants against equal criteria. The market rules and mechanisms should be transparent and well understood by all participants. Further, the signal of preferences from participants should be as strong and full of information as possible.
Third, markets require simplicity, speed, and low congestion to attract participants and prevent them from leaving mid-transaction. The market should be simple enough to easily understand, see the current state of, and easy to participate in. Likewise, the market needs to have the appropriate speed - fast enough for participants to not leave mid-transaction, while also slow enough for enough participants to have a chance to be considered. When markets become thick they often become congested, so balancing a thick market with speed is essential. Thickness and speed also provides liquidity for participants as additional transactions can be made easily and quickly.
With these three elements in place, markets can be designed and operated optimally for all participants. In the next article, we will see how we can apply these principles of good Market Design and the learnings from Matching Theory to design effective multi-sided marketplaces within software applications.
For further reading on Market Design itself, I highly recommend the book from Nobel Prize winner Alvin Roth - “Who Gets What and Why”.