Simple Task-Assignment Problem

Question

I have this simple 'assignment' problem:

We have a set of agents $A = \{a_1, a_2, \dotso, a_n\}$ and set of tasks $T= \{t_1, t_2, \dotso, t_m\}$. Note that $m$ is not necessarily equal to $n$. Unlike the general assignment formulation in Wikipedia, a task $t_c$ can only be assigned to an agent based on the task's preferred agents $ta_c \subseteq A$. For example, if we have $ta_1= \{a_1, a_3\}$, that means that task $t_1$ can only be assigned to either agents $a_1$ or $a_3$. Now, each agent $t_d$ has a quota $q_d$ where $q_d$ is positive integer. This means that $a_d$ must be assigned with $q_d$ number of tasks.

The Problem

Given above and a set of quota $\{q_1, q_2, \dotso, q_n\}$, is there an assignment of tasks to agents such that all agents meet their respective quota $q$. Note that it is not necessarily that all tasks be assigned to an agent.

Possible Solution

I have tried reformulating this problem in terms of a bipartite graph $G(A, T, E = \cup ta_c)$ and expressed as a form of matching problem where given a matching $M$, a vertex agent $a_d\in A$ is matched up to $q_d$ times or is incident to $q_d$ edges in $M$ but the vertices in $T$ is incident to only one edge in $M$. Not really like the usual matching problem which requires that the edges in $M$ are pairwise non-adjacent.

However, it was suggested by someone (from cstheory, he knows who he is) that I could actually work this out as a maximum matching problem, by replicating an agent $a_d$ into $q_d$ vertices and 'conceptually' treat them as different vertices as input to the matching algorithm. The set of edges $E$ is also modified accordingly. Call the modified graph as $G'$

It is possible to have more than 1 maximum matchings from graph $G'$. Now, if I understand this correctly, I still have to check each of the resulting maximum matchings and see that at least one of them satisfies the $qouta$ constraint of each $agent$ to actually provide the solution to the problem.

Now, I want to prove that not finding one maximum matching $M$ $\in$ set of all maximum matchings of the graph $G'$ that satisfies the $qouta$ constraint of the problem guarantees that there really exists no solution to the problem instance, otherwise a solution exist which is $M$.

I want to show that this algorithm always give correct result.

Question

Can you share to me some intuition on how I might go to show this?

Answer 1

As I stated on the CSTheory post, this is solved via maximum matching. The following should give enough intuition to show that each agent $a_i$ has a $q_i$-matching iff a transformed graph $G'$ has a matching. First, construct the graph $G$. Now, for each agent $a_i$ and quota $q_i$, make a new graph $G'$ that has $q_i$ copies of $a_i$. That is to say, if agent $a_i$ has quota $q_i = 3$, make 2 new nodes $a_i', a_i''$ that have the same tasks as $a_0$.

Here is an illustration to help. Supposed we have the complete bipartite graph $K_{2,3}$ where agent $q_1 = 2, q_2 = 1$.

Original graph $G$, and modified graph $G'$:

We see that agent $a_1$ has two copies in the new graph $G'$, while agent $a_2$ maintains just his lone copy. Solving for the maximum matching in $G'$ and then merging all copies of an agent to the original and you will have your best possible assignment. Since the edges are unweighted, one possible solution is (and merged solution):