Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Contribution Games in Social Networks

Speaker  Elliot Anshelevich

Affiliation  Rensselaer Polytechnic Institute

Host  Yuval Peres

Duration  00:54:50

Date recorded  3 November 2010

We consider network contribution games, where each agent in a social network has a budget of effort that it can contribute to different collaborative projects or relationships. Depending on the contribution of the involved agents a relationship will flourish or drown, and to measure the success we use a reward function for each relationship. Every agent is trying to maximize the reward from all relationships that it is involved in. We consider pairwise equilibria of this game, and characterize the existence, computational complexity, and quality of equilibrium based on the types of reward functions involved. For example, when all reward functions are concave, we prove that the price of anarchy is at most 2. For convex functions the same only holds under some special but very natural conditions. A special focus of the talk are minimum effort games, where the reward of a relationship depends only on the minimum effort of any of the participants. Finally, we show tight bounds for approximate equilibria and convergence of dynamics in these games.

©2010 Microsoft Corporation. All rights reserved.
> Contribution Games in Social Networks