Not logged in.

Quick Search - Contribution

Contribution Details

Type Conference or Workshop Paper
Scope Discipline-based scholarship
Published in Proceedings Yes
Title An axiomatic approach to characterizing and relaxing strategyproofness of one-sided matching mechanisms
Organization Unit
Authors
  • Timo Mennle
  • Sven Seuken
Presentation Type paper
Item Subtype Original Work
Refereed Yes
Status Published in final form
Language
  • English
ISBN 9781450325653
Page Range 37 - 38
Event Title Fifteenth ACM Conference on Economics and Computation
Event Type conference
Event Location Palo Alto, California, USA
Event Start Date June 7 - 2014
Event End Date June 13 - 2014
Place of Publication New York, New York, USA
Publisher ACM Press
Abstract Text We study one-sided matching mechanisms where agents have vNM utility functions and report ordinal preferences. We first show that in this domain strategyproof mechanisms are characterized by three intuitive axioms: swap monotonicity, upper invariance, and lower invariance. Our second result is that dropping lower invariance leads to an interesting new relaxation of strategyproofness, which we call partial strategyproofness. In particular, we show that mechanisms are swap monotonic and upper invariant if and only if they are strategyproof on a restricted domain where agents have sufficiently different valuations for different objects. Furthermore, we show that this domain restriction is maximal and use it to define a single-parameter measure for the degree of strategyproofness of a manipulable mechanism. We also provide an algorithm that computes this measure. Our new partial strategyproofness concept finds applications in the incentive analysis of non-strategyproof mechanisms, such as the Probabilistic Serial mechanism, different variants of the Boston mechanism, and the construction of new hybrid mechanisms.
Digital Object Identifier 10.1145/2600057.2602885
PDF File Download
Export BibTeX
EP3 XML (ZORA)