Quantifying the Strategyproofness of Mechanisms via Metrics on Payoff Distributions

Benjamin Lubin, David Parkes
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:357-366, 2009.

Abstract

Strategyproof mechanisms provide robust equilibrium with minimal assumptions about knowledge and rationality but can be unachievable in combination with other desirable properties such as budget-balance, stability against deviations by coalitions, and computational tractability. In the search for maximally-strategyproof mechanisms that simultaneously satisfy other desirable properties, we introduce a new metric to quantify the strategyproofness of a mechanism, based on comparing the payoff distribution, given truthful reports, against that of a strategyproof "reference" mechanism that solves a problem relaxation. Focusing on combinatorial exchanges, we demonstrate that the metric is informative about the eventual equilibrium, where simple regretbased metrics are not, and can be used for online selection of an effective mechanism.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-lubin09a, title = {Quantifying the Strategyproofness of Mechanisms via Metrics on Payoff Distributions}, author = {Lubin, Benjamin and Parkes, David}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {357--366}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/lubin09a/lubin09a.pdf}, url = {https://proceedings.mlr.press/r7/lubin09a.html}, abstract = {Strategyproof mechanisms provide robust equilibrium with minimal assumptions about knowledge and rationality but can be unachievable in combination with other desirable properties such as budget-balance, stability against deviations by coalitions, and computational tractability. In the search for maximally-strategyproof mechanisms that simultaneously satisfy other desirable properties, we introduce a new metric to quantify the strategyproofness of a mechanism, based on comparing the payoff distribution, given truthful reports, against that of a strategyproof "reference" mechanism that solves a problem relaxation. Focusing on combinatorial exchanges, we demonstrate that the metric is informative about the eventual equilibrium, where simple regretbased metrics are not, and can be used for online selection of an effective mechanism.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Quantifying the Strategyproofness of Mechanisms via Metrics on Payoff Distributions %A Benjamin Lubin %A David Parkes %B Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2009 %E Jeff Bilmes %E Andrew Y. Ng %F pmlr-vR7-lubin09a %I PMLR %P 357--366 %U https://proceedings.mlr.press/r7/lubin09a.html %V R7 %X Strategyproof mechanisms provide robust equilibrium with minimal assumptions about knowledge and rationality but can be unachievable in combination with other desirable properties such as budget-balance, stability against deviations by coalitions, and computational tractability. In the search for maximally-strategyproof mechanisms that simultaneously satisfy other desirable properties, we introduce a new metric to quantify the strategyproofness of a mechanism, based on comparing the payoff distribution, given truthful reports, against that of a strategyproof "reference" mechanism that solves a problem relaxation. Focusing on combinatorial exchanges, we demonstrate that the metric is informative about the eventual equilibrium, where simple regretbased metrics are not, and can be used for online selection of an effective mechanism. %Z Reissued by PMLR on 04 October 2026.
APA
Lubin, B. & Parkes, D.. (2009). Quantifying the Strategyproofness of Mechanisms via Metrics on Payoff Distributions. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:357-366 Available from https://proceedings.mlr.press/r7/lubin09a.html. Reissued by PMLR on 04 October 2026.

Related Material