Optimal flow control of an M/M/1 queue with a balanced budget

The following problem is considered. There are several users who send jobs to an M/M/1 queue and have privately observed information relating to their benefits from the rate of job submissions and their costs due to waiting in the queue. Each user´s benefits and costs are unknown to the queue manager and to other users. The manager´s objective is to achieve “optimal” flow control, where the optimality depends on arriving at an appropriate trade-off between delay and the job arrival rate assigned to each user: the allocations should be such that no user can be made better off by a reallocation without hurting at least one other user. Since the optimality calculation requires knowledge of the users´ private information, we propose an algorithm that converges to the optimum, while inducing users to reveal information relating to their benefits and costs truthfully, and balances the manager´s budget. Earlier work on this problem has produced a flow control algorithm that requires the queue manager to incur a potentially huge deficit; this leads to several theoretical and practical problems