OR student seminar

Motivated by applications in the gig economy, we study approximation algorithms for a sequential pricing problem. The input is a bipartite graph G=(I,J,E) between individuals I and jobs J. The platform has a value of v_j for matching job j to an individual worker. To find a matching, the platform can consider the edges (i, j) in any order and make worker i a one-time take-it-or-leave-it offer to complete the job j at a price of the platform's choosing, after which the worker accepts with a known probability. What is the best way to make offers to maximize revenue and/or social welfare?

The optimal algorithm is known to be NP-hard to compute (even if there is only a single job). With this in mind, we design efficient approximations to the optimal policy via a new Random-Order Online Contention Resolution Scheme (RO-OCRS) for matching. Our main result is a 0.456-balanced RO-OCRS in bipartite graphs and a 0.45-balanced RO-OCRS in general graphs. These algorithms improve on the recent bound of 0.432 of Brubach et al., and improve on the best-known lower bounds for the correlation gap of matching, despite applying to a significantly more restrictive setting. From this we obtain a 0.456-approximate algorithm for the sequential pricing problem.

We would like to thank the generosity of the Management Science and Engineering department, the Operations, Information, and Technology group at the Business School, Infanger Investment Technology, and the Diener-Veinott family for supporting this event.