Nearly Optimal Pricing Algorithms for Production Constrained and Laminar Bayesian Selection
Nima Anari, Rad Niazadeh, Amin Saberi, Ali Shameli · 2019
In the Bayesian online selection problem, the goal is to find a pricing algorithm for serving a sequence of arriving buyers that maximizes the expected social-welfare (or revenue) subject to different types of structural constraints. The focus of this paper is on the case where the allowable subsets of served customers are characterized by a laminar matroid with constant depth. This problem is a special case of the well-known matroid Bayesian online selection problem studied in [Kleinberg & Weinberg, 2012], when the underlying matroid is laminar. We give the first Polynomial-Time Approximation Scheme (PTAS) for the above problem. Our approach is based on rounding the solution of a hierarchy of linear programming relaxations that can approximate the optimum online solution with any degree of accuracy as well as a concentration argument that shows our rounding does not have a considerable loss in the expected social welfare.