A game mechanism for single machine sequencing with zero risk

A problem is studied in which several non-cooperating clients compete for earlier execution of their jobs in a processing sequence of a single service provider in order to minimize job completion time costs. The clients can move their jobs earlier in a given sequence. They are assumed not to take a risky decision that can decrease their utility function. A game mechanism is suggested such that each client has no incentive to claim false cost and a social criterion is addressed, which is the minimum total cost of all clients. Algorithmic aspects of this mechanism are analyzed such as relations between the values of game equilibria and the social optimum, the computational complexity of finding a game equilibrium and the values of the price of anarchy and the price of stability.