کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
476430 699468 2006 23 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An LP approach to compute the pre-kernel for cooperative games
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 33, Issue 2, February 2006, Pages 535–557
نویسندگان
,