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.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.subjectGame Theory
dc.subjectInfinite Games
dc.subjectNash Equilibrium
dc.subjectTrading Agent
dc.subjectTrading Agents
dc.titleGenerating trading agent strategies: Analytic and empirical methods for infinite and large games.
dc.description.thesisdegreedisciplineApplied Sciences
dc.description.thesisdegreedisciplineComputer science
dc.description.thesisdegreegrantorUniversity of Michigan, Horace H. Rackham School of Graduate Studies
dc.owningcollnameDissertations and Theses (Ph.D. and Master's)

Files in this item

Show simple item record

Remediation of Harmful Language

The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.


If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.