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

Abstract

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

p39-qin.pdf
Files (796.0 kB)
Name Size Download all
md5:17aaf5c6408f9c4b9a5293324a2c41d9
796.0 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 20, 2023