Reordering an existing queue

We investigate the problem of reordering agents starting from an existing queue. First, we introduce four important axioms of the problem, budget balance (BB), outcome efficiency (OE), strategyproofness (SP), and individual rationality (IR). Unfortunately, it is easy to show that these four axioms are incompatible in the current setup. Given this negative result, we examine the consequences of relaxing BB, OE and SP, one at a time. Our results are as follows: (i) There is no mechanism satisfying OE, SP and IR which runs a nonnegative surplus at all profiles. (ii) When there are two agents, the only non-trivial mechanisms satisfying BB, SP and IR are Fixed price trading mechanisms but there are additional mechanisms when there are more than two agents. We identify an intuitive mechanism which we call the median price exchange mechanism and characterize its maximal level of inefficiency. (iii) By weakening SP to `one-sided' strategyproofness, we identify two mechanisms, the buyers' mechanism and the sellers' mech- anism, and characterize them on the basis of independence axioms.