  In several applications of real-time matching of demand to supply in online
marketplaces, the platform allows for some latency to batch the demand and
improve the efficiency. Motivated by these applications, we study the optimal
trade-off between batching and inefficiency under adversarial arrival. As our
base model, we consider K-stage variants of the vertex weighted b-matching in
the adversarial setting, where online vertices arrive stage-wise and in K
batches -- in contrast to online arrival. Our main result for this problem is
an optimal (1-(1-1/K)^K)- competitive (fractional) matching algorithm,
improving the classic (1-1/e) competitive ratio bound known for its online
variant (Mehta et al., 2007; Aggarwal et al., 2011). We also extend this result
to the rich model of multi-stage configuration allocation with free-disposals
(Devanur et al., 2016), which is motivated by the display advertising in video
streaming platforms.
  Our main technique is developing tools to vary the trade-off between
"greedy-ness" and "hedging" of the algorithm across stages. We rely on a
particular family of convex-programming based matchings that distribute the
demand in a specifically balanced way among supply in different stages, while
carefully modifying the balancedness of the resulting matching across stages.
More precisely, we identify a sequence of polynomials with decreasing degrees
to be used as strictly concave regularizers of the maximum weight matching
linear program to form these convex programs. At each stage, our algorithm
returns the corresponding regularized optimal solution as the matching of this
stage (by solving the convex program). Using structural properties of these
convex programs and recursively connecting the regularizers together, we
develop a new multi-stage primal-dual framework to analyze the competitive
ratio. We further show this algorithm is optimally competitive.
