2026-07-24T01:20:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15637 2024-03-06T10:55:49Z ddc:004 open_access

On the Existence of Competitive Equilibrium with Chores Chaudhury, Bhaskar Ray Garg, Jugal McGlaughlin, Peter Mehta, Ruta Fair Division Competitive Equilibrium Fixed Point Theorems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bhaskar Ray Chaudhury and Jugal Garg and Peter McGlaughlin and Ruta Mehta 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.41 urn:nbn:de:0030-drops-156378 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.41 eng https://creativecommons.org/licenses/by/4.0/legalcode