Stronger bidding strategies through empirical game-theoretic analysis and reinforcement learning.
dc.contributor.author | Schvartzman, Leonardo Julian | |
dc.contributor.advisor | Wellman, Michael P. | |
dc.date.accessioned | 2016-08-30T16:25:50Z | |
dc.date.available | 2016-08-30T16:25:50Z | |
dc.date.issued | 2009 | |
dc.identifier.uri | http://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:3382400 | |
dc.identifier.uri | https://hdl.handle.net/2027.42/127126 | |
dc.description.abstract | Empirical game-theoretic analysis (EGTA) combines tools from simulation, search, statistics, and game-theoretic concepts to study strategic properties of large multiagent scenarios. One direct application of EGTA techniques is the study of complex market problems which, due to dynamic behavior by many agents, large strategy spaces, incomplete and incrementally revealed information, have generally resisted direct solution. I report applications of EGTA techniques to study the specific problem posed by bidding in continuous double auctions (CDAs). I develop a simulator emulating a generic CDA game commonly found in the literature, and conduct the most comprehensive CDA strategic study yet, covering versions of all major CDA strategies published to date. This EGTA study confirms prior findings about the relative performance of the different strategies. In order to improve upon existing proposals and automate the search for equilibrium strategies, I develop a general methodology to derive new strategy candidates that interleaves EGTA with reinforcement learning (RL). I apply this methodology to the CDA game, and obtain new strategies that are stronger than any other published CDA policy, culminating in a new Nash equilibrium supported by learned strategies only. I evaluate this methodology on a second scenario, the Trading Agent Competition (TAC) Travel game. Building upon an existing simulator and a dataset comprising five years of observations, I apply a similar approach to derive new CDA bidding strategies in the TAC Travel domain by interleaving EGTA and RL. New experiments confirm the superiority of the learned strategies, and find a new approximate Nash equilibrium that consists of learned strategies only. These results are evidence that the combined EGTA/RL methodology is an effective method for generating stronger strategies for CDAs, and a promising approach for other domains with similar characteristics. I formulate an iterative framework to evaluate alternative strategy exploration policies, and experimentally evaluate a set of generic policies on three market problems. I find that policies seeking beneficial deviations or best responses perform generally well, and that stochastic introduction of suboptimal deviations can often lead to more effective exploration of the strategy space in the early stages of the process. | |
dc.format.extent | 123 p. | |
dc.language | English | |
dc.language.iso | EN | |
dc.subject | Analysis | |
dc.subject | Bidding | |
dc.subject | Continuous Double Auctions | |
dc.subject | Empirical | |
dc.subject | Game Theory | |
dc.subject | Reinforcement Learning | |
dc.subject | Strategies | |
dc.subject | Stronger | |
dc.subject | Theoretic | |
dc.subject | Trading Agent | |
dc.title | Stronger bidding strategies through empirical game-theoretic analysis and reinforcement learning. | |
dc.type | Thesis | |
dc.description.thesisdegreename | PhD | en_US |
dc.description.thesisdegreediscipline | Applied Sciences | |
dc.description.thesisdegreediscipline | Artificial intelligence | |
dc.description.thesisdegreediscipline | Computer science | |
dc.description.thesisdegreegrantor | University of Michigan, Horace H. Rackham School of Graduate Studies | |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/127126/2/3382400.pdf | |
dc.owningcollname | Dissertations and Theses (Ph.D. and Master's) |
Files in this item
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.
Accessibility
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.