## Abstract

Our first result shows membership in PPAD for the problem of computing approximate equilibria for an Arrow-Debreu exchange market for piecewise-linear concave (PLC) utility functions. As a corollary we also obtain membership in PPAD for Leontief utility functions. This settles an open question of Vazirani and Yannakakis (2011). Next we show FIXP-hardness of computing equilibria in Arrow-Debreu exchange markets under Leontief utility functions, and Arrow-Debreu markets under linear utility functions and Leontief production sets, thereby settling these open questions of Vazirani and Yannakakis (2011). As corollaries, we obtain FIXP-hardness for PLC utilities and for Arrow-Debreu markets under linear utility functions and polyhedral production sets. In all cases, as required under FIXP, the set of instances mapped onto will admit equilibria, i.e., will be "yes" instances. If all instances are under consideration, then in all cases we prove that the problem of deciding if a given instance admits an equilibrium is ETR-complete, where ETR is the class Existential Theory of Reals. As a consequence of the results stated above, and the fact that membership in FIXP has been established for PLC utilities, the entire computational difficulty of Arrow-Debreu markets under PLC utility functions lies in the Leontief utility subcase. This is perhaps the most unexpected aspect of our result, since Leontief utilities are meant for the case that goods are perfect complements, whereas PLC utilities are very general, capturing not only the cases when goods are complements and substitutes, but also arbitrary combinations of these and much more. Finally, we give a polynomial time algorithm for finding an equilibrium in Arrow-Debreu exchange markets under Leontief utility functions provided the number of agents is a constant. This settles part of an open problem of Devanur and Kannan (2008).

Original language | English (US) |
---|---|

Title of host publication | STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Pierre McKenzie, Valerie King, Hamed Hatami |

Publisher | Association for Computing Machinery |

Pages | 890-901 |

Number of pages | 12 |

ISBN (Electronic) | 9781450345286 |

DOIs | |

State | Published - Jun 19 2017 |

Event | 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 - Montreal, Canada Duration: Jun 19 2017 → Jun 23 2017 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | Part F128415 |

ISSN (Print) | 0737-8017 |

### Other

Other | 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 |
---|---|

Country | Canada |

City | Montreal |

Period | 6/19/17 → 6/23/17 |

## Keywords

- ETR
- FIXP
- Leontief
- Market equilibria
- PLC
- PPAD

## ASJC Scopus subject areas

- Software