Title: Two-sided Facility Location,
Abstract: Recent years have witnessed the rise of many successful e-commerce
marketplace platforms like the Amazon marketplace, AirBnB, Uber/Lyft, and
Upwork, where a central platform mediates economic transactions between buyers
and sellers. Motivated by these platforms, we formulate a set of facility
location problems that we term Two-sided Facility location. In our model,
agents arrive at nodes in an underlying metric space, where the metric distance
between any buyer and seller captures the quality of the corresponding match.
The platform posts prices and wages at the nodes, and opens a set of facilities
to route the agents to. The agents at any facility are assumed to be matched.
The platform ensures high match quality by imposing a distance constraint
between a node and the facilities it is routed to. It ensures high service
availability by ensuring flow to the facility is at least a pre-specified lower
bound. Subject to these constraints, the goal of the platform is to maximize
the social surplus (or gains from trade) subject to weak budget balance, i.e.,
profit being non-negative.
We present an approximation algorithm for this problem that yields a $(1 +
\epsilon)$ approximation to surplus for any constant $\epsilon > 0$, while
relaxing the match quality (i.e., maximum distance of any match) by a constant
factor. We use an LP rounding framework that easily extends to other objectives
such as maximizing volume of trade or profit.
We justify our models by considering a dynamic marketplace setting where
agents arrive according to a stochastic process and have finite patience (or
deadlines) for being matched. We perform queueing analysis to show that for
policies that route agents to facilities and match them, ensuring a low
abandonment probability of agents reduces to ensuring sufficient flow arrives
at each facility.