Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
The Distortion of Prior-Independent b-Matching Mechanisms
pp 1-29
11 Feb 2026
Abstract
In a setting wheremitems need to be partitioned amongnagents, we evaluate the performance of mechanisms that take as input each agent's ordinal preferences, i.e., their ranking of the items from most- to least-preferred. The standard measure for evaluating ordinal mechanisms is the distortion, and the vast majority of the literature on distortion has focused on worst-case analysis, leading to some overly pessimistic results. We instead evaluate the distortion of mechanisms with respect to their expected performance when the agents' preferences are generated stochastically. We first show that no ordinal mechanism can achieve a distortion better thane/(e-1)≈ 1.582 , even if each agent needs to receive exactly one item (i.e.,m=n ) and every agent's values for different items are drawn i.i.d.\ {f}{r}{o}m the same known distribution. We then complement this negative result by proposing an ordinal mechanism that achieves the optimal distortion ofe/(e-1)even if each agent's values are drawn from an agent-specific distribution that is unknown to the mechanism. To further refine our analysis, we also optimize the distortion gap, i.e., the extent to which an ordinal mechanism approximates the optimal distortion possible for the instance at hand, and we propose a mechanism with a near-optimal distortion gap of1.076 . Finally, we also evaluate the distortion and distortion gap of simple mechanisms that have a one-pass structure.
Metrics
1 Record Views
Details
- Title
- The Distortion of Prior-Independent b-Matching Mechanisms
- Creators
- Ioannis Caragiannis - Aarhus UniversityVasilis Gkatzelis - Drexel UniversitySebastian Homrighausen - Aarhus University
- Publication Details
- pp 1-29
- Number of pages
- 29
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Computer Science
- Other Identifier
- 991022163435604721