The Communication Complexity of Efficient Allocation Problems

Abstract

We analyze the communication burden of surplus-maximizing allocations. We study both the continuous and discrete models of communication, measuring its burden with the dimensionality of the message space and the number of transmitted bits, respectively. In both cases, we offer a lower bound on the amount of com-munication. This bound is applied to the problem of allocating L heterogeneous objects among N agents, whose valuations are (i) unrestricted, (ii) submodular, or (iii) homogeneous in objects. In cases (i) and (ii), efficiency requires exponential communication in L. Furthermore, in case (i), polynomial communication in L cannot ensure a higher surplus than selling all objects as a bundle. On the other hand, in case (iii), exact efficiency requires the transmission of L numbers, but can be approximated arbitrarily closely using only O(log L) bits. When a Walrasian equilibrium with per-item prices exists, efficiency is achieved with deterministic communication that is polynomial in L.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 47 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.