Analysis and Optimization of Multi-Dimensional Percentile Mechanisms
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 367-373.
Abstract
We consider the mechanism design problem for agents with single-peaked preferences over multi-dimensional domains when multiple alternatives can be chosen. Facility location and committee selection are classic embodiments of this problem. We propose a class of percentile mechanisms, a form of generalized median mechanisms, that are strategy-proof, and derive worst-case approximation ratios for social cost and maximum load for L1 and L2 cost models. More importantly, we propose a sample-based framework for optimizing the choice of percentiles relative to any prior distribution over preferences, while maintaining strategy-proofness. Our empirical investigations, using social cost and maximum load as objectives, demonstrate the viability of this approach and the value of such optimized mechanisms vis-a-vis mechanisms derived through worst-case analysis.
@inproceedings{ijcai2013p62,
title = {Analysis and Optimization of Multi-Dimensional Percentile Mechanisms},
author = {Sui, Xin and Boutilier, Craig and Sandholm, Tuomas},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {367--373},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/62},
}
TY - CPAPER TI - Analysis and Optimization of Multi-Dimensional Percentile Mechanisms AU - Sui, Xin AU - Boutilier, Craig AU - Sandholm, Tuomas T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 367 EP - 373 UR - https://ijcai.org/proceedings/2013/62 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
