Ron Peretz

We suppose that players in a cooperative game are located within a graph structure, such as a social network or supply route, that limits coalition formation to coalitions along connected subsets within the graph. This in turn leads to a more general study of coalitional games in which there are arbitrary limitations on the collections of coalitions that may be formed. Within this context we define a generalisation of the Shapley value that is studied from an axiomatic perspective. The resulting `graph value' (and `S-value' in the general case) is endogenously asymmetric, with the automorphism group of the graph playing a crucial role in determining the relative values of players.

We study repeated games in which each player i is restricted to (mixtures of) strategies that can recall up to ki stages of history. Characterising the set of equilibrium payoffs boils down to identifying the individually rational level of each player. In contrast to the classic folk theorem, in which players have unrestricted recall, punishing a bounded-recall player may involve correlation between the punishers' actions. We quantify this correlation in terms of the average per-stage mutual information between the punishers' actions conditioned on the punishee's recalled history. The amount of correlation is proportional to the ratio between the recall capacities of the punishers and the punishee times the logarithm of the number of actions in the stage game. Our result extends to an arbitrary number of players and to other models of bounded memory.