Forming Coalitions in Normal-Form Games

Abstract

For a given n -person normal-form game G , we consider all possible sets of mutually exclusive and collective exhaustive coalitions of the n players. For each such set of coalitions, we define a coalitional semi-cooperative game Γ of G as one in which 1 ) the coalitions are taken as the players of this new game, 2 ) each coalition tries to maximize the sum of its individual players’ payoffs, and 3 ) the players within a coalition cooperate to do so. The purpose of this paper is to determine an optimal set of coalitions for G for some relevant notion of optimality. To do so, for the payoff matrix of each possible Γ of G , we determine all Greedy Scalar Equilibria (GSEs), where a GSE is an analog of the Nash equilibrium but always exists in pure strategies. For each of these GSEs, we divide the total payoff for each coalition among its members in the same proportions as its members average over the entire payoff matrix of G . Doing so gives n modified individual player payoffs associated with each GSE of all the Γ s . For each of these GSEs, we then compute the geometric mean of its n modified payoffs. A set of coalitions associated with a GSE is deemed optimal for G if the corresponding geometric mean is a maximum among all the GSEs for all the Γ s . An optimal set of coalitions thus incorporates the selfishness of the coalitions via the GSE, while the geometric mean of the redistribution of the players’ payoffs models the cooperation of and the fairness for the individual players.