Making Pairs
(2015) Abstract
 This thesis makes a contribution to matching theory. It consists of five selfcontained 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 worldwide. This was particularly highlighted 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 selfcontained 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 worldwide. This was particularly highlighted 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 knifeedge 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 twosided, 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, nonmanipulability 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 nonmanipulable rule. I also examine two extensions: the manytoone setting and the general pairing problem. (Less)
Please use this url to cite or link to this publication:
http://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
 20150605 14:15
 language
 English
 LU publication?
 yes
 id
 86037d59ccf94c27b1f987907f739d28 (old id 5366432)
 date added to LUP
 20150511 17:27:25
 date last changed
 20160919 08:45:16
@misc{86037d59ccf94c27b1f987907f739d28, abstract = {This thesis makes a contribution to matching theory. It consists of five selfcontained 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 worldwide. This was particularly highlighted 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 knifeedge 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 twosided, 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, nonmanipulability 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 nonmanipulable rule. I also examine two extensions: the manytoone setting and the general pairing problem.}, author = {Gudmundsson, Jens}, keyword = {equilibrium,existence,Pairing,matching,stability,algorithms}, language = {eng}, title = {Making Pairs}, year = {2015}, }