Fair cost-sharing methods for scheduling jobs on parallel machines

We consider the problem of sharing the cost of scheduling n jobs on m parallel machines among a set of agents. In our setting, each agent owns exactly one job and the cost is given by the makespan of the computed assignment. We focus on α-budget-balanced cross-monotonic cost-sharing methods since they guarantee the two substantial mechanism properties α  -budget-balance and group-strategyproofness and provide fair cost-shares. For identical jobs on related machines and for arbitrary jobs on identical machines, we give (m+1)/(2m)(m+1)/(2m)-budget-balanced cross-monotonic cost-sharing methods and show that this is the best approximation possible. As our major result, we prove that the approximation factor for cross-monotonic cost-sharing methods is unbounded for arbitrary jobs and related machines. We therefore develop a cost-sharing method in the (m+1)/(2m)(m+1)/(2m)-core, a weaker but also fair solution concept.