Home | Business News | Browse by Publication | E | Economic Theory

Procedurally fair and stable matching.

Article Excerpt
Summary. We motivate procedural fairness for matching mechanisms and study two procedurally fair and stable mechanisms: employment by lotto (Aldershof et al., 1999) and the random order mechanism (Roth and Vande Vate, 1990, Ma, 1996). For both mechanisms we give various examples of probability distributions on the set of stable matchings and discuss properties that differentiate employment by lotto and the random order mechanism. Finally, we consider an adjustment of the random order mechanism, the equitable random order mechanism, that combines aspects of procedural and "endstate" fairness.

Keywords and Phrases: Procedural fairness, Random mechanism, Stability, Two-sided matching.

JEL Classification Numbers: C78, D63.

1 Introduction

The marriage model describes a two-sided, one-to-one matching market without money where the two sides of the market for instance are workers and firms (job matching) or medical students and hospitals (matching of students to internships). We use the common terminology in the literature and refer to one side of the market as "men" and to the other as "women." An outcome for a marriage market is called a matching, which can simply be described by a collection of single agents and "married" pairs (consisting of one man and one woman). Loosely speaking, a matching is stable if all agents have acceptable spouses and there is no couple whose members both like each other better than their current spouses. Gale and Shapley (1962) formalized this notion of stability for marriage markets and provided an algorithm to calculate stable matchings. These classical results (Gale and Shapley, 1962) inspired many researchers to study stability not only for the marriage model, but for more general models as well. We refer to Roth and Sotomayor (1990) for a comprehensive account on stability for two-sided matching models.

In this paper we study fairness and stability in marriage markets. Masarani and Gokturk (1989) showed several impossibilities to obtain a fair deterministic matching mechanism within the context of Rawlsian justice. In contrast to this cardinal approach we focus on the ordinal aspects of the model and opt for an approach of procedural fairness. Since for any deterministic matching mechanism we can detect an inherent favoritism either for one side of the market or for some agents over others, in order to at least recover ex ante fairness, we consider probabilistic matching mechanisms that assign to each marriage market a probability distribution on the set of stable matchings. We do not intend to judge the fairness of a probabilistic matching mechanism by judging the assigned probability distributions (the "endstate"), but by considering procedurally fair matching algorithms in which the sequence of moves for the agents is drawn from a uniform distribution. Hence, whenever an agent has the same probability to move at a certain point in the procedure that determines the final probability distribution, we consider the random matching mechanism to be procedurally fair. In other words, here we focus on "procedural justice" rather than on endstate justice (see Moulin, 1997, 2003). After a discussion of procedural fairness, we explain our procedural fairness concept for matching markets, discuss two procedurally fair and stable matching mechanisms, and conclude with a stable mechanism that combines some aspects of procedural and endstate fairness.

The first procedurally fair and stable matching mechanism we consider, called employment by lotto, was proposed by Aldershof et al. (1999). Loosely speaking, employment by lotto can be considered to be a random serial dictatorship on the set of stable matchings. A first agent is drawn randomly and can discard all stable matchings in which he/she is not matched to his/her best partner (possibly him/herself) in a stable matching. Exclude the first agent and his/her partner from the set of agents and randomly choose the next agent who can discard all stable matchings in which he/she is not matched to his/her best partner in the reduced set of stable matchings. Continue with this sequential reduction of the set of stable matchings until it is reduced to a singleton. Using all possible sequences of agents, this mechanism induces a probability distribution on the set of stable matchings. The associated probabilistic matching mechanism of this probabilistic sequential dictatorship equals employment by lotto. We give various examples of probability distributions on the set of stable matchings induced by employment by lotto and show certain limitations of this mechanism (e.g., complete information of all agents' preferences is needed).

The second procedurally fair and stable matching mechanism we consider is a random matching mechanism based on Roth and Vande Vate's (1990) results. We follow Ma (1996) and refer to this rule as the random order mechanism. The basic idea is as follows. Imagine an empty room with one entrance. At the beginning, all agents are waiting outside. At each step of the algorithm one agent is chosen randomly and invited to enter. Before an agent enters, the matching in the room is stable. However, once an agent enters the room, the existing matching in the room may become unstable, meaning that the new agent can form a blocking pair with another agent that already is present in the room. By satisfying this (and possible subsequent) blocking pair(s) in a certain way a new stable matching including the entering agent is obtained for the marriage market in the room. After a finite number of steps a stable matching for the original marriage market is obtained. Using all possible sequences of agents, this mechanism induces a probability distribution on the set of stable matchings. The associated probabilistic matching mechanism equals the random order mechanism. We give various examples of probability distributions on the set of stable matchings induced by the random order mechanism. Furthermore, we correct the probability distribution for the marriage market considered by Ma (1996). We detected that the small mistake in the calculations by Ma (1996) is due to the fact that even though the example looks very symmetric, some of the calculations are not as "symmetric" since the random order mechanism does not satisfy what we call independence of dummy agents; that is, the final probability distribution on the set of stable matchings may crucially depend on preferences of agents who are matched to the same partner in all stable matchings.

Third, following a suggestion by Romero-Medina (2002), we briefly discuss an adjustment of the random order mechanism, the equitable random order mechanism, that combines aspects of procedural and endstate fairness.

Our examples show that even for small markets the three mechanisms may give completely different outcomes. In all our examples, we implement the mechanisms in Matlab[c]. In some examples the resulting probabilities are rounded.

The article is organized as follows. In Section 2 we introduce marriage markets and stability. In Section 3 we first introduce and discuss procedural fairness. In Section 3.1 we study employment by lotto, in Section 3.2 the random order mechanism, and in Section 3.3 its adjustment, the equitable random order mechanism. We conclude with Section 4.

2 Matching markets and stability

First we introduce the model...

View this article FREE - Now for a Limited Time, try Goliath Business News
Free for 3 Days!