Cost-sharing mechanisms for scheduling under general demand settings

We investigate cost-sharing mechanisms for scheduling cost-sharing games. We assume that the demand is general---that is, each player can be allocated one of several levels of service. We show how to design mechanisms for these games that are weakly group strategyproof, approximately budget-balanced, and approximately efficient, using approximation algorithms for the underlying scheduling problems. We consider scheduling cost-sharing games in single machine, parallel machine, and concurrent open shop environments.


European Journal of Operational Research. doi:10.1016/j.ejor.2011.09.030