The accountable function: a new approach to scheduling problems

We study cooperative cost-sharing in scheduling problems where agents differ in job lengths but share identical waiting costs. While the optimistic and pessimistic cost functions are natural approaches to compute the waiting cost of a coalition, their symmetry - well established for queueing problems - breaks down for scheduling. In particular, the pessimistic Shapley value violates equity by rewarding longer jobs. To address this, we propose an alternative formulation, termed ``accountable cost" of serving a coalition. Under this, the coalitional members are served first, but they internalize the externality imposed on the non-coalitional members. We show that the accountable cost game is concave and the Shapley value of this game coincides with the decreasing serial rule, thereby restoring the lost symmetry. We also provide axiomatic characterizations of both the optimistic and accountable Shapley values, explore extensions to multi-server environments, and discuss connections with general sequencing problems. These results position the accountable function as a principled counterpart to the optimistic approach, unifying efficiency and fairness in the cooperative analysis of scheduling problems.