Computing an Element in the Lexicographic Kernel of a Game |
| |
Authors: | Ulrich Faigle Walter Kern Jeroen Kuipers |
| |
Institution: | 1. Zentrum für Angewandte Informatik, Universit?t zu K?ln, Weyertal 80, 50931, Koln, Germany 2. Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, P.O. Box 217, 7500, AE, Enschede, Netherlands 3. Department of Mathematics, Maastricht University, P.O. Box 616, 6200, MD, Maastricht, Netherlands
|
| |
Abstract: | The lexicographic kernel of a game lexicographically maximizes the surplusses s
ij
(rather than the excesses as would the nucleolus) and is contained in both the least core and the kernel. We show that an element in the lexicographic kernel can be computed efficiently, provided we can efficiently compute the surplusses s
ij
(x) corresponding to a given allocation x. This approach improves the results in Faigle et al. (in Int J Game Theory 30:79–98, 2001) and allows us to determine a kernel element without appealing to Maschler transfers in the execution of the algorithm.We thank the referees for clarifying the presentation of the proof of Proposition 2.1. |
| |
Keywords: | Kernel Lexicographic Computational complexity |
本文献已被 SpringerLink 等数据库收录! |
|