Computation of Fisher–Gale Equilibrium by Auction

Journal of the Operations Research Society of China - 2018
Yurii Nesterov1, Vladimir Shikhman2
1Center for Operations Research and Econometrics, Catholic University of Louvain, 1348, Louvain-la-Neuve, Belgium
2Department of Mathematics, Technische Universität Chemnitz, 09126, Chemnitz, Germany

Tóm tắt

AbstractWe study the Fisher model of a competitive market from the algorithmic perspective. For that, the related convex optimization problem due to Gale and Eisenberg (Ann Math Stat 30(1):165–168, 1959) is used. The latter problem is known to yield a Fisher equilibrium under some structural assumptions on consumers’ utilities, e.g., homogeneity of degree 1, homotheticity. Our goal is to examine applicability of the convex optimization framework by departing from these traditional assumptions. We just assume the concavity of consumers’ utility functions. For this case, we suggest a novel concept of Fisher–Gale equilibrium by using consumers’ utility prices. The prices of utility transfer the utility of consumption bundle to a common numéraire. We develop a subgradient-type algorithm from Convex Analysis to compute a Fisher–Gale equilibrium via Gale’s approach. In order to decentralize prices, we additionally implement the auction design, i.e., consumers settle and update their individual prices and producers sell at the highest offer price. Our price adjustment is based on a tatonnement procedure, i.e., the prices change proportionally to consumers’ individual excess supplies. Historical averages of consumption are shown to clear the market of goods. Our algorithm is justified by a global rate of convergence. In the worst case, the number of price updates needed to achieve an $$\varepsilon $$ ε -tolerance is proportional to $$\frac{1}{\varepsilon ^2}$$ 1 ε 2 .

Từ khóa


Tài liệu tham khảo

Brainard, W.C., Scarf, H.: How to compute equilibrium prices in 1891. Am. J. Econ. Sociol. 64(1), 57–83 (2005)

Eisenberg, E., Gale, D.: Consensus of subjective probabilities: the Pari–Mutuel method. Ann. Math. Stat. 30(1), 165–168 (1959)

Eisenberg, E.: Aggregation of utility functions. Manag. Sci. 7(4), 337–350 (1961)

Jain, K., Vazirani, V., Ye., Y.: Market equilibria for homothetic, quasi-concave utilities and economies of scale in production. In: Proceeding SODA’05, pp. 63–71 (2005)

Chen, L., Ye, Y., Zhang, J.: A note on equilibrium pricing as convex optimization. In: Internet and Network Economics, Lecture Notes in Computer Science, vol. 4858, pp. 7–16 (2007)

Gale, D.: The Theory of Linear Economic Models. McGraw Hill, New York (1960)

Devanur, N.R., Papadimitriou, Ch.H., Saberi, A., Vazirani, V.V.: Market equilibrium via a primal–dual algorithm for a convex program. J. ACM 55(5), 1–18 (2008)

Ye, Y.: A path to the Arrow–Debreu competitive market equilibrium. Math. Program. 111(1–2), 315–348 (2008)

Codenotti, B., Mccune, B., Varadarajan, V.: Market equilibrium via the excess demand function. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 74–83. ACM Press, New York (2005). https://doi.org/10.1145/1060590.1060601

Garg, R., Kapoor, S.: Auction algorithms for market equilibrium. Math. Oper. Res. 31(4), 714–729 (2006)

Birnbaum, B., Devanur, N., Xiao, L.: Distributed algorithms via gradient descent for fisher markets. In: ACM Conference on Electronic Commerce, pp. 127–136 (2011)

Fleischer, L., Garg, R., Kapoor, S., Khandekar, R., Saberi, A.: A fast and simple algorithm for computing market equilibria. In: Internet and Network Economics, Lecture Notes in Computer Science, vol. 5385, pp. 19–30 (2008)

Milgrom, P.: Putting auction theory to work: the simultaneous ascending auction. J. Polit. Econ. 108(2), 245–272 (2000)

Codenotti, B., Pemmaraju, S., Varadarajan, V.: The computation of market equilibria. Acm Sigact News 35(4), 23–37 (2004)

Vazirani, V.: Combinatorial algorithms for market equilibria. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V. (eds.) Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)

Nesterov, Yu., Shikhman, V.: Quasi-monotone subgradient methods for nonsmooth convex minimization. J. Optim. Theory Appl. 165(3), 917–940 (2015)

Cheung, Y.K., Cole, R., Devanur, N.: Tatonnement beyond gross substitutes? Gradient descent to the rescue. STOC 13, 191–200 (2013)

Nesterov, Yu.: Introductory Lectures on Convex Optimization. Kluwer, Boston (2004)

Mas-Colell, A., Whinston, M.D., Green, J.R.: Microeconomic Theory. Oxford University Press, New York (1995)

Rubinstein, A.: Equilibrium in the jungle. Econ. J. 117(522), 883–896 (2007)

Schotter, A.: Microeconomics: a modern approach. South-Western Cengage Learning, Mason (2009)

Mont, O.: Consumption and ecological economics: towards sustainability. In: Pertsova, C.C. (ed.) Ecological Economics Research Trends, pp. 13–44. Nova Sciences Publishers, Hauppauge, NY (2007)

Marschak, T., Selten, R.: General Equilibrium with Price-Making Firms. Springer, Berlin (1974)

Negishi, T.: Welfare economics and existence of an equilibrium for a competitive economy. Metroeconomica 12(2–3), 92–97 (1960)

Mantel, R.R.: The welfare adjustment process: its stability properties. Int. Econ. Rev. 12(3), 415–439 (1971)

Mullainathan, S., Thaler, R.H.: Behavioral economics. In: International Encyclopedia of Social and Behavioral Sciences, Smelser, N.J., Baltes, P.B. (Editors-in-Chief), pp. 1094–1100. Elsevier, Amsterdam (2001)

Cherchye, L., Demuynck, T., De Rock, B.: Is utility transferable? A revealed preference analysis. Theor. Econ. 10(1), 51–65 (2015)

Miyake, M.: On the applicability of Marshallian partial-equilibrium analysis. Math. Soc. Sci. 52(2), 176–196 (2006)

Vives, X.: Small income effects: a Marshallian theory of consumer surplus and downward sloping demand curves. Rev. Econ. Stud. 54, 87–103 (1987)

Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)

Zălinescu, C.: Convex Analysis in General Vector Spaces. World Scientific, Singapore (2002)

Rosen, J.B.: Existence and uniqueness of equilibrium points for concave $$n$$-person games. Econometrica 31(3), 520–534 (1965)

Seel, N.M. (ed.): Incremental learning. In: Encyclopedia of the Sciences of Learning, Springer, Berlin (2012)

Thông tin
Thông tin xuất bản

Journal of the Operations Research Society of China

Thông tin tác giả