Contribution Games in Social Networks

Details Contribution Games in Social Networks Contribution Games in Social Networks

2010-04-11

arxiv.org/abs/1004.1854v4

Algorithmica, Volume 63, 1-2 (2012), pp. 51--90

Computer Science

Computer Science and Game Theory

36 pages, 2 figures

Scientific paper

We consider network contribution games, where each agent in a social network has a budget of effort that he 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 paper 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.

Affiliated with

Also associated with

No associations

Rating

Contribution Games in Social Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Contribution Games in Social Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Contribution Games in Social Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-261937