Optimal budget-balanced ranking mechanisms to assign identical objects

Strategy-proof and budget-balanced ranking mechanisms assign q units of an object to n agents. The efficiency loss is the largest ratio of surplus loss to efficient surplus, over all profiles of nonnegative valuations. The smallest efficiency loss is achieved by the following allocation rule: for $$q\le \lfloor \frac{n}{2}\rfloor $$ q ≤ ⌊ n 2 ⌋ , assign one object to each of the $$q-1$$ q - 1 top ranked agents, a substantial probability of one object to the qth ranked agent, and distribute the remaining probability equally to a group of agents ranked behind the qth agent; for $$q>\lfloor \frac{n}{2}\rfloor $$ q > ⌊ n 2 ⌋ , assign a small probability to the $$(q+1)$$ ( q + 1 ) th ranked agent, an equally substantial probability to a group of agents ranked immediately before the $$(q+1)$$ ( q + 1 ) th agent, and one object to each of the agent ranked before the group. In both cases, the size of the “equal group” depends on q and n. Suppose $$\frac{q}{n}$$ q n is fixed and $$\frac{q}{n}\ne \frac{1}{2}$$ q n ≠ 1 2 , then as q and n increase, the smallest efficiency loss tends to zero exponentially. Participation is voluntary in the above mechanisms only when q is smaller than a threshold that depends on n.