A Value for Games Restricted by Augmenting Systems

Abstract

This paper deals with cooperative games in which only certain coalitions are allowed to form. There have been previous models developed to confront the problem of nonfeasible coalitions. Games restricted by a communication graph are games in which the feasible coalitions are those that induce connected subgraphs. Another type of model is determined by the positions of the players in a so-called permission structure. In this paper, the restrictions to the cooperation are given by a combinatorial structure called an augmenting system which generalizes antimatroid structure and the system of connected subgraphs of a graph. Furthermore, the class of augmenting systems includes the conjunctive and disjunctive systems derived from a permission structure. The value α is a generalization of the Myerson value for games restricted by graphs and the Shapley value for games restricted by permission structures. The main results of the paper are the characterization of the value α for augmenting structures by using component efficiency, loop-null, and balanced contributions, and another characterization by consistency of this value. Furthermore, we implement a direct algorithm to compute this value by using the outputs of the original game.