Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Relaxing strategyproofness in one-sided matching

Relaxing strategyproofness in one-sided matching Relaxing Strategyproofness in One-sided Matching TIMO MENNLE and SVEN SEUKEN University of Zurich We consider the one-sided matching problem, where agents must be matched to indivisible objects. Our first result is a novel characterization of strategyproof mechanisms by three intuitive axioms. Furthermore, we introduce partial strategyproofness, a new relaxation of strategyproofness that bridges the gap between full and weak strategyproofness. Partial strategyproofness finds application in the incentive analysis of non-strategyproof mechanisms, such as Probabilistic Serial, different variants of the Boston mechanism, and hybrid mechanisms. In this letter, we summarize the main results from [Mennle and Seuken 2014a] and demonstrate how they can be used for the design and analysis of matching mechanisms.1 Categories and Subject Descriptors: J.4.a [Social and Behavioral Sciences]: Economics General Terms: Economics; Theory Additional Key Words and Phrases: Matching, Mechanism Design, Strategyproofness 1. INTRODUCTION The (probabilistic) one-sided matching problem is concerned with the allocation of indivisible goods to self-interested agents with privately known preferences in domains where monetary transfers are not permitted. Such problems often arise in situations that are of great importance to peoples' lives. For example, students must be matched to schools, teachers to training programs, or tenants to houses. Strategyproof mechanisms, such http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM SIGecom Exchanges Association for Computing Machinery

Relaxing strategyproofness in one-sided matching

Mennle, Timo; Seuken, Sven
ACM SIGecom Exchanges , Volume 13 (1) – Nov 25, 2014
Download PDF
4 pages

Loading next page...
 
/lp/association-for-computing-machinery/relaxing-strategyproofness-in-one-sided-matching-nSeRpKWfB2
Publisher
Association for Computing Machinery
Copyright
Copyright © 2014 by ACM Inc.
ISSN
1551-9031
DOI
10.1145/2692375.2692381
Publisher site
See Article on Publisher Site

Abstract

Relaxing Strategyproofness in One-sided Matching TIMO MENNLE and SVEN SEUKEN University of Zurich We consider the one-sided matching problem, where agents must be matched to indivisible objects. Our first result is a novel characterization of strategyproof mechanisms by three intuitive axioms. Furthermore, we introduce partial strategyproofness, a new relaxation of strategyproofness that bridges the gap between full and weak strategyproofness. Partial strategyproofness finds application in the incentive analysis of non-strategyproof mechanisms, such as Probabilistic Serial, different variants of the Boston mechanism, and hybrid mechanisms. In this letter, we summarize the main results from [Mennle and Seuken 2014a] and demonstrate how they can be used for the design and analysis of matching mechanisms.1 Categories and Subject Descriptors: J.4.a [Social and Behavioral Sciences]: Economics General Terms: Economics; Theory Additional Key Words and Phrases: Matching, Mechanism Design, Strategyproofness 1. INTRODUCTION The (probabilistic) one-sided matching problem is concerned with the allocation of indivisible goods to self-interested agents with privately known preferences in domains where monetary transfers are not permitted. Such problems often arise in situations that are of great importance to peoples' lives. For example, students must be matched to schools, teachers to training programs, or tenants to houses. Strategyproof mechanisms, such

Journal

ACM SIGecom Exchanges – Association for Computing Machinery

Published: Nov 25, 2014

There are no references for this article.