Performance bounds for Nash equilibria in submodular utility systems with user groups

It is shown that for a valid non-cooperative utility system, if the social utility function is submodular, then any Nash equilibrium achieves at least 1 / 2 of the optimal social utility, subject to a function-dependent additive term. Moreover, if the social utility function is nondecreasing and submodular, then any Nash equilibrium achieves at least of the optimal social utility, where c is the curvature of the social utility function. In this paper, we consider variations of the utility system considered by Vetta, in which users are grouped together. Our aim is to establish how grouping and cooperation among users affect performance bounds. We consider two types of grouping. The first type is from a previous paper, where each user belongs to a group of users having social ties with it. For this type of utility system, each user’s strategy maximises its social group utility function, giving rise to the notion of social-aware Nash equilibrium. We prove that this social utility system yields to the boundin...