A General Statistical Framework for Designing Strategy-proof Assignment Mechanisms

Harikrishna Narasimhan Harvard University, David Parkes Harvard University
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:514-523, 2016.

Abstract

We develop a statistical framework for the design of a strategy-proof assignment mechanism that closely approximates a target outcome rule. The framework can handle settings with and without money, and allows the designer to employ techniques from machine learning to control the space of strategy-proof mechanisms searched over, by providing a rule class with appropriate capacity. We solve a sample-based optimization problem over a space of mechanisms that correspond to agent-independent price functions (virtual prices in the case of settings without money), subject to a feasibility constraint on the sample. A transformation is applied to the obtained mechanism to ensure feasibility on all type profiles, and strategy-proofness. We derive a sample complexity bound for our approach in terms of the capacity of the chosen rule class and provide applications for our results.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-university16n, title = {A General Statistical Framework for Designing Strategy-proof Assignment Mechanisms}, author = {University, Harikrishna Narasimhan Harvard and University, David Parkes Harvard}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {514--523}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/university16n/university16n.pdf}, url = {https://proceedings.mlr.press/r14/university16n.html}, abstract = {We develop a statistical framework for the design of a strategy-proof assignment mechanism that closely approximates a target outcome rule. The framework can handle settings with and without money, and allows the designer to employ techniques from machine learning to control the space of strategy-proof mechanisms searched over, by providing a rule class with appropriate capacity. We solve a sample-based optimization problem over a space of mechanisms that correspond to agent-independent price functions (virtual prices in the case of settings without money), subject to a feasibility constraint on the sample. A transformation is applied to the obtained mechanism to ensure feasibility on all type profiles, and strategy-proofness. We derive a sample complexity bound for our approach in terms of the capacity of the chosen rule class and provide applications for our results.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T A General Statistical Framework for Designing Strategy-proof Assignment Mechanisms %A Harikrishna Narasimhan Harvard University %A David Parkes Harvard University %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-university16n %I PMLR %P 514--523 %U https://proceedings.mlr.press/r14/university16n.html %V R14 %X We develop a statistical framework for the design of a strategy-proof assignment mechanism that closely approximates a target outcome rule. The framework can handle settings with and without money, and allows the designer to employ techniques from machine learning to control the space of strategy-proof mechanisms searched over, by providing a rule class with appropriate capacity. We solve a sample-based optimization problem over a space of mechanisms that correspond to agent-independent price functions (virtual prices in the case of settings without money), subject to a feasibility constraint on the sample. A transformation is applied to the obtained mechanism to ensure feasibility on all type profiles, and strategy-proofness. We derive a sample complexity bound for our approach in terms of the capacity of the chosen rule class and provide applications for our results. %Z Reissued by PMLR on 04 October 2026.
APA
University, H.N.H. & University, D.P.H.. (2016). A General Statistical Framework for Designing Strategy-proof Assignment Mechanisms. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:514-523 Available from https://proceedings.mlr.press/r14/university16n.html. Reissued by PMLR on 04 October 2026.

Related Material