18 citations · 55 across the 18 of their papers we have counts for
4 papers · 1 filter
Secretaries with Advice
Paul Dütting, Silvio Lattanzi, Renato Paes Leme +1
The secretary problem is probably the purest model of decision making under uncertainty. In this paper we ask which advice can we give the algorithm to improve its success probabil…
An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions
Paul Dütting, Thomas Kesselheim, Brendan Lucier
Prophet inequalities compare the expected performance of an online algorithm for a stochastic optimization problem to the expected optimal solution in hindsight. They are a major a…
Efficient Two-Sided Markets with Limited Information
Paul Dütting, Federico Fusco, Philip Lazos +2
A celebrated impossibility result by Myerson and Satterthwaite (1983) shows that any truthful mechanism for two-sided markets that maximizes social welfare must run a deficit, resu…
The Complexity of Contracts
Paul Duetting, Tim Roughgarden, Inbal Talgam-Cohen
We initiate the study of computing (near-)optimal contracts in succinctly representable principal-agent settings. Here optimality means maximizing the principal's expected payoff o…