Abstract
We provide the first strongly polynomial time exact combinatorial algorithm to compute Fisher equilibrium for the case when utility functions do not satisfy the Gross substitutability property. The motivation for this comes from the work of Kelly, Maulloo, and Tan [15] and Kelly and Vazirani [16] on rate control in communication networks. We consider a tree like network in which root is the source and all the leaf nodes are the sinks. Each sink has got a fixed amount of money which it can use to buy the capacities of the edges in the network. The edges of the network sell their capacities at certain prices. The objective of each edge is to fix a price which can fetch the maximum money for it and the objective of each sink is to buy capacities on edges in such a way that it can facilitate the sink to pull maximum flow from the source. In this problem, the edges and the sinks play precisely the role of sellers and buyers, respectively, in the Fisher’s market model. The utility of a buyer (or sink) takes the form of Leontief function which is known for not satisfying Gross substitutability property. We develop an O(m 3) exact combinatorial algorithm for computing equilibrium prices of the edges. The time taken by our algorithm is independent of the values of sink money and edge capacities. A corollary of our algorithm is that equilibrium prices and flows are rational numbers. Although there are algorithms to solve this problem but they are all based on convex programming techniques. To the best of our knowledge, ours is the first strongly polynomial time exact combinatorial algorithm for computing equilibrium prices of Fisher model under the case when buyers’ utility functions do not satisfy Gross substitutability property.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arrow, K., Debreu, G.: Existence of an equilibrium for a competitive economy. Econometrica 22, 265–290 (1954)
Codenotti, B., Varadarajan, K.: Efficient computation of equilibrium prices for markets with leontief utilities. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 371–382. Springer, Heidelberg (2004)
Deng, X., Papadimitriou, C.H., Safra, S.: On the complexity of equilibria. In: STOC 2002 (2002)
Devanur, N.R., Papadimitriou, C.H., Saberi, A., Vazirani, V.V.: Market equilibrium via a primal-dual-type algorithm. In: 43rd Symposium on Foundations of Computer Science (FOCS 2002), November 2002, pp. 389–395 (2002)
Devanur, N.R., Vazirani, V.V.: An improved approximation scheme for the computing arrow-debreu prices in the linear case. In: Proceedings of Foundations of Software Technology and Theoretical Computer Science, 2003 (2002)
Eisenberg, E.: Aggregation of utility functions. Management Science 7(4), 337–350 (1961)
Eisenberg, E., Gale, D.: Consensus of subjective probabilities: The pari-mutuel method. Annals of Mathematical Statistics 30, 165–168 (1959)
Garg, R., Kapoor, S.: Auction algorithms for market equilibrium. In: STOC (2004)
Garg, R., Kapoor, S.: Auction algorithms for market equilibrium. In: Proceedings of the 36th Annual ACM Symposium on the Theory of Computing (2004)
Garg, R., Kapoor, S., Vazirani, V.: An auction-based market equilibrium algorithms for the separable gross substitutability case. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol. 3122, pp. 128–138. Springer, Heidelberg (2004)
Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of ACM 42, 1115–1145 (1995)
Jain, K., Mahdian, M., Saberi, A.: Approximating market equilibrium. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol. 2764, pp. 98–108. Springer, Heidelberg (2003)
Jain, K.: A polynomial time algorithm for computing the arrow-debreu market equilibrium for linear utilities. In: FOCS (2004)
Jain, K., Vazirani, V.V., Ye, Y.: Market equilibria for homothetic, quasi-concave utilities and economies of scale in production. In: Proceedings, 16th Annual ACM-SIAM Symposium on Discrete Algorithms (2005)
Kelly, F.P., Maulloo, A.K., Tan, D.K.H.: Rate control in communication networks. Journal of Operational Research Society 49, 237–252 (1998)
Kelly, F.P., Vazirani, V.V.: Rate control as a market equilibrium (2003) (in preparation)
Papadimitriou, C.H.: Algorithms, games, and the Internet. In: ACM STOC 2001, Hersonissos, Crete, Greece, July 6-8 (2001)
Scarf, H.: The computation of economic equilibria (with collaboration of t. hansen). In: Cowles Foundation Monograph No. 24. Yale University Press, New Haven (1973)
Walras, L.: Éléments d’économie politique pure ou théorie de la richesse sociale (Elements of Pure Economics, or The Theory of Social Wealth), Lausanne, Paris (1874)
Ye, Y.: A path to arrow-debreu competitive market equilibrium (2004) (preprint)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Garg, D., Jain, K., Talwar, K., Vazirani, V.V. (2005). A Primal-Dual Algorithm for Computing Fisher Equilibrium in the Absence of Gross Substitutability Property. In: Deng, X., Ye, Y. (eds) Internet and Network Economics. WINE 2005. Lecture Notes in Computer Science, vol 3828. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11600930_4
Download citation
DOI: https://doi.org/10.1007/11600930_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30900-0
Online ISBN: 978-3-540-32293-1
eBook Packages: Computer ScienceComputer Science (R0)