Social network services have transformed daily lives and have influenced most aspects of society in the developed world, including politics, entertainment, sports and education. These services provide information that is both generated and consumed by their users. In some cases it has resulted in billions of dollars of commerce, but in other cases the search for a revenue stream persists. The true economic value of this information and its dissemination is neither understood today nor recognized by providers of online social network service.

This project entails a research approach combining the analysis of competitive market equilibria and their computational properties, analysis of online social networks and their communication properties, and cooperative game theory, to reach such an understanding and provide mechanisms to benefit from it. The project will also illustrate and validate the mechanisms on case studies. More specifically, the project aims to understand the impact of social influence on the Arrow-Debreu market model. The project investigates the nature of utility functions, the nature of social influence graphs, and the mix of traders in the information dissemination market. It aims to understand the effects of these on the computational complexity of market equilibria as well as the convergence of market dynamics.

This project will provide fundamental insights on the economics of social information dissemination. It will enable a better understanding of these complex systems and will provide fundamental tools for more efficient and robust designs. A successful completion of the project will not only provide theoretical and technical contributions, but will affect the design and implementation of the next generation of social networks and the information market that exists therein. The results can aid in the public understanding of such complex systems as well as inform policy debate.

Project Report

In this project, we aimed to improve our current understanding of various computational problems related to the Arrow-Debreu market model, and to apply this classical model in the analysis of social networks and their communication properties. We have been working on the following directions: 1. We show that information markets for personal information are incrementally deployable in today's economy. To this end, we establish a model of revenue through advertisement driven by real traffic data and ad placement price, and then use cooperative game theory to show that users, providers and publishers can all benefit from it. 2. We investigate the convergence and efficiency of a general information sharing game with multiple channels and arbitrary group-based utility. We establish first that affinity and aversion in such information sharing always exhibit a Nash equilibrium. Going further, we show that protection against deviating coalitions of multiple players is in general much harder to obtain: with single-valued friendship utility and a condition on the girth of the underlying social graphs, stable configurations are found. Otherwise, we prove that it is (NP-)hard to decide on their existence, to obtain optimal configurations or even to approximate it. We obtain additional results on the price of anarchy, illustrating a tension between stability and efficiency. Interestingly, both of these conditions seem to be reconciled in practice by several models of social networks, an optimistic outcome that remains puzzling and difficult to comprehend. 3. We show that, for any constant c < -1, the problem of finding an equilibrium in a CES (constant elasticity of substitution) market with parameter c is (PPAD-)hard. It implies that CES markets are easy to solve if and only if the set of market equilibria is convex. Our hardness proof framework and techniques are novel and can be extended to general families of utility functions under certain conditions. 4. We show how the prioritization of traffic in information networks can improve user utility under certain conditions. Specifically we show that network neutrality regulations are harmful for user utility in an oligopolistic scenario. In a monopolistic scenario when there is a single provider that carries information traffic, network neutrality is beneficial to users. However, even in the monopolistic scenario creating a 'public option' network provides additional utility for the users over a neutral network. Thus, the public option is a non-regulatory alternative to network neutrality and offers a solution to a vexing public policy issue. 5. As we rely increasingly on social networks, especially microblogging sites like Twitter and Weibo, to diffuse news information and inform our collective decisions, a major algorithmic problem is whether such networks make the most of a critical scarce resource: users' reading time. Using analysis of millions of tweets from recent news events, we prove that information filtering is present in today's microblogging: users who post less tend to 'select' such topical information to pick what is likely to be more popular. We prove that such information filtering is instrumental in building a diversity of news offering that accounts for audience with various involvements, or in the contrary leads to an unstable news landscape: depending on the greediness of audience / bloggers, an equilibrium can be reached to incentivize better news, whereas some policies create instability.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Type
Standard Grant (Standard)
Application #
1139915
Program Officer
Balasubramanian Kalyanasundaram
Project Start
Project End
Budget Start
2011-09-01
Budget End
2013-08-31
Support Year
Fiscal Year
2011
Total Cost
$249,993
Indirect Cost
Name
Columbia University
Department
Type
DUNS #
City
New York
State
NY
Country
United States
Zip Code
10027