A Complexity View of Markets with Social Influence

Xi Chen, Shang-Hua Teng

Introduction

In classical economic theory, the Arrow-Debreu model serves as the cornerstone for understanding how markets reach equilibrium—a state where supply perfectly matches demand. A fundamental assumption of this model is the absence of "externalities," meaning an individual's utility or satisfaction is derived solely from their own consumption. However, real-world behavior often contradicts this. Social influence, such as the "iPhone effect" (network effects) or "keeping up with the Joneses" (conspicuous consumption), suggests that our neighbors' possessions significantly impact our own valuations.

While the existence of equilibria in markets with social influence has been established, the computational difficulty of actually finding these equilibria remained an open question. This research investigates whether the addition of a social network layer makes finding fair market prices computationally intractable, even in seemingly simple market configurations.

Models of Social Influence

The researchers analyze two primary utility models to capture social dynamics:

  1. Linear Influence Model: In this model, the possessions of a neighbor directly alter the "slope" of a trader's utility function, effectively changing how much they value an additional unit of a specific good.
  2. Threshold Influence Model: Here, a neighbor's possessions influence the "threshold" at which a trader's valuation of a good shifts, modeled through piecewise-linear functions.

To explore the complexity of these models, the authors employ a reduction from Sparse Two-Player Nash Equilibria. By constructing a "gadget" market, they demonstrate how traders' optimal choices can simulate the strategies of players in a complex game, thereby linking market equilibrium to known hard problems in game theory.

The Complexity of Equilibrium: Shattering the "Few Goods" Myth

A prevailing intuition in market design is that if the number of goods is small (a constant such as two or three), the equilibrium is computationally easy to solve. This research fundamentally shatters that myth. The authors prove that in the presence of social influence, a market with as few as four goods is PPAD-hard to solve.

Crucially, this hardness persists even when the social network is relatively simple—specifically, when the network is "planar" (can be drawn on a 2D map without crossing edges) and has a "bounded degree" (each person has a limited number of connections). This discovery shifts the focus of market complexity from the variety of goods to the topology of the social network.

Algorithmic Silver Linings: Hierarchical Networks

Despite the general hardness results, the paper identifies specific conditions under which equilibria can be found more efficiently. The authors propose a divide-and-conquer algorithm designed for hierarchical influence networks.

By discretizing possible prices and allocations and recursively analyzing sub-trees of the social hierarchy, they show that an approximate equilibrium can be found in quasi-polynomial time ($m^{O(\log m)}$). This suggests that while general social influence creates immense complexity, real-world markets may remain tractable if their underlying social structures are organized into clear hierarchies.

Limitations and Future Directions

The study highlights several areas for further exploration:

  • Price Assumptions: The algorithm for hierarchical networks assumes that prices do not drop to near-zero levels. If a market allows for extremely cheap goods (where $1/p_i$ is not bounded by a polynomial), the current algorithmic guarantees may not hold.
  • Complex Influence Functions: The focus was on linear and threshold models. Future research could examine non-linear effects, such as sigmoid or exponential influence.
  • Market Dynamics: This research provides a static analysis. Investigating how prices evolve over time and whether they naturally converge to these equilibria in a social context remains a vital next step.

Conclusion

By integrating social network theory with market equilibrium analysis, this paper provides a new lens on economic complexity. It demonstrates that social influence is not just a psychological phenomenon but a computational one, where the structure of our connections can make the "invisible hand" of the market significantly harder to find.

Summary updated

Abstract

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.
BibTeX
@inproceedings{chen2011complexity,
  author = {Xi Chen and Shang-Hua Teng},
  title = {{A Complexity View of Markets with Social Influence}},
  booktitle = {ICS},
  year = {2011},
  url = {https://openreview.net/forum?id=xHprbCssyZ},
}

Loading related content...

Figure