From pricing to prophets, and back!

被引：29

作者：

Correa, Jose ^{[1
]}

Foncea, Patricio ^{[2
]}

Pizarro, Dana ^{[1
]}

Verdugo, Victor ^{[3
]}

机构：

[1] Univ Chile, Dept Ingn Ind, Santiago, Chile

[2] MIT, Operat Res Ctr, Cambridge, MA 02139 USA

[3] Univ OHiggins, Inst Ciencias Ingn, Rancagua, Chile

来源：

OPERATIONS RESEARCH LETTERS | 2019年 / 47卷 / 01期

关键词：

Prophet inequalities; Posted-price mechanisms; Approximation; SUPREMUM EXPECTATIONS; STOP RULE;

D O I：

10.1016/j.orl.2018.11.010

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this work we prove that designing PPMs is equivalent to finding stopping rules for prophets. This extends the connection that any prophet type inequality can be turned into a PPM with the same approximation guarantee (Hajiaghayi et al. 2007: Chawla et al. 2010). Our reduction is robust under multiple settings including matroid feasibility constraints, or different arrival orderings. One fundamental observation implied by this result is that designing PPMs in general is equally hard from an approximation perspective to designing PPMs when the valuations are regular. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：25 / 29

页数：5