Pricing in Dynamic Two-sided Markets with Service Guarantees

We consider dynamic two-sided markets, where buyers and sellers arrive over time following Poisson processes. Each agent has private value and patience level for receiving/providing service, and a known location in an underlying metric space. The platform posts prices and wages at nodes in the metric space, as well as choose agents for matching to simultaneously ensure three orthogonal objectives: 1) maximizing profit; 2) minimizing maximum metric distance of any match; and 3) minimizing abandonment probability of an accepted agent. We consider a natural class of scheduling policies, and develop LP rounding techniques that find approximately optimal policies.