2.9k citations · 3.2k across the 12 of their papers we have counts for
5 papers · 1 filter
Envy Freedom and Prior-free Mechanism Design
Nikhil R. Devanur, Jason D. Hartline, Qiqi Yan
We consider the provision of an abstract service to single-dimensional agents. Our model includes position auctions, single-minded combinatorial auctions, and constrained matching…
An approximately truthful-in-expectation mechanism for combinatorial auctions using value queries
Shaddin Dughmi, Tim Roughgarden, Jan Vondrak +1
This manuscript presents an alternative implementation of the truthful-in-expectation mechanism of Dughmi, Roughgarden and Yan for combinatorial auctions with weighted-matroid-rank…
From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions
Shaddin Dughmi, Tim Roughgarden, Qiqi Yan
We design an expected polynomial-time, truthful-in-expectation, (1-1/e)-approximation mechanism for welfare maximization in a fundamental class of combinatorial auctions. Our resul…
Mechanism Design via Correlation Gap
Qiqi Yan
For revenue and welfare maximization in single-dimensional Bayesian settings, Chawla et al. (STOC10) recently showed that sequential posted-price mechanisms (SPMs), though simple i…
Robust Mechanisms for Risk-Averse Sellers
Mukund Sundararajan, Qiqi Yan
The existing literature on optimal auctions focuses on optimizing the expected revenue of the seller, and is appropriate for risk-neutral sellers. In this paper, we identify good m…