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 in settings 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. Complexity induces heterogeneous demands even among agents with homogeneous preferences, as individuals allocate varying levels of cognitive effort. We define the equilibrium region as the set of price configurations that satisfy the necessary economic and computational conditions for equilibrium to exist. In this region, price configurations maximize the difficulty of the budget problem in addition to satisfying market clearing conditions. We evaluate the predictions of CCE through a controlled market experiment. We find that trading prices consistently force the budget problem to the equilibrium region. Further supporting and central to the CCE framework, the equilibrium bundles of goods generate markedly different utility levels across agents. This outcome contradicts a core feature of WE, namely, the equalization of utilities. In a setting where it exists, we reject WE on both prices and utilities, in favour of CCE.

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

JEL codes: C62, C92, D51

Presented at: 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)