309 citations · 1.1k across the 60 of their papers we have counts for
3 papers · 2 filters
Randomized Online Algorithms for the Buyback Problem
Ashwinkumar B. V., Robert Kleinberg
In the matroid buyback problem, an algorithm observes a sequence of bids and must decide whether to accept each bid at the moment it arrives, subject to a matroid constraint on the…
Amplified Hardness of Approximation for VCG-Based Mechanisms
Shaddin Dughmi, Hu Fu, Robert Kleinberg
If a two-player social welfare maximization problem does not admit a PTAS, we prove that any maximal-in-range truthful mechanism that runs in polynomial time cannot achieve an appr…
Pricing Randomized Allocations
Patrick Briest, Shuchi Chawla, Robert Kleinberg +1
Randomized mechanisms, which map a set of bids to a probability distribution over outcomes rather than a single outcome, are an important but ill-understood area of computational m…