309 citations · 1.1k across the 60 of their papers we have counts for
23 papers · 1 filter
Threshold Tests as Quality Signals: Optimal Strategies, Equilibria, and Price of Anarchy
Siddhartha Banerjee, David Kempe, Robert Kleinberg
We study a signaling game between two firms competing to have their product chosen by a principal. The products have qualities drawn i.i.d. from a common prior. The principal aims…
Optimal Stopping with Behaviorally Biased Agents: The Role of Loss Aversion and Changing Reference Points
Jon Kleinberg, Robert Kleinberg, Sigal Oren
People are often reluctant to sell a house, or shares of stock, below the price at which they originally bought it. While this is generally not consistent with rational utility max…
Revenue Monotonicity Under Misspecified Bidders
Makis Arsenis, Odysseas Drosis, Robert Kleinberg
We investigate revenue guarantees for auction mechanisms in a model where a distribution is specified for each bidder, but only some of the distributions are correct. The subset of…
Pandora's Problem with Nonobligatory Inspection
Hedyeh Beyhaghi, Robert Kleinberg
Martin Weitzman's "Pandora's problem" furnishes the mathematical basis for optimal search theory in economics. Nearly 40 years later, Laura Doval introduced a version of the proble…
Delegated Search Approximates Efficient Search
Jon Kleinberg, Robert Kleinberg
There are many settings in which a principal performs a task by delegating it to an agent, who searches over possible solutions and proposes one to the principal. This describes ma…
Bernoulli Factories and Black-Box Reductions in Mechanism Design
Shaddin Dughmi, Jason Hartline, Robert Kleinberg +1
We provide a polynomial time reduction from Bayesian incentive compatible mechanism design to Bayesian algorithm design for welfare maximization problems. Unlike prior results, our…
Exponential Segregation in a Two-Dimensional Schelling Model with Tolerant Individuals
Nicole Immorlica, Robert Kleinberg, Brendan Lucier +1
We prove that the two-dimensional Schelling segregation model yields monochromatic regions of size exponential in the area of individuals' neighborhoods, provided that the toleranc…
Simple and Near-Optimal Mechanisms For Market Intermediation
Rad Niazadeh, Yang Yuan, Robert D. Kleinberg
A prevalent market structure in the Internet economy consists of buyers and sellers connected by a platform (such as Amazon or eBay) that acts as an intermediary and keeps a share…
Behavioral Mechanism Design: Optimal Contests for Simple Agents
Arpita Ghosh, Robert Kleinberg
Incentives are more likely to elicit desired outcomes when they are designed based on accurate models of agents' strategic behavior. A growing literature, however, suggests that pe…
Optimal Auctions for Correlated Buyers with Sampling
Hu Fu, Nima Haghpanah, Jason Hartline +1
Crémer and McLean [1985] showed that, when buyers' valuations are drawn from a correlated distribution, an auction with full knowledge on the distribution can extract the full soci…
On the Complexity of Computing an Equilibrium in Combinatorial Auctions
Shahar Dobzinski, Hu Fu, Robert Kleinberg
We study combinatorial auctions where each item is sold separately but simultaneously via a second price auction. We ask whether it is possible to efficiently compute in this game…
On the Ratio of Revenue to Welfare in Single-Parameter Mechanism Design
Robert Kleinberg, Yang Yuan
What fraction of the potential social surplus in an environment can be extracted by a revenue-maximizing monopolist? We investigate this problem in Bayesian single-parameter enviro…
Multi-parameter Mechanisms with Implicit Payment Computation
Moshe Babaioff, Robert Kleinberg, Aleksandrs Slivkins
In this paper we show that payment computation essentially does not present any obstacle in designing truthful mechanisms, even for multi-parameter domains, and even when we can on…
Optimal Mechanisms for Selling Information
Moshe Babaioff, Robert Kleinberg, Renato Paes Leme
The buying and selling of information is taking place at a scale unprecedented in the history of commerce, thanks to the formation of online marketplaces for user data. Data provid…
An Analysis of One-Dimensional Schelling Segregation
Christina Brandt, Nicole Immorlica, Gautam Kamath +1
We analyze the Schelling model of segregation in which a society of n individuals live in a ring. Each individual is one of two races and is only satisfied with his location so lon…
Dynamic Pricing with Limited Supply
Moshe Babaioff, Shaddin Dughmi, Robert Kleinberg +1
We consider the problem of dynamic pricing with limited supply. A seller has identical items for sale and is facing potential buyers ("agents") that are arriving sequential…
Truthfulness via Proxies
Shahar Dobzinski, Hu Fu, Robert Kleinberg
This short note exhibits a truthful-in-expectation -approximation mechanism for combinatorial auctions with subadditive bidders that uses polynomia…
Optimal Auctions with Correlated Bidders are Easy
Shahar Dobzinski, Hu Fu, Robert Kleinberg
We consider the problem of designing a revenue-maximizing auction for a single item, when the values of the bidders are drawn from a correlated distribution. We observe that there…
Truthful Mechanisms with Implicit Payment Computation
Moshe Babaioff, Robert D. Kleinberg, Aleksandrs Slivkins
It is widely believed that computing payments needed to induce truthful bidding is somehow harder than simply computing the allocation. We show that the opposite is true: creating…
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…
Algorithmic Pricing via Virtual Valuations
Shuchi Chawla, Jason Hartline, Robert Kleinberg
Algorithmic pricing is the computational problem that sellers (e.g., in supermarkets) face when trying to set prices for their items to maximize their profit in the presence of a k…