基于Fenchel-Moreau共轭方法的预核/预核仁计算

摘要

Computing the (pre-)nucleolus of a coalitional game with transferable utility (TU game) is generally NP-hard. Therefore, no universal polynomial-time algorithm exists. However, polynomial-time algorithms exist for specific game classes. The most general approach in the literature is based on the ellipsoid method and Maschler’s approximation scheme. In contrast, we propose polynomial-time solvability by using a Fenchel-Moreau conjugation-based approach from convex analysis that applies the method of Meinhardt (2013) to compute a pre-kernel element. This method not only allows the computation of the pre-nucleolus for game classes with a singleton pre-kernel with a runtime complexity of O(n 3). It also works for game classes with a set-valued pre-kernel whenever the pre-nucleolus is a vertex or a separated point within the pre-kernel set. Finally, we focus on the replication of the pre-nucleolus in the sense of Meinhardt (2024) for a class of related games to demonstrate the versatility of the Fenchel-Moreau conjugation-based approach while referring to group algebra.