Connection of two approaches to~the~Fisher~model

V. I. Shmyrev

Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 2, pp. 91-108.

Résumé

The article continues the author's research on the problem of finding equilibrium in economic exchange models. For the Fisher model, it was previously known that the equilibrium problem can be reduced to some optimization problem. This result was obtained by Gale and Eisenberg, while the final algorithms on this way were not found. The author proposed the original polyhedral complementarity approach, which generated an optimization problem of a different type. This approach made possible the development of finite algorithms for finding the equilibrium. So far, the equivalence of these two optimization problems has not been shown. However, it turned out that the dual problems obtained in a special way are equivalent. In this paper, a general scheme of duality for convex optimization problems is proposed. This scheme allows us to clarify the nature of duality and the relationship between the Gale–Eisenberg and the polyhedral complementarity approaches. Illustr. 1, bibliogr. 17.

Détail

Keywords: exchange model, economic equilibrium, optimization problem, complementarity, duality.
Mots-clés : simplex

Bibliographie

[1] Gale D., “The linear exchange model”, J. Math. Econ., 3:2 (1976), 205–209 | DOI | MR | Zbl

[2] Eaves B. C., “A finite algorithm for linear exchange model”, J. Math. Econ., 3:2 (1976), 197–203 | DOI | MR | Zbl

[3] V. I. Shmyrev, “On an approach to the determination of equilibrium in elementary exchange models”, Sov. Math. Dokl., 27:1 (1983), 230–233 | MR | Zbl

[4] V. I. Shmyrev, “An algorithm for the search of equilibrium in the linear exchange model”, Sib. Math. J., 26:2 (1985), 288–300 | DOI | MR | Zbl | Zbl

[5] V. I. Shmyrev, “A generalized linear exchange model”, J. Appl. Ind. Math., 2:1 (2008), 125–142 | DOI | MR | Zbl

[6] V. I. Shmyrev, “An algorithm for finding equilibrium in the linear exchange model with fixed budgets”, J. Appl. Ind. Math., 3:4 (2009), 505–518 | DOI | MR | Zbl

[7] Eisenberg E., Gale D., “Consensus of subjective probabilities: The pari-mutuel method”, Ann. Math. Stat., 30:1 (1959), 165–168 | DOI | MR | Zbl

[8] Devanur N. R., Papadimitriou C. H., Saberi A., Vazirani V. V., “Market equilibrium via a primal-dual algorithm for a convex program”, J. ACM, 55:5 (2008), 22, 18 pp. | DOI | MR | Zbl

[9] Shmyrev V. I., “An algorithmic approach for searching an equilibrium in fixed budget exchange models”, Russian contributions to game theory and equilibrium theory, Theory Decis. Libr., Ser. C, 39, Springer, Heidelberg, 2006, 217–235 | DOI | Zbl

[10] Birnbaum B., Devanur N. R., Xiao L., “Distributed algorithms via gradient descent for Fisher markets”, Proc. 12th ACM Conf. Electronic Commerce (San Jose, CA, USA, June 5–9, 2011), ACM, New York, 2011, 127–136 | DOI

[11] Cole R., Devanur N., Gkatzelis V., Faira K. J., Mai T., Vazirani V. V., Yazdanbod S., “Convex program duality, Fisher markets, and Nash social welfare”, Proc. 2017 ACM Conf. Economics and Computation (Cambridge, MA, USA, June 26–30, 2017), ACM, New York, 2017, 459–460 | DOI

[12] V. I. Shmyrev, “Duality in linear economic models of exchange”, Tr. Inst. Mat. Mekh., 26, no. 3, 2020, 258–274 (Russian) | MR

[13] Svaiter B. F., “A new duality theory for mathematical programming”, J. Math. Program. Oper. Res., 60:8–9 (2011), 1209–1231 | MR | Zbl

[14] Shmyrev V. I., “Polyhedral complementarity approach to equilibrium problem in linear exchange models”, Optimization algorithms — Examples, IntechOpen, London, 2018, 27–46

[15] J. B. Dennis, Mathematical Programming and Electrical Networks, MIT Press, Cambridge, MA, 1959 | MR | MR

[16] V. I. Shmyrev, Introduction to Mathematical Programming, Inst. Kompyut. Issled., M., 2002 (Russian)

[17] R. Rockafellar, Convex Analysis, Princeton Univ. Press, Princeton, 1970 | MR | Zbl