What is mechanism design, and why does it matter for kidneys and auctions?

Mechanism design is a field that works backward. Ordinary game theory studies a strategic environment that already exists and explains the outcomes that follow from people's strategic behavior. Mechanism design starts from the outcome someone wants and asks whether a strategic environment can be built so that the outcome arises from that behavior. The designed environment is called a mechanism. Lecture notes describe the field as sometimes called reverse game theory, and say mechanisms underlie elections, kidney exchange platforms, online dating, spectrum auctions and online advertising. Kidney exchanges and auctions are two of the most studied cases. [1]

A Darden School article describes the field as sitting at the intersection of economics, game theory and artificial intelligence, taking an engineering approach to problems where individuals, markets and institutions interact. [2]

Auctions are the main focus of the Stanford-style and MIT-style course notes in the results. In a single-item sealed-bid auction, each of n bidders has a private value for the item. Each bidder privately sends a bid. The designer then chooses an allocation rule, which gives the probability that each bidder gets the item, and a price rule, which sets what each bidder pays. A bidder's utility is her value minus her payment if she wins, and minus her payment if she does not. [1]

The designer first picks an objective, and the notes begin with maximizing welfare, then looks for rules that achieve it. The same notes point out that auctions are familiar from online marketplaces such as eBay, from the ads shown in banners and sponsored search results, and from government sales of spectrum or drilling rights. [1]

Kidney exchange is a setting without money. A patient's willing living donor may be medically incompatible with that patient. Their kidney can then be swapped with those of other patient-donor pairs so each patient receives a compatible kidney. Course notes say this need motivates a nationwide exchange where incompatible pairs register and are matched with others, and that a central design question is how to build one. Such mechanisms operate without monetary transfers, and a primary concern is strategic behavior by participants. [3] [4]

Market designers in the early 2000s noticed that the two main kinds of U.S. kidney exchange matched basic exchange forms in the matching literature on house allocation. Roth, Sönmez and Ünver then analyzed how efficient, incentive-compatible exchanges could be organized. The notes say this work formed the backbone of several programs in the U.S. and elsewhere. [5]

Their 2004 design allows exchanges of any size and lets patients rank compatible kidneys, since mismatches in HLA proteins affect survival. It uses a top trading cycles and chains mechanism, in which patients point to preferred kidneys, cycles are cleared, and chains ending in the waitlist are chosen by a selection rule. With the rules described, the notes state that it is a dominant strategy for patients to report preferences truthfully and to declare all their donors. [5]

Their 2005 design reflects medical constraints on swaps. Only two pairs may take part in one exchange, and all compatible live-donor kidneys are treated as equally likely to survive. It uses a priority mechanism, which goes down a priority list and matches each patient if possible. The notes state that it is Pareto efficient and makes truthful reporting of compatible kidneys and available donors a dominant strategy. [5]

In both cases the designer cannot simply ask participants for the truth, because they may gain by misreporting. Bidders could understate values, and patients or hospitals could withhold donors or preferences. The designed rules aim to make honest reporting the best strategy while still delivering a goal such as welfare or efficient matching. The search results also list medical residency matching as another healthcare market where design work has been applied. [1] [5] [6]