Reordering an existing queue

We consider the mechanism design problem of reordering an existing queue when waiting costs are unknown and processing times for jobs are identical. In contrast to the corresponding problem without an initial queue, budget balance (BB), outcome efficiency (OE), strategyproofness (SP), and individual rationality (IR) are incompatible. We investigate the implications of dropping BB and OE. Dropping BB yields no mechanism which never runs a budget deficit but allowing for a bound on the budget deficit yields positive results. Dropping OE yields only fixed-price trading or constant mechanisms when there are two agents but there are additional mechanisms when there are more agents. We identify a mechanism which is not a fixed-price trading mechanism and characterize its maximal level of ‘queue inefficiency’.