Computing the cores of strategic games with punishment–dominance relations

In this paper, we discuss the computational complexity of the strategic cores of a class of n-person games defined by Masuzawa (Int J Game Theory 32:479–483, 2003), which includes economic situations with monotone externality. We propose an algorithm for finding an α-core strategy of any game in this class which, counting the evaluation of a payoff for a strategy profile as one step, terminates after O(n ³· M) operations, where M is the maximum size of a strategy set of any of the n players. The idea underlying this method is based on the property of reduced games. This paper is based on a part of the doctoral dissertation of the author. The author thanks Mikio Nakayama, Masashi Umezawa, William Thomson, an associate editor, and the anonymous referee for their helpful comments, suggestions, and advice. Thanks are also due to Yukihiko Funaki for a comment that led the author to this subject. The author is responsible for errors and inadvertencies.