×

A value for games restricted by augmenting systems. (English) Zbl 1232.91024

The paper considers cooperative transferable utility games in which only certain coalitions are allowed to form. The seminal paper in this line of research analyses games with graph-restricted communication (cf. [R. B. Myerson, Math. Oper. Res. 2, 225–229 (1977; Zbl 0402.90106)]). In such games, players can cooperate if and only if they are connected in the communication graph and a solution can be obtained by applying standard solutions to a restricted game that takes account of the cooperation restrictions. Another type of model is determined by the position of the players in a so-called permission structure (cf. [R. P. Gilles, G. Owen and R. van den Brink, Int. J. Game Theory 20, No. 3, 277–293 (1992; Zbl 0764.90106)]). In this setup, the authors assume that the restrictions to the cooperation are given by a combinatorial structure called an augmenting system that generalizes both the previous models. In this way, two important lines of research in the literature are unified. Augmenting systems were introduced in [J. M. Bilbao, SIAM J. Discrete Math. 17, No. 1, 122–133 (2003; Zbl 1066.91009)].
In the current paper, a couple of nice examples taken from the real life motivate the model. Let \(N\) be a finite set. An augmenting system is a set system \((N,F)\) with the following properties: (1) \(\emptyset \in F\), (2) if \(S, T \in F\) with \(S\cap T \neq \emptyset\), then \(S \cup T \in F\), and (3) for \(S, T \in F\) with \(S\subset T \) there exists \(i\in T\backslash S\) such that \(S \cup \{i\} \in F\). Augmenting systems also generalize the set systems called antimatroids (cf. [H. Edelman and R. E. Jamison, Geom. Dedicata 19, 247–270 (1985; Zbl 0577.52001)]). The so-called \(\alpha\)-value is considered and it is a generalization of the Myerson value for games with communication restricted by a graph and the well-known Shapley value (cf. [L. S. Shapley, “A value for \(n\)-person games,” Contrib. Theory of Games, II, Ann. Math. Stud. No. 28, 307–317 (1953; Zbl 0050.14404)]) for games restricted by permission structures. The \(\alpha\)-value of a cooperative game with an augmenting system is the Shapley value of the so-called restricted game. A characterization is obtained for the \(\alpha\)-value by using the properties of component efficiency, loop-null, and balanced contributions and hence a result is obtained with the same flavour of the results in [Myerson, loc.cit.] and [M. Slikker, Int. J. Game Theory 33, No. 4, 505–514 (2005; Zbl 1091.91006)]. Tools from discrete mathematics are used in this extended setting. Arguments of induction are used in the main proofs and also the representation of cooperative games in terms of the well-known unanimity games. A second characterization is proposed by using a property of consistency inspired by the results in [S. Hart and A. Mas-Colell, Econometrica 57, No. 3, 589–614 (1989; Zbl 0675.90103)]. Moreover, they implement a direct algorithm to compute the \(\alpha\)-value that is written with Mathematica [S. Wolfram, The Mathematica Book. Cambridge: Cambridge University Press (1999; Zbl 0924.65002)] and whose computational complexity is polynomial in the cardinality of the feasible coalitions. The algorithm is based on an explicit formula given by Bilbao (loc. cit., 2003).

MSC:

91A12 Cooperative games

Software:

Mathematica
PDFBibTeX XMLCite
Full Text: DOI Link