Quality of local equilibria in discrete exchange economies

This paper defines the notion of a local equilibrium of quality $(r,s)$, $0\le 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 Fu, Kleinberg and Lavi (2012) which are exactly the local equilibria of quality $(1,1)$. For $1<r,s$ the local equilibria of quality $(r,s)$ are 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.