Computer Science – Computer Science and Game Theory
Scientific paper
2010-09-02
Computer Science
Computer Science and Game Theory
Scientific paper
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.
Chen Xi
Teng Shang-Hua
No associations
LandOfFree
A Complexity View of Markets with Social Influence does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Complexity View of Markets with Social Influence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Complexity View of Markets with Social Influence will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-375106