A matching problem with $N$ men, $N$ women and $N$ houses [closed]

Question

Consider a matching problem with $N$ men, $N$ women and $N$ houses where each man has to be paired with exactly $1$ woman and then each couple has to be allotted to $1$ house. Now let's consider all $N!$ possible partner matchings and then allot houses adversarially for each matching such that the number of unique houses visited by an average man/woman, aggregated across all $N!$ matchings, is minimized. Is there a provable lower bound to this minimum value? Are there any known theorems that can be applied to prove such a lower bound?

Answer 1

Let me first try to state what I believe the question to be more clearly. You have $n$ men, $n$ women and $n$ houses. You want to choose $n!$ ways to partition into $n$ triples, each consisting of a man, woman and house, such that over these $n!$ ways, if you ignore the houses, you get every possible matching of men to women exactly once.

You want to know (I think) the following. For each person, count the number of different houses that they appear in a triple with. You want to make the average of this over all people, or, equivalently, the sum of this over all people, as small as possible.

If so, the best you can do is a sum of $n(n+1)$, or equivalently an average of $\frac{n+1}{2}$. You can clearly do this by matching the women to houses in the same way every time, so every man gets matched to $n$ different houses but every woman only gets matched to $1$ house.

To show you can't do better, note that the sum can equivalently be expressed as the sum over houses of the number of people who ever get matched to that house. Now we'll show every house gets at least $n+1$ different people matched to it. If this is not the case, there is some house that can only be matched to one of $k$ possible men and $n-k$ possible women for some $k$. But now there is a matching of men to women where these $k$ men get matched to the other $k$ women, and no pair of that matching can live in this house, contradiction. Thus the sum over houses is at least $n(n+1)$, as required.