Earning limits in fisher markets with spending-constraint utilities

Xiaohui Bei, Jugal Garg, Martin Hoefer, Kurt Mehlhorn

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

Abstract

Earning limits are an interesting novel aspect in the classic Fisher market model. Here sellers have bounds on their income and can decide to lower the supply they bring to the market if income exceeds the limit. Beyond several applications, in which earning limits are natural, equilibria of such markets are a central concept in the allocation of indivisible items to maximize Nash social welfare. In this paper, we analyze earning limits in Fisher markets with linear and spending-constraint utilities. We show a variety of structural and computational results about market equilibria. The equilibrium price vectors form a lattice, and the spending of buyers is unique in non-degenerate markets. We provide a scaling-based algorithm that computes an equilibrium in time O(n3ℓlog(ℓ+nU), where n is the number of agents, ℓ≥n a bound on the segments in the utility functions, and U the largest integer in the market representation. Moreover, we show how to refine any equilibrium in polynomial time to one with minimal prices, or one with maximal prices (if it exists). Finally, we discuss how our algorithm can be used to obtain in polynomial time a 2-approximation for Nash social welfare in multi-unit markets with indivisible items that come in multiple copies.

Original languageEnglish (US)
Title of host publicationAlgorithmic Game Theory - 10th International Symposium, SAGT 2017, Proceedings
EditorsVittorio Bilo, Michele Flammini
PublisherSpringer
Pages67-79
Number of pages13
ISBN (Print)9783319666990
DOIs
StatePublished - Jan 1 2017
Event10th International Symposium on Algorithmic Game Theory, SAGT 2017 - L’Aquila, Italy
Duration: Sep 12 2017Sep 14 2017

Publication series

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

Other

Other10th International Symposium on Algorithmic Game Theory, SAGT 2017
Country/TerritoryItaly
CityL’Aquila
Period9/12/179/14/17

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Earning limits in fisher markets with spending-constraint utilities'. Together they form a unique fingerprint.

Cite this