Two-sided Facility Location
alijani at cs.duke.edu
||Thursday, November 2, 2017
||12:00pm - 2:00pm
||D344 LSRC, Duke
We formulate a novel set of facility location problems that we term Two-sided Facility location. We motivate this problem by two-sided markets, where agents with heterogeneous valuations/costs arrive at known locations 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 nodes in the metric space, and opens a set of virtual markets or facilities in the metric space to route the agents to. The agents at any virtual market are assumed to be matched. The platform ensures high match quality by imposing a maximum distance constraint between a supply/demand node and the facilities it is routed to. It ensures high service availability by ensuring flow of supply and demand to any virtual market are equal, and furthermore, these are at least a pre-specified lower bound. Subject to these constraints, the goal of the platform is to maximize the social surplus 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. It uses a novel LP rounding framework, and easily extends to other objectives such as maximizing volume of trade subject to weak budget balance, or maximizing 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 virtual markets and match them, ensuring a low abandonment probability of agents reduces to ensuring sufficient flow arrives at each virtual market. Such an analysis also helps us posit facility location variants that capture settings where the platform elicits deadlines truthfully by posting lotteries over different prices and wages for different deadlines.
Reza Alijani is a 3rd year PhD student in the Department of Computer Science at Duke University.
Advisor(s): Kamesh Munagala
Committee: Vincent Conitzer, Debmalya Panigrahi