Dominating set games. (Q703283)

This paper presents several representation theorems for the solubility of three cost allocation problems, which are presented as cooperative games. In each problem, a graph \(G = (V, E)\) is given along with a cost function: given \(S \subseteq V\), \(c(S)\) is the cost of \(k\)-dominating the vertices in \(S\), i.e., building a set \(K \subseteq V\) such that every vertex in \(S\) is within distance \(k\) (under an appropriate distance metric) of an element of \(K\). The three problems are associated with three cost functions: given a vector \(w \in \mathbb R^{| V| }\) and a positive integer \(k\): 1) The \textit{rigid dominating set game} requires that \(K \subseteq S\) and that distance is measured along edges within the restriction of \(G\) to \(S\). 2) The \textit{intermediate dominating set game} still requires that \(K \subseteq S\), but allows distance to be measured along any paths in \(G\). 3.) The \textit{relaxed dominating set game} drops the requirement that \(K \subseteq S\). The primary result is a representation theorem that asserts that all three games are soluble (i.e., have non-empty cores) simultaneously.