How Computational Complexity Can Restore General Equilibrium in Markets with Indivisible Goods

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.