Consider a bipartite graph of vertices of people $P_1,P_2,\dots,P_p$ with edges connected to vertices of tasks tasks $T_1,T_2,\dots,T_t$. An edge from $P_i$ to $T_j$ means that the person $P_i$ can do the task $T_j$. In our scenario, each person can perform the same number of tasks, say $l$ tasks, i.e., the degree of each person's vertex is $l$. Also, assume that each task can be performed by $r$ people, i.e., the degree of each task's vertex is $r$.
To that end, I have used a construction such that people $P_1,P_2,\dots,P_p$ can be partitioned into $r$ disjoint and equal-cardinality groups $G_1,G_2,\dots,G_r$ such that the following conditions hold
- Any pair of people from the same group have no task in common, i.e., no task they can both perform.
- Any pair of people from different groups have exactly one task in common, i.e., one task they can both perform.
- The people in a group can collectively perform all tasks $T_1,T_2,\dots,T_t$.
I have used Mutually Orthogonal Latin squares for the above construction, however I will skip the details since I think it may distract from the question; to briefly mention it, groups correspond to Latin squares, people correspond to the symbols and tasks correspond to coordinates $(x,y)$ of the square grid. Note that the above construction uses exactly $r$ groups which is consistent with the fact that each task can be performed by $r$ people among $P_1,P_2,\dots,P_p$.
Now suppose that $r$ is odd and that each task is considered complete if it has performed by at least half of the people who are capable of doing it, i.e., from $(r+1)/2$ people. My problem is the following
If you can employ up to $q$ people what is the maximum number of tasks can they complete?
This resembles a bipartite matching problem. However, in this case matching the maximum number of task vertices with people vertices is not enough. For a task to be completed it needs to be matched to at least $(r+1)/2$ people's vertices, so we have one minimum degree constraint for that. Also, we cannot employ for than $q$ people. Can you pinpoint me to sources of a relevant problem? Is there a bipartite matching algorithm which considers degree constraints?
My end goal is to find a closed-form expression for that maximum number of tasks we can complete.
