Prior independent mechanisms via prophet inequalities with limited information

Pablo D. Azar, Robert Kleinberg, Seth Matthew Weinberg

Research output: Contribution to journalArticle

Abstract

Prophet 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.

Original languageEnglish (US)
JournalGames and Economic Behavior
DOIs
StateAccepted/In press - Jan 1 2018

Fingerprint

Limited information
Buyers
Seller

All Science Journal Classification (ASJC) codes

  • Economics and Econometrics
  • Finance

Cite this

@article{d73344a15af84aadab4ef2ab1133055e,
title = "Prior independent mechanisms via prophet inequalities with limited information",
abstract = "Prophet 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.",
author = "Azar, {Pablo D.} and Robert Kleinberg and Weinberg, {Seth Matthew}",
year = "2018",
month = "1",
day = "1",
doi = "https://doi.org/10.1016/j.geb.2018.05.006",
language = "English (US)",
journal = "Games and Economic Behavior",
issn = "0899-8256",
publisher = "Academic Press Inc.",

}

Prior independent mechanisms via prophet inequalities with limited information. / Azar, Pablo D.; Kleinberg, Robert; Weinberg, Seth Matthew.

In: Games and Economic Behavior, 01.01.2018.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Prior independent mechanisms via prophet inequalities with limited information

AU - Azar, Pablo D.

AU - Kleinberg, Robert

AU - Weinberg, Seth Matthew

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Prophet 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.

AB - Prophet 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.

UR - http://www.scopus.com/inward/record.url?scp=85049105613&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049105613&partnerID=8YFLogxK

U2 - https://doi.org/10.1016/j.geb.2018.05.006

DO - https://doi.org/10.1016/j.geb.2018.05.006

M3 - Article

JO - Games and Economic Behavior

JF - Games and Economic Behavior

SN - 0899-8256

ER -