An LP approach to compute the pre-kernel for cooperative games

We present an algorithm to compute the (pre)-kernel of a TU-game 〈N,ν〉〈N,ν〉 with a system of n2+1 linear programming problems. In contrast to the algorithms using convergence methods to compute a point of the (pre)-kernel the emphasis of the chosen method lies not on efficiency and guessing good starting points but on computing large parts or in good cases the whole (pre)-kernel of a game. The chosen algorithm computes on a first step by relying on linear programming the n2 largest bi-symmetrical amounts δijε which can be transferred from player ii to jj while remaining in the strong εε-core. The associated payoff vector is a midpoint of the εε-core segment in ii–jj direction and is therefore a candidate that satisfies the bisection property. From these results we can determine in a sophisticated pattern-matching procedure the constraints which are needed to construct the final linear programming problem for computing at least a (pre)-kernel point of the game. From the derived final linear program large parts or the whole (pre)-kernel can be easily calculated. Finally, the program checks if the computed (pre)-kernel candidate belongs to the (pre)-kernel. In cases where the candidate does not pass the (pre)-kernel check, the function is called a further time with additional informations about the game. A further call could be necessary if the intersection set of the n2 solution sets is empty and no correction of the final LP is applied for, in this case, for at least one distinct pair of players the largest bi-symmetrical transfer is of no importance to compute a (pre)-kernel point, that is, no candidate of the final linear problem satisfies the bisection property. This implies that at least one largest bi-symmetrical transfer δijε is greater than the maximal transfer in ii–jj direction that is possible at a (pre)-kernel point y⇀ while remaining in the core, that is, δijε>δijε(y⇀), with y⇀∈K*(Γ). Hence, if the solution intersection set is non-empty, then all payoff vectors in the intersection set possess the bisection property and are therefore (pre)-kernel elements. The (pre)-kernel of a TU-game with an empty core can be computed, for instance, by providing the epsilon value for the least-core as an additional information.