Skip to main content
SpringerLink
Log in

The complexity of resource allocation and price mechanisms under bounded rationality

  • Research Articles
  • Published:
Economic Theory Aims and scope Submit manuscript

Summary

We develop a framework for designing and evaluating the complexity of mechanisms that allocate resources in a distributed setting to agents or processors with bounded computational ability. We discuss several mechanisms and describe the construction of efficient price based mechanisms, which exploit the decentralized aspects of the problem. These price mechanisms are polynomial in the number of resources, precision of the solution, and the logarithm of the number of agents.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Arrow, K., Hurwicz, L.: Decentralization and computation in resource allocation. In: Pfouts, R. (ed.) Essays in economics and econometrics. Chapel Hill: University of North Carolina Press, 1960

    Google Scholar 

  2. Blum, L.: Lectures on a theory of computation and complexity over the reals (or an arbitrary ring). Technical Report TR-89-065, International Computer Science Institute, Perkeley, CA, December 1989

    Google Scholar 

  3. Blum, L., Shub, M., Smale, S.: On a theory of computation over the real numbers:NP-completeness, recursive functions, and universal machines. Bull. ACM21, 1–46 (1988)

    Google Scholar 

  4. Ecker, J. G., Kupfershmid, J.: The ellipsoid algorithm for nonlinear programming. Math. Prog.27, 83–106 (1983)

    Google Scholar 

  5. Ferguson, D. W., Nikolau, C., Yemini, Y.: Microeconomic algorithms for load balancing in distributed computer systems. Proceedings of the 8th International Conference on Distributed Computing Systems, 1988

  6. Friedman, E. J.: The complexity of allocating resources in parallel: upper and lower bounds. In: Pardalos, P. (ed.) Complexity in numerical optimization. Singapore: World Scientific 1993

    Google Scholar 

  7. Friedman, E. J.: A strongly polynomial algorithm for convex programs with combinatorial constraints and resource allocation. Technical report UCB/ERL/IGCT M92/6, Interdisciplinary Group on Coordination Theory, Electronics Research Laboratory, University of California, Berkeley, CA 94720, January 1992

    Google Scholar 

  8. Hochbaum, D. S.: Lower and upper bounds for the allocation problem and other nonlinear optimization problems. Manuscript, School of Business Administration and Industrial Engineering and Operations Research, University of California, Berkeley, CA 94720. September 1989, Revised December 1990

    Google Scholar 

  9. Huberman, B.: The ecology of computation. Amsterdam: North Holland 1988

    Google Scholar 

  10. Hurwicz, L.: The design of mechanisms for resource allocation. Am. Econ. Rev. 1–30 (1973)

  11. Hurwicz, L.: On informational decentralization and efficiency in resource allocation mechanism. In: Reiter, S. (ed.) Studies in mathematical economics. Washington D.C.: Mathematical Association of America 1986

    Google Scholar 

  12. Hurwicz, L.: On informationally decentralized systems. In: McGuire, C. B., Radner, R. (ed.) Decision and organization. Minneapolis: University of Minnesota Press 1986

    Google Scholar 

  13. Hurwicz, L.: On the dimensional requirements of informationally decentralized pareto satisfactory adjustment processes. In: Arrow, K. J., Hurwicz, L. (ed.) Studies in resource allocation processes. Cambridge, New York: Cambridge University Press 1977

    Google Scholar 

  14. Hurwicz, L., Marschak, T.: Discrete allocation mechanisms: dimensional requirements for resource-allocation mechanisms when the desired outcomes are unbounded. J. Complexity1, 264–303 (1985)

    Google Scholar 

  15. Ibaraki, T., Katoh, N.: Resource allocation problems: algorithmic approaches. MIT Press 1988

  16. Khachian, L. G.: A polynomial algorithm for linear programming. Sov. Math. Doklady20, 191–4 (1979)

    Google Scholar 

  17. Kurose, J. F., Simha, R.: A microeconomic approach to optimal resource allocation in distributed computer systems. IEEE Trans. Comp.38, 705–16 (1989)

    Google Scholar 

  18. Leighton, F. T.: Introduction to parallel algorithms and architectures. Morgan-Kaufman 1991

  19. Levin, A. Yu.: On an algorithm for minimizing convex functions. Sov. Maths.1, 286–90 (1965)

    Google Scholar 

  20. Luenberger, D. G.: Linear and nonlinear programming, 2nd edn. Reading, Massachusetts: Addison-Wesley Publishing Company 1984

    Google Scholar 

  21. Marschak, T. A.: Organizational design. In: Arrow, K. J., Intrilligator, M. D. (eds.) Handbook of mathematical economics. New York. North-Holland 1986

    Google Scholar 

  22. Megiddo, N.: Towards a genuinely polynomial algorithm for linear programming. Siam J. Comp.12, 347–59 (1983)

    Google Scholar 

  23. Mount, K., Reiter, S.: The existence of a locally stable dynamic process with a statically minimal message space. In: Groves, T., Radner, R., Reiter, S. (eds.) Information, incentives, and economic mechanisms: essays in honor of Leonid Hurwicz. Minneapolis: University of Minnesota Press 1987

    Google Scholar 

  24. Mount, K., Reiter, S.: The informational size of message spaces. J. Econ. Theory8, 161–192 (1974)

    Google Scholar 

  25. Mount, K., Reiter, S.: A model of computing with human agents 1990. Discussion Paper No. 890. Center for Mathematical Studies, J.L. Kellogg Graduate School of Management, Northwestern University, Evanston, Ilinois 60208

  26. Nemirovsky, A. S., Yudin, D. B.: Problem complexity and method efficiency in optimization. New York: Wiley 1983

    Google Scholar 

  27. Oren, S. S., Smith, S.: Critical mass and tariffs in electronics communication markets. Bell J. Econ.12, 467–487 (1981)

    Google Scholar 

  28. Papadimitriou, C. H., Steiglitz, K.: Combinatorial optimization: algorithms and complexity. Englewood Cliffs, New Jersey: Prentice-Hall, Inc. 1982

    Google Scholar 

  29. Radner, R.: The organization of decentralized information processing. Econometrica61, 1109–1146 (1993)

    Google Scholar 

  30. Rockafellar, R. T.: Convex analysis. Princeton, New Jersey: Princeton University Press 1970

    Google Scholar 

  31. Russell, S., Wefald, E.: Do the right thing: studies in limited rationality. Boston: MIT Press, 1991

    Google Scholar 

  32. Sanders, B.: An incentive compatible flow control algorithm for rate allocation in computer networks. IEEE Trans. Comp.37, 1062–72 (1988)

    Google Scholar 

  33. Sanders, B.: A private good/public good for optimal flow control of an m/m/1 queue. IEEE Trans. Autom. Contr.30, 1143–5 (1985)

    Google Scholar 

  34. Sapetnekar, S., Rao, V., Vaidya, P., Kang, S.: An exact solution for the transistor sizing problem for cmos circuits using convex optimization. Mimeo 1992

  35. Scarf, H.: Some examples of global instability of the competitive equilibria. Int. Econ. Rev.1, 157–72 (1960)

    Google Scholar 

  36. Shenker, S.: Efficient network allocations with selfish users. In: King, P. J. B., Mitrani, I., Pooley, R. J. (eds.) Performance '90, pp. 279–285. New York: North-Holland 1990

    Google Scholar 

  37. Simon, H. A.: Theories of bounded rationality. In: McGuire, C. B., Radner, R. (eds.) Decision and organization. Minneapolis: University of Minnesota Press 1986

    Google Scholar 

  38. Smale, S.: A convergent process of price adjustment and global newton methods. J. Math. Econ.3, 107–20 (1976)

    Google Scholar 

  39. Vaidya, P. M.: A new algorithm for minimizing convex functions over convex sets. In: 30th Annual Symposium on the Foundations of Computer Science, pp. 332–337. IEEE, October 1989

  40. Varian, H. R.: Microeconomic analysis. New York: Norton, W. W. 1978

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The Fuqua School of Business, Duke University, 27708-0120, Durham, NC, USA

    Eric J. Friedman

  2. Department of IEOR, University of California, 94720, Berkeley, CA, USA

    Shmuel S. Oren

Authors
  1. Eric J. Friedman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shmuel S. Oren
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

We thank Thomas Marschak and a anonymous referee for helpful suggestions. This research was been supported by National Science Foundation Grant IRI-8902813.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Friedman, E.J., Oren, S.S. The complexity of resource allocation and price mechanisms under bounded rationality. Econ Theory 6, 225–250 (1995). https://doi.org/10.1007/BF01212489

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01212489

Keywords

Search

Navigation