Algorithms for Two-sided Online Marketplaces

Abstract

The recent emergence of new successful two-sided online platforms has transformed the concept of a marketplace. Numerous two-sided mechanism design problems, including those studied in this thesis, are motivated by these platforms. Similar to any other mechanism design problem, we wish to optimize an objective in the presence of selfish agents. However, there are unique features to a two-sided market, such as supply uncertainty and the need for ensuring budget balance, which make these problems particularly challenging. In our problems, we design models to capture the two-sidedness, identify the challenges, and use algorithmic techniques to solve these problems.We start with a Bayesian single item auction with n independent buyers. For this problem, we show how the existence of a trusted intermediary can result in a better outcome for buyers without hurting the seller's revenue. In this model, the intermediary gets to see the true valuations of buyers and will reveal some information after that in the form of a signal. The intermediary does not have any control over agents after sending this signal, and any agent only maximizes their utility. This essentially means that the seller will run an optimal auction conditioned on receiving any signal. For this problem, we design approximately optimal ways of revealing information. The previous problem is an interesting model to show how a platform can mediate in the market and improve the outcome for every agent. That problem is a single item static problem. Next, we focus on pricing in two problems with multiple dynamic agents on the seller side. The first problem is an extension of the multiple-choice prophet inequality to the setting in which each item might disappear after an a priori unknown amount of time. This can be viewed as a way to model the supply uncertainty arising because of the fact that different sellers might depart after some time. Considering the importance of prophet inequalities in online posted pricing mechanisms, we hope that incorporating features of two-sided markets in the model and finding new prophet inequalities will be useful and provide new insights. In our last problem, we design a model to capture a general dynamic two-sided market. In our model, agents (buyers and sellers) with heterogeneous valuations/costs, service quality requirements, and patience levels (or deadlines) arrive over time. Both buyers and sellers arrive to the market following Poisson processes, and each buyer/seller has a private value/cost for service, as well as a private patience level for receiving/providing service. In addition, each agent has a known location in an underlying metric space, where the metric distance between any buyer and seller captures the quality of the corresponding match. The platform knows the distribution over values/costs and patience levels and can post prices and wages at nodes in the metric space, as well as choose agents for matching. It uses these controls to maximize the social surplus subject to weak budget balance while guaranteeing a high match quality and a service time (with a high probability) smaller than their patience.