dc.contributor.advisor Chaudhuri, Swarat Bansal, Suguman 2017-07-31T18:56:26Z 2017-07-31T18:56:26Z 2016-12 2016-09-15 December 2016 Bansal, Suguman. "Algorithmic analysis of Regular repeated games." (2016) Master’s Thesis, Rice University. https://hdl.handle.net/1911/95650. https://hdl.handle.net/1911/95650 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. application/pdf eng Repeated gamesBounded rationalityNash equilibiraNash equilibria computationRegular repeated gamesAutomataComparators Algorithmic analysis of Regular repeated games 2017-07-31T18:56:26Z Thesis Text Computer Science Engineering Rice University Masters Master of Science
﻿