Speaker:     Piotr Faliszewski

Affiliation: AGH Institute of Technology (Krakow)

Title:       Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation

Date:        Tuesday, 3 Mar 2015

Time:        5:00 pm

Location:    Owen Glenn building, room 260-321

We consider the following problem: There is a set of items (e.g., movies) and a group of agents (e.g., passengers on a plane); each agent has some intrinsic utility for each of the items. Our goal is to pick a set of K items that maximize the total derived utility of all the agents (i.e., in our example we are to pick K movies that we put on the plane’s entertainment system). However, the actual utility that an agent derives from a given item is only a fraction of its intrinsic one, and this fraction depends on how the agent ranks the item among the chosen, available, ones. We provide a formal specification of the model and provide concrete examples and settings where it is applicable. We show that the problem is hard in general, but we show a number of tractability results for its natural special cases.

Everyone welcome!

Speaker:    Nimrod Talmon

Affiliation: Technical University of Berlin

Title:          Multi-Player Diffusion Games on Graph Classes

Date:          Tuesday, 24 Feb 2015

Time:          5:00 pm

Location:   Owen G. Glenn building, room 260-321

We study competitive diffusion games on graphs introduced by Alon et al. (2010) to model the spread of influence in social networks. Extending results of Roshanbin (2014) for two players, we investigate the existence of pure strategy Nash-equilibria for at least three players on different classes of graphs including paths, cycles, and grid graphs. As a main result, we answer an open question proving that there is no Nash-equilibrium for three players on m × n grids for m and n not smaller than 5.

Everyone welcome!