التفاصيل البيبلوغرافية
| العنوان: |
Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities. |
| المؤلفون: |
VAZIRANI, VIJAY V., YANNAKAKIS, MIHALIS |
| المصدر: |
Journal of the ACM; May2011, Vol. 58 Issue 3, p10:1-10:25, 25p |
| مصطلحات موضوعية: |
ALGORITHMS, UTILITY functions, ECONOMIC equilibrium, MATHEMATICAL models of economics, MATHEMATICAL economics, MARKETS |
| مستخلص: |
We consider Fisher and Arrow–Debreu markets under additively separable, piecewise-linear, concave utility functions and obtain the following results. For both market models, if an equilibrium exists, there is one that is rational and can be written using polynomially many bits. There is no simple necessary and sufficient condition for the existence of an equilibrium: The problem of checking for existence of an equilibrium is NP-complete for both market models; the same holds for existence of an e-approximate equilibrium, for e = O(n−5). Under standard (mild) sufficient conditions, the problem of finding an exact equilibrium is in PPAD for both market models. Finally, building on the techniques of Chen et al. [2009a] we prove that under these sufficient conditions, finding an equilibrium for Fisher markets is PPAD-hard. [ABSTRACT FROM AUTHOR] |
|
Copyright of Journal of the ACM is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Complementary Index |
Full Text Finder