2008/10/01 by Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi +1 · 6 citations
Economics, Econometrics and Finance · Decision Sciences · #Economic theories and models #Game Theory and Applications #Game Theory and Voting Systems
paper · doi:10.1145/1411509.1411512
openalex publication_date 2008/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
We give the first polynomial time algorithm for exactly computing an equilibrium for the linear utilities case of the market model defined by Fisher. Our algorithm uses the primal--dual paradigm in the enhanced setting of KKT conditions and convex programs. We pinpoint the added difficulty raised by this setting and the manner in which our algorithm circumvents it.