Search

Suppose identical jobs need to be processed by a single processor. Processing is carried out one job after the other, in batches, and jobs are released only when their entire batch is done. Each job is held by an agent, who tries to minimize costs. The cost of an individual job is linear in two terms: a congestion cost, dependent on the size of the batch, and a lateness cost, dependent also on the number of jobs preceding the batch. The agents need to decide on the sequential index of the batch they ascribe to. This decision problem is stated as a non-cooperative game, with applications both in ride sharing and in queues in which the server must never be idle. We derive its (mixed) symmetric equilibrium, which always exists, and its pure non-symmetric equilibrium, when it exists. The corresponding social optimization problem is solved as well, leading, in the mixed symmetric case, to an explicit formula for the price of anarchy. [ABSTRACT FROM AUTHOR]