A Dynamic VCG Mechanism for Random Allocation Spaces

We construct a dynamic version of the VCG pivot mechanism applicable to private value environments in which the allocation space in each period is random. A key characteristic of this setting is that while the allocations chosen by the coordinator in each stage are based on the actual realization of the random set of feasible allocations, the agent's reports in each step are made prior to this realization. This adds an additional layer to the problem, as players reporting their type now will take into account the distributional characteristics of the feasible allocation sets. We consider a modified social welfare function, in which "the public", regarded as a non-player, also receives utility from allocation decisions. For both the finite and the infinite horizon case, we construct mechanisms that satisfy a suitable notion of incentive compatibility and individual rationality and are weak budget balanced. Finally, we outline how our mechanisms may be applied to the problem of dynamically allocating random goods to a group of players that have private valuations for different item bundles.