Hall's marriage theorem states that a collection of men can get married iff for every group of $k \geq 1$ men, the total number of women that like one or more of them is at least $k$. For example, if:
- $M_1$ is liked by $W_1$ and $W_2$;
- $M_2$ is liked by $W_2$ and $W_3$;
- $M_3$ is liked by $W_3$ only.
Then the condition is satisfied and so a matching exists ($W_1$-$M_1$, $W_2$-$M_2$ and $W_3$-$M_3$).
But what happens if the men come serially? For example, let's suppose that $M_1$ comes first and selects any woman that likes him; then $M_2$ comes and selects any remaining woman that likes him; etc. In this case, the process will not necessarily conclude with a successful matching! For example, it is possible that:
- $M_1$ selects $W_2$;
- $M_2$ selects $W_3$;
- $M_3$ now remains lonely because the only woman that liked him is already married!
However, if $M_3$ is liked by all women, then the selection always concludes with a marriage, regardless of what $M_1$ and $M_2$ do.
MY QUESTION IS: What conditions, stronger than Hall's marriage condition, guarantee that, for every selection of each man $M_i$, the following men in the series ($M_j$ for $j>i$) can select women that like them, so that the selection always concludes with all men being married?
NOTES:
- The number of women can be equal or larger than the number of men.
- The order of men is pre-specified ($M_1$, ..., $M_n$); only the selection of each man is unknown in advance.
If you're looking for a sufficient condition (Your question is "what conditions guarantee"), here's a simple one : if every women likes only one man, and no pair of women like the same man, then there is a match.
But I assume you are looking for a necessary and sufficient condition ?