Welfare Maximization with Friends-of-Friends Network Externalities

VCLA and WPI will host a talk by Wolfgang Dvorak on May 18, 2015.

ABSTRACT

Online social networks allow the collection of large amounts of data about the influence between users connected by a friendship-like relationship. When distributing items among agents forming a social network, this information allows us to exploit network externalities that each agent receives from his neighbors owning the same item. In this talk we consider Friends-of-Friends (2-hop) network externalities, i.e., externalities that not solely depend on the neighbors that get the same item but also on neighbors of neighbors. For these externalities we study a setting where multiple different items are assigned to unit-demand agents. Specifically, we study the problem of welfare maximization under different types of externality functions and as these problems are NP-hard we investigate approximation algorithms. To this end we provide two kind of results. (1) Hardness of Approximation: We show that welfare maximization is APX-hard under the different types of externality functions, i.e. for each type of externality functions there is a constant such that no polynomial time algorithm can guarantee a better approximation ratio. In particular there is no Polynomial-time approximation scheme for any of these problems. (2) Approximation Algorithms: Let n be the number of agents and m be the number of items. We give the following polynomial time algorithms. (i) An O(sqrt n)-approximation algorithm for general concave externality functions based on a combinatorial argument; (ii) an O(log m)-approximation algorithm for linear externality functions based on a Linear Programming relaxation and randomized rounding; and (iii) an 5/18 (1-1/e)-approximation algorithm for 2-hop step function externalities based on submodular function maximization. The talk is based on joint work with Sayan Bhattacharya, Monika Henzinger and Martin Starnberger (STACS 2105 and follow up work). (paper available at: http://drops.dagstuhl.de/opus/volltexte/2015/4906/pdf/6.pdf)