Finding the Nucleoli of Large Cooperative Games: A Disproof with Counter-Example

Meinhardt, Holger Ingmar (2016): Finding the Nucleoli of Large Cooperative Games: A Disproof with Counter-Example.

Abstract

Nguyen and Thomas (2016) claimed that they have found a method to compute the nucleoli of games with more than 50 players using nested linear programs (LP). Unfortunately, this claim is false. They incorrectly applied the indirect proof by ``A and not B implies A and not A'' to conclude that ``if A then B''is valid. In fact, they prove that a truth implies a falsehood. As established by Meinhardt (2015a), this is a wrong statement. Therefore, instead of giving a proof of their main Theorem 4b, they give a disproof. It comes as no surprise to us that the flow game example presented by these authors to support their arguments is obviously a counter-example of their algorithm. We show that the computed solution by this algorithm is neither the nucleolus nor a core element of the flow game. Moreover, the stopping criterion of all proposed methods is wrong, since it does not satisfy one of Kohlberg's properties (cf. Kohlberg (1971)). As a consequence, none of these algorithms is robust.

• Item Type: MPRA Paper
• Language: English
• Keywords: Transferable Utility Game, Nucleolus, Flow Problem, Propositional Logic; Circular Reasoning (circulus in probando); Indirect Proof; Proof by Contradiction; Proof by Contraposition.
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games

References

E. Kohlberg. On the Nucleolus of a Characteristic Function Game. SIAM Journal of Applied Mathematics, 20:62–66, 1971.

H. I. Meinhardt. The Matlab Game Theory Toolbox MatTuGames Version 0.4: An Introduction, Basics, and Examples. Technical report, Karlsruhe Institute of Technology (KIT), 2013.

H. I. Meinhardt. The Incorrect Usage of Propositional Logic in Game Theory: The Case of Disproving Oneself. ArXiv e-prints, abs/1509.05883, 2015a. URL http://arxiv.org/abs/1509.05883.

H. I. Meinhardt. MatTuGames: A Matlab Toolbox for Cooperative Game Theory. Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany, 2015b. URL http://www.mathworks.com/matlabcentral/fileexchange/ 35933-mattugames. Version 0.8.

Tri-Dung Nguyen and Lyn Thomas. Finding the nucleoli of large cooperative games. European Journal of Operational Research, 248(3):1078 – 1092, 2016. ISSN 0377-2217. doi: http://dx.doi.org/10.1016/j.ejor.2015.08.017. URL http: //www.sciencedirect.com/science/article/pii/S0377221715007547.