@inproceedings{MastersThesis,
title={Algorithmic analysis of Regular Repeated Games},
author={Bansal, S.},
year={Master's thesis, Rice University, 2016},
abstract={The problem on computing rational behaviors in multi-agent systems with selfish agents (Games) has become paramount for the analysis of such systems. {\em Nash equilibria} is one of the most central notions of rational behavior. While the problem of computing Nash equilibria in simple games is well understood, the same cannot be said for more complex games. {\em Repeated games} are one such class of games. In this thesis, we introduce {\em regular repeated games} as a model for repeated games with bounded rationality. In regular repeated games, agent strategies are given by weighted (discounted-sum aggregate), non-deterministic B\"uchi transducers. We design an algorithm {\ComputeNash} to compute all Nash equilibria in a regular repeated game. The crux of the algorithm lies in determining if a strategy profile is in Nash equilibria or not. For this it is necessary to compare the discounted sum on one infinite execution with that one other executions. Such relational reasoning has not been studies in the literature before. To this end, we introduce the concept of an {\em $\omega$-regular comparators}. We demonstrate promise of our approach via experimental analysis on case studies: Iterated Prisoner's Dilemma, repeated auctions, and a model of the Bitcoin protocol.}
}