Prophet secretary for combinatorial auctions and matroids

Soheil Ehsani, Mohammadtaghi Hajiaghayi, Thomas Kesselheim, Sahil Singla

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

Abstract

The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items because of their applications in mechanism design. The most important of these generalizations are to matroids and to combinatorial auctions (extends bipartite matching). Kleinberg-Weinberg [33] and Feldman et al. [17] show that for adversarial arrival order of random variables the optimal prophet inequalities give a 1=2-approximation. For many settings, however, it's conceivable that the arrival order is chosen uniformly at random, akin to the secretary problem. For such a random arrival model, we improve upon the 1=2approximation and obtain (1-1=e)-approximation prophet inequalities for both matroids and combinatorial auctions. This also gives improvements to the results of Yan [45] and Esfandiari et al. [15] who worked in the special cases where we can fully control the arrival order or when there is only a single item. Our techniques are threshold based. We convert our discrete problem into a continuous setting and then give a generic template on how to dynamically adjust these thresholds to lower bound the expected total welfare.

Original languageEnglish (US)
Title of host publication29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
EditorsArtur Czumaj
PublisherAssociation for Computing Machinery
Pages700-714
Number of pages15
ISBN (Electronic)9781611975031
DOIs
StatePublished - Jan 1 2018
Externally publishedYes
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States
Duration: Jan 7 2018Jan 10 2018

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
CountryUnited States
CityNew Orleans
Period1/7/181/10/18

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Prophet secretary for combinatorial auctions and matroids'. Together they form a unique fingerprint.

  • Cite this

    Ehsani, S., Hajiaghayi, M., Kesselheim, T., & Singla, S. (2018). Prophet secretary for combinatorial auctions and matroids. In A. Czumaj (Ed.), 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 (pp. 700-714). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611975031.46