Computing optimal online matching is hard for random arrivals

Computational Hardness of Online Stochastic Matching

Data Structures and AlgorithmsComputational ComplexityComputer Science and Game Theory

Summary

Finding the best way to match online requests to fixed resources as they arrive randomly is a difficult problem. The paper shows that even with simple graph structures and known probability patterns for requests, calculating the absolute best matching strategy is computationally very hard. This means no fast algorithms can guarantee near-perfect solutions unless some major assumptions in computer science are overturned. The results answer open questions about how complexity changes when requests arrive in random orders or independently.

What this means in practice

  • For online marketplace engineers: Know that computing perfect matching policies for random request arrivals can be infeasible, guiding practical algorithm design towards heuristics instead.
  • For cloud resource schedulers: Avoid investing effort into optimal scheduling in stochastic settings with random arrivals, since computing it exactly is proven computationally hard.

A theory result. No direct application yet.

Authors

Yifeng Teng, Zongjun Yang

Abstract

In the online stochastic matching problem on a bipartite graph, offline vertices are given in advance, and online requests arrive sequentially from known distributions, each matched immediately and irrevocably to a free neighbor or rejected. Computational hardness results of the optimal online strategy have been known only for instances where online vertices have a fixed arrival order [Papadimitriou et al., 2024]. For random-order arrivals or even i.i.d. arrivals, it has been long open since the problem was proposed [Feldman et al., 2009]. In this paper, we give the first computational hardness results for online stochastic matching with random-order arrivals. In particular, we prove that for known i.i.d. arrivals, computing the online optimum is APX-hard, ruling out a Polynomial-Time Approximation Scheme unless P = NP, even in unweighted graphs with two offline neighbors per online vertex. For random-order arrivals, even when there is only one offline node (i.e., the prophet secretary setting), computing the optimal online policy is #P-hard, resolving an open problem since [Dütting et al., 2023].