Earning and utility limits in fisher markets

Xiaohui Bei, Jugal Garg, Martin Hoefer, Kurt Mehlhorn

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Article number10
JournalACM Transactions on Economics and Computation
Volume7
Issue number2
DOIs
StatePublished - Jul 18 2019

Fingerprint

Polynomials
Market Equilibrium
Polynomial time
Welfare
Utility Function
Hardness
Exceed
Market
Multiple Equilibria
Indivisible
Market Model
Refinement
Uniqueness
Complement
NP-complete problem
Maximise
Scaling
Upper bound
Unit
Integer

Keywords

  • Earning limits
  • Equilibrium computation
  • Market equilibrium
  • Spending-constraint utilities
  • Utility limits

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Statistics and Probability
  • Economics and Econometrics
  • Marketing
  • Computational Mathematics

Cite this

Earning and utility limits in fisher markets. / Bei, Xiaohui; Garg, Jugal; Hoefer, Martin; Mehlhorn, Kurt.

In: ACM Transactions on Economics and Computation, Vol. 7, No. 2, 10, 18.07.2019.

Research output: Contribution to journalArticle

Bei, Xiaohui ; Garg, Jugal ; Hoefer, Martin ; Mehlhorn, Kurt. / Earning and utility limits in fisher markets. In: ACM Transactions on Economics and Computation. 2019 ; Vol. 7, No. 2.
@article{ae1f6d5a750e4e7fbbafedbe07717edd,
title = "Earning and utility limits in fisher markets",
abstract = "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.",
keywords = "Earning limits, Equilibrium computation, Market equilibrium, Spending-constraint utilities, Utility limits",
author = "Xiaohui Bei and Jugal Garg and Martin Hoefer and Kurt Mehlhorn",
year = "2019",
month = "7",
day = "18",
doi = "10.1145/3340234",
language = "English (US)",
volume = "7",
journal = "ACM Transactions on Economics and Computation",
issn = "2167-8375",
publisher = "Association for Computing Machinery (ACM)",
number = "2",

}

TY - JOUR

T1 - Earning and utility limits in fisher markets

AU - Bei, Xiaohui

AU - Garg, Jugal

AU - Hoefer, Martin

AU - Mehlhorn, Kurt

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

VL - 7

JO - ACM Transactions on Economics and Computation

JF - ACM Transactions on Economics and Computation

SN - 2167-8375

IS - 2

M1 - 10

ER -