A big challenge in artificial intelligence (AI) is creating autonomous agents that can interact well with other agents over extended periods of time. Most previously developed algorithms have been designed in the context of Repeated Games, environments in which the agents interact in the same scenario repeatedly. However, in most real-world interactions, relationships between people and autonomous agents consist of sequences of distinct encounters with different incentives and payoff structures. Therefore, in this thesis, we consider Interaction Games, which model interactions in which the scenario changes from encounter to encounter, often in ways that are unanticipated by the players. For example, in Interaction Games, the magnitude of payoffs as well as the structure of these payoffs can differ across encounters. Unfortunately, while there have been many algorithms developed for Repeated Games, there are no known algorithms for playing Interaction Games. Thus, we have developed two different algorithms, augmented Fictitious Play (aFP) and augmented S# (Aug-S#), for playing these games. These algorithms are designed to generalize Fictitious Play and S# algorithms, which were previously created for Repeated Games, to the more general kinds of scenarios modeled by Interaction Games. This thesis primarily focuses on the evaluation of these algorithms. We first analyze the behavioral and performance properties of these algorithms when associating with other autonomous algorithms. We then report on the results of a user study in which these algorithms were paired with people in two different Interaction Games. Our results show that while the generalized algorithms demonstrate many of the same properties in Interaction Games as they do in Repeated Games, the complexity of Interaction Games appear to alter the kinds of behaviors that are successful, particularly in environments in which communication between players is not possible.



College and Department

Physical and Mathematical Sciences; Computer Science



Date Submitted


Document Type





repeated interactions, game theory, machine learning