On finding the nucleolus of an \(n\)-person cooperative game (Q810387): Difference between revisions

The first efficient algorithm to compute the nucleolus was proposed by \textit{E. Kohlberg} [SIAM J. Appl. Math. 23, 34--39 (1972; Zbl 0243.90057)], who showed that it is sufficient to solve a single linear programming (LP) problem for that. This method and its modifications work fine for many reasonable games (and examples are given, e.g., in a standard textbook by \textit{G. Owen} [Game theory. 2nd ed. Orlando etc.: Academic Press, Inc. (1982; Zbl 0544.90103)]), but when the number of players \(n\) increases, an additional computational problem appears: the coefficients of a related LP problem have a very wide range, and so due to finite precision of a computer we cannot use normal real numbers or even double precision reals. Another algorithm was proposed by \textit{M. Maschler}, \textit{B. Peleg} and \textit{L. S. Shapley} [Math. Oper. Res. 4, 303--338 (1979; Zbl 0426.90097)], who showed how to find a nucleolus by solving several (up to \(4^ n)\) LP problems with coefficients that take only the values \(0,1,-1\). This method also works well for many cases, but \(4^ n\) is too much for big \(n\). The author proposes a new method, where at most \(2^ n\) LP problems with coefficients \(0,1,-1\) have to be solved. Some of these LP problems differ only in one coefficient, and therefore if we have already solved one of them, we can easier solve the other one. Thus the total computation time will be even smaller than \(2^ n\) times the running time of one LP problem.