LFCS Seminar: Mihalis Yannakakis
The Complexity of NonMonotone Markets
What 


When 
Jul 16, 2013 from 04:00 PM to 05:00 PM 
Contact Name  jcheney@inf.ed.ac.uk 
Add event to calendar 
vCal iCal 
We introduce the notion of nonmonotone utilities, which covers a wide variety of utility functions in economic theory. We show that it is PPADhard to compute an approximate ArrowDebreu market equilibrium in markets with linear and nonmonotone utilities. Building on this result, we settle the longstanding open problem regarding the complexity of computing an approximate ArrowDebreu market equilibrium in markets with Constant Elasticity of Substitutes (CES) utilities.
(Joint work with Xi Chen and Dimitris Paparas of Columbia University.)