The relative interior of the base polyhedron and the core (Q5955113): Difference between revisions

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.