Computing competitive equilibria with mixed manna

Jugal Garg, Peter McGlaughlin

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

Abstract

Fair division is the problem of allocating a set of items among a set of agents in a fair and efficient way. It arises naturally in a wide range of real-life settings. Competitive equilibrium (CE) is a central solution concept in economics to study markets, and due to its remarkable fairness and efficiency properties (e.g., envy-freeness, proportionality, core stability, Pareto optimality), it is also one of the most preferred mechanisms for fair division even though there is no money involved. The vast majority of work in fair division focuses on the case of disposable goods, which all agents like or can throw away at no cost. In this paper, we consider the case of mixed manna under linear utilities where some items are positive goods liked by all agents, some are bads (chores) that no one likes, and remaining some agents like and others dislike. The recent work of Bogomolnaia et al. [13] initiated the study of CE in mixed manna. They establish that a CE always exists and maintains all the nice properties found in the case of all goods. However, computing a CE of mixed manna is genuinely harder than in the case of all goods due to the non-convex and disconnected nature of the CE set. Our main result is a polynomial-time algorithm for computing a CE of mixed manna when the number of agents or items is constant.

Original languageEnglish (US)
Title of host publicationProceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020
EditorsBo An, Amal El Fallah Seghrouchni, Gita Sukthankar
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages420-428
Number of pages9
ISBN (Electronic)9781450375184
StatePublished - 2020
Event19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020 - Virtual, Auckland, New Zealand
Duration: May 19 2020 → …

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume2020-May
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Conference

Conference19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020
CountryNew Zealand
CityVirtual, Auckland
Period5/19/20 → …

Keywords

  • Competitive equilibrium
  • Fair division
  • Mixed manna

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'Computing competitive equilibria with mixed manna'. Together they form a unique fingerprint.

Cite this