Computing equilibria in markets with budget-additive utilities
We present the first analysis of Fisher markets with buyers that have budget-additive utility functions. Budget-additive utilities are elementary concave functions with numerous applications in online adword markets and revenue optimization problems. They extend the standard case of linear utilities...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/89959 http://hdl.handle.net/10220/47170 |
| _version_ | 1811690225631494144 |
|---|---|
| author | Garg, Jugal Hoefer, Martin Bei, Xiaohui Mehlhorn, Kurt |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Garg, Jugal Hoefer, Martin Bei, Xiaohui Mehlhorn, Kurt |
| author_sort | Garg, Jugal |
| collection | NTU |
| description | We present the first analysis of Fisher markets with buyers that have budget-additive utility functions. Budget-additive utilities are elementary concave functions with numerous applications in online adword markets and revenue optimization problems. They extend the standard case of linear utilities and have been studied in a variety of other market models. In contrast to the frequently studied CES utilities, they have a global satiation point which can imply multiple market equilibria with quite different characteristics. Our main result is an efficient combinatorial algorithm to compute a market equilibrium with a Pareto-optimal allocation of goods. It relies on a new descending-price approach and, as a special case, also implies a novel combinatorial algorithm for computing a market equilibrium in linear Fisher markets. We complement this positive result with a number of hardness results for related computational questions. We prove that it isNP-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. |
| first_indexed | 2024-10-01T06:00:37Z |
| format | Journal Article |
| id | ntu-10356/89959 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T06:00:37Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | ntu-10356/899592023-02-28T19:24:09Z Computing equilibria in markets with budget-additive utilities Garg, Jugal Hoefer, Martin Bei, Xiaohui Mehlhorn, Kurt School of Physical and Mathematical Sciences Budget-Additive Utility DRNTU::Science::Mathematics Market Equilibrium We present the first analysis of Fisher markets with buyers that have budget-additive utility functions. Budget-additive utilities are elementary concave functions with numerous applications in online adword markets and revenue optimization problems. They extend the standard case of linear utilities and have been studied in a variety of other market models. In contrast to the frequently studied CES utilities, they have a global satiation point which can imply multiple market equilibria with quite different characteristics. Our main result is an efficient combinatorial algorithm to compute a market equilibrium with a Pareto-optimal allocation of goods. It relies on a new descending-price approach and, as a special case, also implies a novel combinatorial algorithm for computing a market equilibrium in linear Fisher markets. We complement this positive result with a number of hardness results for related computational questions. We prove that it isNP-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. Published version 2018-12-21T04:52:02Z 2019-12-06T17:37:29Z 2018-12-21T04:52:02Z 2019-12-06T17:37:29Z 2016 Journal Article Bei, X., Garg, J., Hoefer, M., & Mehlhorn, K. (2016). Computing equilibria in markets with budget-additive utilities. Leibniz International Proceedings in Informatics, 57, 8-. doi:10.4230/LIPIcs.ESA.2016.8 https://hdl.handle.net/10356/89959 http://hdl.handle.net/10220/47170 10.4230/LIPIcs.ESA.2016.8 en Leibniz International Proceedings in Informatics © 2016 Xiaohui Bei, Jugal Garg, Martin Hoefer, and Kurt Mehlhorn; Licensed under Creative Commons License CC-BY. 14 p. application/pdf |
| spellingShingle | Budget-Additive Utility DRNTU::Science::Mathematics Market Equilibrium Garg, Jugal Hoefer, Martin Bei, Xiaohui Mehlhorn, Kurt Computing equilibria in markets with budget-additive utilities |
| title | Computing equilibria in markets with budget-additive utilities |
| title_full | Computing equilibria in markets with budget-additive utilities |
| title_fullStr | Computing equilibria in markets with budget-additive utilities |
| title_full_unstemmed | Computing equilibria in markets with budget-additive utilities |
| title_short | Computing equilibria in markets with budget-additive utilities |
| title_sort | computing equilibria in markets with budget additive utilities |
| topic | Budget-Additive Utility DRNTU::Science::Mathematics Market Equilibrium |
| url | https://hdl.handle.net/10356/89959 http://hdl.handle.net/10220/47170 |
| work_keys_str_mv | AT gargjugal computingequilibriainmarketswithbudgetadditiveutilities AT hoefermartin computingequilibriainmarketswithbudgetadditiveutilities AT beixiaohui computingequilibriainmarketswithbudgetadditiveutilities AT mehlhornkurt computingequilibriainmarketswithbudgetadditiveutilities |