Matchmaking
Morris H. DeGroot, Paul I. Feder, Prem K. Goel · The Annals of Mathematical Statistics · 1971
Matching problems are discussed in many elementary probability books, such as Feller (1968). In one version of the problem, as described by Hodges and Lehmann (1964), the photographs of $n$ film stars are paired randomly with $n$ photographs of the same stars taken when they were babies, and the distribution of the number of correct matches is derived. In this paper we shall study the same problem when the photographs are paired on the basis of various measurements that are made on them, rather than randomly. For example, suppose that $r$ different facial measurements are made on the photograph of each star and that $s$ facial measurements are made on each baby photograph. By comparing these measurements, it will typically be possible to devise a method for pairing the photographs that will yield a larger number of correct matches than would be obtained from random pairing. In fact, the procedures that will be developed in this paper can be regarded as formalizations of the heuristic procedures that a person follows when he pairs the photographs on the basis of perceived resemblances. In other versions of the same problem, dental records of parents are to be matched with dental records of their children, or measurements made on the chest X-rays of $n$ individuals are to be matched with other medical records of these same individuals. The problems described here are related in principle to problems of document linkage that have been treated in the statistical literature [see, e.g., DuBois (1969) and the references given there] but the models and methods that are used here seem to be new and unrelated to the models and methods that have previously been used in such problems. For any positive integer $k$, we shall let $R^k$ denote the space of all $k$-dimensional vectors $z = (z_1, \cdots, z_k)$, where $- \infty 0, u > 0, \\ &= 0 \\ \text{otherwise}\end{align*} We shall now present a summary of the specific problems that will be considered in this paper and some of the results that will be obtained. In Section 2, the problem of pairing the vectors $ u_1, \cdots, u_n$ with the vectors $w_1, \cdots, w_n$ in order to maximize the probability of a completely correct set of $n$ matches is considered. It is shown that the probability is maximized if the values of $\gamma( u_1), \cdots, \gamma( u_n)$ are ordered from smallest to largest, the values of $\delta(w_1), \cdots \delta(w_n)$ are similarly ordered, and corresponding terms in these two orderings are paried with each other. This solution is also the maximum likelihood solution for the problem of pairing $ u_1, \cdots, u_n$ with $w_1, \cdots, w_n$. In Section 3 this maximum likelihood solution is applied to the multivariate normal distribution and is shown to have a natrual and intuitive interpretation in terms of regression. In Section 4, we consider the problem of choosing a vector $w_j$ from the set $w_1, \cdots, w_n$ in order to maximize the probability of correctly matching one specified vector $ u_1$ from the set $ u_1, \cdots, u_n$. It is shown that if $\gamma( u_i)$ is the minimum or the maximum of the $n$ values $\gamma( u_1), \cdots, \gamma( u_n)$, then $ u_i$ should be paired with a vector $w_j$ for which $\delta(w_j)$ is a minimum or a maximum, respectively. For intermediate values of $\gamma( u_i)$, the solution is shown to be more complicated. In Section 5, the problem of pairing $ u_1, \cdots, u_n$ with the vectors $w_1, \cdots, w_n$ in order to maximize the expected number of correct matches is considered. Although the general solution of this problem is complicated, it is shown here again that the vector $ u_i$ for which $\gamma( u_i)$ is a minimum should always be paired with the vector $w_j$ for which $\delta(w_j)$ is a minimum and the vector $ u_i$ for which $\gamma( u_i)$ is a maximum should always be paired with the vector $w_j$ for which $\delta(w_j)$ is a maximum. In particular, it follows that when $n = 3$, the solution to this problem and the maximum likelihood solution are always identical. In Section 6, sufficient conditions are given under which, for an arbitrary value of $n$, the maximum likelihood solution will also maximize the expected number of correct matches. The simplest and most striking sufficient condition given there, but also the most severe condition, is that $\lbrack \max_i \gamma( u_i) - \min_i\gamma( u_i) \rbrack \lbrack \max_j \delta(w_j) - \min_j \delta(w_j) \rbrack \leqq 1.$ Finally, in Section 7, some examples are given in which these sufficient conditions are not satisfied and the maximum likelihood solution does not maximize the expected number of correct matches.