Matching problems with preferences are all around us OCo they arise when agents seek to be allocated to one another on the basis of ranked preferences over potential outcomes. Efficient algorithms are needed for producing matchings that optimise the satisfaction of the agents according to their preference lists.In recent years there has been a sharp increase in the study of algorithmic aspects of matching problems with preferences, partly reflecting the growing number of applications of these problems worldwide. This book describes the most important results in this area, providing a timely update to The Stable Marriage Problem: Structure and Algorithms (D Gusfield and R W Irving, MIT Press, 1989) in connection with stable matching problems, whilst also broadening the scope to include matching problems with preferences under a range of alternative optimality criteria."

Matching problems with preferences are all around us: they arise when agents seek to be allocated to one another on the basis of ranked preferences over potential outcomes. Efficient algorithms are needed for producing matchings that optimise the satisfaction of the agents according to their preference lists.In recent years there has been a sharp increase in the study of algorithmic aspects of matching problems with preferences, partly reflecting the growing number of applications of these problems worldwide. The importance of the research area was recognised in 2012 through the award of the Nobel Prize in Economic Sciences to Alvin Roth and Lloyd Shapley.This book describes the most important results in this area, providing a timely update to The Stable Marriage Problem: Structure and Algorithms (D Gusfield and R W Irving, MIT Press, 1989) in connection with stable matching problems, whilst also broadening the scope to include matching problems with preferences under a range of alternative optimality criteria.

Matching under preferences involves matching agents to one another, subject to various optimality criteria such as stability, popularity, and Pareto-optimality, etc. Each agent expresses ordinal preferences over a subset of the others. Real-life applications include assigning graduating medical students to hospitals, high school students to colleges, public houses to applicants, and so on. We consider various matching problems with preferences. In this dissertation, we present efficient algorithms to solve them, prove hardness results, and develop linear programming theory around them. In the first part of this dissertation, we present two characterizations for the set of super-stable matchings. Super-stability is one of the optimality criteria when the preference lists contain ties. The first algorithm computes irreducible super-stable matchings in the super-stable matching lattice. The second algorithm takes O(mn) time, where m denotes the number of edges and n denotes the number of vertices and gives an explicit rotation poset that can be used to construct all super-stable matchings. In the second part, we present a polyhedral characterization of the set of all super-stable matchings, i.e. a linear system that is integral and describes the super-stable matching polytope. We also give alternative proof for the integrality of the strongly stable matching polytope. We also use linear programming techniques to solve an application of the stable matching problem. In the third part, we present NC algorithms for the popular matching problem. Popularity is another optimality criterion, where each agent gives a vote and the outcome matching has majority votes. In the last part, we consider envy-freeness, a relaxation of stability in the Hospitals/Residents setting, which allows blocking pairs involving a resident and an empty position of a hospital. Envy-free matching might not exist. We prove NP-hardness results of minimizing envy (if envy is inevitable) in terms of envy-pairs and envy-residents in the Hospitals/Residents Problem with Lower Quota

Two-sided matching provides a model of search processes such as those between firms and workers in labor markets or between buyers and sellers in auctions. This book gives a comprehensive account of recent results concerning the game-theoretic analysis of two-sided matching. The focus of the book is on the stability of outcomes, on the incentives that different rules of organization give to agents, and on the constraints that these incentives impose on the ways such markets can be organized. The results for this wide range of related models and matching situations help clarify which conclusions depend on particular modeling assumptions and market conditions, and which are robust over a wide range of conditions. 'This book chronicles one of the outstanding success stories of the theory of games, a story in which the authors have played a major role: the theory and practice of matching markets ... The authors are to be warmly congratulated for this fine piece of work, which is quite unique in the game-theoretic literature.' From the Foreword by Robert Aumann