Theory Lunch Seminar

Wednesday, September 29, 2021 - 12:00pm to 1:00pm

Location:

In Person and Virtual ET Gates Hillman 8102 and Zoom

Speaker:

DAVID WAJC, Motwani Postdoctoral Fellow in Theoretical Computer Science https://web.stanford.edu/~wajc/

Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities

The rich literature on online Bayesian selection problems has long focused on so-called prophet inequalities, which compare the gain of an online algorithm to that of a "prophet" who knows the future. An equally-natural, though significantly less well-studied benchmark is the optimum online algorithm, which may be omnipotent (i.e., computationally-unbounded), but not omniscient. What is the computational complexity of the optimum online? How well can a polynomial-time algorithm approximate it?

Motivated by applications in two-sided matching markets, such as housing markets, we study the above questions for the online stochastic maximum-weight matching problem under vertex arrivals. For this problem, a number of 1/2-competitive algorithms are known against optimum offline. This is the best possible ratio for this problem, as it generalizes the original single-item prophet inequality problem.

We present a polynomial-time algorithm which approximates the optimal online algorithm within a factor of 0.51---beating the best-possible prophet inequality. In contrast, we show that it is PSPACE-hard to approximate this problem within some constant α < 1.

Based on joint work with Christos Papadimitriou, Tristan Pollner and Amin Saberi.

Related Reading

In Person and Zoom Participation. See announcement.

Event Website:

http://www.cs.cmu.edu/~theorylunch/

For More Information, Contact:

Keywords:

Seminar Series