Senior Honors Thesis Defense: Barter with Limited Liquidity

Abstract

Matching algorithms are widely used to allocate resources in contexts in which money is morally repugnant. Real-world applications of such algorithms include the assignment of students to public schools in New York and Boston, the assignment of medical students to hospital residency programs, and the reassignment of kidney-transplant patients and their voluntary donors to blood-type compatible pairs. Little research has focused on designing algorithms for markets in which money is not repugnant, yet barter is preferable. Such markets often arise amidst hyperinflation or limited liquidity, as observed during numerous economic crises, including those in Greece (2009), Zimbabwe (2008), Argentina (1998), and the former USSR (1990s).

We present a model of barter markets with limited liquidity based on the House Allocation problem proposed by Shapley and Scarf (1974). We study the Top Trading Cycle algorithm, the standard non-monetary matching algorithm, and propose modifications to incorporate monetary exchange. The game-theoretic effects of these modifications are analyzed with a focus on stability, strategy- proofness, incentive-compatibility, and welfare maximization. The algorithms are then tested on datasets of synthetic markets, and compared on empirical measures of the above game-theoretic properties.