de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

Posted Prices, Smoothness, and Combinatorial Prophet Inequalities

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons134206

Kesselheim,  Thomas
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

arXiv:1612.03161.pdf
(Preprint), 550KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Dütting, P., Feldman, M., Kesselheim, T., & Lucier, B. (2016). Posted Prices, Smoothness, and Combinatorial Prophet Inequalities. Retrieved from http://arxiv.org/abs/1612.03161.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-002C-4E77-8
Zusammenfassung
We present a general framework for proving combinatorial prophet inequalities and constructing posted-price mechanisms. Our framework applies to stochastic welfare optimization problems, in which buyers arrive sequentially and make utility-maximizing purchases. Our analysis takes the form of an extension theorem: we derive sufficient conditions for achieving welfare bounds in the special case of deterministic valuations, then prove that these bounds extend directly to stochastic settings. Furthermore, our welfare bounds compose in the sense that the welfare guarantees are preserved when buyers participate in many optimization problems simultaneously. Our sufficient conditions have a natural economic interpretation, and our approach is closely connected to the smoothness framework for bounding the price of anarchy of mechanisms. We show that many smooth mechanisms can be recast as posted-price mechanisms with comparable performance guarantees. We illustrate the power of our framework in a range of applications, including combinatorial auctions, matroids, and sparse packing programs, where we unify and improve many of the previously known results.