Invited Session Fri.1.MA 043

Friday, 10:30 - 12:00 h, Room: MA 043

Cluster 8: Game theory [...]

Algorithmic game theory


Chair: Azarakhsh Malekian



Friday, 10:30 - 10:55 h, Room: MA 043, Talk 1

Brendan Lucier
Strategyproof mechanisms for competitive influence in social networks

Coauthors: Allan Borodin, Mark Braverman, Joel Oren


Motivated by models of competitive influence spread in networks, we study mechanisms for allocating nodes to self-interested agents with negative externalities. For example, a social network provider may wish to allow advertisers to provide special offers to influential individuals. The advertisers benefit in that product adoption may spread through the network, but a competing product may adversely impact the rate of adoption.
We construct a mechanism for distributing advertisement space to two competing players. The mechanism is not specific to any particular model for influence spread; it applies to most previously-studied models. Our mechanism yields a constant factor approximation to the optimal total product influence, and is strategyproof in the sense that advertisers maximize their expected total product diffusion by reporting their advertising demands truthfully. We also discuss extensions of our mechanism to three or more players under additional restrictions that are satisfied by many models studied in the literature.



Friday, 11:00 - 11:25 h, Room: MA 043, Talk 2

Nicole Immorlica
Social networks and segregation

Coauthors: Christina Brandt, Gautam Kamath, Robert D. Kleinberg


Social networks form the basic medium of social interaction. The structure of these networks significantly impacts and co-evolves with the behavioral patterns of society. Important societal outcomes - the global reach of an epidemic, the degree of cooperation in an online network, the adoption of new technologies - are dictated by social networks.
In this talk, we explore the impact of networks on segregation. In 1969, economist Thomas Schelling introduced a landmark model of racial segregation in which individuals move out of neighborhoods where their ethnicity constitutes a minority. Simple simulations of Schelling's model suggest that this local behavior can cause global segregation effects. In this talk, we provide a rigorous analysis of Schelling's model on ring networks. Our results show that, in contrast to prior interpretations, the outcome is nearly integrated: the average size of an ethnically-homogenous region is independent of the size of the society and only polynomial in the size of a neighborhood.



Friday, 11:30 - 11:55 h, Room: MA 043, Talk 3

Markus Mobius
Treasure hunt

Coauthors: Szeidl Adam, Phan Tuan


We seed a large real-world social network with binary information and analyze subsequent social learning. A unique feature of our field experiment is that we measure both the pre-existing social networks and the actual conversation
network. Our experiment allows us to test how rational agents behave when processing information that originates within their social network. We find that information decays quickly with social distance and that agents mainly incorporate information within social distance 2. Conversations through common friends do not increase the weight that a subject places on signals from direct friends but linearly increases the weight on signals from indirect friends. This suggests that agents are able to avoid double-counting information from
indirect friends. We propose a simple "streams model'' of social learning that is consistent with the evidence from our experiment.


  personal loans online . Thanks to that, they have a great variety of drugs that can help in these cases. Female Viagra is not an exception.