When Dividing Mixed Manna Is Easier Than Dividing Goods: Competitive Equilibria with a Constant Number of Chores

Jugal Garg, Martin Hoefer, Peter McGlaughlin, Marco Schmalhofer

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

Abstract

We study markets with mixed manna, where m divisible goods and chores shall be divided among n agents to obtain a competitive equilibrium. Equilibrium allocations are known to satisfy many fairness and efficiency conditions. While a lot of recent work in fair division is restricted to linear utilities, we focus on a substantial generalization to separable piecewise-linear and concave (SPLC) utilities. We first derive polynomial-time algorithms for markets with a constant number of items or a constant number of agents. Our main result is a polynomial-time algorithm for instances with a constant number of chores (as well as any number of goods and agents) under the condition that chores dominate the utility of the agents. Interestingly, this stands in contrast to the case when the goods dominate the agents utility in equilibrium, where the problem is known to be PPAD-hard even without chores.

Original languageEnglish (US)
Title of host publicationAlgorithmic Game Theory - 14th International Symposium, SAGT 2021, Proceedings
EditorsIoannis Caragiannis, Kristoffer Arnsfelt Hansen
PublisherSpringer
Pages329-344
Number of pages16
ISBN (Print)9783030859466
DOIs
StatePublished - 2021
Event14th International Symposium on Algorithmic Game Theory, SAGT 2021 - Virtual, Online
Duration: Sep 21 2021Sep 24 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12885 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Symposium on Algorithmic Game Theory, SAGT 2021
CityVirtual, Online
Period9/21/219/24/21

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'When Dividing Mixed Manna Is Easier Than Dividing Goods: Competitive Equilibria with a Constant Number of Chores'. Together they form a unique fingerprint.

Cite this