Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminar: Mihalis Yannakakis

LFCS Seminar: Mihalis Yannakakis

— filed under:

The Complexity of Non-Monotone Markets

What
  • LFCS Seminar
When Jul 16, 2013
from 04:00 PM to 05:00 PM
Contact Name
Add event to calendar vCal
iCal

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

(Joint work with Xi Chen and Dimitris Paparas of Columbia University.)

Document Actions