I have the following question to answer:

A fraternity has n student members. In Fall’18, m courses are being offered and for each course i, some subset $S_i$ of the fraternity members are taking the course together. They have come up with the following cheating scheme: For each course i, some member in the set $S_i$ will be responsible for doing all the work in that course, and other members of $S_i$ will simply copy the work. Since people would rather not work, they want the responsibility be divided as fairly as possible. Your task in this problem is to give an algorithm to do this efficiently. The fairness criterion is the following: Say that person $p$ is in some $k$ of the sets, which have sizes $n_1, n_2, . . . , n_k$, respectively. Person p should really have to be responsible for $1/n_1 + 1/n_2 + ...1/n_k$ courses, because this is the amount of resource that this person effectively uses. Of course this number may not be an integer, so let’s round it up to an integer. The fairness criterion is simply that she should not be responsible for more than these many courses. For example, say that there are two courses, and Alice and Bob are taking course 1 together, and Alice, Carl, and Dilbert are taking course 2 together. Alice’s fair cost would be$1/2 + 1/3 = 1$ So Alice being responsible for both the courses would not be fair. Any solution except that one is fair.

• Prove that there always exists a fair solution.

• Give a polynomial-time algorithm for computing a fair solution from the sets $S_i$ [Hint: Try to model the problem using network flow in such a way that part 1 falls out directly from the integrality theorem for network flow, and part 2 just follows from the fact that we can solve max flow in polynomial time. So, it all boils down to coming up with the right flow graph to model the problem.]

I am having trouble modeling the flow. I know that the basic concept of the proof of a fair solution is using the property that having integer capacities means that your maximum flow will be an integer. However, I am not sure of how I can use this to solve this problem.

Hints on how to get to a solution would be much appreciated.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.