Computing equilibria in markets with budget-additive utilities

Xiaohui Bei, Jugal Garg, Martin Hoefer, Kurt Mehlhorn

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

Abstract

We present the first analysis of Fisher markets with buyers that have budget-additive utility functions. Budget-additive utilities are elementary concave functions with numerous applications in online adword markets and revenue optimization problems. They extend the standard case of linear utilities and have been studied in a variety of other market models. In contrast to the frequently studied CES utilities, they have a global satiation point which can imply multiple market equilibria with quite different characteristics. Our main result is an efficient combinatorial algorithm to compute a market equilibrium with a Pareto-optimal allocation of goods. It relies on a new descending-price approach and, as a special case, also implies a novel combinatorial algorithm for computing a market equilibrium in linear Fisher markets. We complement this positive result with a number of hardness results for related computational questions. We prove that it is NP-hard to compute a market equilibrium that maximizes social welfare, and it is PPAD-hard to find any market equilibrium with utility functions with separate satiation points for each buyer and each good.

Original languageEnglish (US)
Title of host publication24th Annual European Symposium on Algorithms, ESA 2016
EditorsChristos Zaroliagis, Piotr Sankowski
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770156
DOIs
StatePublished - Aug 1 2016
Event24th Annual European Symposium on Algorithms, ESA 2016 - Aarhus, Denmark
Duration: Aug 22 2016Aug 24 2016

Publication series

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

Other

Other24th Annual European Symposium on Algorithms, ESA 2016
CountryDenmark
CityAarhus
Period8/22/168/24/16

Keywords

  • Budget-additive utility
  • Equilibrium computation
  • Market equilibrium

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Computing equilibria in markets with budget-additive utilities'. Together they form a unique fingerprint.

Cite this