Header

UZH-Logo

Maintenance Infos

Trade-offs between strategyproofness and efficiency of ordinal mechanisms - Zurich Open Repository and Archive


Mennle, Timo. Trade-offs between strategyproofness and efficiency of ordinal mechanisms. 2016, University of Zurich, Faculty of Economics.

Abstract

There are some things that money cannot buy. For various reasons, moral or otherwise, society has set boundaries regarding the use of money for certain resources and transactions. Such restrictions often arise in situations that are of great importance to people's lives: subsidized housing must be assigned to tenants, seats at public schools must be assigned to students, or a new president must be elected. The design of mechanisms for these problems is plagued by severe impossibility results pertaining to strategyproofness. In this thesis we address the research question of how to trade off strategyproofness and other desiderata in the design of ordinal mechanisms. For the assignment domain we introduce the new relaxed incentive concept of partial strategyproofness which can be used to measure the incentive properties of non-strategyproof mechanisms. We employ this concept to show that a choice between three popular school choice mechanisms, the Deferred Acceptance mechanism and two variants of the Boston mechanism, involves an implicit trade-off between strategyproofness and efficiency. Next, we give conditions under which hybrid mechanisms facilitate meaningful trade-offs between strategyproofness and efficiency in the assignment domain. Finally, in the general ordinal domain we introduce a new framework to assess mechanisms by their manipulability and their welfare deficit. The welfare deficit is a measure for their ability to achieve another desideratum, such as efficiency, stability, or fairness. Within this framework the Pareto frontier consists of those mechanisms that trade off manipulability and deficit optimally. Our main result is a structural characterization of this Pareto frontier.

Abstract

There are some things that money cannot buy. For various reasons, moral or otherwise, society has set boundaries regarding the use of money for certain resources and transactions. Such restrictions often arise in situations that are of great importance to people's lives: subsidized housing must be assigned to tenants, seats at public schools must be assigned to students, or a new president must be elected. The design of mechanisms for these problems is plagued by severe impossibility results pertaining to strategyproofness. In this thesis we address the research question of how to trade off strategyproofness and other desiderata in the design of ordinal mechanisms. For the assignment domain we introduce the new relaxed incentive concept of partial strategyproofness which can be used to measure the incentive properties of non-strategyproof mechanisms. We employ this concept to show that a choice between three popular school choice mechanisms, the Deferred Acceptance mechanism and two variants of the Boston mechanism, involves an implicit trade-off between strategyproofness and efficiency. Next, we give conditions under which hybrid mechanisms facilitate meaningful trade-offs between strategyproofness and efficiency in the assignment domain. Finally, in the general ordinal domain we introduce a new framework to assess mechanisms by their manipulability and their welfare deficit. The welfare deficit is a measure for their ability to achieve another desideratum, such as efficiency, stability, or fairness. Within this framework the Pareto frontier consists of those mechanisms that trade off manipulability and deficit optimally. Our main result is a structural characterization of this Pareto frontier.

Statistics

Downloads

9 downloads since deposited on 06 Jan 2017
9 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Dissertation
Referees:Seuken Sven, Sönmez Tayfun, Budish Eric
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Language:English
Date:2016
Deposited On:06 Jan 2017 15:38
Last Modified:21 Feb 2017 15:58
Number of Pages:399
Free access at:Official URL. An embargo period may apply.
Official URL:http://www.ifi.uzh.ch/ce/publications/thesis_mennle_a4.pdf
Other Identification Number:merlin-id:14390

Download

Preview Icon on Download
Preview
Filetype: PDF
Size: 3MB

TrendTerms

TrendTerms displays relevant terms of the abstract of this publication and related documents on a map. The terms and their relations were extracted from ZORA using word statistics. Their timelines are taken from ZORA as well. The bubble size of a term is proportional to the number of documents where the term occurs. Red, orange, yellow and green colors are used for terms that occur in the current document; red indicates high interlinkedness of a term with other terms, orange, yellow and green decreasing interlinkedness. Blue is used for terms that have a relation with the terms in this document, but occur in other documents.
You can navigate and zoom the map. Mouse-hovering a term displays its timeline, clicking it yields the associated documents.

Author Collaborations