Trung Dang

We derive a novel multi-dimensional online contention resolution scheme with the objective of maximizing revenue. In particular, we obtain polylog upper and lower bounds to the ex-ante buy-many objective, achieved via an sequential dynamic item pricing mechanism.

We study the general model of Costly Information Combinatorial Selection (CICS). In this problem, a decision maker needs to select a feasible subset of stochastic variables, and can only learn information about their values through a series of costly steps, modeled by a Markov decision process. The algorithmic objective is to maximize the total value of the selection *minus* the cost of information acquisition. In this work, we obtain improved bounds on the commitment gap of CICS through a reduction to a simpler problem of Bayesian Combinatorial Selection where information is free. By establishing a close relationship between these problems, we are able to relate the commitment gap of CICS to ex ante free-order prophet inequalities. As a consequence, we obtain improved approximation results for CICS, including the well-studied variant of Pandora’s Box with Optional Inspection under matroid feasibility constraints.

We study the problem of maximization under noisy values. In particular, there are n boxes with hidden i.i.d. reward x_i from an unknown distribution; these values are pertubed with independent heterogeneous Gaussian noises, producing y_i’s. We must choose one box from only knowing y_i and the variances of the Gaussian noises, obtaining reward x_i from such box. We show that the policy of "selecting \max y_i" and its variants of "selecting \max y_i - c \sigma_i" can be far from the hindsight optimal; however, a small pertubation to this policy, namely "selecting \max y_i$ among the low variance boxes" may achieve a constant approximation to the hindsight optimal within some regime, and no algorithms can obtain a constant approximation outside of this regime.