Prophet inequalities and secretary problems have been extensively studied in recent years due to their elegance, connections to online algorithms, stochastic optimization, and mechanism design problems in game theoretic settings. Rubinstein and Singla developed a notion of combinatorial prophet inequalities in order to generalize the standard prophet inequality setting to combinatorial valuation functions such as submodular and subadditive functions. For non-negative submodular functions they demonstrated a constant factor prophet inequality for matroid constraints. Along the way they showed a variant of the correlation gap for non-negative submodular functions. In this paper we revisit their notion of correlation gap as well as the standard notion of correlation gap and prove much tighter and cleaner bounds. Via these bounds and other insights we obtain substantially improved constant factor combinatorial prophet inequalities for both monotone and non-monotone submodular functions over any constraint that admits an Online Contention Resolution Scheme. In addition to improved bounds we describe efficient polynomial-time algorithms that achieve these bounds.
翻译:近几年来,对先知的不平等和秘书问题进行了广泛研究,原因是其优雅、与在线算法的连接、随机优化和游戏理论环境中的机制设计问题。Rubinstein和Singla发展了一个组合先知不平等的概念,目的是将标准的先知不平等环境推广到组合评估功能,如子模块和子添加功能。对于非负的子模块功能,它们表现出了非负的预知对子模块制约的一贯不平等。与此同时,它们展示了非负的子模块功能的关联差距的变式。在本文中,我们重新审视了它们的相关性差距概念以及相关性差距的标准概念,并证明这些界限更加紧凑和清洁。通过这些界限和其他洞见,我们大大改进了单调和亚模块对接受在线内容解析计划的任何制约的常态组合先知不平等。除了改进了界限外,我们还描述了实现这些界限的有效多时算法。