Knowledge and Games: Theory and Implementation

This dissertation offers a computer science perspective on questions about knowledge and interaction, presenting ways to equip artificial agents with the corresponding reasoning abilities. We limit general frameworks of epistemic logic and game theory to obtain practical implementations grounded in theory.

The fundamental idea of the main part of the dissertation (chapters 1 to 3) is to view computer processes, or otherwise distributed programs, as players in a game-theoretic setting with incomplete information. As such, they could communicate to acquire information and perform game-theoretic algorithms.

In Chapter 1, we lay the technical foundations for the execution of synchronous communication, and thus the achievement of common knowledge, between computer processes representing players. To this end, we study dialects of the process calculus CSP, which is available in the form of programming languages. We argue that, for our purposes, the process system must have a certain symmetry, and we demonstrate that in order to meet this requirement, a certain “guard” construct must be present in the language. Since this construct is not commonly present, our result is practically sufficient to identify a unique programming language suitable for our purposes.

In Chapter 2, we define what we call “interaction structures,” a concrete class of communication networks. We outline the types of communication scenarios we focus on and study properties of the knowledge resulting from this type of communication. These properties can be used to simplify reasoning about knowledge in our setting.

In Chapter 3, we study games with an interaction structure that allows players to communicate their preferences, assuming that each player initially knows only their own preferences. We look at the results of repeated elimination of strictly dominated strategies that can be obtained in any given communication state. Insights from the previous chapters are used to provide an epistemic foundation for our results and to show a distributed algorithm that implements the procedures locally in each player process.

After this main part of the dissertation, we proceed with more loosely related satellite chapters.

Chapter 4 is conceptually close to the main part of the dissertation, with the difference that it focuses on a centralized rather than a distributed approach, and considers computer games instead of games in the strict game-theoretic sense. We argue that reasoning about knowledge, including knowledge of others' knowledge, plays a crucial role in strategic and social interaction in real life. We review existing literature and games that simulate such interaction and demonstrate that this aspect is currently neglected. We provide concrete scenarios from existing computer games that could benefit from the integration of such reasoning techniques, and substantiate one of them with a description of a simple implementation intended for experimental evaluation.

In Chapter 5, we propose an abstract approach to coalition formation that focuses on simple rules for merging and splitting groups. We identify conditions under which any sequence of these rules results in a unique partition. Our main conceptual tool is a specific definition of a stable partition. The results are parameterized by a preference relation between the partitions of a group of players and are naturally applicable to coalition TU-games, hedonic games, and exchange economy games.

In Chapter 6, we extend the existing framework of mixed multi-unit combinatorial auctions with time constraints, present an expressive bidding language, and show how the problem of determining the winner of such auctions can be solved through an integer programming implementation. Mixed multi-unit combinatorial auctions are auctions where bidders can bid on combinations of transformations of goods rather than just on the goods themselves. For example, a transformation might take dough and water and produce bread. This model holds significant potential for applications in the field of supply chain formation.

Finally, in Chapter 7, we offer a glimpse into possible future directions for the implementation of epistemic logic.