Approximate Random Allocation Mechanisms

We generalize the scope of random allocation mechanisms, in which the mechanism first identifies a feasible “expected allocation” and then implements it by randomizing over nearby feasible integer allocations. The previous literature has shown that the cases in which this is possible are sharply limited. We show that if some of the feasibility constraints can be treated as goals rather than hard constraints, then, subject to weak conditions that we identify, any expected allocation that satisfies all the constraints and goals can be implemented by randomizing among nearby integer allocations that satisfy all the hard constraints exactly and the goals approximately. By defining ex post utilities as goals, we are able to improve the ex post properties of several classic assignment mechanisms, such as the random serial dictatorship. We use the same approach to prove the existence of ϵ-competitive equilibrium in large markets with indivisible items and feasibility constraints.