COWLES FOUNDATION FOR RESEARCH IN
ECONOMICS Box 208281
COWLES FOUNDATION DISCUSSION PAPER NO. 1865 Notes on Computational Complexity of GE Inequalities Donald J. Brown July 2012 Recently, Cheryche et al. (2011) proved the important negative result
that deciding the strong feasibility of the Marshallian equilibrium inequalities,
introduced by Brown and Matzkin (1996), is NP-complete. Here, I show that the weak
feasibility of the equivalent Hicksian equilibrium inequalities, introduced by Brown and
Shannon (2000), can be decided in oracle-polynomial time. |
