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

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

Stage: Under review at Econometrica

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), University of San Francisco Economics Seminar (San Francisco, 2025), Tepper School of Business Economics Seminar (Pittsburgh, 2025), University of Pittsburgh Behavioral/Experimental Seminar (Pittsburgh, 2025), University of Exeter Behavioural and Experimental Economics Seminar (Exeter, 2024), 1^st Annual Conference of UK-based Behavioural and Experimental Economists (Leicester, 2024), WU Vienna Economics Seminar (Vienna, 2024)