Essays on Matching

Sammanfattning: This thesis makes a contribution to matching theory and mechanism design. It consists of four self-contained papers focusing on kidney exchange, object allocation and partnership formation. The first paper, Pairwise Kidney Exchange over the Blood Group Barrier, investigates how the use of immunosuppressive drugs can be implemented within kidney exchange programs. Thanks to advances in medicine, immunosuppressive drugs can be used to enable some kidney transplants that were previously infeasible due to blood group incompatibilities. We introducea class of Pareto efficient matchings and provide a method for finding such matchings. We show that introducing immunosuppressive drugs would have a larger impact on the number of transplants than three-way exchanges and altruistic participation in a simulation study.The second paper, Triage in Kidney Exchange, considers a problem where there is a planner in charge of designing a kidney exchange program. The planner sorts patients into “priority groups” based on how urgent their conditions are. I define a class of matchings that are Pareto efficient regardless of how patients are sorted into priority groups or how the planner chooses to design the kidney exchange program. Such matchings can be found using integer programmingand include a number of well studied subclasses of matchings as special cases. The third paper, Overlapping Multiple Object Assignments, deals with an object allocation problem where agents are assigned bundles of objects. The assignments are allowed to overlap in the sense that multiple agents can be assigned the same object as long as the agents are “compatible”. This object allocation problem is closely related to zoning, where a city is divided into, e.g., industrial, commercial and residential districts. The main result shows that a rule assigning bundles of objects to agents is group-strategyproof, Pareto efficient and satisfies a third property called compatibility-monotonicity if and only if it belongs to a class of rules called compatibility-sorting sequential dictatorships. The fourth paper, A Method for Finding the Maximal Set in Excess Demand, provides a slight amendment to a method used to find an equilibrium (whenever it exists) in the partnership formation problem. Using a computationally simple method for finding a particular set of agents, we show that an equilibrium payoff vector can be found in polynomial time.