Show simple item record

Generating trading agent strategies: Analytic and empirical methods for infinite and large games.

dc.contributor.authorReeves, Daniel M.
dc.contributor.advisorWellman, Michael P.
dc.date.accessioned2016-08-30T15:57:03Z
dc.date.available2016-08-30T15:57:03Z
dc.date.issued2005
dc.identifier.urihttp://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqm&rft_dat=xri:pqdiss:3192760
dc.identifier.urihttps://hdl.handle.net/2027.42/125482
dc.description.abstractA <italic>Strategy Generation Engine</italic> is a system that reads a description of a game or market mechanism and outputs strategies for participants. Ideally, this means a game solver---an algorithm to compute Nash equilibria. This is a well-studied problem and very general solutions exist, but they can only be applied to small, finite games. This thesis presents methods for finding or approximating Nash equilibria for infinite games, and for intractably large finite games. First, I define a broad class of one-shot, two-player infinite games of incomplete information. I present an algorithm for computing best-response strategies in this class and show that for many particular games the algorithm can be iterated to compute Nash equilibria. Many results from the game theory literature are reproduced---automatically---using this method, as well as novel results for new games. Next, I address the problem of finding strategies in games that, even if finite, are larger than what any exact solution method can address. Our solution involves (1) generating a small set of candidate strategies, (2) constructing via simulation an approximate payoff matrix for the simplification of the game restricted to the candidate strategies, (3) analyzing the empirical game, and (4) assessing the quality of solutions with respect to the underlying full game. I leave methods for generating candidate strategies domain-specific and focus on methods for taming the computational cost of empirical game generation. I do this by employing Monte Carlo variance reduction techniques and introducing a technique for approximating many-player games by reducing the number of players. We are additionally able to solve much larger payoff matrices than the current state-of-the-art solver by exploiting symmetry in games. I test these methods in small games with known solutions and then apply them to two realistic market scenarios: Simultaneous Ascending Auctions (SAA) and the Trading Agent Competition (TAC) travel-shopping game. For these domains I focus on two key price prediction approaches for generating candidate strategies for empirical analysis: self-confirming price predictions and Walrasian equilibrium prices. We find that these are highly effective strategies in SAA and TAC, respectively.
dc.format.extent205 p.
dc.languageEnglish
dc.language.isoEN
dc.subjectAnalytic
dc.subjectEmpirical
dc.subjectGame Theory
dc.subjectGenerating
dc.subjectInfinite Games
dc.subjectLarge
dc.subjectMethods
dc.subjectNash Equilibrium
dc.subjectStrategies
dc.subjectTrading Agent
dc.subjectTrading Agents
dc.titleGenerating trading agent strategies: Analytic and empirical methods for infinite and large games.
dc.typeThesis
dc.description.thesisdegreenamePh.D.
dc.description.thesisdegreedisciplineApplied Sciences
dc.description.thesisdegreedisciplineComputer science
dc.description.thesisdegreegrantorUniversity of Michigan, Horace H. Rackham School of Graduate Studies
dc.description.bitstreamurlhttp://deepblue.lib.umich.edu/bitstream/2027.42/125482/2/3192760.pdf
dc.owningcollnameDissertations and Theses (Ph.D. and Master's)


Files in this item

Show simple item record