7 papers
Single-Sample Prophet Inequalities: A Combinatorial to Single-Item Reduction
Shuchi Chawla, Trung Dang
We study single-sample prophet inequalities for online combinatorial allocation. Our main contribution is a general reduction from combinatorial to single-item prophet inequalities…
Pricing Pandora's Boxes: Revenue Maximization in Sequential Information Acquisition
Shuchi Chawla, Dimitris Christou, Trung Dang +1
We study a mechanism design problem in which a seller controls access to information about a set of stochastic alternatives, and a buyer sequentially acquires information in order…
Fair Division Under Inaccurate Preferences
Trung Dang, Daniel Halpern, Anuran Makur +3
The fair allocation of scarce resources is a central problem in mathematics, computer science, operations research, and economics. While much of the fair-division literature assume…
Commitment Gap via Correlation Gap
Shuchi Chawla, Dimitris Christou, Trung Dang
Selection problems with costly information, dating back to Weitzman's Pandora's Box problem, have received much attention recently. We study the general model of Costly Information…
Multi-Unit Combinatorial Prophet Inequalities
Shuchi Chawla, Trung Dang, Zhiyi Huang +1
We consider a combinatorial auction setting where buyers have fractionally subadditive (XOS) valuations over the items and the seller's objective is to maximize the social welfare.…
Robust Max Selection
Trung Dang, Zhiyi Huang
We introduce a new model to study algorithm design under unreliable information, and apply this model for the problem of finding the uncorrupted maximum element of a list containin…
A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization
Shuchi Chawla, Dimitris Christou, Trung Dang +3
We study multi-buyer multi-item sequential item pricing mechanisms for revenue maximization with the goal of approximating a natural fractional relaxation -- the ex ante optimal re…