License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.82
URN: urn:nbn:de:0030-drops-129488
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12948/
Go to the corresponding LIPIcs Volume Portal

Zhang, Hanrui

Improved Prophet Inequalities for Combinatorial Welfare Maximization with (Approximately) Subadditive Agents

pdf-format:
LIPIcs-ESA-2020-82.pdf (0.5 MB)

Abstract

We give a framework for designing prophet inequalities for combinatorial welfare maximization. Instantiated with different parameters, our framework implies (1) an O(log m / log log m)-competitive prophet inequality for subadditive agents, improving over the O(log m) upper bound via item pricing, (2) an O(D log m / log log m)-competitive prophet inequality for D-approximately subadditive agents, where D ∈ {1, … , m-1} measures the maximum number of items that complement each other, and (3) as a byproduct, an O(1)-competitive prophet inequality for submodular or fractionally subadditive (a.k.a. XOS) agents, matching the optimal ratio asymptotically. Our framework is computationally efficient given sample access to the prior and demand queries.

BibTeX - Entry

@InProceedings{zhang:LIPIcs:2020:12948,
  author =	{Hanrui Zhang},
  title =	{{Improved Prophet Inequalities for Combinatorial Welfare Maximization with (Approximately) Subadditive Agents}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{82:1--82:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12948},
  URN =		{urn:nbn:de:0030-drops-129488},
  doi =		{10.4230/LIPIcs.ESA.2020.82},
  annote =	{Keywords: Prophet Inequalities, Combinatorial Welfare Maximization, (Approximate) Subadditivity}
}

Keywords: Prophet Inequalities, Combinatorial Welfare Maximization, (Approximate) Subadditivity
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI