Optimal allocations with capacity constrained verification

Abstract

A principal has $m$ identical objects to allocate among a group of $n$ agents. Objects are desirable and the principal's value of assigning an object to an agent is the agent's private information. The principal can verify up to $k$ agents, where $k<m$, thereby perfectly learning the types of those verified. We find the mechanism that maximizes the principal's expected utility when no monetary transfers are available. In this mechanism, an agent receives an object if (i) his type is above a cutoff and among the $m$ highest types, (ii) his type is above some lower cutoff but among the $k$ highest types, or (iii) he receives an object in a lottery that allocates the remaining objects randomly.