ausblenden:
Schlagwörter:
Computer Science, Computer Science and Game Theory, cs.GT,Computer Science, Data Structures and Algorithms, cs.DS
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.
