Disrupting Bipartite Trading Networks: Matching for Revenue Maximization

Abstract

Online platforms and marketplaces have revolutionized everyday commerce, breaking down many of the physical and geographic barriers that previously prevented trade. Today, these online marketplaces facilitate trillions of dollars of trade and have disrupted a wide variety of markets like retail commerce (Amazon, eBay), transportation (Uber, Lyft), food delivery (Instacart, UberEats), and many others. However, the growing power of these platforms also comes at a cost, with regulatory bodies taking an increasing interest in the competitive practices of these platforms in the past years. Motivated by the interest in these competitive practices, we study the incentives facing platforms when choosing how to match their users together – e.g., buyers and sellers on Amazon. We model the role of an online platform disrupting a network of n unit-demand buyers and m unit-supply sellers. Each seller can transact with a subset of the buyers whom she already knows outside of the platform, as well as with any additional buyers to whom she is introduced or matched by the platform. Given these constraints on trade, we model prices and transactions as being induced by a competitive equilibrium. The platform's revenue is proportional to the total price of all trades between platform-introduced buyers and sellers. We consider a revenue-maximizing platform and study the effect of the platform on social welfare (the sum of transacting buyers' values for the items they receive). We show that even when the platform optimizes for revenue, the social welfare is at least an O(log(min{n,m}))-approximation to the ideal welfare, giving non-trivial guarantees for social welfare even in the presence of platform behavior. When the platform can significantly increase social welfare, i.e. when the existing market is inefficient, we give a polynomial-time algorithm that guarantees a logarithmic approximation of the optimal welfare as revenue, also attaining a logarithmic fraction of optimal social welfare in the process. In general, we show that the platform's revenue-maximization problem is computationally intractable, but we provide structural results for revenue-optimal matchings and isolate special cases in which the platform can efficiently compute them. Finally, we prove significantly stronger bounds for revenue and social welfare in homogeneous-goods markets, where each seller is selling an identical item. We prove that revenue maximization aligns perfectly with welfare maximization in these markets; any revenue-optimal platform matching also maximizes overall social welfare. In inefficient homogeneous-goods markets, we give a constant-factor poly-time approximation algorithm for revenue that also maximizes social welfare.