Distributing Awards Efficiently: More on King Solomon's Problem

We consider a multi-awards generalization of King Solomon's problem: $k$ identical and indivisible awards should be distributed among $n$ agents, $k<n$, with the top $k$ valuation agents receiving the awards. Agents have complete information about each others' valuations. Glazer and Ma (1989) analyzed the single-prize (i.e., $k=1$) version of this problem. We show that in the `more than two agents' problem the mechanism of Glazer and Ma admits inefficient equilibria and thus fails to solve Solomon's problem. So, first we modify their mechanism to rule out inefficient equilibria and implement efficient prize allocation in subgame perfect equilibrium when there are at least three agents. Then it is shown that a simple repeated application of our modified mechanism will distribute $k\;(>1)$ prizes efficiently in subgame perfect equilibria without any monetary transfers in equilibrium. Finally, in the multi-awards case we relax the complete information assumption and achieve implementation of efficient allocation by iterative elimination of weakly dominated strategies, using a generalization of Olszewski's (2003) mechanism