[Date Prev][Date Next][Date Index]
talk announcement Mon, 18 May 2015 - Wolfgang Dvorak "Welfare Maximization with Friends-of-Friends Network Externalities"
the Institute for Information Systems cordially invites you to the following
Speaker: Wolfgang Dvorak
University of Vienna, Faculty of Computer Science, Austria
DATE: Monday, 18 May 2015
TIME: 3 pm s.t.
VENUE: Seminarroom Goedel
TITLE: Welfare Maximization with Friends-of-Friends Network Externalities
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:
With kind support of the Vienna Center for Logic and Algorithms (VCLA) and the
Wolfgang Pauli Institut (WPI).