Local optima, local equilibria and bounded complementarity in discrete exchange economies
share
In a discrete exchange economy an allocation is a local optimum if no transfer of a single item can improve the social welfare. In an economy in which all agents' valuations are a-submodular, i.e., exhibit complementarity bounded by a, any local optimum is a 1 + a^2-approximation of the fractional optimum. A local optimum is naturally associated with a set of item prices. Together with these prices it forms a local equilibrium. The quality of a local equilibrium is characterized by a real number in [ 0 , 1 ]. The quality of a local equilibrium measures the fit between the allocation and the prices. Any local equilibrium of quality q provides, without any assumption on the type of the agents' valuations, an allocation whose value is at least q^2/ 1 + q^2 the optimal fractional allocation. Local equilibria of quality 1 are exactly the conditional equilibria introduced by Fu, Kleinberg and Lavi. In any exchange economy with a-submodular valuations, any local optimum and the item prices associated with it provide a local equilibrium of a quality at least equal to 1/a. In such an economy any greedy allocation provides a local equilibrium that is at least 1/1 + a the optimal fractional allocation.
READ FULL TEXT