# Complexity of markets

Computation in economic mechanisms

February 20, 2021 — May 13, 2021

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.

## 1 References

Arora, Barak, Brunnermeier, et al. 2011. “Computational Complexity and Information Asymmetry in Financial Products.”

*Communications of the ACM*.
Arthur. 1995. “Complexity in Economic and Financial Markets.”

*Complexity*.
Aziz, Biró, de Haan, et al. 2019. “Pareto Optimal Allocation Under Uncertain Preferences: Uncertainty Models, Algorithms, and Complexity.”

*Artificial Intelligence*.
Aziz, Caragiannis, Igarashi, et al. 2021. “Fair Allocation of Combinations of Indivisible Goods and Chores.”

Aziz, and de Keijzer. 2011. “Complexity of Coalition Structure Generation.”

Bossaerts, Bowman, Fattinger, et al. 2020. “Computational Complexity and Asset Pricing.” SSRN Scholarly Paper ID 3475433.

Bowles. 2004.

*Microeconomics: Behavior, Institutions, and Evolution*.
Bowles, Kirman, and Sethi. 2017. “Retrospectives: Friedrich Hayek and the Market Algorithm.”

*Journal of Economic Perspectives*.
Daskalakis, Constantinos, Deckelbaum, and Tzamos. 2012a. “Optimal Pricing Is Hard.” In

*Internet and Network Economics*.
———. 2012b. “The Complexity of Optimal Mechanism Design.”

*arXiv:1211.1703 [Cs]*.
Daskalakis, C., Goldberg, and Papadimitriou. 2009. “The Complexity of Computing a Nash Equilibrium.”

*SIAM Journal on Computing*.
Eremeev. 2017. “On Computational Complexity of the Electric Power Flow Optimization Problem in Market Environment.”

*Journal of Applied and Industrial Mathematics*.
Feigenbaum, Koller, and Shor. 1995. “A Game-Theoretic Classification of Interactive Complexity Classes.” In

*Proceedings of Tenth Annual IEEE Structure in Complexity Theory Conference, 1995*.
Gao, and Kroer. 2020. “First-Order Methods for Large-Scale Market Equilibrium Computation.”

*arXiv:2006.06747 [Cs, Math]*.
Gemp, McWilliams, Vernade, et al. 2020. “EigenGame: PCA as a Nash Equilibrium.” In.

Hayek. 1945. “The Use of Knowledge in Society.”

*The American Economic Review*.
Ho, Kastner, and Wong. 1978. “Teams, Signaling, and Information Theory.”

*IEEE Transactions on Automatic Control*.
Levine. 2016. “Are Index Funds Communist?”

*Bloomberg.com*.
Maymin. 2011. “Markets Are Efficient If and Only If P = NP.”

*Algorithmic Finance*.
McLennan. n.d. “The Computational Complexity of Games and Markets: An Introduction for Economists.”

Mcleod, Emmerson, Kohn, et al. 2008. “Finding the Invisible Hand: An Objective Model of Financial Markets.”

Nisan. 2007.

*Algorithmic Game Theory*.
———. n.d. “Algorithmic Mechanism Design.”

Ohsawa. 2021. “Unbiased Self-Play.”

*arXiv:2106.03007 [Cs, Econ, Stat]*.
Roughgarden, and Talgam-Cohen. 2019. “Approximately Optimal Mechanism Design.”

*Annual Review of Economics*.
Shafer, and Vovk. 2001. “Introduction: Probability and Finance as a Game.” In

*Probability and Finance: It’s Only a Game!*
Smith. 2015. “Information Transfer Economics: Information Equilibrium as an Economic Principle.”

*Information Transfer Economics*(blog).
Spufford. 2012.

*Red Plenty*.
von Mises. 2016.

*Economic Calculation In the Socialist Commonwealth*.
Ye. 2008. “A Path to the Arrow–Debreu Competitive Market Equilibrium.”

*Mathematical Programming*.