Friendship, Altruism, and Reward Sharing in Stable Matching and Contribution Games

Details Friendship, Altruism, and Reward Sharing in Stable Matching and Contribution Games Friendship, Altruism, and Reward Sharing in Stable Matching and Contribution Games

2012-04-25

arxiv.org/abs/1204.5780v1

Computer Science

Computer Science and Game Theory

Scientific paper

We study stable matching problems in networks where players are embedded in a social context, and may incorporate friendship relations or altruism into their decisions. Each player is a node in a social network and strives to form a good match with a neighboring player. We consider the existence, computation, and inefficiency of stable matchings from which no pair of players wants to deviate. When the benefits from a match are the same for both players, we show that incorporating the well-being of other players into their matching decisions significantly decreases the price of stability, while the price of anarchy remains unaffected. Furthermore, a good stable matching achieving the price of stability bound always exists and can be reached in polynomial time. We extend these results to more general matching rewards, when players matched to each other may receive different utilities from the match. For this more general case, we show that incorporating social context (i.e., "caring about your friends") can make an even larger difference, and greatly reduce the price of anarchy. We show a variety of existence results, and present upper and lower bounds on the prices of anarchy and stability for various matching utility structures. Finally, we extend most of our results to network contribution games, in which players can decide how much effort to contribute to each incident edge, instead of simply choosing a single node to match with.

Affiliated with

Also associated with

No associations

Rating

Friendship, Altruism, and Reward Sharing in Stable Matching and Contribution Games 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 Friendship, Altruism, and Reward Sharing in Stable Matching and Contribution Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Friendship, Altruism, and Reward Sharing in Stable Matching and Contribution Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-313126