2011 | OriginalPaper | Chapter
Social Context Congestion Games
Authors : Vittorio Bilò, Alessandro Celi, Michele Flammini, Vasco Gallotti
Published in: Structural Information and Communication Complexity
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider the social context games introduced in [2], where we are given a classical game, an undirected social graph expressing knowledge among the players and an aggregating function. The players and strategies are as in the underlying game, while the players costs are computed from their
immediate costs
, that is the original payoffs in the underlying game, according to the neighborhood in the social graph and to the aggregation function. More precisely, the
perceived cost
incurred by a player is the result of the aggregating function applied to the immediate costs of her neighbors and of the player herself. We investigate social context games in which the underlying games are linear congestion games and Shapley cost sharing games, while the aggregating functions are min, max and sum. In each of the six arising cases, we first completely characterize the class of the social network topologies guaranteeing the existence of pure Nash equilibria. We then provide optimal or asymptotically optimal bounds on the price of anarchy of 22 out of the 24 cases obtained by considering four social cost functions, namely, max and sum of the players’ immediate and perceived costs. Finally, we extend some of our results to multicast games, a relevant subclass of the Shapley cost sharing ones.