Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

An economic view of prophet inequalities

An economic view of prophet inequalities Over the past decade, an exciting connection has developed between the theory of posted-price mechanisms and the prophet inequality, a result from the theory of optimal stopping. This survey provides an overview of this literature, covering extensions and applications of the prophet inequality through the lens of an economic proof of this classic result. We focus on highlighting ways in which the economic perspective drives new advances in the theory of online stochastic optimization, and vice versa. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM SIGecom Exchanges Association for Computing Machinery

An economic view of prophet inequalities

Lucier, Brendan
ACM SIGecom Exchanges , Volume 16 (1): 24 – Sep 25, 2017
Download PDF
24 pages

Loading next page...
 
/lp/association-for-computing-machinery/an-economic-view-of-prophet-inequalities-jPZ7lwy5r8
Publisher
Association for Computing Machinery
Copyright
Copyright © 2017 Author
ISSN
1551-9031
eISSN
1551-9031
DOI
10.1145/3144722.3144725
Publisher site
See Article on Publisher Site

Abstract

Over the past decade, an exciting connection has developed between the theory of posted-price mechanisms and the prophet inequality, a result from the theory of optimal stopping. This survey provides an overview of this literature, covering extensions and applications of the prophet inequality through the lens of an economic proof of this classic result. We focus on highlighting ways in which the economic perspective drives new advances in the theory of online stochastic optimization, and vice versa.

Journal

ACM SIGecom Exchanges – Association for Computing Machinery

Published: Sep 25, 2017

Keywords: approximation

References

  • Beating 1--1/e for ordered prophets
    Abolhassani, ; M., ; Ehsani, ; S., ; Esfandiari, ; H., ; Hajiaghayi, ; T., M.; Kleinberg, ; R., ; Lucier, ; B.,
  • Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers
    Alaei, ; S.,
  • The simple economics of approximately optimal auctions
    Alaei, ; S., ; Fu, ; H., ; Haghpanah, ; N., ; Hartline, ; J.,
  • Online prophet-inequality matching with applications to ad allocation
    Alaei, ; S., ; Hajiaghayi, ; M., ; Liaghat, ; V.,
  • The online stochastic generalized assignment problem
    Alaei, ; S., ; Hajiaghayi, ; M., ; Liaghat, ; V.,
  • Optimal auctions vs
    Alaei, ; S., ; Hartline, ; D., J.; Niazadeh, ; R., ; Pountourakis, ; E., ; Yuan, ; Y.,
  • Simple ratio prophet inequalities for a mortal with multiple choices
    Assaf, ; D., ; Samuel-Cahn, ; E.,
  • Prophet inequalities with limited information
    Azar, ; D., P.; Kleinberg, ; R., ; Weinberg, ; M., S.
  • Matroids, secretary problems, and online mechanisms
    Babaioff, ; M., ; Immorlica, ; N., ; Kleinberg, ; R.,
  • Understanding incentives: Mechanism design becomes algorithm design
    Cai, ; Y., ; Daskalakis, ; C., ; Weinberg, ; M., S.
  • A duality based unified approach to bayesian mechanism design
    Cai, ; Y., ; Devanur, ; R., N.; Weinberg, ; M., S.
  • Simultaneous bayesian auctions and computational complexity
    Cai, ; Y., ; Papadimitriou, ; H., C.
  • Simple mechanisms for subadditive buyers via duality
    Cai, ; Y., ; Zhao, ; M.,
  • Algorithmic pricing via virtual valuations
    Chawla, ; S., ; Hartline, ; D., J.; Kleinberg, ; D., R.
  • Multi-parameter mechanism design and sequential posted pricing
    Chawla, ; S., ; Hartline, ; D., J.; Malec, ; L., D.; Sivan, ; B.,
  • Bayesian combinatorial auctions
    Christodoulou, ; G., ; Kovács, ; A., ; Schapira, ; M.,
  • Posted price mechanisms for a random stream of customers
    Correa, ; J., ; Foncea, ; P., ; Hoeksma, ; R., ; Oosterwijk, ; T., ; Vredeveld, ; T.,
  • Prophet inequalities made simple: Stochastic optimization by pricing non-stochastic inputs
    Dütting, ; P., ; Feldman, ; M., ; Kesselheim, ; T., ; Lucier, ; B.,
  • Polymatroid prophet inequalities
    Dütting, ; P., ; Kleinberg, ; R.,
  • A unifying hierarchy of valuations with complements and substitutes
    Feige, ; U., ; Feldman, ; M., ; Immorlica, ; N., ; Izsak, ; R., ; Lucier, ; B., ; Syrgkanis, ; V.,
  • Simultaneous auctions are (almost) efficient
    Feldman, ; M., ; Fu, ; H., ; Gravin, ; N., ; Lucier, ; B.,
  • Combinatorial auctions via posted prices
    Feldman, ; M., ; Gravin, ; N., ; Lucier, ; B.,
  • A simple o(log log(rank))-competitive algorithm for the matroid secretary problem
    Feldman, ; M., ; Svensson, ; O., ; Zenklusen, ; R.,
  • Automated mechanism design and prophet inequalities
    Hajiaghayi, ; M., ; Kleinberg, ; R., ; Sandholm, ; W., T.
  • Bayesian mechanism design
    Hartline, ; D., J.
  • A survey of prophet inequalities in optimal stopping theory
    Hill, ; T., ; Kertz, ; P., R.
  • Comparisons of stop rule and supremum expectations of i
    Hill, ; P., T.; Kertz, ; P., R.
  • Fast approximation algorithms for the knapsack and sum of subset problems
    Ibarra, ; H., O.; Kim, ; E., C.
  • Job matching, coalition formation, and gross substitutes
    Kelso, ; S, Alexander; J., ; Crawford, ; P., V.
  • Matroid prophet inequalities
    Kleinberg, ; R., ; Weinberg, ; M., S.
  • Semiamarts and finite values
    Krengel, ; U., ; Sucheston, ; L.,
  • On semiamarts, amarts, and processes with finite value
    Krengel, ; U., ; Sucheston, ; L.,
  • Combinatorial auctions with decreasing marginal utilities
    Lehmann, ; B., ; Lehmann, ; D., ; Nisan, ; N.,
  • Obviously strategy-proof mechanisms
    Li, ; S.,
  • Optimal auction design
    Myerson, ; R.,
  • The price of anarchy in games of incomplete information
    Roughgarden, ; T.,
  • Beyond matroids: Secretary problem and prophet inequality with general constraints
    Rubinstein, ; A.,
  • Combinatorial prophet inequalities
    Rubinstein, ; A., ; Singla, ; S.,
  • Comparison of threshold stop rules and maximum for independent nonnegative random variables
    Samuel-Cahn, ; E.,
  • Composable and efficient mechanisms
    Syrgkanis, ; V., ; Tardos, ; É,
  • Non-approximability results for optimization problems on bounded degree instances
    Trevisan, ; L.,