Market equilibrium under separable, piecewise-linear, concave utilities
Abstract
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 ε-approximate equilibrium, for ε = 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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- May 01, 2011
- Source ID
- 10.1145/1970392.1970394
Entities
People
- Mihalis Yannakakis
- Vijay V. Vazirani
Organizations
- Columbia University
- Division of Computing and Communication Foundations
- Georgia Tech
- Office of Naval Research