TY - JOUR
T1 - Earning and utility limits in fisher markets
AU - Bei, Xiaohui
AU - Garg, Jugal
AU - Hoefer, Martin
AU - Mehlhorn, Kurt
N1 - Funding Information:
Jugal Garg is supported by NSF CRII Award 1755619. Authors’ addresses: X. Bei, Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, 637371; email: xhbei@ntu.edu.sg; J. Garg, Dept. of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana-Champaign, 104 S Mathews Ave, Urbana, IL 61801, USA; email: jugal@ illinois.edu; M. Hoefer, Institute for Computer Science, Goethe University Frankfurt, Robert-Mayer-Strasse 11-15, 60325 Frankfurt am Main, Germany; email: mhoefer@cs.uni-frankfurt.de; K. Mehlhorn, Max-Planck-Institut für Informatik, Algorithms and Complexity Group, Campus E1 4, 66123 Saarbruecken, Germany; email: mehlhorn@mpi-inf.mpg.de. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM. 2167-8375/2019/07-ART10 $15.00 https://doi.org/10.1145/3340234
Publisher Copyright:
© 2019 Copyright held by the owner/author(s).
PY - 2019/7/18
Y1 - 2019/7/18
N2 - Earning limits and utility limits are novel aspects in the classic Fisher market model. Sellers with earning limits have bounds on their income and lower the supply they bring to the market if income exceeds the limit. Buyers with utility limits have an upper bound on the amount of utility that they want to derive and lower the budget they bring to the market if utility exceeds the limit. Markets with these properties can have multiple equilibria with different characteristics. We analyze earning limits and utility limits in markets with linear and spending-constraint utilities. For markets with earning limits and spending-constraint utilities, we show that equilibrium price vectors form a lattice and the spending of buyers is unique in non-degenerate markets. We provide a scaling-based algorithm to compute 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. We show how to refine any equilibrium in polynomial time to one with minimal prices or one with maximal prices (if it exists). Moreover, our algorithm can be used to obtain in polynomial time a 2-approximation for maximizing Nash social welfare in multi-unit markets with indivisible items that come in multiple copies. For markets with utility limits and linear utilities, we show similar results—lattice structure of price vectors, uniqueness of allocation in non-degenerate markets, and polynomial-time refinement procedures to obtain equilibria with minimal and maximal prices. We complement these positive results with 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.
AB - Earning limits and utility limits are novel aspects in the classic Fisher market model. Sellers with earning limits have bounds on their income and lower the supply they bring to the market if income exceeds the limit. Buyers with utility limits have an upper bound on the amount of utility that they want to derive and lower the budget they bring to the market if utility exceeds the limit. Markets with these properties can have multiple equilibria with different characteristics. We analyze earning limits and utility limits in markets with linear and spending-constraint utilities. For markets with earning limits and spending-constraint utilities, we show that equilibrium price vectors form a lattice and the spending of buyers is unique in non-degenerate markets. We provide a scaling-based algorithm to compute 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. We show how to refine any equilibrium in polynomial time to one with minimal prices or one with maximal prices (if it exists). Moreover, our algorithm can be used to obtain in polynomial time a 2-approximation for maximizing Nash social welfare in multi-unit markets with indivisible items that come in multiple copies. For markets with utility limits and linear utilities, we show similar results—lattice structure of price vectors, uniqueness of allocation in non-degenerate markets, and polynomial-time refinement procedures to obtain equilibria with minimal and maximal prices. We complement these positive results with 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.
KW - Earning limits
KW - Equilibrium computation
KW - Market equilibrium
KW - Spending-constraint utilities
KW - Utility limits
UR - http://www.scopus.com/inward/record.url?scp=85069508623&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85069508623&partnerID=8YFLogxK
U2 - 10.1145/3340234
DO - 10.1145/3340234
M3 - Article
AN - SCOPUS:85069508623
SN - 2167-8375
VL - 7
JO - ACM Transactions on Economics and Computation
JF - ACM Transactions on Economics and Computation
IS - 2
M1 - 10
ER -