We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Satiation in Fisher Markets and Approximation of Nash Social Welfare.
- Authors
Garg, Jugal; Hoefer, Martin; Mehlhorn, Kurt
- 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. Funding: J. Garg was supported by the National Science Foundation [Grant CCF-1942321 (CAREER)]. M. Hoefer was supported by Deutsche Forschungsgemeinschaft [Grants Ho 3831/5-1, Ho 3831/6-1, and Ho 3831/7-1].
- Subjects
DEUTSCHE Forschungsgemeinschaft; NATIONAL Science Foundation (U.S.); SOCIAL services; POLYNOMIAL time algorithms; REAL estate sales; APPROXIMATION algorithms; DIRECTED graphs; DEALERS (Retail trade); VALUATION
- Publication
Mathematics of Operations Research, 2024, Vol 49, Issue 2, p1109
- ISSN
0364-765X
- Publication type
Article
- DOI
10.1287/moor.2019.0129