How computational complexity can restore general equilibrium in markets with indivisible goods

Authors: Peter Bossaerts, Konstantinos Ioannidis, Robert Woods, Nitin Yadan

Stage: Cambridge Working Papers in Economics

Abstract: We study market equilibrium with indivisible goods and tight budget constraints, where a traditional Walrasian Equilibrium (WE) may fail to exist. We introduce the Complexity Compensating Equilibrium (CCE), in which prices endogenously render the budget problem computationally difficult, inducing heterogeneous demands even with homogeneous preferences. The equilibrium region is the set of price configurations that maximize computational difficulty while satisfying market clearing. In a controlled experiment, trading prices consistently fall within this region. Final holdings generate markedly different utility levels across participants — contradicting WE's equalization of utilities. Where WE exists, we reject it in favor of CCE.

Keywords: general equilibrium, indivisibilities, cognitive effort, NP-hard, complexity compensating equilibrium, walrasian equilibrium, market experiment

JEL codes: C62, C92, D51

Presented at: 77^th Econometric Society European Meeting (Dublin, 2026), Economic Science Association European Meeting (Brno, 2025), 2^nd Workshop on Computational Complexity and Economic Decision Making (Cambridge, 2025), 75^th Allied Social Science Associations Annual Meeting (San Francisco 2025), University of Pittsburgh Economics Seminar (2025), Carnegie Mellon University Economics Seminar (2025), 1^st Annual Conference of the Network of the UK-Based Experimental and Behavioural Economists (Leicester, 2024), University of Vienna Behavioral/Experimental Seminar (Vienna, 2024), 14^th Society for Experimental Finance Conference (Stavanger, 2024)