Three essays in matching mechanism design

Autor: Nesterov, Alexander
Jazyk: angličtina
Rok vydání: 2016
Předmět:
Druh dokumentu: Doctoral Thesis
DOI: 10.18452/17647
Popis: In diese Dissertation, betrachte ich das Problem der Aufteilung der unteilbaren Objekte unter Agenten, ihren Vorlieben entsprechend, und die Transfers fehlen. In Kapitel 1 studiere ich den Kompromiss zwischen Fairness und Effizienz in der Klasse der strategy-proof Aufteilungsmechanismen. Das wichtigste Ergebnis ist, dass für die strategy-proof Mechanismen folgende Effizienz- und Fairness-Kriterien nicht miteinander vereinbar sind: (1) Ex-post-Effizienz und Neidfreiheit, (2) Ordnung-Effizienz und schwache Neidfreiheit und (3) Ordnung-Effizienz und gleiche-Teilung-untere-Grenze. In Kapitel 2 ist der Fokus auf zwei Darstellungen einer Zuteilung: als probabilistische Zuordnung und als Lotterie über deterministische Zuordnungen. Um die Gestaltung der praktischen Lotterie-Mechanismen zu erleichtern schlagen wir neue Werkzeuge für den Erhalt der stochastischen Verbesserungen bei Lotterien vor. Als Anwendungen schlagen wir Lotterie Mechanismen, die die weit verbreiteten Random serial dictatorship Mechanismus verbessern, und eine Lotterie-Darstellung seiner Konkurrent, die Probabilistic serial Mechanismus, vor. In Kapitel 3 schlage ich einen neuen Mechanismus vor, der Schüler an Grundschulen zuweist: Adaptive Acceptance (AA). AA sammelt von Neumann-Morgenstern Präferenzen von Studenten über Schulen und implementiert die Zuordnung unter Verwendung eines iterativen Verfahrens, das ähnlich der vorherrschenden Immediate Acceptance (IA) ist. AA verfügt über eine starke Kombination von Anreize und Effizienzeigenschaften im Vergleich zu IA und sein Rivale, Deferred Acceptance (DA).
I consider the problem of allocating indivisible objects among agents according to their preferences when transfers are absent. In Chapter 1, I study the tradeoff between fairness and efficiency in the class of strategy-proof allocation mechanisms. The main finding is that for strategy-proof mechanisms the following efficiency and fairness criteria are mutually incompatible: (1) Ex-post efficiency and envy-freeness, (2) ordinal efficiency and weak envy-freeness and (3) ordinal efficiency and equal division lower bound. In Chapter 2, the focus is on two representations of an allocation when randomization is used: as a probabilistic assignment and as a lottery over deterministic assignments. To help facilitate the design of practical lottery mechanisms, we provide new tools for obtaining stochastic improvements in lotteries. As applications, we propose lottery mechanisms that improve upon the widely-used random serial dictatorship mechanism, and a lottery representation of its competitor, the probabilistic serial mechanism. In Chapter 3, I propose a new mechanism to assign students to primary schools: the Adaptive Acceptance rule (AA). AA collects von Neumann-Morgenstern utilities of students over schools and implements the assignment using an iterative procedure similar to the prevalent Immediate Acceptance rule (IA). AA enjoys a strong combination of incentive and efficiency properties compared to IA and its rival, the Deferred Acceptance rule (DA). In case of strict priorities, AA implements the student-optimal stable matching in dominant strategies, which dominates each equilibrium outcome of IA. In case of no priorities, AA is ex-post efficient while some equilibrium outcomes of IA are not; also, AA causes loss of ex-ante efficiency less often than DA. If, in addition, students have common ordinal preferences, AA is approximately strategy-proof and ex-ante dominates DA.
Databáze: Networked Digital Library of Theses & Dissertations
Externí odkaz: