The relative interior of the base polyhedron and the core (Q5955113)

For cooperative games in the transferable utility form, the paper provides two characterizations for the relative interior of the core to be non-empty, one of them in terms of the prenucleolus and the other in terms of the new concept of minimum no-blocking payoff. Let \({\mathcal N}\) denote the collection of subsets of \(N=\{1,2,\dots, n\}\) and \(v:{\mathcal N}\to \mathbb{R}_+\). \(\Gamma= \{N,v (\cdot)\}\) describes a cooperative game. The core of the game \(\Gamma\) is given by: \[ C(\Gamma)= \left\{x \in\mathbb{R}^n_+ :\sum_{i\in S}x^i\geq v(S) \text{ for all }S\neq \emptyset,\;S\in {\mathcal N},\sum_{i\in N} x^i=v(N) \right\} \] Let \(x\) be an allocation for \(N\), i.e., \(x\in\mathbb{R}^n_+\) and \(\sum_{j \in N}x^i= v(N)\). The excess of \(S\) against \(x\) is \(e(S,x)= v(S)-\sum_{i\in S} x^i\). Let \(\Theta(x)\) denote the \((2^n-1)\)-dimensional vector of excesses of all possible (non-empty) coalitions arranged in a decreasing order and, so that, if two coalitions have equal excess then they are arranged decreasing by coalition size and then lexicographically decreasing by player indices. The prenucleolus of a game is the unique allocation \(x\) for \(N\) such that, for any other allocation \(y\neq x\), there exists some \(1\leq j\leq 2^n-1\) satisfying \(\Theta_i (x)=\Theta_i (y)\) for all \(i<j\) and \(\Theta_j(x) <\Theta_j(y)\). The minimum no-blocking payoff is defined by \[ V(\Gamma)=\text{Min} \sum_{i\in N} x^i \] \[ \text{s.t. }x\in\mathbb{R}^n_+\quad \text{and} \quad\sum_{i\in S}x^i \geq v(S) \quad \text{for all} \quad S\neq N \] The following two theorems are established: Theorem 1: The relative interior of \(C(\Gamma)\neq \emptyset\) if and only if the first component of the prenucleolus is zero and the second component is negative. Theorem 2: (i) \(C(\Gamma)\neq \emptyset\) if and only if \(v(N)\geq V(\Gamma)\); (ii) the relative interior of \(C(\Gamma) \neq\emptyset\) and only if \(v(N)<V (\Gamma)\). Applications are discussed.