Project

Back to overview

Trading off Strategyproofness and Efficiency in Matching Markets

English title Trading off Strategyproofness and Efficiency in Matching Markets
Applicant Seuken Sven
Number 156836
Funding scheme Project funding (Div. I-III)
Research institution Institut für Informatik Universität Zürich
Institution of higher education University of Zurich - ZH
Main discipline Economics
Start/End 01.01.2015 - 30.09.2018
Approved amount 281'436.00
Show all

All Disciplines (2)

Discipline
Economics
Information Technology

Keywords (9)

School Choice; Market Design; Efficiency; Strategyproofness; Matching; Mechanism Design; Trade-offs; Efficient Frontier; Assignment Mechanisms

Lay Summary (German)

Lead
Manche Dinge sind für Geld nicht zu haben, wie zum Beispiel der Zugang zu den besten öffentlichen Schulde, Spenderorgane, oder Praktika bei NGOs. Aus moralischen und ethischen Gründen ist die Nutzung von Geld eingeschränkt wenn es um unsere Gesundheit, Bildung oder Arbeitssituation geht. Das Matching Problem entsteht wenn Teilnehmer und/oder Objekte einander zugeordnet werden müssen, monetäre Zahlungen ausgeschlossen sind und die Präferenzen der Teilnehmer unbekannt sind.
Lay summary

Beim Design von Matching Märkten sind zwei wichtige Design-Kriterien „Fairness“ und „Effizienz“, wobei Effizienz bedeutet, dass möglichst viele Teilnehmer möglichst glücklich mit dem Endergebnis sind. Um ein gutes Matching berechnen zu können, müssen allerdings zunächst die Präferenzen der einzelnen Teilnehmer in Erfahrung gebracht werden. Abhängig vom Verfahren das für die Berechnung verwendet wird, kann es sich jedoch für einzelne Teilnehmer lohnen, bezüglich ihrer Präferenzen zu lügen. Diese Lügen können sich wiederum negativ auf andere Teilnehmer auswirken. Darum ist neben Effizienz und Fairness auch „Anreizkompatibilität“ ein wichtiges Kriterium.

Frühere Forschung hat gezeigt, dass es unmöglich ist, Verfahren zu entwickeln, die alle drei Kriterien optimal erfüllen. Stattdessen müssen stets Abstriche gemacht werden. Bisher wurden vor allem Markt-Designs vorgestellt, die bestimmte Kriterien entweder erfüllen oder nicht. Unser Ziel ist die Entwicklung neuer Konzepte zur Messung der Anreizkompatibilität und der Effizienz. Diese neuen Konzepte ermöglichen dann das Design von Märkten die verschiedene Kriterien optimal balancieren.

Unsere Ergebnisse werden das Verständnis von Matching Märkten grundlegend erweitern. Die Gesellschaft profitiert von verbesserten Matching Märkten beispielsweise indem mehr Eltern ihre Kinder auf Schulen ihrer Wahl ausbilden lassen können und junge Mediziner eine praktische Ausbildung erhalten, die sie besonders interessiert.

Direct link to Lay Summary Last update: 03.03.2015

Responsible applicant and co-applicants

Employees

Publications

Publication
Fast Iterative Combinatorial Auctions via Bayesian Learning
BreroGianluca, LahaieSebastien, SeukenSven (2019), Fast Iterative Combinatorial Auctions via Bayesian Learning, in Thirty-third AAAI Conference of Artificial Intelligence (AAAI-19), Honolulu, HawaiiAAAI, Menlo Park, CA, USA.
Combinatorial Auctions via Machine Learning-based Preference Elicitation
Brero Gianluca, Lubin Benjamin, Seuken Sven (2018), Combinatorial Auctions via Machine Learning-based Preference Elicitation, in Twenty-seventh International Joint Conference on Artificial Intelligence and the Twenty-third Europe, Stockholm, SwedenInternational Joint Conferences on Artificial Intelligence , Online.
First-Choice Maximal and First-Choice Stable School Choice Mechanisms
Dur Umut, Mennle Timo, Seuken Sven (2018), First-Choice Maximal and First-Choice Stable School Choice Mechanisms, in the 2018 ACM Conference, Ithaca, NY, USAACM, New York, NY, USA.
The Pareto Frontier for Random Mechanisms
Mennle Timo, Seuken Sven (2016), The Pareto Frontier for Random Mechanisms, in Proceedings of the 17th ACM Conference on Economics and Computation (EC), Maastricht, The NetherlandsACM, New York, NY, USA.
The Power of Local Manipulation Strategies in Assignment Mechanisms
Mennle Timo, Weiss Michael, Philipp Basil, Seuken Sven (2015), The Power of Local Manipulation Strategies in Assignment Mechanisms, in Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), Buenos Aires, ArgentinaAAAI Press, Palo Alto, CA, USA.

Collaboration

Group / person Country
Types of collaboration
Boston College / Prof. Tayfun Sönmez United States of America (North America)
- in-depth/constructive exchanges on approaches, methods or results
Boston University / Prof. Benjamin Lubin United States of America (North America)
- in-depth/constructive exchanges on approaches, methods or results
- Publication
- Exchange of personnel
North Carolina State University / Prof. Umut Dur United States of America (North America)
- in-depth/constructive exchanges on approaches, methods or results
- Publication
University of Lausanne / Prof. Bettina Klaus Switzerland (Europe)
- in-depth/constructive exchanges on approaches, methods or results

Scientific events

Active participation

Title Type of contribution Title of article or contribution Date Place Persons involved
Thirty-third AAAI Conference of Artificial Intelligence (AAAI-19) Talk given at a conference Fast Iterative Combinatorial Auctions via Bayesian Learning 27.01.2019 Honolulu, Hawaii, United States of America Brero Gianluca;
INFORMS Annual Meeting Talk given at a conference Machine Learning-powered Iterative Combinatorial Auctions 04.11.2018 Phoenix, United States of America Brero Gianluca; Seuken Sven;
Twenty-seventh International Joint Conference on Artificial Intelligence and the Twenty-third European Conference on Artificial Intelligence (IJCAI-ECAI-18) Talk given at a conference Combinatorial Auctions via Machine Learning-based Preference Elicitation 13.07.2018 Stockholm, Sweden Brero Gianluca; Seuken Sven;
19th ACM Conference on Economics and Computation (EC) Talk given at a conference First-Choice Maximal and First-Choice Stable School Choice Mechanisms 18.06.2018 Ithaca, United States of America Seuken Sven;
12th Workshop Matching in Practice Talk given at a conference First Choice-Maximizing School Choice Mechanisms 15.12.2016 Budapest, Hungary Mennle Timo;
17th ACM Conference on Economics and Computation (EC) Talk given at a conference The Pareto Frontier for Random Mechanisms 24.07.2016 Maastricht, Netherlands Mennle Timo; Seuken Sven;
5th World Congress of the Game Theory Society (GAMES) Talk given at a conference Partial Strategyproofness: An Axiomatic Approach to Relaxing Strategyproofness for Assignment Mechanisms 24.07.2016 Maastricht, Netherlands Mennle Timo; Seuken Sven;
13th Meeting of the Society for Social Choice and Welfare Talk given at a conference The Pareto Frontier for Random Mechanisms 28.06.2016 Lund, Sweden Mennle Timo;
Meeting of the COST Action IC1250 on Computational Social Choice Talk given at a conference The Pareto Frontier for Random Mechanisms 02.11.2015 Istanbul, Turkey Mennle Timo;
World Congress of the Econometric Society (ESWC'15) Talk given at a conference Partial Strategyproofness: An Axiomatic Approach to Relaxing Strategyproofness for Assignment Mechanisms 17.08.2015 Montreal, Canada Mennle Timo;
24th International Joint Conference on Artificial Intelligence (IJCAI) Talk given at a conference The Power of Local Manipulation Strategies in Assignment Mechanisms 25.07.2015 Buenos Aires, Argentina Mennle Timo;


Communication with the public

Communication Title Media Place Year
Video/Film Märkte ohne Geld German-speaking Switzerland 2017
Talks/events/exhibitions Wieviel ist die Mona Lisa wert? Die Zukunft des Online-Shoppings... German-speaking Switzerland 2017

Awards

Title Year
Mercator Award 2017 for Junior Researchers 2017

Abstract

There are some things that money cannot buy, like access to the best public schools, a donated kidney, or internship positions at NGOs. For moral and ethical reasons, society has decided to set boundaries regarding the use of money for resources that affect our health, our education, or our work situation. In domains like these, where resources (or matching partners) are scarce and monetary transfers are restricted, we face a matching problem, where people and/or objects must be assigned to each other. The design and analysis of matching mechanisms is part of the relatively new research field called market design. As market designers, we care specifically about the efficiency, strategyproofness, and fairness of the markets we design. Unfortunately, prior research has shown that it is impossible to achieve the optimum on all three dimensions simultaneously, which makes this an interesting market design challenge. Obviously, trade-offs are necessary. Yet, prior work on matching mechanisms has not led to a good understanding of the necessary and possible trade-offs.Instead, the mechanisms studied in previous research only represent discrete points in the space of all possible mechanisms. For example, in one-sided matching, Random Serial Dictatorship is strategyproof, but only ex-post efficient. Probabilistic Serial is ordinally efficient, but only weakly strategyproof. Finally, Rank Value mechanisms are rank efficient, but not even weakly strategyproof. In two-sided matching markets, Deferred Acceptance mechanisms are stable, as well as strategyproof and weakly Pareto efficient for the proposing side. In contrast, the Boston mechanism is strongly Pareto efficient, but manipulable and unstable. While these individual mechanisms are now relatively well understood, the design of mechanisms with intermediate properties is a largely unexplored area; we know relatively little regarding how to trade off small portions of one property for another. The overall goal of this research project is to significantly improve our understanding regarding the possible and necessary trade-offs between efficiency, strategyproofness and other desiderata for matching mechanisms, to ultimately design new mechanisms that make optimal trade-offs. To reach this goal, the research is divided into three separate parts: In Part #1, we study partial strategyproofness, a relaxation of strategyproofness essential for the analysis of trade-offs in matching markets. We first refine and strengthen the partial strategyproofness concept. We then adapt the concept to two-sided matching markets. Finally, we apply the concept to existing non-strategyproof mechanisms and uncover its connection to strategyproofness in the large. In Part #2, we develop new, flexible dominance and efficiency concepts that are needed for the analysis and construction of mechanisms with intermediate properties. This is an important task, because the comparison of mechanisms by conventional dominance concepts is generally ambiguous. To address this problem, we use constrained efficiency and introduce more distinguishing and flexible concepts.In Part #3, we employ our new strategyproofness and efficiency concepts to analyze the necessary and possible trade-offs in matching markets. We first study mechanisms on the efficient frontier, i.e., we seek mechanisms that provide optimal efficiency given certain constraints and, if possible, provide characterizations of these mechanisms. Finally, we propose limit mechanisms as an interesting way to design new mechanisms that make desirable trade-offs. Our research will significantly advance our understanding of the design space for matching mechanisms, in particular regarding what trade-offs are possible and necessary. It will also lead to new insights about the achievable "balance" of various desiderata relevant in real-world matching applications. Finally, our results have great potential to influence future market design research and to provide directions for experimental work regarding human behavior in matching markets.
-