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, 〉 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 ( n 2) largest bi-symmetrical amounts ij which can be transferred from player into j while remaining in the strong -core. The associated payoff vector is a midpoint of the -core segment in i–j 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. ... mehrIn cases where the candidate does not pass the (pre)-kernel check, the function is called a further time with additional informations about the game. Afurther 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 i–j 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.