A Hierarchical Quantized Auction for Fog Resources

In the emerging fog computing ecosystem, a fundamental problem is to allocate the available resources for computing and communication. Moreover, in many cases these resources have a natural hierarchical structure to them, e.g., allocating resources to network slices, which in turn are shared by a group of users. We consider auction-based approaches for allocating resources in such an environment so as to account for diverse user incentives. The well-known Vickrey-Clarke-Groves(VCG) mechanism provides a strong solution to the incentive issue, but also has the well-known drawback of requiring an excessive amount of information for a wireless system. Recent work has shown that, when allocating a single divisible resource, this information can be reduced via quantization while maintaining VCG's incentive properties. Here, we build on this approach and apply it instead to a hierarchical setting, in which users are divided into groups. Each group is subject to a local resource constraint as well as a global resource constraint across all groups. We specify a distributed quantized mechanism for such a setting that has the same incentive properties as VCG. We characterize the communication overhead and the worst-case efficiency loss in this mechanism. We also consider how to assign constraints on groups for a given sum constraint as well as for a case where the sum-constraint can be varied at a given per unit cost.