  Motivated by applications in the gig economy, we study approximation
algorithms for a \emph{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. In order to find a
matching, the platform can consider the edges $(i j) \in E$ in any order and
make a one-time take-it-or-leave-it offer of a price $\pi_{ij} = w$ of its
choosing to $i$ for completing $j$. The worker accepts the offer with a known
probability $ p_{ijw} $; in this case the job and the worker are irrevocably
matched. 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 $\frac{1}{2}(1-e^{-2})\approx 0.432$
of [BGMS21], and improve on the best known lower bounds for the correlation gap
of matching, despite applying to a significantly more restrictive setting. As a
consequence of our OCRS results, we obtain a $0.456$-approximate algorithm for
the sequential pricing problem. We further extend our results to settings where
workers can only be contacted a limited number of times, and show how to
achieve improved results for this problem, via improved algorithms for the
well-studied stochastic probing problem.
