A further development of an original approach to the equilibrium problem in a linear exchange model and its variations is presented. The conceptual basis of the approach is polyhedral complementarity. The original problem is reduced to a fixed point problem for a piecewise constant point-to-set mapping on the price simplex. For the model with fixed budgets (Fisher model), the emerging mapping is potential, and this provides a new reduction of the equilibrium problem to a pair of optimization problems. The problems are in duality similarly to linear programming problems. This reduction of the Fisher model differs from the well-known reduction of E. Eisenberg and D. Gale and allows a development of two finite algorithms for searching equilibrium prices. In this paper we present a new conceptually complete version of the approach. We give an explicit formulation of the dual variant of the obtained reduction for the Fisher model and its generalizations. The reduction of the equilibrium problem to an optimization problem is also obtained for the general exchange model with variable budgets.
Keywords: exchange model, economic equilibrium, fixed point, polyhedral complementarity, optimization problem, conjugate function, algorithm
Received October 18, 2019
Revised April 12, 2020
Accepted July 27, 2020
Funding Agency: This work was supported by the Russian Foundation for Basic Research (project no.~19-010-00910~А) and by the Programme for Fundamental Scientific Research of SB RAS No.~I.5.1 (project 0314-2019-0018)
Vadim Ivanovich Shmyrev, Dr. Phys.-Math. Sci., Sobolev Institute of Mathematics; Novosibirsk State University, Novosibirsk, 630990 Russia, e-mail: shvi@math.nsc.ru
REFERENCES
1. Shmyrev V.I. On an approach to the determination of equilibrium in elementary exchange models. Sov. Math. Dokl., 1983, vol. 27, no. 1, pp. 230–233.
2. Shmyrev V.I. The problem of polyhedral complementarity. Optimizatsiya, 1988, vol. 44(61), pp. 82–95 (in Russian).
3. Eaves B.C. A finite algorithm for the linear exchange model. Journal of Mathematical Economics, 1976, vol. 3, no. 2, pp. 197–203. doi: 10.1016/0304-4068(76)90028-8
4. Gale D. The linear exchange model. J. Math. Econom., 1976, vol. 3, no. 2, pp. 205–209. doi: 10.1016/0304-4068(76)90029-X
5. Shmyrev V.I. Polyhedral complementarity approach to equilibrium problem in linear exchange models. In: Optimization Algorithms: Examples, Jan Valdman (ed), London, United Kingdom: IntechOpen, 2018, pp. 27–46. doi: 10.5772/intechopen.77206
6. Shmyrev V.I. Polyhedral complementarity algorithms for finding equilibrium in linear models of competitive economics. Diskretn. Anal. Issled. Oper., 2014, vol. 21, no. 2, pp. 84–101 (in Russian).
7. Shmyrev V.I. Polyhedral Complementarity on a simplex. Potentiality of regular mappings. J. Appl. Indust. Math., 2018, vol. 12, no. 1, pp. 167–176. doi: 10.1134/S1990478918010155
8. Eisenberg E., Gale D. Consensus of subjective probabilities: The pari-mutuel method. Ann. Math. Statist., 1959, vol. 30, no. 1, pp. 165–168. doi: 10.1214/aoms/1177706369
9. Devanur N.R., Papadimitriou C.H., Saberi A., Vazirani V.V. Market equilibrium via a primal–dual algorithm for a convex program. Journal of the ACM (JACM), 2008, vol. 55, no. 5, art.-no. 22, 18 p. doi: 10.1145/1411509.1411512
10. Birnbaum B., Devanur N.R., Xiao L. Distributed algorithms via gradient descent for Fisher markets. In: Proc. 12th ACM Conf. on Electronic Commerce, N Y: ACM, 2011, pp. 127–136. doi: 10.1145/1993574.1993594
11. Lemke C.E. Bimatrix equilibrium points and mathematical programming. Management Science, 1965, vol. 11, no. 7, pp. 681–689. doi: 10.1287/mnsc.11.7.681
12. Adsul B., Babu C. S., Gang J., Mehta R., Sohoni M. A simplex-like algorithm for Fisher markets. In: Algorithmic Game Theory (SAGT 2010), S. Kontogiannis, E. Koutsoupias, P.G. Spirakis (eds), Berlin; Heidelberg: Springer, 2010, Lecture Notes in Computer Science, vol 6386, pp. 18–29. doi: 10.1007/978-3-642-16170-4_3
13. Garg J., Mehta R., Sohoni M., Vishnoi N. K. Towards polynomial simplex-like algorithms for market equilibria. In: Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia: SIAM, 2013, pp. 1226–1242. doi: 10.1137/1.9781611973105.89
14. Devanur N.R., Jain K., Mai T., Vazirani V.V., Yazdanbod S. New convex programs for Fisher’s market model and its generalizations [e-resource], 2016, 23 p. Available on https://arxiv.org/pdf/1603.01257.pdf .
15. Cole Richard, Devanur Nikhil, Gkatzelis Vasilis, Jain Kamal, Mai Tung, Vazirani Vijay V., Yazdanbod Sadra. Convex program duality, Fisher markets, and Nash social welfare. In: Proc. 18th ACM Conf. on Economics and Computation, 2017, Massachusets Institute of Technology, pp. 459–460. doi: 10.1145/3033274.3085109
16. Shmyrev V.I. Polyhedral complementarity and fixed points problem of decreasing regular mappings on simplex. In: Proc. VIII Inter. Conf. on Optimization Methods and Applications (OPTIMA-2017), Petrovac, Montrnegro, 2017, Yu.G. Evtushenko, M.Yu. Khachay, O.V. Khamisov, Yu.A. Kochetov, V.U. Malkova, M.A. Posypkin (eds), 2017, vol. 1987, pp. 511–516.
17. Shmyrev V.I. Vvedenie v matematicheskoe programmirovanie [Introduction to mathematical programming]. Moscow: Inst. Komp. Issl. Publ., 2002, 192 p.
18. Pontryagin L.S. Foundations of combinatorial topology. N Y: Dover Publ., 2015, 112 p. ISBN: 978-0-486-40685-5 . Original Russian text published in Pontryagin L.S. Osnovy kombinatornoi topologii, Moscow: Nauka Publ., 1986, 120 p.
19. Rockafellar R. Convex analysis. Princeton: Princeton University Press, 1970, 451 p. ISBN: 0691015864 . Translated to Russian under the title Vypuklyi analiz. Moscow: Mir Publ., 1973, 469 p.
20. Vazirani V.V. Spending constraint utilities, with applications to the adwords market. Math. Oper. Research, 2010, vol. 35, no. 2, pp. 458–478. doi: 10.1287/moor.1100.0450
Cite this article as: V.I. Shmyrev. Duality in linear economic models of exchange, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 3, pp. 258–274.
