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

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

Stage: Under review

Links: PDF

Abstract: Walrasian Equilibrium (WE) may fail to exist when goods are indivis- ible. We propose the Complexity Compensating Equilibrium (CCE), in which prices render consumers’ budget problem instances computationally most difficult, so demands can become heterogeneous because agents apply different cognitive effort or are endowed with varying cognitive capability. We show that CCE can exist even where WE does not, and we derive and test its necessary conditions. In a controlled experiment, trade prices are high despite zero marginal cost on the supply side, and tend to locate con- sumers’ budget problem instance in regions of high computational difficulty. We further find that prices are highly volatile, forcing agents to repeatedly solve a relatively small NP-hard problem under severe time constraints. When WE exists, observed prices deviate significantly from it and final holdings imply markedly different earnings levels, rejecting WE in favor of CCE.

Keywords: indivisible goods, general equilibrium; computational complexity; Walrasian equilibrium; complexity compensating equilibrium

JEL codes: C62, C92, D51

Presented at: Society for Experimental Finance North America Regional Conference (Salt Lake City, 2027), 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)