Operations Research seminar

Operations Research seminar

Two-step values for games with two-level communication structures

Anna Khmelnitskaya, UT-EWI-DMMP


We consider TU games endowed with both coalition and communication structures, the so-called games with two-level communication structures. In this model a two-level communication structure relates fundamentally to the given coalition structure and consists of a communication graph on the collection of the a priori unions in the coalition structure, as well as a communication graph within each union. The communication structures under scrutiny are given by combinations of graphs of different types, both undirected--arbitrary graphs and cycle-free graphs, and directed--line-graphs with linearly ordered players, rooted forests and sink forests. We introduce two families of two-step values for games with two-level communication structures adapting the two-step procedures staying behind two coalitional values for games with coalition structures, the Owen value introduced in Owen (1977) and the two-step Shapley value introduced in Kamijo (2009), and provide their axiomatic characterizations that have some axioms in common which in turn allows to compare these families. Our approach that is based also on unified treatment of several component efficient values for games with communication structures, called for simplicity graph games, generates two-stage solution concepts that provide consistent application of values for graph games on both levels. The incorporation of different solutions for graph games aims not only to enrich the solution concept for games with two-level graph structures. It also opens a broad diversity of applications impossible otherwise because there exists no universal solution concept for graph games that is applicable to the full variety of possible undirected and directed graph structures. Furthermore, it allows to choose, depending on types of graph structures under scrutiny, the most preferable, in particular, the most computationally efficient combination of values among others suitable

The paper co-authored with Sylvain Beal from University of Besanson and Philippe Solal from the University of Saint-Etienne