Home > Research > Publications & Outputs > Auction based models for ticket allocation prob...


Text available via DOI:

View graph of relations

Auction based models for ticket allocation problem in IT service delivery industry

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paperpeer-review

Publication date7/07/2008
Host publication2008 IEEE International Conference on Services Computing
Number of pages8
ISBN (print)9780769532837
<mark>Original language</mark>English


In this paper, we study the service request (ticket) allocation problem which arises in every IT service delivery organization. We refer to this problem as Ticket Allocation Problem (TAP). We first show that TAP is an instance of the online scheduling problem on unrelated machines, which is known to be a hard problem. Next, we describe a baseline model, namely push model, that deals with the TAP. The push model is an industry wide standard and can be used with any known online scheduling algorithm for unrelated machines. To elaborate this further, we discuss a well known Generalized List Scheduling algorithm which can be used by the push model. We prove a bound for this algorithm's competitive ratio which beats all the known bounds. We show that push model suffers from an inherent inefficiency due to scheduler having incomplete and imprecise information regarding agents' proficiency. Finally, we show that if the scheduling algorithm used by the push model can be converted into a truthful auction mechanism then all the inefficiencies of the push model can be overcome. We refer to the resulting model as the pull model. To illustrate the idea, we map the Generalized List Scheduling algorithm into a truthful auction mechanism. Through simulation experiments, we show that the auction based pull model results in higher efficiency than the push model. © 2008 IEEE.