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 relatin g to their benefits from the rate of job submissions and their costs d ue 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 t o achieve ''optimal'' flow control, where the optimality depends on ar riving at an appropriate trade-off between delay and the job arrival r ate 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 th e users' private information, we propose an algorithm that converges t o 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 [1] has produced a flow control algorit hm that requires the queue manager to incur a potentially huge deficit ; this leads to several theoretical and practical problems.