Satiation in Fisher Markets and Approximation of Nash Social Welfare

• 成果类型: Article; Early Access
• 署名作者: Garg, Jugal; Hoefer, Martin; Mehlhorn, Kurt
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; Goethe University Frankfurt; Max Planck Society
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2019.0129
• 发表日期: 2023
• 关键词: budgeted allocations; equilibrium; algorithm; approximability; auctions; utility; prices

摘要

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 p ffiffiffiffiffiffififfi approximation hardness for additive valuations to 8=7