Show simple item record

dc.contributor.advisor Chaudhuri, Swarat
dc.creatorBansal, Suguman
dc.date.accessioned 2017-07-31T18:56:26Z
dc.date.available 2017-07-31T18:56:26Z
dc.date.created 2016-12
dc.date.issued 2016-09-15
dc.date.submitted December 2016
dc.identifier.citation Bansal, Suguman. "Algorithmic analysis of Regular repeated games." (2016) Master’s Thesis, Rice University. https://hdl.handle.net/1911/95650.
dc.identifier.urihttps://hdl.handle.net/1911/95650
dc.description.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.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectRepeated games
Bounded rationality
Nash equilibira
Nash equilibria computation
Regular repeated games
Automata
Comparators
dc.title Algorithmic analysis of Regular repeated games
dc.date.updated 2017-07-31T18:56:26Z
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Computer Science
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Masters
thesis.degree.name Master of Science


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record