Ning Chen and Atri Rudra

The concept of "fair" pricing and allocation in the above example is called
*Walrasian equilibrium*. In this work we study the complexity
of computing such an equilibrium for the special case of
*single minded auction* (as the name suggests in such an
auction every buyer is interested in exactly one bundle of good). It was
known that checking the existence of such an equilibrium was NP-hard.
In this work, we look at different notions of approximations of Walrasian
equilibrium. We prove a conjecture from a previous work regarding one
such approximate Walrasian equilibrium. We also define
a new notion of approximation that is more natural and prove that it is
NP-hard to compute any such approximation that is reasonably "efficient".

- Proceedings of the 1st Workshop on Internet and Network Economics (WINE), Pgs 141-150. December 2005. [PDF]