Ning Chen and Atri Rudra

Walrasian Equilibrium: Hardness, Approximations and Tractable Instances

Abstract : Imagine a scenario where a movie rental store is going out of business and wants to clear out its current inventory. Further suppose that based on their rental records, the store has an estimate of which combinations (or bundles) of items would interest a member and how much they would be willing to pay for those bundles. The store then sets prices for each individual item and allocates bundles to the members (or buyers) with the following ``fairness" criterion--- given the prices on the items no buyer would prefer to be allocated any bundle other than those currently allocated to her. Further, it is the last day of the sale and it is imperative that no item remain after the sale is completed. A natural way to satisfy this constraint is to give away any unallocated item for free. This paper looks at the complexity of computing such allocation and prices.

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".