Hard and Easy k-Typed Compact Coalitional Games: The Knowledge of Player Types Marks the Boundary

Coalitional games model scenarios where rational agents can form coalitions so as to obtain higher worths than by acting in isolation. Once a coalition forms and obtains its worth, the problem of how this worth can be fairly distributed has to be faced. Desirable worth distributions are usually referred to as solution concepts. Recent research pointed out that, while reasoning problems involving such solution concepts are hard in general for games specified in compact form (e.g., graph games), some of them, in particular the core, become tractable when agents come partitioned into a fixed number k of types, i.e., of classes of strategically equivalent players. The paper continues along this line of research, by firstly showing that two other relevant solution concepts, the kernel and the nucle-olus, are tractable in this setting and independently of the specific game encoding, provided worth functions are given as a polynomial-time computable oracles. Then, it analyzes a different setting where games are still k-typed but the actual player partitioning is not a-priori known. Within this latter setting, the paper addresses the question about how efficiently strategic equivalence between pairs of players can be recognized, and reconsiders the computational complexity of the core, the kernel, and the nucleolus. All such problems and notions emerged to be intractable, thereby evidencing that the knowledge of player types marks the boundary of tractability for reasoning about k-typed coalitional games.