Notes on Computational Complexity of GE Inequalities
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.
Brown, Donald J., "Notes on Computational Complexity of GE Inequalities" (2012). Cowles Foundation Discussion Papers. 2226.