TL;DR
This paper investigates the computational complexity of finding market equilibria in economies where traders' preferences are influenced by their social network. They demonstrate that even simple social structures, like planar graphs with bounded degrees, can make finding equilibria computationally hard (PPAD-hard), challenging a common assumption that markets with few goods are always easy to solve. Conversely, they show that hierarchical social structures allow for efficient approximate equilibrium computation.
What Problem Does This Paper Address?
In traditional economic theory, market equilibria are found using models like the Arrow-Debreu model, where a trader's utility depends solely on the goods they possess. However, in reality, social interactions significantly influence our preferences and valuations. For instance, the perceived value of a smartphone might increase if many of one's friends own one due to network effects. This paper addresses the question of how incorporating this "social influence" into economic models affects the computational difficulty of finding market equilibria. Specifically, it aims to understand and characterize the impact of social influence on the complexity of computing and approximating these equilibria. The authors also challenge a prevailing belief, termed the "myth of a constant number of goods," which suggests that markets with a fixed, small number of goods are always computationally tractable.
Methods
The paper employs a combination of complexity-theoretic and algorithmic approaches.
Complexity-Theoretic: * PPAD-Hardness Reductions: The core of their complexity results involves reducing known hard problems (specifically, SPARSE-NASH, the problem of finding Nash equilibria in sparse two-player games) to market equilibrium problems with social influence. This is a standard technique to prove that a problem is at least as hard as the problem it's reduced from. * Focus on Specific Influence Models: They analyze two concrete models of social influence: * Linear Influence: Traders' utility functions are linear, and the slopes of these functions are influenced by their neighbors' possessions. * Threshold Influence: Traders' utility functions are piecewise-linear, and their thresholds are influenced by neighbors. * Constrained Market Structures: They prove hardness results even under strong structural constraints on the market, such as a constant number of goods (specifically four) and a bounded-degree, planar social influence graph.
Algorithmic: * Divide-and-Conquer: For markets with hierarchical social influence graphs, they develop a divide-and-conquer algorithm. This approach recursively breaks down the problem into smaller subproblems, leveraging the tree-like structure of the influence graph. * Approximate Equilibria: The algorithms focus on finding approximate market equilibria, defined by specific bounds on budget feasibility, optimality, and market clearing. This is a common approach when exact solutions are computationally intractable.
Datasets
Not discussed in the paper. The paper focuses on theoretical models and algorithmic constructions rather than empirical evaluation on real-world datasets.
Key Insights and Ideas
- Social Influence Can Be Computationally Costly: The most striking insight is that even simple social structures (bounded-degree, planar influence graphs) can render market equilibrium computation PPAD-hard, contrary to the intuition that fewer goods imply easier computation. This highlights the non-trivial computational implications of social interactions.
- Challenging the "Myth of a Constant Number of Goods": The paper provides a concrete counterexample to the belief that markets with a constant number of goods are always easy to solve. Their construction demonstrates PPAD-hardness for markets with just four goods.
- Structure Matters: Hierarchical vs. Arbitrary Networks: The paper reveals a significant difference in computational tractability based on the structure of the social influence graph. While arbitrary or planar graphs can lead to hardness, hierarchical structures allow for efficient algorithms. This suggests that understanding the topology of social influence is crucial for designing efficient algorithms.
- Equilibrium Existence Proofs: The paper extends existing equilibrium existence theorems to markets with social influence, utilizing Kakutani's fixed-point theorem. This provides a theoretical foundation for the problems they analyze.
Key Results
- PPAD-Hardness for Planar, Bounded-Degree Markets: The paper proves that finding an approximate market equilibrium is PPAD-hard for markets with:
- Linear influence utilities, a constant number of goods (4), and a bounded-degree, planar influence graph.
-
Threshold influence utilities, an arbitrary number of goods, and a bounded-degree, planar influence graph. These results hold even for the special case of Fisher's market model.
-
Efficient Algorithm for Hierarchical Markets: For markets with a constant number of goods and a hierarchical influence graph, they provide a polynomial-time algorithm (specifically, $m^{O(\log m)}$) for finding an approximate market equilibrium, provided that prices are not too small. This is a significant contrast to the hardness results for arbitrary influence graphs.
Limitations and Future Work
- Approximation Ratios: While the paper provides hardness results for approximate equilibria, the specific approximation ratios achieved by their algorithms (e.g., $1/poly(m)$) might be improvable.
- General Utility Functions: The analysis is focused on linear and threshold influence utility functions. Extending the results to more general forms of utility functions influenced by social interactions would be a natural next step.
- Real-World Data: The paper is theoretical. Future work could involve testing their findings and algorithms on real-world social network data and market data to empirically validate the impact of social influence on equilibrium computation.
- Algorithmic Improvements for Planar/Bounded-Degree Graphs: While the paper shows hardness for planar, bounded-degree graphs, developing algorithms that achieve good approximation ratios for these cases (even if not polynomial time) remains an open challenge.
Summary updated