309 citations · 1.1k across the 60 of their papers we have counts for
4 papers · 1 filter
Sharp Dichotomies for Regret Minimization in Metric Spaces
Robert Kleinberg, Aleksandrs Slivkins
The Lipschitz multi-armed bandit (MAB) problem generalizes the classical multi-armed bandit problem by assuming one is given side information consisting of a priori upper bounds on…
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…