2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Beautiful proof (you forgot to mention the induction base, but it is obviously true). So in the example given in the question, we will initially pick the set $P = \{C\}$, since $|P|=|N(P)|=1$. Indeed there is a picking sequence $<C>$. Then we remain with $\{A,B\}$ and continue in the same way. $\endgroup$ – Erel Segal-Halevi Apr 28 '18 at 18:13
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ By "good picking order" I meant an order where people cannot make mistakes. In the order ABC, it is possible that A will mistaskenly pick 2. In the order CBA, mistakes are not possible. $\endgroup$ – Erel Segal-Halevi Apr 28 '18 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.