138 citations · 191 across the 22 of their papers we have counts for
3 papers · 2 filters
The Complexity of Non-Monotone Markets
Xi Chen, Dimitris Paparas, Mihalis Yannakakis
We introduce the notion of non-monotone utilities, which covers a wide variety of utility functions in economic theory. We then prove that it is PPAD-hard to compute an approximate…
Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
We show that one can approximate the least fixed point solution for a multivariate system of monotone probabilistic max(min) polynomial equations, referred to as maxPPSs (and minPP…
Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
We show that one can approximate the least fixed point solution for a multivariate system of monotone probabilistic polynomial equations in time polynomial in both the encoding siz…