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