Making Pairs
(2015)- Abstract
- This thesis makes a contribution to matching theory. It consists of five self-contained papers. It is a study predominately on the existence of stable outcomes. These are desirable both from a practical and a theoretical standpoint. Matching theory has grown in importance in recent years following its successful applications to, for instance, kidney exchange, the National Resident Matching Program, and school choice world-wide. This was particularly high-lighted when two researchers on matching theory, Alvin Roth and Lloyd Shapley, were awarded the Nobel Prize in 2012.
The first paper, When Do Stable Roommate Matchings Exist? A Review, is a survey on the literature on the roommate problem. I compare different preference... (More) - This thesis makes a contribution to matching theory. It consists of five self-contained papers. It is a study predominately on the existence of stable outcomes. These are desirable both from a practical and a theoretical standpoint. Matching theory has grown in importance in recent years following its successful applications to, for instance, kidney exchange, the National Resident Matching Program, and school choice world-wide. This was particularly high-lighted when two researchers on matching theory, Alvin Roth and Lloyd Shapley, were awarded the Nobel Prize in 2012.
The first paper, When Do Stable Roommate Matchings Exist? A Review, is a survey on the literature on the roommate problem. I compare different preference restrictions that ensure the existence of stable matchings and generalize some of them to a more general setting in which agents are allowed to be indifferent between partners and have outside options to turn to.
The second paper, A Competitive Partnership Formation Process, examines the partnership formation problem. Specifically, we study how one can find an equilibrium in said problem without demanding full information disclosure by the agents. We derive a process that achieves this. If there is no equilibrium, the process can still be used to gain some insight to the structure of the problem. Several fundamental properties of equilibrium are derived.
The third paper, A Method for Finding the Maximal Set in Excess Demand, is a companion paper to the second paper and shows how the process defined in A Competitive Partnership Formation Process can be modified and improved upon from a computational point of view.
The fourth paper, Assignment Games with Externalities, generalizes the assignment game by introducing externalities. These are important in practice. For instance, the profit of a firm surely depends on the success of its competitors. We find that the classical results are overturned except in a knife-edge case. We show that, even with the slightest externalities, there may not exist a stable outcome.
The fifth paper, Sequences in Pairing Problems, is a comprehensive study of two-sided, repeated matching. Allowing the pairing to change regularly over time can lead to improvements both in terms of efficiency and fairness. In contrast to the static setting, I find that two very appealing properties, non-manipulability and stability, can be reconciled through sequencing. Moreover, the rule I suggest is novel and fundamentally different from the one that has had the most success in the matching literature. On a rich domain of preferences, my rule is singled out as the only stable and non-manipulable rule. I also examine two extensions: the many-to-one setting and the general pairing problem. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/5366432
- author
- Gudmundsson, Jens LU
- supervisor
- opponent
-
- Echenique, Federico, California Institute of Technology
- organization
- publishing date
- 2015
- type
- Thesis
- publication status
- published
- subject
- keywords
- equilibrium, existence, Pairing, matching, stability, algorithms
- defense location
- Holger Crafoord EC3:211
- defense date
- 2015-06-05 14:15:00
- language
- English
- LU publication?
- yes
- id
- 86037d59-ccf9-4c27-b1f9-87907f739d28 (old id 5366432)
- date added to LUP
- 2016-04-04 13:07:40
- date last changed
- 2018-11-21 21:12:20
@phdthesis{86037d59-ccf9-4c27-b1f9-87907f739d28,
abstract = {{This thesis makes a contribution to matching theory. It consists of five self-contained papers. It is a study predominately on the existence of stable outcomes. These are desirable both from a practical and a theoretical standpoint. Matching theory has grown in importance in recent years following its successful applications to, for instance, kidney exchange, the National Resident Matching Program, and school choice world-wide. This was particularly high-lighted when two researchers on matching theory, Alvin Roth and Lloyd Shapley, were awarded the Nobel Prize in 2012.<br/><br>
<br/><br>
The first paper, When Do Stable Roommate Matchings Exist? A Review, is a survey on the literature on the roommate problem. I compare different preference restrictions that ensure the existence of stable matchings and generalize some of them to a more general setting in which agents are allowed to be indifferent between partners and have outside options to turn to.<br/><br>
<br/><br>
The second paper, A Competitive Partnership Formation Process, examines the partnership formation problem. Specifically, we study how one can find an equilibrium in said problem without demanding full information disclosure by the agents. We derive a process that achieves this. If there is no equilibrium, the process can still be used to gain some insight to the structure of the problem. Several fundamental properties of equilibrium are derived.<br/><br>
<br/><br>
The third paper, A Method for Finding the Maximal Set in Excess Demand, is a companion paper to the second paper and shows how the process defined in A Competitive Partnership Formation Process can be modified and improved upon from a computational point of view.<br/><br>
<br/><br>
The fourth paper, Assignment Games with Externalities, generalizes the assignment game by introducing externalities. These are important in practice. For instance, the profit of a firm surely depends on the success of its competitors. We find that the classical results are overturned except in a knife-edge case. We show that, even with the slightest externalities, there may not exist a stable outcome. <br/><br>
<br/><br>
The fifth paper, Sequences in Pairing Problems, is a comprehensive study of two-sided, repeated matching. Allowing the pairing to change regularly over time can lead to improvements both in terms of efficiency and fairness. In contrast to the static setting, I find that two very appealing properties, non-manipulability and stability, can be reconciled through sequencing. Moreover, the rule I suggest is novel and fundamentally different from the one that has had the most success in the matching literature. On a rich domain of preferences, my rule is singled out as the only stable and non-manipulable rule. I also examine two extensions: the many-to-one setting and the general pairing problem.}},
author = {{Gudmundsson, Jens}},
keywords = {{equilibrium; existence; Pairing; matching; stability; algorithms}},
language = {{eng}},
school = {{Lund University}},
title = {{Making Pairs}},
year = {{2015}},
}