Approximate Market Equilibrium for Near Gross Substitutes
- Chinmay Karande ,
- Nikhil Devanur
In Proc. WINE 2007 |
The property of Weak Gross Substitutibility (WGS) of goods in a market has been found to be conducive to efficient algorithms for finding equilibria. In this paper, we give a natural definition of a δ-approximate WGS property, and show that the auction algorithm of [GK04, GKV04] can be extended to give an ( + δ)-approximate equilibrium for markets with this property.