×

Competitive equilibrium and trading networks: a network flow approach. (English) Zbl 1470.91156

Summary: Under full substitutability of preferences, it is known that a competitive equilibrium exists in trading networks and is equivalent to (chain) stable outcomes. In this paper, we formulate the problem of finding an efficient set of trades as a generalized submodular flow problem in a suitable network. Existence of a competitive equilibrium and its equivalence with the seemingly weaker notion of stability follow directly from the optimality conditions of the flow problem. Our formulation enables us to perform comparative statics with respect to the number of buyers, sellers, and trades. For instance, we establish that if a new buyer is added to the economy, at an equilibrium the prices of all existing trades increase. In addition, we give a polynomial time algorithm for finding competitive equilibria in trading networks and testing (chain) stability.

MSC:

91B60 Trade models
90B10 Deterministic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Upper Saddle River, NJ).Google Scholar · Zbl 1201.90001
[2] Ausubel LM (2006) An efficient dynamic auction for heterogeneous commodities. Amer. Econom. Rev. 96(3):602-629.Crossref, Google Scholar · doi:10.1257/aer.96.3.602
[3] Barthold TA (1994) Issues in the design of environmental excise taxes. J. Econom. Perspective 8(1):133-151.Crossref, Google Scholar · doi:10.1257/jep.8.1.133
[4] Blum Y, Roth AE, Rothblum UG (1997) Vacancy chains and equilibration in senior-level labor markets. J. Econom. Theory 76(2):362-411.Crossref, Google Scholar · Zbl 0892.90047 · doi:10.1006/jeth.1997.2307
[5] Danilov V, Koshevoy G, Murota K (2001) Discrete convexity and equilibria in economies with indivisible goods and money. Math. Social Sci. 41(3):251-273.Crossref, Google Scholar · Zbl 1004.91052 · doi:10.1016/S0165-4896(00)00071-8
[6] Danilov V, Koshevoy GA, Lang C (2003) Gross substitution, discrete convexity, and submodularity. Discrete Appl. Math. 131(2):283-298.Crossref, Google Scholar · Zbl 1030.90096 · doi:10.1016/S0166-218X(02)00456-0
[7] Fleiner T, Jankó Z, Tamura A, Teytelboym A (2018) Trading networks with bilateral contracts. Working paper, Harvard Business School, Cambridge.Google Scholar
[8] Fujishige S, Yang Z (2003) A note on Kelso and Crawford’s gross substitutes condition. Math. Oper. Res. 28(3):463-469.Link, Google Scholar · Zbl 1082.91054
[9] Granot F, Veinott AF (1985) Substitutes, complements and ripples in network flows. Math. Oper. Res. 10(3):471-497.Link, Google Scholar · Zbl 0577.90024
[10] Gul F, Stacchetti E (1999) Walrasian equilibrium with gross substitutes. J. Econom. Theory 87(1):95-124.Crossref, Google Scholar · Zbl 0998.91010 · doi:10.1006/jeth.1999.2531
[11] Gul F, Stacchetti E (2000) The English auction with differentiated commodities. J. Econom. Theory 92(1):66-95.Crossref, Google Scholar · Zbl 0962.91027 · doi:10.1006/jeth.1999.2580
[12] Hatfield JW, Milgrom P (2005) Matching with contracts. Amer. Econom. Rev. 95(4):913-935.Crossref, Google Scholar · doi:10.1257/0002828054825466
[13] Hatfield JW, Kominers SD, Nichifor A, Ostrovsky M, Westkamp A (2013) Stability and competitive equilibrium in trading networks. J. Political Econom. 121(5):966-1005.Crossref, Google Scholar · doi:10.1086/673402
[14] Hatfield JW, Kominers SD, Nichifor A, Ostrovsky M, Westkamp A (2019a) Chain stability in trading networks. Proc. 2018 ACM Conf. Econom. Comput. (ACM, New York), 617-618.Google Scholar
[15] Hatfield JW, Kominers SD, Nichifor A, Ostrovsky M, Westkamp A (2019b) Full substitutability. Theory Econom. 14(4):1535-1590.Crossref, Google Scholar · Zbl 1448.91124 · doi:10.3982/TE3240
[16] Ikebe YT, Tamura A (2015) Stability in supply chain networks: An approach by discrete convex analysis. J. Oper. Res. Soc. Japan 58(3):271-290.Google Scholar · Zbl 1339.90056
[17] Ikebe YT, Sekiguchi Y, Shioura A, Tamura A (2015) Stability and competitive equilibria in multi-unit trading networks with discrete concave utility functions. Japan J. Industrial Appl. Math. 32(2):373-410.Crossref, Google Scholar · Zbl 1330.91130 · doi:10.1007/s13160-015-0175-7
[18] Iwata S, Moriguchi S, Murota K (2005) A capacity scaling algorithm for M-convex submodular flow. Math. Programming 103(1):181-202.Crossref, Google Scholar · Zbl 1079.90112 · doi:10.1007/s10107-004-0562-3
[19] Kelso AS, Crawford V (1982) Job matching, coalition formation, and gross substitutes. Econometrica 50(6):1483-1504.Crossref, Google Scholar · Zbl 0503.90019 · doi:10.2307/1913392
[20] King M, Tarbush B, Teytelboym A (2019) Targeted carbon tax reforms. Eur. Econom. Rev. 119(C):526-547.Google Scholar
[21] Leme RP (2017) Gross substitutability: An algorithmic survey. Games Econom. Behav. 106:294-316.Crossref, Google Scholar · Zbl 1414.91268 · doi:10.1016/j.geb.2017.10.016
[22] Moriguchi S, Murota K (2003) Capacity scaling algorithm for scalable M-convex submodular flow problems. Optimal Methods Software 18(2):207-218.Crossref, Google Scholar · Zbl 1176.90509 · doi:10.1080/1055678031000099178
[23] Murota K (1999) Submodular flow problem with a nonseparable cost function. Combinatorica 19(1):87-109.Crossref, Google Scholar · Zbl 0947.90119 · doi:10.1007/s004930050047
[24] Murota K (2003) Discrete Convex Analysis: Monographs on Discrete Mathematics and Applications 10 (Society for Industrial and Applied Mathematics, Philadelphia, PA).Crossref, Google Scholar · Zbl 1029.90055 · doi:10.1137/1.9780898718508
[25] Murota K (2016) Discrete convex analysis: A tool for economics and game theory. J. Mechanism Institution Design 1(1):151-273.Crossref, Google Scholar · doi:10.22574/jmid.2016.12.005
[26] Murota K, Tamura A (2003a) Application of M-convex submodular flow problem to mathematical economics. Japan J. Industrial Appl. Math. 20(3):257-277.Crossref, Google Scholar · Zbl 1092.91058 · doi:10.1007/BF03167422
[27] Murota K, Tamura A (2003b) New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities. Discrete Appl. Math. 131(2):495-512.Crossref, Google Scholar · Zbl 1094.90023 · doi:10.1016/S0166-218X(02)00469-9
[28] Ostrovsky M (2008) Stability in supply chain networks. Amer. Econom. Rev. 98(3):897-923.Crossref, Google Scholar · doi:10.1257/aer.98.3.897
[29] Shapley LS, Shubik M (1971) The assignment game I: The core. Internat. J. Game Theory 1(1):111-130.Crossref, Google Scholar · Zbl 0236.90078 · doi:10.1007/BF01753437
[30] Shioura A (2004) Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem. Discrete Appl. Math. 134(1-3):303-316.Crossref, Google Scholar · Zbl 1038.90059 · doi:10.1016/S0166-218X(03)00255-5
[31] Shioura A, Tamura A (2015) Gross substitutes condition and discrete concavity for multi-unit valuations: A survey. J. Oper. Res. Soc. Japan 58(1):61-103.Crossref, Google Scholar · Zbl 1367.91114 · doi:10.15807/jorsj.58.61
[32] Sun N, Yang Z (2006) Equilibria and indivisibilities: Gross substitutes and complements. Econometrica 74(5):1385-1402.Crossref, Google Scholar · Zbl 1138.91535 · doi:10.1111/j.1468-0262.2006.00708.x
[33] Sun N, Yang Z (2009) A double-track adjustment process for discrete markets with substitutes and complements. Econometrica 77(3):933-952.Crossref, Google Scholar · Zbl 1180.91157 · doi:10.3982/ECTA6514
[34] Sun N, Yang Z (2014) An efficient and incentive compatible dynamic auction for multiple complements. J. Political Econom. 122(2):422-466.Crossref, Google Scholar · doi:10.1086/674550
[35] Wasserman J, Manning WG, Newhouse JP, Winkler JD (1991) The effects of excise taxes and regulations on cigarette smoking. J. Health Econom. 10(1):43-64.Crossref, Google Scholar · doi:10.1016/0167-6296(91)90016-G
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.