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

作　　者：Yajing Liu Edwin K.P.Chong Ali Pezeshki 

机构地区：[1]Department of Electrical and Computer Engineering,Colorado State University,Fort Collins,CO,USA [2]Department of Electrical and Computer Engineering&Department of Mathematics,Colorado State University,Fort Collins,CO,USA

出　　处：《Journal of Control and Decision》2018年第1期1-18,共18页控制与决策学报（英文）

基　　金：NSF and Division of Computing and Communication Foundations[grant number CCF-1422658];the CSU Information Science and Technology Center(ISTeC)。

摘　　要：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 1/(1+c)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 bounding results of Vetta for non-cooperative system,thus establishing provable performance guarantees for the social-aware Nash equilibria.For the second type of grouping we consider,the set of users is partitioned into l disjoint groups,where the users within a group cooperate to maximise their group utility function,giving rise to the notion of group Nash equilibrium.In this case,each group can be viewed as a new user with vector-valued actions,and a 1/2 bound for the performance of group Nash equilibria follows from the result of Vetta.But as we show tighter bounds involving curvature can be established.By defining the group curvature cki associated with group i with ki users,we show that if the social utility function is nondecreasing and submodular,then any group Nash equilibrium achieves at least 1/(1+max1≤i≤l cki)of the optimal social utility,which is tighter than that for the case without grouping.As a special case,if each user has the same action space,then we have that any group Nash equilibrium achieves at least 1/

关 键 词：Group Nash equilibrium social-aware Nash equilibrium SUBMODULARITY utility system 

分 类 号：R57[医药卫生—消化系统]