Complexity of markets

Computation in economic mechanisms

What is the computational power of a market? What is the computational complexity of the work that markets do? Socialist calculation debate. Computational complexity and command-and-control-economics.

Classic: Cosma Shalizi: In Soviet Union, Optimization Problem Solves You. See also his notebook on Planned Economies.


Arora, Sanjeev, Boaz Barak, Markus Brunnermeier, and Rong Ge. 2011. β€œComputational Complexity and Information Asymmetry in Financial Products.” Communications of the ACM 54 (5): 101–7.
Arthur, W Brian. 1995. β€œComplexity in Economic and Financial Markets.” Complexity 1 (1): 20–25.
Aziz, Haris, PΓ©ter BirΓ³, Ronald de Haan, and Baharak Rastegari. 2019. β€œPareto Optimal Allocation Under Uncertain Preferences: Uncertainty Models, Algorithms, and Complexity.” Artificial Intelligence 276 (November): 57–78.
Aziz, Haris, Ioannis Caragiannis, Ayumi Igarashi, and Toby Walsh. 2021. β€œFair Allocation of Combinations of Indivisible Goods and Chores.” arXiv.
Aziz, Haris, and Bart de Keijzer. 2011. β€œComplexity of Coalition Structure Generation.” arXiv.
Bossaerts, Peter, Elizabeth Bowman, Felix Fattinger, Harvey Huang, Carsten Murawski, Anirudh Suthakar, Shireen Tang, and Nitin Yadav. 2020. β€œComputational Complexity and Asset Pricing.” SSRN Scholarly Paper ID 3475433. Rochester, NY: Social Science Research Network.
Bowles, Samuel. 2004. Microeconomics: Behavior, Institutions, and Evolution. Princeton University Press.
Bowles, Samuel, Alan Kirman, and Rajiv Sethi. 2017. β€œRetrospectives: Friedrich Hayek and the Market Algorithm.” Journal of Economic Perspectives 31 (3): 215–30.
Daskalakis, C., P. Goldberg, and C. Papadimitriou. 2009. β€œThe Complexity of Computing a Nash Equilibrium.” SIAM Journal on Computing 39 (January): 195–259.
Daskalakis, Constantinos, Alan Deckelbaum, and Christos Tzamos. 2012a. β€œOptimal Pricing Is Hard.” In Internet and Network Economics, edited by Paul W. Goldberg, 7695:298–308. Berlin, Heidelberg: Springer Berlin Heidelberg.
β€”β€”β€”. 2012b. β€œThe Complexity of Optimal Mechanism Design.” arXiv:1211.1703 [Cs], November.
Eremeev, A. V. 2017. β€œOn Computational Complexity of the Electric Power Flow Optimization Problem in Market Environment.” Journal of Applied and Industrial Mathematics 11 (4): 500–505.
Feigenbaum, J., D. Koller, and P. Shor. 1995. β€œA Game-Theoretic Classification of Interactive Complexity Classes.” In Proceedings of Tenth Annual IEEE Structure in Complexity Theory Conference, 1995, 227–37.
Gao, Yuan, and Christian Kroer. 2020. β€œFirst-Order Methods for Large-Scale Market Equilibrium Computation.” arXiv:2006.06747 [Cs, Math], June.
Gemp, Ian, Brian McWilliams, Claire Vernade, and Thore Graepel. 2020. β€œEigenGame: PCA as a Nash Equilibrium.” In.
Hayek, Friedrich A. 1945. β€œThe Use of Knowledge in Society.” The American Economic Review 35 (4): 519–30.
Ho, Yu-Chi, M. Kastner, and E. Wong. 1978. β€œTeams, Signaling, and Information Theory.” IEEE Transactions on Automatic Control 23 (2): 305–12.
Levine, Matt. 2016. β€œAre Index Funds Communist?”, August 24, 2016.
Maymin, Philip Z. 2011. β€œMarkets Are Efficient If and Only If P = NP.” Algorithmic Finance 1 (1): 1–11.
McLennan, Andrew. n.d. β€œThe Computational Complexity of Games and Markets: An Introduction for Economists,” 86.
Mcleod, Doug, Garry Emmerson, Robert Kohn, and Geoff Kingston (universit. 2008. β€œFinding the Invisible Hand: An Objective Model of Financial Markets.”
Mises, Ludwig von. 2016. Economic Calculation In the Socialist Commonwealth. Lulu Press, Inc.
Nisan, Noam. 2007. Algorithmic Game Theory. Cambridge ; New York: Cambridge University Press.
β€”β€”β€”. n.d. β€œAlgorithmic Mechanism Design,” 44.
Ohsawa, Shohei. 2021. β€œUnbiased Self-Play.” arXiv:2106.03007 [Cs, Econ, Stat], June.
Roughgarden, Tim, and Inbal Talgam-Cohen. 2019. β€œApproximately Optimal Mechanism Design.” Annual Review of Economics 11 (1): 355–81.
Shafer, Glenn, and Vladimir Vovk. 2001. β€œIntroduction: Probability and Finance as a Game.” In Probability and Finance: It’s Only a Game! Wiley-Interscience.
Smith, Jason. 2015. β€œInformation Transfer Economics: Information Equilibrium as an Economic Principle.” Information Transfer Economics (blog).
Spufford, Francis. 2012. Red Plenty. 1st edition. London: Faber Non Fiction.
Ye, Yinyu. 2008. β€œA Path to the Arrow–Debreu Competitive Market Equilibrium.” Mathematical Programming 111 (1-2): 315–48.

No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.