Optimal budget-balanced ranking mechanisms to assign identical objects
2019
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 \), assign one object to each of the \(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 \), assign a small probability to the \((q+1)\)th ranked agent, an equally substantial probability to a group of agents ranked immediately before the \((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}\) is fixed and \(\frac{q}{n}\ne \frac{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.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
25
References
1
Citations
NaN
KQI