[Date Prev][Date Next][Date Index]

*From*: Eva Nedoma <eva@kr.tuwien.ac.at>*Date*: Mon, 4 May 2015 13:27:58 +0200 (CEST)

Dear all, the Institute for Information Systems cordially invites you to the following talk: ====================================================================== Speaker: Wolfgang Dvorak University of Vienna, Faculty of Computer Science, Austria http://homepage.univie.ac.at/wolfgang.dvorak/ ====================================================================== DATE: Monday, 18 May 2015 TIME: 3 pm s.t. VENUE: Seminarroom Goedel ====================================================================== TITLE: Welfare Maximization with Friends-of-Friends Network Externalities ====================================================================== 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) ======================================================================= With kind support of the Vienna Center for Logic and Algorithms (VCLA) and the Wolfgang Pauli Institut (WPI).