The Fair Resource Allocation Problem with Submodular Constraints

The problem of allocating a limited resource to relevant activities in a fair manner on the basis of a certain general objective function has recently been considered by N. Katoh, T. Ibaraki, and H. Mine. We generalize Katoh, Ibaraki, and Mine's problem to the one with a feasible region expressed by a submodular function and give an efficient solution algorithm. The proposed algorithm is of the same complexity as and simpler than Katoh, Ibaraki, and Mine's when specialized to their problem.