Can a perfect matching always be found by a picking sequence?

Question

There are $n$ people and $n$ items. For each person, there is a set of items he likes. Our goal is to give to each person a single item that he likes, i.e, find a perfect matching in the preference graph (encoding the "like" relation).

In some cases, this may be done using a picking sequence: order the people in a queue and let each person in turn pick a single item he likes. For example, suppose that:

• $A$ likes $\{1,2\}$
• $B$ likes $\{2,3\}$
• $C$ likes $\{3\}$

Then, $\langle C,B,A\rangle$ is a good picking sequence, since $C$ necessarily picks $3$, then $B$ picks $2$, then $A$ picks $1$ and we get a perfect matching. On the other hand, $\langle C,A,B\rangle$ is not a good picking sequence, since after $C$ picks $3$, it is possible that $A$ will pick $2$, and then $B$ will remain without an item.

So, my question is: If a perfect matching exists, can it always be found by a picking sequence?

Answer 1

Yes, it can. This can be proved by mathematical induction on $n$.

Denote by $U$ the set of people. For a subset of people $P$, denote by $N(P)$ the neighborhood of $P$, that is the set of items that at least one person in $P$ likes. By Hall's marriage theorem, $|P|\le |N(P)|$ for all $P$.

If $|P|< |N(P)|$ for all $P\subsetneq U$, then we can let an arbitrary person pick first. After his picking, $N(P)$ is decreased by at most 1 for all $P$, so $|P|\le |N(P)|$ holds for all $P$ in the remaining graph. Therefore there is still a perfect matching in the remaining graph by Hall's marriage theorem, and there is a valid picking sequence by inductive assumption.

If there exists $P\subsetneq U$ such that $|P|=|N(P)|$, then there is a perfect matching in the subgraph induced by $P\cup N(P)$, and by inductive assumption there is a valid picking sequence for people in $P$ in this subgraph. We can apply this picking sequence in our orignial graph first, and the result is the same, that is, exactly all items in $N(P)$ are picked. Note there is still a perfect matching in the remaining graph, so we can again use the inductive assumption to complete the picking sequence.

Answer 2

Assuming that the order in which a person would pick is consistent IOW everyone will always pick 1 over 2. Then yes there is always an order in which the solution will come out: the picking sequence of the persons is the same as the order of the items they pick.

In your example ABC is also a good picking order, A will pick 1, B will pick 2 and C will pick 3.