Evolutionary optimization of ZIP60: a controlled explosion in hyperspace

ABSTRACT

The "ZIP" adaptive trading algorithm has been demonstrated to outperform human traders in experimental studies of continuous double auction (CDA) markets. The original ZIP algorithm requires the values of eight control parameters to be set correctly. A new extension of the ZIP algorithm, called ZIP60, requires the values of 60 parameters to be set correctly. ZIP60 is shown here to produce significantly better results than the original ZIP (called "ZIP8" hereafter). A genetic algorithm (GA) is used to search the 60-dimensional ZIP60 parameter space, and it finds parameter vectors that yield ZIP60 traders with mean scores significantly better than those of ZIP8s. This paper shows that this optimizing evolutionary search works best when the GA itself controls the dimensionality of the search-space, so that the search commences in an 8-d space and thereafter the dimensionality of the search-space is gradually increased by the GA until it is exploring a 60-d space. Furthermore, the results from ZIP60 cast some doubt on prior ZIP8 results concerning the evolution of new 'hybrid' auction mechanisms that appeared to be better than the CDA.

REFERENCES

• 1: Anthony Bagnall , Iain Toft, Autonomous Adaptive Agents for Single Seller Sealed Bid Auctions, Autonomous Agents and Multi-Agent Systems, v.12 n.3, p.259-292, May 2006 [doi>10.1007/s10458-005-4948-2]
• 2: Andrew Byde, Applying evolutionary game theory to auction mechanism design, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779954]
• 3: Chatfield, C. & Collins, A. (1980), An Introduction to Multivariate Analysis. Chapman and Hall.
• 4: Clearwater, S., ed. (1995), Market-Based Control. World Scientific Press.
• 5: Dave Cliff , Phil Husbands , Inman Harvey, Explorations in evolutionary robotics, Adaptive Behavior, v.2 n.1, p.73-110, Summer 1993 [doi>10.1177/105971239300200104]
• 6: Cliff, D. (1997), "Minimal-intelligence agents for bargaining behaviours in market environments". HPLabs Report HPL-97--91.
• 7: Cliff, D. (1998a), "Genetic optimization of adaptive trading agents for double-auction markets" in Proc. Comp. Intell. in Financial Eng. (CIFEr98), New York, IEEE/IAFE, pp.252--258.
• 8: Cliff, D. (1998b), "Evolutionary optimization of parameter sets for adaptive software-agent traders in CDA markets". Proc. Artif. Societies & Comp. Markets (ASCMA98).
• 9: Cliff, D. & Bruten, J. (1999), "Animat Market-Trading Interactions as Collective Social Adaptive Behavior". Adaptive Behavior 7(3&4):385--414.
• 10: Cliff, D. (2002a), "Evolution of market mechanism through a continuous space of auction-types". Presented at Computational Intelligence in Financial Engineering (CIFEr), Hawaii.
• 11: Cliff, D. (2002b), "Evolution of market mechanism through a continuous space of auction-types II". In: H. Arabnia, & Y. Mun. (eds) Proc. Int. Conf. Internet Comput. Vol.III, , pp.682--688.
• 12: Cliff, D. (2003), Explorations in evolutionary design of online auction market mechanisms. Electronic Commerce Research & Applications Journal, 2(2):162--175, 2003.
• 13: Cliff, D. (2005), "ZIP60: Further Explorations in the Evolutionary Design of Online Auction Market Mechanisms." Hewlett-Packard Laboratories Technical Report HPL-2005-85.
• 14: Cliff, D. (2006), ZIP60: an enhanced extension of the ZIP trading algorithm. Submitted for review.
• 15: Das, R., Hanson, J., Kephart, J., & Tesauro, G. (2001), "Agent-human interactions in the CDA" Proc. IJCAI-01.
• 16: Feltovich, N. (2003), "Nonparametric tests of differences in medians: comparison of the Wilcoxon-Mann-Whitney and robust rank-order tests", Experimental Economics, 6:273--297.
• 17: Friedman, D. (1991), "A Simple Testable Model of Price Formation in the CDA Market", J. Econ. Behav. & Org. 15:47--70.
• 18: Gerding, E., Somefun, K., & La Poutréé, H. (2004), "Multi-Attribute Bilateral Bargaining in a One-to-Many Setting", In Proc. Workshop Agent Mediated Elec. Comm. VI (AMEC-04).
• 19: Gjerstad, S. & Dickhaut, J. (1998), "Price Formation in Double Auctions", Games & Economic Behavior, 22:1--29.
• 20: Gode, D. & Sunder, S. (1993), "Allocative efficiency of markets with ZI traders", J. Polit. Econ., 101:119--137.
• 21: Greenwald, A., Guillemette, B., Naroditskiy, V., & Tschantz, M., (2005), "Scaling Up the Sample Average Approximation Method for Stochastic Optimization with Applications to Trading Agents" in Jansen, S. (ed) Notes IJCAI-05 W'shop Trading Agent Design & Analysis (TADA05).pp.21--27.
• 22: Harvey, I. (1994), The Artificial Evolution of Adaptive Behavior. PhD Thesis, School of Cognitive and Computing Sciences, University of Sussex, U.K.
• 23: Minghua He , Ho-fung Leung , Nicholas R. Jennings, A Fuzzy-Logic Based Bidding Strategy for Autonomous Agents in Continuous Double Auctions, IEEE Transactions on Knowledge and Data Engineering, v.15 n.6, p.1345-1363, November 2003 [doi>10.1109/TKDE.2003.1245277]
• 24: Ladley, D. & Bullock, S. (2005), "Who to listen to: Exploiting information quality in a ZIP-agent market" in Jansen, S. (ed) W'shop Trad. Agent Des. & Anal. (TADA05). pp.28--34.
• 25: Li, L. & Smith, S. (2004), "Speculation Agents for Dynamic, Multi-period CDAs in B2B Exchanges", Proc. 37th Hawaii Int. Conf. Sys. Sci.
• 26: Kevin M. Lochner , Michael P. Wellman, Rule-Based Specification of Auction Mechanisms, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.818-825, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.237]
• 27: David Pardoe , Peter Stone, Developing adaptive auction mechanisms, ACM SIGecom Exchanges, v.5 n.3, p.1-10, April 2005 [doi>10.1145/1120680.1120682]
• 28: Park, S., Durfee, E., & Birmingham, W. (2004), "Use of Markov Chains to Design an Agent Bidding Strategy for CDAs", J. Art. Intell. Res. (JAIR), 22: 175--214.
• 29: Phelps, S., Parsons, S., & McBurney, P. (2004), "An Evolutionary Game-theoretic Comparison of 2 CDA Market Designs". Proc AMEC-IV.
• 30: Chris Preist , Maarten van Tol, Adaptive agents in a persistent shout double auction, Proceedings of the first international conference on Information and computation economies, p.11-18, October 25-28, 1998, Charleston, South Carolina, United States [doi>10.1145/288994.288998]
• 31: Daniel M. Reeves , Michael P. Wellman , Jeffrey K. MacKie-Mason , Anna Osepayshvili, Exploring bidding strategies for market-based scheduling, Decision Support Systems, v.39 n.1, p.67-85, March 2005 [doi>10.1016/j.dss.2004.08.014]
• 32: Robinson, N. (2002), Evolutionary Optimization of Market-Based Control Systems for Resource Allocation in Compute Farms. MSc Thesis, Uni. Sussex, U.K.
• 33: Rust, J., Miller, J., & Palmer, R. (1992), "Behavior of trading automata in a CDA market" in Friedman, D., & Rust, J. (eds) The Double Auction Market, pp.155--198. Addison-Wesley
• 34: Shipp, D. (2004), The effects of changes to supply and demand on trader agents and marketplaces. MSc Thesis, School of Computing, Uni. of Leeds, UK.
• 35: Siegel, S., & Castellan, N. (1988), Nonparametric Statistics for the Behavioral Sci., McGraw Hill.
• 36: Smith, V. (1962), "Experimental study of competitive market behavior" J. Polit. Econ., 70:111--137.
• 37: Stanley, K. & Miikkulainen, R. (2004), "Competitive Coevolution through Evolutionary Complexification", Journal of Artificial Intelligence Research (JAIR), 21:63--100.
• 38: Tesauro, G. & Das, R. (2001), "High-Performance Bidding Agents for the Continuous Double Auction", Economic Agents, Models, & Mechanisms W'shop, (IJCAI).
• 39: Gerald Tesauro , Jonathan L. Bredin, Strategic sequential bidding in auctions using dynamic programming, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 2, July 15-19, 2002, Bologna, Italy [doi>10.1145/544862.544885]
• 40: Vytelingum, P., Dash, R., David, E., & Jennings, N. (2004), "A risk-based bidding strategy for continuous double auctions" Proc. 16th Euro. Conf. Art. Intel., Valencia, Spain, pp.79--83.
• 41: Walia, V. (2002), Evolving Market Design, MSc Thesis, Computer Science, Birmingham Uni, UK.
• 42: Wellman, M., Reeves, D., Lochner, K., & Suri, R. (2005), "Searching for Walverine 2005" in Jansen, S. (ed) Notes IJCAI-05 W'shop Trading Agent Design & Analysis (TADA05). pp.1--6.
• 43: Wichett, D. (2004), Coadaptive Dynamics of Minimal Intelligence Trading Agents. MSc Thesis, Uni. Birmingham, UK

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Industrial automation; Office automation
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems
      I.2.6 Learning
          Subjects: Parameter learning

  J. Computer Applications
  J.1 ADMINISTRATIVE DATA PROCESSING
      Subjects: Financial (e.g., EFTS)
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Design, Economics, Experimentation, Performance

Keywords:
ZIP8 ZIP60, Zero-Intelligence-Plus (ZIP) Traders, algorithmic trading, auction markets, automated market-mechanism design