How Pervasive Is the Myerson-Satterthwaite Impossibility?
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 233-237.
Abstract
The Myerson-Satterthwaite theorem is a foundational impossibility result in mechanism design which states that no mechanism can be Bayes-Nash incentive compatible, individually rational, and not run a deficit. It holds universally for priors that are continuous, gapless, and overlapping. Using automated mechanism design, we investigate how often the impossibility occurs over discrete valuation domains. While the impossibility appears to hold generally for settings with large numbers of possible valuations (approaching the continuous case), domains with realistic valuation structure circumvent the impossibility with surprising frequency. Even if the impossibility applies, the amount of subsidy required to achieve individual rationality and incentive compatibility is relatively small, even over large unstructured domains.Abraham Othman, Tuomas Sandholm
@inproceedings{ijcai2009p48,
title = {How Pervasive Is the Myerson-Satterthwaite Impossibility?},
author = {Othman, Abraham and Sandholm, Tuomas},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {233--237},
year = {2009},
url = {https://ijcai.org/proceedings/2009/48},
}
TY - CPAPER TI - How Pervasive Is the Myerson-Satterthwaite Impossibility? AU - Othman, Abraham AU - Sandholm, Tuomas T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 233 EP - 237 UR - https://ijcai.org/proceedings/2009/48 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
