Linear Programming Based Near-Optimal Pricing for Laminar Bayesian Online Selection
Linear Programming Based Near-Optimal Pricing for Laminar Bayesian Online Selection
复制标题
DOI：
10.2139/ssrn.3430156
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
Nima Anari;Rad Niazadeh;A. Saberi;A. Shameli
中科院分区：
文献类型：
--
作者：
Nima Anari;Rad Niazadeh;A. Saberi;A. Shameli
在贝叶斯在线选择问题中，目标是针对一系列到达的买家设计定价方案，以最大程度地利用受不同类型的结构约束的预期社交福利（或收入）。受运营管理应用程序的启发，本文的重点是服务客户集以层流矩阵为特征的情况。当层状矩阵具有恒定深度时，我们给出了第一个多项式时间近似方案（PTA）。我们的方法是基于将线性编程松弛层次结构的解决方案舍入式解决方案，该层次结构以任何程度的准确性和一个浓度参数近似于最佳的在线解决方案，并显示舍入会造成微小的损失。我们还研究了另一种变化，我们称之为生产约束的问题，为此，允许的服务客户集的特征是产生和运输限制的集合，形成了某种形式的层状矩阵。使用类似的基于LP的方法，我们即使层层曲线的深度不恒定，我们也会为此问题设计一个PTA。该分析利用了层层家族的低级选择中最佳选择规则的负依赖性。最后，我们讨论了本文中采用的基于线性编程的方法，并重新衍生了文献中已知的一些经典的先知不平等现象。
In the Bayesian online selection problem, the goal is to design a pricing scheme for a sequence of arriving buyers that maximizes the expected social-welfare (or revenue) subject to different types of structural constraints. Inspired by applications in operations management, the focus of this paper is on the cases where the set of served customers is characterized by a laminar matroid. We give the first Polynomial-Time Approximation Scheme (PTAS) for the problem when the laminar matroid has constant depth. Our approach is based on rounding the solution of a hierarchy of linear programming relaxations that approximate the optimum online solution with any degree of accuracy plus a concentration argument that shows the rounding incurs a small loss. We also study another variation, which we call the production constrained problem, for which the allowable set of served customers is characterized by a collection of production and shipping constraints forming a certain form of laminar matroid. Using a similar LP-based approach, we design a PTAS for this problem even when the depth of the laminar matroid is not constant. The analysis exploits the negative dependency of the optimum selection rule in the lower-levels of the laminar family. Finally, we conclude with a discussion of the linear programming based approach employed in the paper and re-derive some of the classic prophet inequalities known in the literature.