Prior-free online mechanisms for queueing with arrivals

摘要

Agents from a finite population arrive at various discrete times, and exit after they use a server for one period each. Each agent has a per-period cost of queueing, which constitutes his private information. Among direct mechanisms that areprior-free, i.e. independent of distributions of arrivals and costs, andonline, i.e. charge only those present in the system, we characterize the class of dynamically strategy-proof mechanisms with least total waiting cost. The budget is balanced eventually under a mild condition on the arrival sequence, while a canonical mechanism that achieves budget balance in each period is also characterized under a stronger condition.