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