Quality of local equilibria in discrete exchange economies

This paper defines the notion of a local equilibrium of quality $(r,s)$, $0 \leq r , s$, in a discrete exchange economy: a partial allocation and item prices that guarantee certain stability properties parametrized by the numbers $r$ and $s$. The quality $(r,s)$ measures the fit between the allocation and the prices: the larger $r$ and $s$ the closer the fit. For $r,s\le 1$ this notion provides a graceful degradation for the conditional equilibria of [10] which are exactly the local equilibria of quality $(1,1)$. For $1 < r , s $thelocalequilibriaofquality$( r , s )$ are {\em more stable} than conditional equilibria. Any local equilibrium of quality $(r,s)$ provides, without any assumption on the type of the agents’ valuations, an allocation whose value is at least $\frac{rs}{1+rs}$ the optimal fractional allocation. In any economy in which all agents’ valuations are $a$-submodular, i.e., exhibit complementarity bounded by $a\ge 1$, there is a local equilibrium of quality $(\frac{1}{a},\frac{1}{a})$. In such an economy any greedy allocation provides a local equilibrium of quality $(1,\frac{1}{a})$. Walrasian equilibria are not amenable to such graceful degradation.