Inheritance of properties in communication situations (Q1423661): Difference between revisions

Traditionally, cooperative games are studied in the context in which agents can communicate with each other; as a result, in principle, every subset \(S\) of the set \(N\) of all agents can be a coalition, and a game can be described by describing, for each such set, the amount \(v(S)\) that players from this set \(S\) can guarantee to win if they act together. Myerson was the first to systematically study cooperative situations in which communications are limited. The description of which pairs of agents can communicate forms a graph \(L\). Due to communication limitations, for a set \(S\), instead of the original value \(v(S)\), we can only guarantee the value \(v^L(S)=\sum_C v(C)\), where \(C\) are \(L\)-induced components of \(S\), i.e., components within which players can communicate with each other. Sometimes, the original cooperative game \(v\) has useful properties that enhance its solution. A natural question is: under what conditions on the graph \(L\) are these properties inherited by the graph-restricted game \(v^L\)? Previously, such inheritance results were only known for super-additivity (\(v(S_1\cup S_2)\geq v(S_1)\cup v(S_2)\)) and convexity (\(S_1\subseteq S_2\) implies \(v(S_1)-v(S_1-\{i\})\geq v(S_2)-v(S_2-\{i\})\)). The author starts with a reasonable property that a Shapley vector -- one of the most widely used solution concepts -- belongs to the core, i.e., cannot be improved by any coalition. Alas, the only graphs for which this property is always inheritable are the two trivial ones: the empty graph (no communications at all) and the complete graph (no restrictions on communication). The property that the Shapley vector belongs to the core both for this game and for all its subgames is somewhat easier to inherit: it is inherited by star graphs. The author analyzed the inheritance of other properties such as average convexity, when \(S_1\subset S_2\) implies that \(\sum\limits_{i\in S_1} [v(S_1)-v(S_1-\{i\})]\geq \sum\limits_{i\in S_1} [v(S_2)-v(S_2-\{i\})]\), i.e., crudely speaking, when the average contribution of the players to a coalition increases when the coalition grows.