Towards Cooperating in Repeated Interactions Without Repeating Structure

June 04, 2020

Huy Pham MS Defense

Huy Pham MS Defense June 10th at 9:30 AM via Zoom Advisor: Jacob Crandall


A big challenge in artificial intelligence (AI) is creating autonomous agents that caninteract well with other agents over extended periods of time. Most previously developedalgorithms have been designed in the context of Repeated Games, environments in which theagents interact in the same scenario repeatedly. However, in most real-world interactions,relationships between people and autonomous agents consist of sequences of distinct encounterswith different incentives and payoff structures. Therefore, in this thesis, we consider InteractionGames, 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, themagnitude 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, thereare no known algorithms for playing Interaction Games. Thus, we have developed twodifferent algorithms, augmented Fictitious Play (aFP) and augmented S# (aug-S#), forplaying these games. These algorithms are designed to generalize Fictitious Play and S#algorithms, which were previously created for Repeated Games, to the more general kindsof scenarios modeled by Interaction Games. This thesis primarily focuses on the evaluationof these algorithms. We first analyze the behavioral and performance properties of thesealgorithms when associating with other autonomous algorithms. We then report on theresults of a user study in which these algorithms were paired with people in two differentInteraction Games. Our results show that while the generalized algorithms demonstrate manyof the same properties in Interaction Games as they do in Repeated Games, the complexityof Interaction Games appear to alter the kinds of behaviors that are successful, particularlyin environments in which communication between players is not possible.