Theory Seminar: On the Computation of Market Equilibria

Friday, January 20, 2017 - 2:00pm
4310 CS

Speaker Name: 

Dimitris Paparas

Speaker Institution: 

University of Wisconsin - Madison

Cookies: 

No

Description: 

We study the problem of efficiently finding a Market Equilibrium in an Arrow-Debreu market. We start by proving PPAD-hardness for the long-standing open problem regarding the complexity of computing an approximate Arrow-Debreu market equilibrium in markets with Constant Elasticity of Substitution (CES) utilities. Building on this result, we introduce the notion of non-monotone utilities, which covers a wide variety of utility functions in economic theory, and show that it is PPAD-hard to compute an approximate Arrow-Debreu market equilibrium in markets with linear and non-monotone utilities.

Joint work with Xi Chen and Mihalis Yannakakis.