ICS 2010
|
|
Welcome to ICS2010
Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings, 156-165,
978-7-302-21752-7
Tsinghua University Press
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 efficiently checkable 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. We note that this is the first result showing membership in PPAD for a market model defined by an important, broad class of utility functions. •Finally, building on the techniques of [CDDT09] we prove that under these sufficient conditions, finding an equilibrium for Fisher markets is PPAD-hard. Preview: 
|
Copyright 2009-2010, Institute for Computer Science, Tsinghua University, All Rights Reserved.