---
title: "Analysis and Optimization of Multi-Dimensional Percentile Mechanisms"
authors:
  - "Xin Sui"
  - "Craig Boutilier"
  - "Tuomas Sandholm"
doi: ""
url: "https://ijcai.org/proceedings/2013/62"
pdf: "https://ijcai.org/proceedings/2013/0062.pdf"
venue: "Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence"
year: 2013
pages: "367-373"
track: ""
keywords:
---

# Analysis and Optimization of Multi-Dimensional Percentile Mechanisms

Xin Sui, Craig Boutilier, Tuomas Sandholm

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