From pricing to prophets, and back!

Abstract

© 2018 Elsevier B.V.In this work we prove that designing PPMs is equivalent to finding stopping rules for prophets. This extends the connection that any prophet type inequality can be turned into a PPM with the same approximation guarantee (Hajiaghayi et al. 2007; Chawla et al. 2010). Our reduction is robust under multiple settings including matroid feasibility constraints, or different arrival orderings. One fundamental observation implied by this result is that designing PPMs in general is equally hard from an approximation perspective to designing PPMs when the valuations are regular.