Combinatorial Prophet Inequalities

DOI10.1137/1.9781611974782.110zbMATH Open1417.91251arXiv1611.00665OpenAlexW2950198148MaRDI QIDQ4575853FDOQ4575853

Aviad Rubinstein, Sahil Singla

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We introduce a novel framework of Prophet Inequalities for combinatorial valuation functions. For a (non-monotone) submodular objective function over an arbitrary matroid feasibility constraint, we give an $O(1)$-competitive algorithm. For a monotone subadditive objective function over an arbitrary downward-closed feasibility constraint, we give an $O(lognlo{g}^{2}r)$-competitive algorithm (where $r$ is the cardinality of the largest feasible subset). Inspired by the proof of our subadditive prophet inequality, we also obtain an $O(logncdotlo{g}^{2}r)$-competitive algorithm for the Secretary Problem with a monotone subadditive objective function subject to an arbitrary downward-closed feasibility constraint. Even for the special case of a cardinality feasibility constraint, our algorithm circumvents an $Omega(sqrtn)$ lower bound by Bateni, Hajiaghayi, and Zadimoghaddam cite{BHZ13-submodular-secretary_original} in a restricted query model. En route to our submodular prophet inequality, we prove a technical result of independent interest: we show a variant of the Correlation Gap Lemma for non-monotone submodular functions.

Full work available at URL: https://arxiv.org/abs/1611.00665

zbMATH Keywords

secretary problemprophet inequalitiescombinatorial valuation functionsmonotone subadditive objective function

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Auctions, bargaining, bidding and selling, and other market models (91B26) Stopping times; optimal stopping problems; gambling theory (60G40)

Cited In (24)

• Tight Revenue Gaps Among Simple Mechanisms
• Title not available (Why is that?)
• Hiring Secretaries over Time: The Benefit of Concurrent Employment
• From pricing to prophets, and back!
• Title not available (Why is that?)
• Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents
• An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions
• Prophet Inequalities for Independent and Identically Distributed Random Variables from an Unknown Distribution
• Making individually fair predictions with causal pathways
• Optimal stopping with multi-dimensional comparative loss aversion
• Prophet inequalities via the expected competitive ratio
• Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs
• Polymatroid Prophet Inequalities
• On submodular prophet inequalities and correlation gap
• Prophet Inequalities with Limited Information
• Stochastic submodular probing with state-dependent costs
• Stochastic submodular probing with state-dependent costs
• Streaming adaptive submodular maximization
• Streaming adaptive submodular maximization
• On the correlation gap of matroids
• Prophet secretary for combinatorial auctions and matroids
• Strong Algorithms for the Ordinal Matroid Secretary Problem
• A constant factor prophet inequality for online combinatorial auctions
• Title not available (Why is that?)

This page was built for publication: Combinatorial Prophet Inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575853)