Incentive Compatible Two-Tiered Resource Allocation without Money

We consider a resource allocation problem with two types of goods: a plentiful good that all agents have approximately the same value for, and a scarce good that agents value differently (imagine, e.g., job requests on an ordinary computing cluster versus a restricted high-performance cluster). A social planner seeks to allocate the scarce resource to the agent who values it most. We depart from the usual mechanism design approach by assuming monetary payments are infeasible, and instead use lotteries and the threat of nonallocation to elicit truthful value reporting. Adapting ideas developed in the context of revenue redistribution, we examine whether there exist allocation rules yielding expected welfare that-in ex post equilibrium-exceeds that of a baseline that randomly assigns the scarce resource, and find that for i.i.d. values the answer is yes only if the value distribution is heavy-tailed. For a variant of the problem where there is a residual claimant for the plentiful good, we identify a mechanism that obtains welfare converging to that of perfectly efficient allocation as the population size grows.