The communication requirements of efficient allocations and supporting prices

The communication requirements of efficient allocations and supporting prices

Noam Nisan a, and Ilya Segal b.


Journal of Economic Theory Volume 129, Issue 1, July 2006, Pages 192-224

Abstract

We show that any communication finding a value-maximizing allocation in a private-information economy must also discover supporting prices (in general personalized and nonlinear). In particular, to allocate L indivisible items between two agents, a price must be revealed for each of the 2L-1 bundles. We prove that all monotonic prices for an agent must be used, hence exponential communication in L is needed. Furthermore, exponential communication is needed just to ensure a higher share of surplus than that realized by auctioning all items as a bundle, or even a higher expected surplus (for some probability distribution over valuations). When the utilities are submodular, efficiency still requires exponential communication (and fully polynomial approximation is impossible). When the items are identical, arbitrarily good approximation is obtained with exponentially less communication than exact efficiency.

Keywords: Communication complexity; Message space dimension; Preference elicitation; Informational efficiency of prices; Combinatorial auctions; Submodular valuations; Substitutable items; Homogenous items; Approximation; Distributional complexity

JEL classification codes: C61; D02; D44

References
H. Abelson, Lower bounds on information transfer in distributed computations, J. Assoc. Comput. Mach. 27 (1980), pp. 384–392. MathSciNet Full Text via CrossRef View Record in Scopus Cited By in Scopus (8)
N. Alon, Y. Matias and M. Szegedy, The space complexity of approximating the frequency moments, J. Comput. System Sci. 58 (1999), p. 137. Abstract Abstract + References PDF (171 K) View Record in Scopus Cited By in Scopus (122)
L. Ausubel, An efficient dynamic auction for heterogeneous commodities, Mimeo, 2002.
L. Ausubel and P. Milgrom, Ascending auctions with package bidding, Frontiers Theoret. Econ. 1 (2002).
L. Babai, P. Frankl, J. Simon, Complexity classes in communication complexity theory, Proc. FOCS (1986) 337–347 .
J. Banks, J. Ledyard and D. Porter, Allocating uncertain and unresponsive resources: an experimental approach, RAND J. Econ. 20 (1989), pp. 1–25. Full Text via CrossRef View Record in Scopus Cited By in Scopus (58)
S. Bikhchandani and J.W. Mamer, Competitive equilibrium in an exchange economy with indivisibilities, J. Econ. Theory 74 (1997), pp. 385–413. Abstract Abstract + References PDF (2519 K) MathSciNet View Record in Scopus Cited By in Scopus (54)
S. Bikhchandani and J. Ostroy, The package assignment model, J. Econ. Theory 107 (2002), pp. 377–406. Abstract Abstract + References PDF (201 K) View Record in Scopus Cited By in Scopus (34)
S. Bikhchandani, R. Vohra, S. de Vries and J. Schummer, Linear programming and Vickrey auctions. In: B. Dietrich and R. Vohra, Editors, Mathematics of the Internet: E-Auction and Markets, Springer, Berlin, New York (2002).
X. Calsamiglia, Decentralized resource allocation and increasing returns, J. Econ. Theory 14 (1977), pp. 262–283. MathSciNet
G.E. Edgar, Measure, Topology, and Fractal Geometry, Springer, Berlin, New York (1990).
J. Feigenbaum, A. Krishnamurthy, R. Sami and S. Shenker, Hardness results for multicast cost sharing, Theoret. Comput. Sci. 304 (2003), pp. 215–236. Abstract Abstract + References PDF (308 K) View Record in Scopus Cited By in Scopus (22)
F. Gul and E. Stacchetti, Walrasian equilibrium with gross substitutes, J. Econ. Theory 87 (1999), pp. 95–124. Abstract Abstract + References PDF (220 K) MathSciNet View Record in Scopus Cited By in Scopus (60)
F. Gul and E. Stacchetti, The english auction with differentiated commodities, J. Econ. Theory 92 (2000), pp. 66–95. Abstract Abstract + References PDF (202 K) View Record in Scopus Cited By in Scopus (32)
F. Hayek, The use of knowledge in society, Amer. Econ. Rev. 35 (1945), pp. 519–530.
R. Holzman, N. Kfir-Dahav, D. Monderer and M. Tennenholtz, Bundling equilibrium in combinatorial auctions, Games Econ. Behav. 47 (2004), pp. 104–123. Abstract Abstract + References PDF (264 K) View Record in Scopus Cited By in Scopus (18)
B. Hudson and T. Sandholm, Effectiveness of query types and policies for preference elicitation in combinatorial auctions, Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS) New York, 19–23 July (2004), pp. 386–393.
L. Hurwicz, On the dimensional requirements of informationally decentralized Pareto-satisfactory processes. In: K.J. Arrow and L. Hurwicz, Editors, Studies in Resource Allocation Processes, Cambridge University Press, New York (1977), pp. 413–424.
L. Hurwicz and T. Marschak, Finite allocation mechanisms: approximate Walrasian versus approximate direct revelation, Econ. Theory 21 (2003), pp. 545–572. Full Text via CrossRef View Record in Scopus Cited By in Scopus (1)
L. Hurwicz and T. Marschak, Comparing finite mechanisms, Econ. Theory 21 (2003), pp. 783–841. Full Text via CrossRef View Record in Scopus Cited By in Scopus (1)
J.S. Jordan, The competitive allocation process is informationally efficient uniquely, J. Econ. Theory 28 (1982), pp. 1–18. Abstract Full Text + Links PDF (964 K) MathSciNet
H. Karloff, Linear Programming, Birkhäuser Verlag, Basel (1991).
A.S. Kelso Jr. and V.P. Crawford, Job matching, coalition formation and gross substitutes, Econometrica 50 (1982), pp. 1483–1504. Full Text via CrossRef
A.D. Korshunov, O Chisle Monotonnykh Bulevykh Funktsi*i, Problemy Kibernetiki 38 (1981), pp. 5–108 (in Russian).
E. Kushilevitz and N. Nisan, Communication Complexity, Cambridge University Press, Cambridge (1997).
A. Kwasnica, J. Ledyard, D. Porter, C. DeMartini, A new and improved design for multi-object iterative auctions, Management Sci., forthcoming.
S. Lahaie, D. Parkes, Applying learning algorithms to preference elicitation in combinatorial auctions, Working paper, Harvard University, 2004.
B. Lehmann, D. Lehmann and N. Nisan, Combinatorial auctions with decreasing marginal utilities, Proceedings of the Third ACM Conference on Electronic Commerce ACM Press, New York (2001), pp. 18–28.
D. Lehmann, L. O’Callaghan and Y. Shoham, Truth revelation in approximately efficient combinatorial auctions, J. Assoc. Comput. Mach. 49 (2002), pp. 577–602. Full Text via CrossRef View Record in Scopus Cited By in Scopus (92)
Z.-Q. Luo, J.N. Tsitsiklis, Communication complexity of algebraic computation, Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, 1991, pp. 758–765.
T. Marschak, On economies of scope in communication, Econ. Design 2 (1996), pp. 1–30.
J. Marschak and R. Radner, Economic Theory of Teams, Yale University Press, New Haven (1972).
A. Mas-Colell, Efficiency and decentralization in the pure theory of public goods, Quart. J. Econ. 94 (1980), pp. 625–641. Full Text via CrossRef
P. Milgrom, Putting auction theory to work: the simultaneous ascending auction, J. Polit. Economy 108 (2000), pp. 245–272. Full Text via CrossRef View Record in Scopus Cited By in Scopus (78)
K. Mount and S. Reiter, The information size of message spaces, J. Econ. Theory 28 (1974), pp. 1–18.
D.C. Parkes, Ibundle: an efficient ascending price bundle auction, Proceedings of the First ACM Conference on Electronic Commerce (1999), pp. 148–157.
D.C. Parkes, Price-based information certificates for minimal-revelation combinatorial auctions, in: J. Padget, et al. (Eds.), Agent-mediated Electronic Commerce-Designing Mechanisms and Systems: Revised Papers from the AAMAS 2002 Workshop on Agent Mediated Electronic Commerce (Lecture Notes in Computer Science), Springer, Berlin, New York, 2002, pp. 103–122.
D.C. Parkes, L. Ungar, An ascending-price generalized Vickrey auction, Working paper, Harvard University, 2002.
S. Reichelstein, Incentive compatibility and informational requirements, J. Econ. Theory 34 (1984), pp. 32–51. Abstract Full Text + Links PDF (911 K) MathSciNet
M.H. Rothkhof, A. Pekeč and R.M. Harstad, Computationally manageable combinatorial auctions, Management Sci. 44 (1998), pp. 1131–1147.
T. Sandholm, S. Suri, A. Gilpin, D. Levine, Cabob: a fast optimal algorithm for combinatorial auctions, 17th International Joint Conference on Artificial Intelligence, Morgan Kaufmann, 2001.
F. Sato, On the informational size of message spaces for resource allocation processes in economies with public goods, J. Econ. Theory 24 (1981), pp. 48–69. Abstract Full Text + Links PDF (1214 K) MathSciNet
C.E. Shannon, A mathematical theory of communication, Bell System Tech. J. 27 (1948) 379–423 , 623–656.
G. Tian, A unique informationally efficient allocation mechanism in economies with consumption externalities, Internat. Econ. Rev. 45 (2004), pp. 79–111. Full Text via CrossRef View Record in Scopus Cited By in Scopus (5)
T. Van Zandt, Decentralized information processing in the theory of organizations, in: Murat Sertel (Ed.), Contemporary Economic Issues, Vol. 4: Economic Design and Behavior, MacMillan Press Ltd., London, 1999, pp. 125–160.
V.V. Vazirani, Approximation Algorithms, Springer, Berlin, New York (2001).
R. Vohra and S. de Vries, Combinatorial auctions: a survey, INFORMS J. Comput. 15 (2003), pp. 284–309.
M. Walker, On the informational size of message spaces, J. Econ. Theory 15 (1977), pp. 366–375. Abstract Full Text + Links PDF (565 K) MathSciNet
A.C.-C. Yao, Some complexity questions related to distributive computing, 34th Annual ACM Symposium on Theory of Computing, 1979, pp. 209–213.
E. Zurel, N. Nisan, An efficient approximate allocation algorithm for combinatorial auctions, ACM Conference on Electronic Commerce, 2001.
An earlier version of this paper was circulated under the title “The Communication Complexity of Efficient Allocation Problems.”Corresponding author. Fax: +1 650 725 5702.