## Abstract

After more than a decade of work in TCS on the computabil- ity of market equilibria, complementary pivot algorithms have emerged as the best hope of obtaining practical al- gorithms. So far they have been used for markets under separable, piecewise-linear concave (SPLC) utility functions [23] and SPLC production sets [25]. Can his approach extend to non-separable utility functions and production sets? A major impediment is rationality, i.e., if all parameters are set to rational numbers, there should be a rational equilibrium. Recently, [35] introduced classes of non-separable utility functions and production sets, called Leontief-free, which are applicable when goods are substitutes. For markets with these utility functions and production sets, and satisfying mild sufficiency conditions, we obtain the following results: • Proof of rationality. • Complementary pivot algorithms based on a suitable adaptation of Lemke's classic algorithm. • A strongly polynomial bound on the running time of our algorithms if the number of goods is a constant, despite the fact that the set of solutions is disconnected. • Experimental verification, which confirms that our algorithms are practical. • Proof of PPAD-completeness. Next we give a proof of membership in FIXP for markets under piecewise-linear concave (PLC) utility functions and PLC production sets by capturing equilibria as fixed points of a continuous function via a nonlinear complementarity problem (NCP) formulation. Finally we provide, for the first time, dichotomies for equilibrium computation problems, both Nash and market; in particular, the results stated above play a central role in arriving at the dichotomies for exchange markets and for markets with production. We note that in the past, dichotomies have played a key role in bringing clarity to the complexity of decision and counting problems.

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

Title of host publication | STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing |

Publisher | Association for Computing Machinery |

Pages | 525-534 |

Number of pages | 10 |

ISBN (Print) | 9781450327107 |

DOIs | |

State | Published - 2014 |

Externally published | Yes |

Event | 4th Annual ACM Symposium on Theory of Computing, STOC 2014 - New York, NY, United States Duration: May 31 2014 → Jun 3 2014 |

### Publication series

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

ISSN (Print) | 0737-8017 |

### Other

Other | 4th Annual ACM Symposium on Theory of Computing, STOC 2014 |
---|---|

Country/Territory | United States |

City | New York, NY |

Period | 5/31/14 → 6/3/14 |

## Keywords

- FIXP
- LCP
- Leontief-free
- Market equilibrium

## ASJC Scopus subject areas

- Software