# Prior independent mechanisms via prophet inequalities with limited information

## Author(s): Azar, Pablo D; Kleinberg, Robert; Weinberg, S Matthew

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1s84b
DC FieldValueLanguage
dc.contributor.authorAzar, Pablo D-
dc.contributor.authorKleinberg, Robert-
dc.contributor.authorWeinberg, S Matthew-
dc.date.accessioned2021-10-08T19:49:50Z-
dc.date.available2021-10-08T19:49:50Z-
dc.date.issued2019-11en_US
dc.identifier.citationAzar, Pablo D., Robert Kleinberg, and S. Matthew Weinberg. "Prior independent mechanisms via prophet inequalities with limited information." Games and Economic Behavior 118 (2019): pp. 511-532. doi:10.1016/j.geb.2018.05.006en_US
dc.identifier.issn0899-8256-
dc.identifier.uri1090-2473-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1s84b-
dc.description.abstractProphet inequalities have recently become a fundamental tool in the design of sequential and multi-dimensional mechanisms in Bayesian settings. However, existing mechanisms—as well as the underlying prophet inequalities behind their analysis—require sophisticated information about the distribution from which inputs are drawn. Our goal in this work is to design prior-independent sequential and multi-dimensional mechanisms. To this end, we first design prophet inequalities that require knowing only a single sample from the input distribution. These results come in two forms: the first is via a reduction from single-sample prophet inequalities to secretary algorithms. The second is via novel single-sample prophet inequalities for k-uniform matroids. Leveraging our new prophet inequalities, we construct the first prior-independent sequential mechanisms where the seller does not know the order in which buyers arrive, and buyers may have asymmetric value distributions. We also construct the first prior-independent multi-dimensional mechanism where buyers may have asymmetric value distributions.en_US
dc.format.extent511 - 532en_US
dc.language.isoen_USen_US
dc.relation.ispartofGames and Economic Behavioren_US
dc.rightsAuthor's manuscripten_US
dc.titlePrior independent mechanisms via prophet inequalities with limited informationen_US
dc.typeJournal Articleen_US
dc.identifier.doi10.1016/j.geb.2018.05.006-