5 papers · 1 filter
Communication Separations for Truthful Auctions: Breaking the Two-Player Barrier
Shiri Ron, Clayton Thomas, S. Matthew Weinberg +1
We study the communication complexity of truthful combinatorial auctions, and in particular the case where valuations are either subadditive or single-minded, which we denote with…
Separating the Communication Complexity of Truthful and Non-Truthful Combinatorial Auctions
Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena +1
We provide the first separation in the approximation guarantee achievable by truthful and non-truthful combinatorial auctions with polynomial communication. Specifically, we prove…
The menu complexity of "one-and-a-half-dimensional" mechanism design
Raghuvansh R. Saxena, Ariel Schvartzman, S. Matthew Weinberg
We study the menu complexity of optimal and approximately-optimal auctions in the context of the "FedEx" problem, a so-called "one-and-a-half-dimensional" setting where a single bi…
On Simultaneous Two-player Combinatorial Auctions
Mark Braverman, Jieming Mao, S. Matthew Weinberg
We consider the following communication problem: Alice and Bob each have some valuation functions and over subsets of items, and their goal is to part…
Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions
Mark Braverman, Jieming Mao, S. Matthew Weinberg
We study the communication complexity of combinatorial auctions via interpolation mechanisms that interpolate between non-truthful and truthful protocols. Specifically, an interpol…