Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 2018 | Published
Journal Article Open

Convex Prophet Inequalities


We introduce a new class of prophet inequalities-convex prophet inequalities-where a gambler observes a sequence of convex cost functions c_i(x_i) and is required to assign some fraction 0 ≤ x_i ≤ 1 to each, such that the sum of assigned values is exactly 1. The goal of the gambler is to minimize the sum of the costs. We provide an optimal algorithm for this problem, a dynamic program, and show that it can be implemented in polynomial time when the cost functions are polynomial. We also precisely characterize the competitive ratio of the optimal algorithm in the case where the gambler has an outside option and there are polynomial costs, showing that it grows as Θ(n^(p-1)/l), where n is the number of stages, p is the degree of the polynomial costs and the coefficients of the cost functions are bounded by [l, u].

Additional Information

© 2018 is held by author/owner(s).

Attached Files

Published - p39-qin.pdf


Files (796.0 kB)
Name Size Download all
796.0 kB Preview Download

Additional details

August 19, 2023
October 20, 2023