In this paper, inspired by the work of Megiddo on the formation of
preferences and strategic analysis, we consider an early market model studied
in the field of economic theory, in which each trader's utility may be
influenced by the bundles of goods obtained by her social neighbors. The goal
of this paper is to understand and characterize the impact of social influence
on the complexity of computing and approximating market equilibria.

We present complexity-theoretic and algorithmic results for approximating
market equilibria in this model with focus on two concrete influence models
based on the traditional linear utility functions. Recall that an Arrow-Debreu
market equilibrium in a conventional exchange market with linear utility
functions can be computed in polynomial time by convex programming. Our
complexity results show that even a bounded-degree, planar influence network
can significantly increase the difficulty of equilibrium computation even in
markets with only a constant number of goods. Our algorithmic results suggest
that finding an approximate equilibrium in markets with hierarchical influence
networks might be easier than that in markets with arbitrary neighborhood
structures. By demonstrating a simple market with a constant number of goods
and a bounded-degree, planar influence graph whose equilibrium is PPAD-hard to
approximate, we also provide a counterexample to a common belief, which we
refer to as the myth of a constant number of goods, that equilibria in markets
with a constant number of goods are easy to compute or easy to approximate.