Incentive Strategies and Algorithms for Networks, Crowds and Markets
This work is motivated by several modern applications involving social networks, crowds, and markets. Our work focuses on the theme of designing effective incentive strategies for these applications. Viral marketing is receiving much attention by practicing marketers and researchers alike. While not a new idea, it has come to the forefront because of multiple effects – products have become more complex, making buyers to increasingly rely on opinions of their peers; consumers have evolved to distrust advertising; and Web2.0 has revolutionized the way people can connect, communicate and share. With power shifting to consumers, it has become important for companies to devise effective viral marketing strategies. Incentives are also a critical aspect of crowd sourcing tasks and play a crucial role in attracting, motivating and sustaining participation. The thesis addresses the following problems. (i) Optimal Control of Information Epidemics: We address two problems concerning information propagation in a population: a) how to maximize the spread of a given message in the population within the stipulated time and b) how to create a given level of buzz- measured by the fraction of the population engaged in conversation on a topic of interest- at a specified time horizon. (ii) Optimal Control Strategies for Social Influence (SI) Marketing: We investigate four SI strategies, namely, recommendation programs, referral programs, consumer reviews and campaigns on on-line forums. The campaign is assumed to be of finite duration, and the objective is to maximize profit, the (un-discounted) revenue minus the expenditure on the SI strategy under consideration, over the campaign duration. For each SI strategy, we focus on its timing, i.e., determining at what times to execute it. We address two important questions pertaining to them: a) how to execute a given SI strategy optimally? and b) having executed it so, what gains does it lead to? (iii) Optimal Mix of Incentive Strategies on Social Networks: The reach of a product in a pop- ulation can be influenced by offering (a) direct incentives to influence the buying behavior of potential buyers and (b) referral rewards to exploit the impact of social influence in inducing a purchasing decision. The company is interested in an optimal mix of these incentive programs. We report results on structure of optimal strategies for the company with significant practical implications. (iv) Truthful Tractable Mechanisms with Applications to Crowd sourcing: We focus on crowd- sourcing applications that involve specialized tasks for which the planner hardly has any idea about crowdworkers’ costs, for example, tagging geographical regions with air pollution levels or severity level of Ebola like disease. The mechanisms have to be robust to untruthful bidding from the crowdworkers. In our work, we propose tractable allocation algorithms that are monotone, leading to design of truthful mechanisms that can be successfully deployed in such applications.