A game mechanism for single machine sequencing with zero risk

• A game decision mechanism is suggested which allows clients to be involved in determining their positions in a processing sequence.
• An arbitrary equilibrium (EQ) can be found in pseudo-polynomial time, though the associated scheduling problem is strongly NP-hard in general.
• If cost functions are such that the problem possesses a FPTAS, it can be used to find an EQ.
• For certain cost functions, the social optimum is the only EQ and the social value of this EQ is at most n−1n−1 times the social optimum.

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.