Algorithmics Of Matching Under Preferences

David F Manlove

• Publisher: WSPC
• Year: 2013
• Print ISBN: 9789814425247
• eBook ISBN: 9789814425261
• Topic: Biological Sciences
• Subtopic: Science General
• Index: Biological Sciences

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.

Contents:

• Preliminary Definitions, Results and Motivation
• Stable Matching Problems:
  • The Stable Marriage Problem: An Update
  • SM and HR with Indifference
  • The Stable Roommates Problem
  • Further Stable Matching Problems
• Other Optimal Matching Problems:
  • Pareto Optimal Matchings
  • Popular Matchings
  • Profile-Based Optimal Matchings

Readership: Students and Professionals interested in algorithms, especially in the study of algorithmic aspects of matching problems with preferences.

Chapter 1

Preliminary definitions, results and motivation

1.1 Introduction

1.1.1 Remit of this book

1.1.1.1 Matching under preferences

This book is about computational problems that involve matching agents to one another, subject to various criteria. Here, the term agent is used loosely to mean any participant in a matching process, and could include commodities in addition to human subjects. In many cases the agents form two disjoint sets, and we seek to assign the agents in one set to those in the other. Examples include assigning junior doctors to hospitals, pupils to schools, kidney patients to donors, and so on.

We primarily focus on the case that a subset of the agents have ordinal preferences over a subset of the others. That is, there is a notion of first choice, second choice, third choice, etc. For example a school-leaver who is applying for admission to university might rank in order of preference a small subset (say 5) of all available universities. Likewise, the universities might form a ranking of their applicants according to academic merit, and possibly other criteria. We will not always insist that the preference lists be strictly ordered: for example a school-leaver might have two universities that are jointly ranked as first choice in her preference list.

Typically there are other constraints in addition to the preference lists: for example, it is reasonable to assume that a school-leaver should not be assigned to more than one university, and likewise a university might have a capacity, indicating the maximum number of students that it could admit in a particular academic session.

1.1.1.2 Free-for-all markets

Applications of matching problems involving ordinal preferences (henceforth the term ordinal preferences will be shortened to preferences) can be very large in practice. For example in 2011, 140,953 students applied for admission to higher education in Hungary [90]. Economists have identified several problems that arise in free-for-all markets, in which the agents are able to negotiate with one another directly in order to arrange assignments [518, 467].

These problems include unravelling in which agents form assignments with one another earlier and earlier in advance of the deadline by which all assignments must be fixed. For example, hospitals wishing to recruit the best applicants might compete with one another by advancing the date when they make their offers. To avoid this issue, agents might be prevented from entering into premature assignments before a certain date.

This can then lead to the problem of congestion, in which agents do not have sufficient time to negotiate with one another over potential assignments prior to the deadline. For example a hospital h offering 20 places to applicants might have to make substantially more than 20 offers, to allow for applicants who will turn down h’s offer.

In an effort to avoid congestion, a new problem might emerge, namely exploding offers. In such a case, agents are given only a short time period to decide whether they are able to form a given assignment, otherwise the potential for making that assignment is removed. For example hospital h might force an applicant r to make a decision swiftly by setting r a deadline, beyond which the offer expires. Unravelling, congestion and exploding offers lead to a situation in which agents might be forced into forming an assignment with one another before they have knowledge of the whole range of potential assignments that may potentially be available to them.

Prior to 1952, the assignment of junior doctors to hospitals in the USA was carried out by a free-for-all market. A detailed description of the problems that this led to (which included unravelling, congestion and exploding offers as described above), with reference to this particular application, has been given in several references in the literature [261, 514, 518, 467].

1.1.1.3 Centralised matching schemes

Centralised matching schemes (referred to as (centralised) clearinghouses by economists) can avoid some of the problems that are inherent in free-for-all markets. These work along the following lines: the input data involving the agents and their preferences over one another are collected by a given deadline by a trusted central authority. This third party then compu...

Table of contents

• Cover
• ALGORITHMICS OF MATCHING UNDER PREFERENCES
• Volumes
• Title
• Copyrights
• Dedication
• Preface
• Foreword
• Acknowledgments
• Contents
• List of Figures
• List of Tables
• List of Algorithms
• Chapter 1
• Part 1
• Part 2
• Biblography
• Glossary
• Index