file.pdf (314.83 kB)
Download file

Analysis and Optimization of Multi-dimensional Percentile Mechanisms

Download (314.83 kB)
journal contribution
posted on 01.03.2006, 00:00 by Xin Sui, Craig Boutilier, Tuomas W Sandholm

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 samplebased 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.

History

Publisher Statement

All Rights Reserved

Date

01/03/2006

Usage metrics

Exports