On finding the nucleolus of an \(n\)-person cooperative game (Q810387): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:16, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On finding the nucleolus of an \(n\)-person cooperative game |
scientific article |
Statements
On finding the nucleolus of an \(n\)-person cooperative game (English)
0 references
1991
0 references
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.
0 references
computational method
0 references
nucleolus
0 references