Satiation in Fisher Markets and Approximation of Nash Social Welfare

Jugal Garg (), Martin Hoefer () and Kurt Mehlhorn ()
Additional contact information
Jugal Garg: Department of Industrial & Enterprise Systems Engineering, University of Illinois Urbana-Champaign, Champaign, Illinois 61801
Martin Hoefer: Institut für Informatik, Goethe Universität Frankfurt/Main, 60325 Frankfurt, Germany
Kurt Mehlhorn: Algorithms and Complexity Group, Max Planck Institut für Informatik, 66123 Saarbrucken, Germany

Mathematics of Operations Research, 2024, vol. 49, issue 2, 1109-1139

Abstract: We study linear Fisher markets with satiation. In these markets, sellers have earning limits , and buyers have utility limits . Beyond applications in economics, they arise in the context of maximizing Nash social welfare when allocating indivisible items to agents. In contrast to markets with either earning or utility limits, markets with both limits have not been studied before. They turn out to have fundamentally different properties. In general, the existence of competitive equilibria is not guaranteed. We identify a natural property of markets (termed money clearing ) that implies existence. We show that the set of equilibria is not always convex, answering a question posed in the literature. We design an FPTAS to compute an approximate equilibrium and prove that the problem of computing an exact equilibrium lies in the complexity class continuous local search ( CLS ; i.e., the intersection of polynomial local search ( PLS ) and polynomial parity arguments on directed graphs ( PPAD )). For a constant number of buyers or goods, we give a polynomial-time algorithm to compute an exact equilibrium. We show how (approximate) equilibria can be rounded and provide the first constant-factor approximation algorithm (with a factor of 2.404) for maximizing Nash social welfare when agents have capped linear (also known as budget-additive) valuations. Finally, we significantly improve the approximation hardness for additive valuations to 8 / 7 > 1.069 .

Keywords: Primary: 68Q25; secondary: 68W40; market equilibrium; equilibrium computation; Nash social welfare; budget-additive utilities (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2019.0129 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:49:y:2024:i:2:p:1109-1139

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().