Welfare Lower Bounds and Strategyproofness in the Queueing Problem

We investigate the implications of welfare lower bounds together with queue-efficiency and strategyproofness in the context of the queueing problem. As a consequence, we provide alternative characterizations of the k-pivotal mechanisms (Mitra and Mutuswami [13]). First, we introduce the k-welfare lower bound, which ensures that no agent is worse off than the case where she is assigned to the kth position in the queue without any monetary transfer. For each k; we show that the k-pivotal mechanisms generate the minimal budget deficit in each queueing problem among all mechanisms satisfying queue-efficiency, strategyproofness and the k-welfare lower bound. Next, we consider a well-known welfare lower bound, the identical preferences lower bound and show that when there are odd number of agents, the k-pivotal mechanisms with k = (n+1)/2 generate the minimal budget deficit in each queueing problem among all mechanisms satisfying queue-efficiency, strategyproofness and the identical preferences lower bound.