2010/12/07 by Martin Hoefer, Michal Penn, Hoefer, Martin +7
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #Economic theories and models #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #Multiagent Systems (cs.MA) #cs.DS #cs.GT #cs.MA
paper · pdf · doi:10.48550/arxiv.1012.1547
12 pages, 1 figure
arxiv created 2010/12/07 · openalex publication_date 2010/12/07 · arxiv updated 2010/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the existence and computational complexity of coalitional stability concepts based on social networks. Our concepts represent a natural and rich combinatorial generalization of a recent approach termed partition equilibrium. We assume that players in a strategic game are embedded in a social network, and there are coordination constraints that restrict the potential coalitions that can jointly deviate in the game to the set of cliques in the social network. In addition, players act in a "considerate" fashion to ignore potentially profitable (group) deviations if the change in their strategy may cause a decrease of utility to their neighbors. We study the properties of such considerate equilibria in application to the class of resource selection games (RSG). Our main result proves existence of a considerate equilibrium in all symmetric RSG with strictly increasing delays, for any social network among the players. The existence proof is constructive and yields an efficient algorithm. In fact, the computed considerate equilibrium is a Nash equilibrium for the standard RSG showing that there exists a state that is stable against selfish and considerate behavior simultaneously. In addition, we show results on convergence of considerate dynamics.