On the Existence of Competitive Equilibrium with Chores

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We study the chore division problem in the classic Arrow-Debreu exchange setting, where a set of agents want to divide their divisible chores (bads) to minimize their disutilities (costs). We assume that agents have linear disutility functions. Like the setting with goods, a division based on competitive equilibrium is regarded as one of the best mechanisms for bads. Equilibrium existence for goods has been extensively studied, resulting in a simple, polynomial-time verifiable, necessary and sufficient condition. However, dividing bads has not received a similar extensive study even though it is as relevant as dividing goods in day-to-day life. In this paper, we show that the problem of checking whether an equilibrium exists in chore division is NP-complete, which is in sharp contrast to the case of goods. Further, we derive a simple, polynomial-time verifiable, sufficient condition for existence. Our fixed-point formulation to show existence makes novel use of both Kakutani and Brouwer fixed-point theorems, the latter nested inside the former, to avoid the undefined demand issue specific to bads.

Original languageEnglish (US)
Title of host publication13th Innovations in Theoretical Computer Science Conference, ITCS 2022
EditorsMark Braverman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772174
StatePublished - Jan 1 2022
Event13th Innovations in Theoretical Computer Science Conference, ITCS 2022 - Berkeley, United States
Duration: Jan 31 2022Feb 3 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference13th Innovations in Theoretical Computer Science Conference, ITCS 2022
Country/TerritoryUnited States


  • Competitive equilibrium
  • Fair division
  • Fixed point theorems

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'On the Existence of Competitive Equilibrium with Chores'. Together they form a unique fingerprint.

Cite this