Hall’s Theorem in Worker–Task Assignments

From Eligibility Lists to a Graph

Suppose a group of workers must each receive a task, and each worker is eligible for only some of the available tasks. The assignment must respect eligibility, and no task may be assigned to two workers. A bipartite graph records exactly these constraints: one part represents workers, the other represents tasks, and an edge records an eligible worker–task pair. The central question is whether there is a way to assign a distinct eligible task to every worker.

All graphs in this tutorial are finite and simple. A bipartite graph \(G=(V,E)\) has its vertices partitioned into two parts, here denoted \(W\) and \(T\), with every edge joining a vertex of \(W\) to one of \(T\). For a set \(X\subseteq W\), its neighborhood \(N(X)\) is the set of tasks adjacent to at least one worker in \(X\). An edge \(wt\) means worker \(w\) is eligible for task \(t\).

The assignment is possible precisely when the graph has a matching that saturates \(W\). Hall’s condition tests whether the available task choices are numerous enough for every group of workers, not just for each worker considered individually.

Hall’s Theorem

The empty set is included: \(N(\varnothing)=\varnothing\), so its condition reads \(0\ge0\). This condition says that any group of \(k\) workers must collectively have at least \(k\) eligible tasks. The theorem does not require \(|W|=|T|\); if the parts have equal size, a matching saturating \(W\) also uses every task.

Proof. First suppose a matching saturates \(W\). For any \(X\subseteq W\), the matching assigns each worker in \(X\) to a different task in \(N(X)\). Therefore \(N(X)\) contains at least \(|X|\) tasks, proving Hall’s condition.

For the converse, assume \(|N(X)|\ge |X|\) for every \(X\subseteq W\). We prove by induction on \(|W|\) that a matching saturating \(W\) exists. If \(|W|=0\), the empty matching saturates \(W\). Now suppose \(|W|>0\), and assume the claim holds for bipartite graphs with fewer workers.

First consider the case that some nonempty proper subset \(S\subset W\) is tight, meaning \(|N(S)|=|S|\). Restrict the graph to workers \(S\) and tasks \(N(S)\). Every subset \(X\subseteq S\) has all its original neighbors in \(N(S)\), so it still satisfies \(|N(X)|\ge |X|\) in this restricted graph. By induction, there is a matching saturating \(S\).

Now consider the remaining workers \(W\setminus S\) and tasks \(T\setminus N(S)\). For any \(Y\subseteq W\setminus S\), the neighbors available in this remaining graph are \(N(Y)\setminus N(S)\). Applying Hall’s condition to \(S\cup Y\) gives $$ |N(S)|+|N(Y)\setminus N(S)| =|N(S\cup Y)| \ge |S|+|Y|. $$ Since \(|N(S)|=|S|\), it follows that \(|N(Y)\setminus N(S)|\ge |Y|\). The remaining graph therefore satisfies Hall’s condition. It has fewer workers than \(G\), so induction gives a matching saturating \(W\setminus S\). The two matchings use disjoint task sets, \(N(S)\) and \(T\setminus N(S)\), so together they saturate \(W\).

It remains to consider the case that no nonempty proper subset of \(W\) is tight. Choose any worker \(w\). Hall’s condition applied to \(\{w\}\) guarantees a neighboring task \(t\). Delete \(w\) and \(t\). For any nonempty \(X\subseteq W\setminus\{w\}\), the set \(X\) is a proper subset of \(W\), so, because its neighborhood size is an integer and it is not tight, \(|N(X)|\ge |X|+1\). Deleting \(t\) removes at most one of these neighbors. Thus the remaining neighborhood of \(X\) has size at least \(|X|\). The empty subset also satisfies Hall’s condition. By induction, the graph after the deletion has a matching saturating \(W\setminus\{w\}\). Adding the edge \(wt\) gives a matching saturating \(W\). Both cases prove the converse, and hence the theorem. \(\square\)

Using Hall’s Condition in an Assignment

To use the theorem directly, list the eligible tasks for each worker, then compute \(N(X)\) for worker subsets \(X\). If one subset has fewer neighboring tasks than workers, the assignment is impossible. If every subset passes the test, Hall’s theorem guarantees an assignment. For a small number of workers, the check can be made by listing all subsets; for larger problems, identifying a useful way to organize the subsets is often the main practical challenge.

Why the Subset Test Matters

Hall’s condition is a group-level test. Counting the choices of each worker separately checks only singleton subsets. That is necessary, but it is not sufficient: several workers may all depend on the same small set of tasks. The second example shows this precisely. Every worker has at least one eligible task, yet the two-worker set \(\{A,B\}\) has only one neighboring task.

Conversely, checking a few promising groups is not enough to establish that an assignment exists. The theorem requires the inequality for every subset of workers, including the whole set and the empty set. In the third example, the two-worker group \(\{A,B\}\) reaches equality, while subsets meeting both groups have a larger neighborhood. Both kinds of subsets matter.

In practice, Hall’s theorem separates feasibility from the act of writing down an assignment: once all subsets satisfy the condition, the theorem guarantees that a matching exists. A proposed assignment should still be checked by confirming that every worker receives an eligible task and that no task is repeated.