Efficient Matchmaking in Assignment Games with Application to Online Platforms

While online platforms such as Uber, Lyft and Airbnb have upended the transportation and accommodation industries, similar startups have struggled to realize comparable levels of success in other industries. For example, in the home services industry, the startup Homejoy, which aspired to be the Uber for home cleaning, went bankrupt in 2015 despite having raised $40 million of funding and having assembled an impressive engineering team. Among the host of competing platforms in the home services industry, there is no consensus on how to best facilitate matches: some platforms have customers initiate contact, while others have customers post their information and wait for providers to reach out. Other platforms recommend matches and prices based on more sophisticated algorithms.

Are there fundamental reasons why matchmaking seems to be harder in certain markets than others? For a given market, what is the most efficient way to facilitate matches? This paper studies these two questions using a rigorous mathematical model that combines the assignment game of Shapley and Shubik (1971) with ideas from communication complexity theory. A market is formalized as a set of customers and providers along with a preference distribution, which specifies a joint distribution of how much benefit each customer derives from being served by each provider and how costly it is for each provider to serve each customer. This distribution is commonly known whereas the actual preferences of each agent is privately known. We quantify the difficulty of matchmaking in a given market based the number of bits agents need to communicate in order for the market to reach a good outcome. We define a good outcome as being ε-stable, which means that no pair of agents can match on their own and both improve their surpluses by ε. Note that our model allows providers to set prices endogenously, which differentiates this paper from previous works on communication complexity in matching markets.

In a market with n agents, we show that finding an ε-stable outcome only requires Θ(log n) bits of communication per agent if the preference of at least one side satisfies one of the following conditions: 1) it is predictable given agents' initial inputs of who they are and what they want (as in Ebay); or 2) it is mostly vertical, meaning that agents on this side of the market mostly agree on the relative desirability of partners (as in Uber or Lyft); or 3) the horizontal component of preferences is dense and independent, meaning that when offered a bounded number of randomly chosen partners, agents are able to find someone that satisfies their horizontal preferences with high probability (as in the market for routine home services). However, if none of these conditions hold, meaning that the horizontal component of both sides' preferences are unpredictable, non-negligible, and sparse (as in the market for nannies and non-routine home services), then finding an ε-stable outcome with high probability may require Ω(√n) bits of communication per agent. In this case we show how to find ε-stable outcomes with a near-optimal performance of O(log n √n) bits of communication, which involves both sides of the market initiating contact. Finally, we show that in thick market with dense preferences on both sides, an ε-stable outcome can be found using upfront prices and one-round of communication, with O(log2 n) bits of communication per agent. These results help practitioners to gauge when is it necessary to adopt a more complex matchmaking strategy such as allowing both sides of the market to initiate contact and to negotiate prices freely, and when it is enough to simply provide a good search interface and recommend prices based on past data.