Seitz, G. (2011). Logics for coalitional games of imperfect information [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-43434
Coalitional games serve as a model for multi-agent systems in which the agents have the possibility to form coalitions in order to achieve certain goals. Alternating-Time Temporal Logic (ATL) is a well-established logic for the formalization of such games in the case that the players always have perfect information about the actual state of the game. Regarding games of imperfect information no such "standard" logic seems to exist, but several approaches can be found in recent literature.<br />In this thesis we discuss and compare some of these approaches with respect to expressivity, complexity, and problems. As it turns out, in the case of memoryless agents some very expressive logics exist which allow one to describe various notions of strategic abilities in coalitional games.<br />Quite on the contrary, the assumption of perfect recall soon leads to the problem that reasonably meaningful logics for such games are undecidable. As our own contribution to the topic, we present an attempt to defuse this problem by approximating such an undecidable logic by decidable ones.