Exploiting Strategic Uncertainty for Incentive Design in Crowd-Based Markets
Strategic interactions and uncertainties are at the heart of many crowd-based platforms. Uncertainties can be at systemic level (e.g., strength of a threat/idea in a cyber-security/crowdfunding setting, average willingness-to-pay for a product, or the average reserved price of drivers in a ride-sharing platform) or can be idiosyncratic, explaining the variations at the microscopic level (e.g., differences in people's perception of threats/ideas, or heterogeneity in tastes of consumers for a product or in reserved prices of drivers in a ride-sharing platform). Such uncertainties along with the interdependencies in utilities lead to strategic uncertainty; that is, uncertainty concerning the actions and beliefs (and beliefs about the beliefs, and so on) of others faced by individual decision makers. As we show in a recent work, market maker/platform can exploit this strategic uncertainty to design profitable incentive programs by conditioning payoffs on some aggregate statistics (e.g., sales volume, mass of active drivers, average investment in security, etc.).
Strategic interactions and uncertainties are at the heart of many crowd-based platforms. Uncertainties can be at systemic level (e.g., strength of a threat/idea in a cyber-security/crowdfunding setting, average willingness-to-pay for a product, or the average reserved price of drivers in a ride-sharing platform) or can be idiosyncratic, explaining the variations at the microscopic level (e.g., differences in people's perception of threats/ideas, or heterogeneity in tastes of consumers for a product or in reserved prices of drivers in a ride-sharing platform). Such uncertainties along with the interdependencies in utilities lead to strategic uncertainty; that is, uncertainty concerning the actions and beliefs (and beliefs about the beliefs, and so on) of others faced by individual decision makers. As we show in a recent work, market maker/platform can exploit this strategic uncertainty to design profitable incentive programs by conditioning payoffs on some aggregate statistics (e.g., sales volume, mass of active drivers, average investment in security, etc.).
As an illustrative application and motivated by the operational value of the network effect, we introduce what we call sales-based rebate mechanisms, as a means of inducing payoff externalities for products with no inherent network effect. We consider a seller offering a product to a mass of consumers with uncertain valuations reflecting both the diversity of consumers' tastes and uncertainty concerning the product's overall perception in the population (i.e., the realized quality). Buyers pay the price when making a purchase and are paid a reward at the end of the sales period. The seller can induce payoff externalities by offering a reward program in which the reward/rebate paid to a buyer is a function of the ex-post sales volume. The reward program induces a global game among the consumers, where heterogeneity of private valuations results in heterogeneous beliefs on sales volume at equilibrium. This enables the seller to effectively price-discriminate, offering different expected net prices at different valuations through conditioning the paid reward on the realized sales volume. As one of our main findings, we articulate that while sellers achieve a growth in their profit for products with an inherent positive network effect, inducing such an effect using an aggregate reward program may reduce the profit.
Characterizing the optimal sales-based rebate mechanism reveals several systematic challenges in incentive design under uncertainty in crowd-based platforms. A conventional assumption in classical theory of global games is for the expected utilities to be monotone with valuations at equilbrium (a.k.a. single-crossing property). Although this facilitates equilibrium analysis by reducing the equilibria to threshold strategies fully representable by a cutoff value satisfying an indifference equation, it may in return result in extremely suboptimal design as it imposes an unwanted constraint on the space of feasible reward programs. To remedy this shortcoming, we formulate the optimal reward program as the solution of an infinite-dimensional optimization problem and use variational optimization techniques to identify several key characteristics of its optimal solution. While finding the optimal reward program is in general an intractable problem, we fully characterize the optimal solution in closed form in two intuitive and structurally simple subspaces of reward programs, which we then show to recover the optimal solution asymptotically (i.e., as the ratio of diversity in tastes to uncertainty in realized quality tends to either zero or infinity).
Another potential application for this idea which we are currently investigating is promotion design in ride-sharing platforms, where uncertainty in the availability of drivers can harm the profit of the platform as it may result in too many or too few providers available for service. Platform can use promotions, such as guaranteed hourly wages promotion by Uber, as a means to influence the decision making of drivers and to cope with the uncertainty in the pool of active drivers.
Characterizing the optimal sales-based rebate mechanism reveals several systematic challenges in incentive design under uncertainty in crowd-based platforms. A conventional assumption in classical theory of global games is for the expected utilities to be monotone with valuations at equilbrium (a.k.a. single-crossing property). Although this facilitates equilibrium analysis by reducing the equilibria to threshold strategies fully representable by a cutoff value satisfying an indifference equation, it may in return result in extremely suboptimal design as it imposes an unwanted constraint on the space of feasible reward programs. To remedy this shortcoming, we formulate the optimal reward program as the solution of an infinite-dimensional optimization problem and use variational optimization techniques to identify several key characteristics of its optimal solution. While finding the optimal reward program is in general an intractable problem, we fully characterize the optimal solution in closed form in two intuitive and structurally simple subspaces of reward programs, which we then show to recover the optimal solution asymptotically (i.e., as the ratio of diversity in tastes to uncertainty in realized quality tends to either zero or infinity).
Another potential application for this idea which we are currently investigating is promotion design in ride-sharing platforms, where uncertainty in the availability of drivers can harm the profit of the platform as it may result in too many or too few providers available for service. Platform can use promotions, such as guaranteed hourly wages promotion by Uber, as a means to influence the decision making of drivers and to cope with the uncertainty in the pool of active drivers.
- Sales-based rebate design, with A. Jadbabaie, Management Science, under review [slides].
- Optimal promotion design in two-sided platforms, with A. Jadbabaie, working paper [slides].
A Theory of (Mis-)Information Spread on Social Networks
“A lie can travel halfway around the world while the truth is still putting on its shoes.”
There is a large body of evidence suggesting that false news and misinformation are more likely to circulate in social networks, spreading faster, deeper, and more widely than accurate information. Recent empirical studies suggest the novelty in the false news as a potential cause for the wider spread of misinformation. As part of a recent research initiative, we aim to complement such empirical findings by providing a theory that rationalizes the decision of individuals in the spread of news and how this could potentially trigger a wider spread of false or inaccurate information.
One potential rationale for our tendency to share novel news lies in our desire to steer others and have them conform to our opinions. If we find a news quite novel and surprising that significantly affects our opinion, the desire to have others think similarly incentivizes us to influence their opinions as well by sharing the news with them. Sharing news can also have affirmative motives: We may have different/opposing opinions from our friends and share news as an affirmation of our point of view, assuming the credibility of the news source as common knowledge.
“A lie can travel halfway around the world while the truth is still putting on its shoes.”
There is a large body of evidence suggesting that false news and misinformation are more likely to circulate in social networks, spreading faster, deeper, and more widely than accurate information. Recent empirical studies suggest the novelty in the false news as a potential cause for the wider spread of misinformation. As part of a recent research initiative, we aim to complement such empirical findings by providing a theory that rationalizes the decision of individuals in the spread of news and how this could potentially trigger a wider spread of false or inaccurate information.
One potential rationale for our tendency to share novel news lies in our desire to steer others and have them conform to our opinions. If we find a news quite novel and surprising that significantly affects our opinion, the desire to have others think similarly incentivizes us to influence their opinions as well by sharing the news with them. Sharing news can also have affirmative motives: We may have different/opposing opinions from our friends and share news as an affirmation of our point of view, assuming the credibility of the news source as common knowledge.
In a recent work on modeling online news dissemination on a Twitter-like social network, we show how novelty and affirmation motives naturally emerge from the utility-maximizing behavior of the agents when persuasion is the main motive for sharing. We further characterize the dynamics of the news spread endogenously generated by micro-level news-sharing decisions and establish necessary and sufficient conditions for emergence of a cascade. This enables us to qualitatively study the relation between the news precision level and the likelihood of a news-sharing cascade. In particular, our model reveals a connection between wisdom of the crowd and cascade likelihood when sharing news is costly; When the society as a whole is biased, i.e., there is a gap between the true state of interest and the aggregation of prior beliefs, the truth almost always triggers a cascade. In contrast, in a wise or unbiased society, cascades are more likely to occur for imprecise news (which are hence more likely to be false).
- A theory of misinformation spread on social networks, with C. Hsu and A. Jadbabaie, working paper.
Local Optimality of Almost Piecewise-Linear Quantizers for Witsenhausen's Counterexample
In his seminal work, Witsenhausen (1968) formulated the first counterexample to the misconception that nothing is to be gained by using nonlinear controllers when loss is quadratic and system is linear subject to Gaussian noise. His counterexample is in form of a simple two-stage Linear-Quadratic-Gaussian (LQG) decentralized control system, where he showed that the optimal controller is nonlinear. Finding the optimal solution, however, is still an open problem.
While Witsenhausen's counterexample has been subject of intense research across multiple communities for half a century, a little is known about the topological properties of its optimal solution (e.g., whether it is continuous or not, the number of its fixed points, etc.). One notable result in this line is that the optimal controller is a strictly increasing function with a real analytic left inverse. Consequently, no piecewise-linear strategy can be optimal, though not ruling out the possibility of a discontinuous, and in particular a ``near piecewise-linear'' optimal solution; a conjecture supported by numerous simulations and heuristic approaches.
In a recent work, we formulate Witsenhausen's counterexample in a leader-follower game setup where the follower makes noisy observations from the leader's action and aims to choose her action as close as possible to that of the leader. Leader who moves first and can see the realization of the state, chooses her action to minimize her ex-ante distance from the follower's action as well as the state. We show the existence of nonlinear perfect Bayesian equilibria at which the leader's strategy is a perturbed slopey variation of an optimal MSE quantizer. We then prove that these equilibria are indeed local minima of the original Witsenhausen's setup. Incorporating some relevant results from asymptotic quantization theory, we show that the proposed local minima are near-optimal in that they are at most a constant factor away from the optimal one, in a regime where the ratio to the optimal cost for the optimal linear design tends to infinity. Our work hence provides a supporting theory for the local optimality of near piecewise-linear strategies for Witsenhausen's problem. we further conjecture that the globally optimal solution is indeed among our proposed local minima, which we are trying to prove incorporating a diverse set of ideas from entropy methods in mathematics, optimal transport, and scale-space theory.
In his seminal work, Witsenhausen (1968) formulated the first counterexample to the misconception that nothing is to be gained by using nonlinear controllers when loss is quadratic and system is linear subject to Gaussian noise. His counterexample is in form of a simple two-stage Linear-Quadratic-Gaussian (LQG) decentralized control system, where he showed that the optimal controller is nonlinear. Finding the optimal solution, however, is still an open problem.
While Witsenhausen's counterexample has been subject of intense research across multiple communities for half a century, a little is known about the topological properties of its optimal solution (e.g., whether it is continuous or not, the number of its fixed points, etc.). One notable result in this line is that the optimal controller is a strictly increasing function with a real analytic left inverse. Consequently, no piecewise-linear strategy can be optimal, though not ruling out the possibility of a discontinuous, and in particular a ``near piecewise-linear'' optimal solution; a conjecture supported by numerous simulations and heuristic approaches.
In a recent work, we formulate Witsenhausen's counterexample in a leader-follower game setup where the follower makes noisy observations from the leader's action and aims to choose her action as close as possible to that of the leader. Leader who moves first and can see the realization of the state, chooses her action to minimize her ex-ante distance from the follower's action as well as the state. We show the existence of nonlinear perfect Bayesian equilibria at which the leader's strategy is a perturbed slopey variation of an optimal MSE quantizer. We then prove that these equilibria are indeed local minima of the original Witsenhausen's setup. Incorporating some relevant results from asymptotic quantization theory, we show that the proposed local minima are near-optimal in that they are at most a constant factor away from the optimal one, in a regime where the ratio to the optimal cost for the optimal linear design tends to infinity. Our work hence provides a supporting theory for the local optimality of near piecewise-linear strategies for Witsenhausen's problem. we further conjecture that the globally optimal solution is indeed among our proposed local minima, which we are trying to prove incorporating a diverse set of ideas from entropy methods in mathematics, optimal transport, and scale-space theory.
- Local optimality of almost piecewise-linear quantizers for Witsenhausen's problem, with A. Jadbabaie, IEEE Transactions on Automatic Control, 2019 (conditionally accepted) [slides].
Dynamic Pricing in Networks with Price-Driven Information Spreading Processes
The inherent complexity of spread on networks (e.g., spread of information, innovation, diseases and failures) induces a new dimension to dynamic decision making in networks; while choosing a strategy maximizing his utility, a decision maker should also take into account the effect of his strategy on the underlying dynamic spread process. A good example is the advertising strategies of small businesses such as smartphone app developers, where the word of mouth of users is often the only low-budget means of advertisement; the seller should thus use the price both to control the profit and to spread the information about the product in the network. To characterize the optimal dynamic pricing strategy in such settings, we have developed an analytically tractable, yet rich framework capturing the effect of dynamic prices on the extent of information diffusion via word of mouth communication of consumers.
Given the spread versus exploit nature of the problem that the seller faces in each period, it is quite natural to expect fluctuations in the optimal pricing policy. What makes our results novel is the optimality of frequent zero-price sales. More precisely, we show that the optimal dynamic pricing policy for durable products with zero or negligible marginal cost drops the price to zero infinitely often. This finding matches our observation from smartphone app industry, where price histories exhibit frequent zero-price sales. The key novel insight here is that zero-price sales allow the seller to reach potentially profitable but uninformed parts of the network via word of mouth of low-valuation zero-price buyers. By properly timing the drop in prices, the firm can ensure that the marginal gain in future profit by selling the product in these previously-unexplored parts of the network dominates the loss in the immediate profit caused by offering the product for free, making the drop of the price to zero a profitable course of action. The results remain valid in face of forward-looking agents, homophily-based engagement of friends in word of mouth, and network externalities under surprisingly mild assumptions.
The inherent complexity of spread on networks (e.g., spread of information, innovation, diseases and failures) induces a new dimension to dynamic decision making in networks; while choosing a strategy maximizing his utility, a decision maker should also take into account the effect of his strategy on the underlying dynamic spread process. A good example is the advertising strategies of small businesses such as smartphone app developers, where the word of mouth of users is often the only low-budget means of advertisement; the seller should thus use the price both to control the profit and to spread the information about the product in the network. To characterize the optimal dynamic pricing strategy in such settings, we have developed an analytically tractable, yet rich framework capturing the effect of dynamic prices on the extent of information diffusion via word of mouth communication of consumers.
Given the spread versus exploit nature of the problem that the seller faces in each period, it is quite natural to expect fluctuations in the optimal pricing policy. What makes our results novel is the optimality of frequent zero-price sales. More precisely, we show that the optimal dynamic pricing policy for durable products with zero or negligible marginal cost drops the price to zero infinitely often. This finding matches our observation from smartphone app industry, where price histories exhibit frequent zero-price sales. The key novel insight here is that zero-price sales allow the seller to reach potentially profitable but uninformed parts of the network via word of mouth of low-valuation zero-price buyers. By properly timing the drop in prices, the firm can ensure that the marginal gain in future profit by selling the product in these previously-unexplored parts of the network dominates the loss in the immediate profit caused by offering the product for free, making the drop of the price to zero a profitable course of action. The results remain valid in face of forward-looking agents, homophily-based engagement of friends in word of mouth, and network externalities under surprisingly mild assumptions.
- Dynamic pricing in social networks: The word of mouth effect, with A. Jadbabaie and A. Kakhbod, Management Science, vol. 64, pp. 971-979, 2018 [full version].
Dynamic Public Learning in Networks of Strategic Agents
Recent advances in information technology and Internet have provided a wide range of channels to aggregate information, from blogs to wikis to the open source movement to prediction markets. There are abundant sources of information (e.g., news channels, social networks, online forums, surveys, and data bases), with every person having access to a personalized set of the sources. The aggregate (or average) action in a population partially accumulates the information dispersed among them. A fundamental question is how the structure of interactions among individual decision makers affects the quality of the information aggregation. This question is extensively studied in the closely related literature of systemic risk and network resilience. Aggregate learning is a twin of systemic volatility; the less volatile the aggregate action of the whole system, the higher the quality of the learning. Mostly concerned with static settings, these works typically come up with a (sometimes contradicting) ranking of network structures in terms of their performance against uncertainties and disruptive events.
We revisit this problem in the context of learning from noisy observations of the public history in a dynamic setting, where the underlying state of the world affecting the utilities moves on a random walk. Our results reveal that the quality of aggregate learning is affected by different network characteristics which vary with the state dynamics. While the quality of learning for slow walks is mainly determined by the local structure of the graph, for fast dynamics the quality of learning is affected by the distribution of Bonacich centralities. This may result in a phase transition in quality of learning between different networks thus ruling out the possibility of ranking network structures in terms of their quality of information aggregation.
Recent advances in information technology and Internet have provided a wide range of channels to aggregate information, from blogs to wikis to the open source movement to prediction markets. There are abundant sources of information (e.g., news channels, social networks, online forums, surveys, and data bases), with every person having access to a personalized set of the sources. The aggregate (or average) action in a population partially accumulates the information dispersed among them. A fundamental question is how the structure of interactions among individual decision makers affects the quality of the information aggregation. This question is extensively studied in the closely related literature of systemic risk and network resilience. Aggregate learning is a twin of systemic volatility; the less volatile the aggregate action of the whole system, the higher the quality of the learning. Mostly concerned with static settings, these works typically come up with a (sometimes contradicting) ranking of network structures in terms of their performance against uncertainties and disruptive events.
We revisit this problem in the context of learning from noisy observations of the public history in a dynamic setting, where the underlying state of the world affecting the utilities moves on a random walk. Our results reveal that the quality of aggregate learning is affected by different network characteristics which vary with the state dynamics. While the quality of learning for slow walks is mainly determined by the local structure of the graph, for fast dynamics the quality of learning is affected by the distribution of Bonacich centralities. This may result in a phase transition in quality of learning between different networks thus ruling out the possibility of ranking network structures in terms of their quality of information aggregation.
- Dynamic public learning in networks of strategic agents: the role of inter/intra-community ties, with A. Jadbabaie and M. Dahleh, in Proceedings of the 56th IEEE Conference on Decision and Control, 2017 (invited paper).
- Aggregate learning from the history in networks, with A. Jadbabaie and M. Dahleh, working paper.
Budget Allocation in Competitive Diffusion: Seeding vs. Quality
A main feature of product consumption in social networks is what is often called the network effect. For such products, consumption of each agent incentivizes the neighboring agents to consume more as well. There are diverse sets of examples for such products or services. New technologies and innovations, mobile applications, online games, social network platforms and online dating services are among many examples in which consuming from a common product or service is more preferable for people. Firms can exploit the network effect to incentivize a larger consumption of their product by seeding the key individuals in the network.
There is a rich literature on identifying the key player(s) in the network. What we do here is to ask a more fundamental question as how to allocate the budget between seeding agents and improving quality, the other key factor in product consumption. We consider two firms competing in a shared market, each having a limited budget which can be invested on the quality or spent on seeding key individuals in the network. We assume that consumers update their consumption as a myopic linear best response to the quality of the products and consumption of the neighbors. We characterize the unique Nash equilibrium of the game between firms and study the effect of the budgets as well as the network structure on the optimal allocation. In particular, we show that at the equilibrium firms invest more budget on quality when their budgets are close to each other. However, as the gap between budgets widens, competition in qualities becomes less effective and firms spend more of their budget on seeding.
A main feature of product consumption in social networks is what is often called the network effect. For such products, consumption of each agent incentivizes the neighboring agents to consume more as well. There are diverse sets of examples for such products or services. New technologies and innovations, mobile applications, online games, social network platforms and online dating services are among many examples in which consuming from a common product or service is more preferable for people. Firms can exploit the network effect to incentivize a larger consumption of their product by seeding the key individuals in the network.
There is a rich literature on identifying the key player(s) in the network. What we do here is to ask a more fundamental question as how to allocate the budget between seeding agents and improving quality, the other key factor in product consumption. We consider two firms competing in a shared market, each having a limited budget which can be invested on the quality or spent on seeding key individuals in the network. We assume that consumers update their consumption as a myopic linear best response to the quality of the products and consumption of the neighbors. We characterize the unique Nash equilibrium of the game between firms and study the effect of the budgets as well as the network structure on the optimal allocation. In particular, we show that at the equilibrium firms invest more budget on quality when their budgets are close to each other. However, as the gap between budgets widens, competition in qualities becomes less effective and firms spend more of their budget on seeding.
- Competitive diffusion in social networks: Quality or seeding?, with A. Fazeli and A. Jadbabaie, IEEE Transactions on Control of Network Systems, vol. 2, pp. 665- 675, 2017.