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

Peter Bossaerts, Konstantinos Ioannidis, Rob Woods and Nitin Yadav

Cambridge Working Papers in Economics from Faculty of Economics, University of Cambridge

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; Markets Experiment (search for similar items in EconPapers)
JEL-codes: C62 C92 D51 (search for similar items in EconPapers)
Date: 2026-01-02
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.econ.cam.ac.uk/sites/default/files/pub ... pe-pdfs/cwpe2603.pdf

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cam:camdae:2603

Access Statistics for this paper

More papers in Cambridge Working Papers in Economics from Faculty of Economics, University of Cambridge
Bibliographic data for series maintained by Jake Dyer ().