Effective Matchmaking (Recursion Theoretic Aspects of a Theorem of Philip Hall)

Alfred B. Manaster, Joseph G. Rosenstein

Proceedings of the London Mathematical Society · 1972 · 53 citations · 5 references

Concepts

Abstract

Given a set B of boys and a set 0 of girls, we call a subset S of BxO a society and we say that b knows g when (b,gy e S. The marriage problem for the society S is said to be solvable if it is possible to marry, in the traditional one-to-one manner, each boy to a girl whom he knows. We are concerned here with the computable analogues of these notions. Thus a society is recursive if there exists an algorithm which, when presented with a boy 6 and a girl g, effectively determines whether 6 knows g. Similarly, the marriage problem for the society S is said to be recursively solvable if there exists a one-to-one algorithm which, when presented with a boy 6, effectively marries him to a girl whom he knows. We first show that, even if (the marriage problem for) a recursive society is solvable, it need not be recursively solvable. We then consider several conditions on solvable recursive societies; for each we determine whether such a society must be recursively solvable and, if not, how computationally complex its solutions need be. We also discuss some sociological variations of the marriage problem and indicate how our results can be applied to them. We have drawn upon ideas from two branches of mathematics— combinatorics and recursive function theory. The combinatorial motivation has its source in a famous theorem of Philip Hall ([4]) which implies that if there are only a finite number of boys, then the society S is solvable if and only if, for each natural number k, any k distinct boys know among them at least k different girls. Using a compactness argument one can show that this same condition is necessary and sufficient even if there are an infinite number of boys, so long as no boy knows infinitely many girls. (See either [5] for a combinatorial argument or [1], p. 47, for a proof based on the propositional calculus. This generalization was first proved by M. Hall ([3]). L. Mirsky's new book ([10]) contains an exhaustive

References

5