3 papers
cs.GT2023
On the Computational Complexity of Mechanism Design in Single-Crossing Settings
Moshe Babaioff, Shahar Dobzinski, Shiri Ron
We explore the performance of polynomial-time incentive-compatible mechanisms in single-crossing domains. Single-crossing domains were extensively studied in the economics literatu…
cs.GT2022
On the Hardness of Dominant Strategy Mechanism Design
Shahar Dobzinski, Shiri Ron, Jan Vondrák
We study the communication complexity of dominant strategy implementations of combinatorial auctions. We start with two domains that are generally considered "easy": multi-unit auc…
cs.GT2020
The Communication Complexity of Payment Computation
Shahar Dobzinski, Shiri Ron
Let be an incentive compatible mechanism where is the social choice function and is the payment function. In many important settings, uniquely determines (u…