On the Complexity of Chore Division

We study the proportional chore division problem where a protocol wants to divide an undesirable object, called chore, among n different players. The goal is to find an allocation such that the cost of the chore assigned to each player be at most 1/n of the total cost. This problem is the dual variant of the cake cutting problem in which we want to allocate a desirable object. Edmonds and Pruhs showed that any protocol for the proportional cake cutting must use at least Omega(n log n) queries in the worst case, however, finding a lower bound for the proportional chore division remained an interesting open problem. We show that chore division and cake cutting problems are closely related to each other and provide an Omega(n log n) lower bound for chore division.