With the advent of social networks such as Facebook and LinkedIn, and online offers/deals web sites, network externalities raise the possibility of marketing and advertising to users based on influence they derive from their neighbors in such networks. Indeed, a user’s knowledge of which of his neighbors “liked” the product, changes his valuation for the product. Much of the work on the mechanism design under network externalities has addressed the setting when there is only one product. We consider a more natural setting when there are multiple competing products, and each node in the network is a unit demand agent.

We first consider the problem of welfare maximization under various different
types of externality functions. Specifically we get a O(log n log(nm))
approximation for concave externality functions, 2O(d)-approximation for convex
externality functions that are bounded above by a polynomial of degree d, and we
give a O(log^{3} n)-approximation when the externality function is
submodular. Our techniques involve formulating non-trivial linear relaxations in
each case, and developing novel rounding schemes that yield bounds vastly
superior to those obtainable by directly applying results from combinatorial
welfare maximization.

We then consider the problem of Nash equilibriumwhere each node in the network is a player whose strategy space corresponds to selecting an item. We develop tight characterization of the conditions under which a Nash equilibrium exists in this game. Lastly, we consider the question of pricing and revenue optimization when the users in the network are selfish agents, and their private information is the vector of valuations for different items. We show that for single parameter settings (when an agents’s intrinsic valuation for every item can be described using one parameter), all our approximation results for welfare maximization extend to revenue maximization. For the multi-parameter setting, we design an O(1)-approximate revenue optimal mechanism for IID agents, when the action of a single agent does not affect the externality enjoyed by remaining agents.

}, author = {Anand Bhalgat and Sreenivas Gollapudi and Kamesh Munagala}, booktitle = {Proc. of ACM Conference on Electronic Commerce (EC)}, month = {June}, publisher = {ACM}, title = {Mechanisms and Allocations with Positive Network Externalities}, url = {http://research.microsoft.com/apps/pubs/default.aspx?id=161962}, year = {2012}, }