English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Posted Prices, Smoothness, and Combinatorial Prophet Inequalities

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.

Item is

Files

show Files
hide Files
:
arXiv:1612.03161.pdf (Preprint), 550KB
Name:
arXiv:1612.03161.pdf
Description:
File downloaded from arXiv at 2017-01-30 09:47
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Dütting, Paul1, Author
Feldman, Michal1, Author
Kesselheim, Thomas2, Author           
Lucier, Brendan1, Author
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: Computer Science, Computer Science and Game Theory, cs.GT,Computer Science, Data Structures and Algorithms, cs.DS
 Abstract: 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.

Details

show
hide
Language(s): eng - English
 Dates: 2016-12-092016
 Publication Status: Published online
 Pages: 56 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1612.03161
URI: http://arxiv.org/abs/1612.03161
BibTex Citekey: DBLP:journals/corr/DuttingFKL16
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show