Dynamic Mechanisms with Verification

We consider a principal who allocates an indivisible object among a finite number of agents who arrive on-line, each of whom prefers to have the object than not. Each agent has access to private information about the principal's payoff if he receives the object. The decision to allocate the object to an agent must be made upon arrival of an agent and is irreversible. There are no monetary transfers but he principal can inspect agents' reports at a cost and punish them. A novelty of this paper is a reformulation of this dynamic problem as a compact linear program. Using the formulation we characterize the form of the optimal mechanism and reduce the dynamic version of the inspection problem with identical distributions to an instance of the secretary problem with one fewer secretary and a modified value distribution. This reduction also allows us to derive a prophet inequality for the dynamic version of the inspection problem