Optimization Online


Cost-sharing mechanisms for scheduling under general demand settings

Sindhura Balireddi (ramaba***at***amazon.com)
Nelson A. Uhan (nuhan***at***purdue.edu)

Abstract: 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.

Keywords: game theory; cost sharing; scheduling; combinatorial optimization

Category 1: Other Topics (Game Theory )

Category 2: Applications -- OR and Management Sciences (Scheduling )

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


Entry Submitted: 11/26/2010
Entry Accepted: 11/26/2010
Entry Last Modified: 10/29/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society