Abstract
In this paper, we present a genetic algorithmic approach to automated auction mechanism design in the context of cat games. This is a follow-up to one piece of our prior work in the domain, the reinforcement learning-based grey-box approach [14]. Our experiments show that given the same search space the grey-box approach is able to produce better auction mechanisms than the genetic algorithmic approach. The comparison can also shed light on the design and evaluation of similar search solutions to other domain problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
[14] is available at http://www.sci.brooklyn.cuny.edu/~jniu/research/publications/.
- 2.
A taxonomy of policies in this domain of auction mechanisms is described in detail in [17].
- 3.
The same solution was adopted in designing marketplace selection strategies for trading agents in cat games. However the two scenarios may need different parameter values. The market selection scenario should favor choices that give a good profit—a cumulative measure—while here we require effective exploration to find a good mechanism in the foreseeable future—a one-time concern.
- 4.
As the Hall of Fame is empty at the beginning of each ga experiment, the first cat game includes four individuals from the population, so the total number of games to evaluate the 20 generations is actually 199. But the difference of one game can be negligible. In theory, it is possible to design the experiments to run exactly the same number of cat games as long as
and 
, however the integer solutions—201 and 2, or 67 and 6—to this equation are not practical for the ga as 
is too small. - 5.
One example is that the scores of cda \(_h\) and ch \(_h\) flatten out much earlier during the experiments than the scores of cda \(_l\) and ch \(_l\) in all the three cases in Fig. 4.
- 6.
A Hall of Famer may come from more than one run of the same experiment.
- 7.
We actually ran additional sets of ga experiments with crossover, each with a different crossover rate, 0.1, 0.4, or 1.0, in contrast to 0.7 that was used in the ga experiments described in the text. It turned out that the ga experiments using 0.7 produced the best results and hence only the results of this set of experiments were included in the text in the comparison against those of the grey-box experiments.
- 8.
A schemata is typically represented in the form, for example, ****01*1***, where * can match 0 or 1. The defining length of a schemata is the maximal distance between bits with deterministic values, and the order of a schemata is the number of bits with deterministic values.
- 9.
These are sometimes called competent genetic algorithms.
- 10.
A co-founder of the field with Fisher and a critic of Fisher’s approach.
- 11.
Similar comparisons between reinforcement learning-based approaches and evolutionary computational approaches do exist in other domains. Further discussions of these comparisons are however beyond the scope of this paper and are not possible due to the space constraint.
and 
, however the integer solutions—201 and 2, or 67 and 6—to this equation are not practical for the 
is too small.References
Burjorjee, K.M.: The fundamental problem with the building block hypothesis. CoRR, abs/0810.3356 (2008)
Chen, Y.-P., Goldberg, D.E.: Convergence time for the linkage learning genetic algorithm. Evol. Comput. 13(3), 279–302 (2005)
Cliff, D.: Evolution of market mechanism through a continuous space of auction-types. Technical report HPL-2001-326, Hewlett-Packard Research Laboratories, Bristol, December 2001
Cliff, D.: Explorations in evolutionary design of online auction market mechanisms. Technical report HPL-2003-80, Hewlett-Packard Research Laboratories, Bristol, July 2003
Conitzer, V., Sandholm, T.: Automated mechanism design for a self-interested designer. In: Proceedings of the Fourth ACM Conference on Electronic commerce (EC 2003), pp. 232–233. ACM, New York (2003)
Forrest, S.: Genetic algorithms: principles of adaptation applied to computation. Science 261, 872–878 (1993)
Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co. Inc., Boston (1989)
Goldberg, D.E.: Real-coded genetic algorithms, virtual alphabets, and blocking. Complex Syst. 5, 139–167 (1990)
Harik, G.R., Lobo, F.G., Goldberg, D.E.: The compact genetic algorithm. IEEE Trans. Evol. Comput. 3, 523–528 (1999)
Haupt, R.L., Haupt, S.E.: Practical Genetic Algorithms, 2nd edn. Wiley, New York (2004)
Holland, J.H.: Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor (1975). Reprinted by MIT Press, Cambridge (1992)
Li, Z., Goodman, E.D.: Exploring building blocks through crossover. In: Kang, L., Cai, Z., Yan, X., Liu, Y. (eds.) ISICA 2008. LNCS, vol. 5370, pp. 707–714. Springer, Heidelberg (2008). doi:10.1007/978-3-540-92137-0_77
Mitchell, M., Forrest, S., Holland, J.H.: The royal road for genetic algorithms: fitness landscapes and GA performance. In: Varela, F.V., Bourgine, P. (eds.) Toward a Practice of Autonomous Systems: First European Conference on Artificial Life, pp. 245–254. MIT Press, Cambridge (1991)
Niu, J., Cai, K., Parsons, S.: A grey-box approach to automated mechanism design. In: David, E., Larson, K., Rogers, A., Shehory, O., Stein, S. (eds.) AMEC/TADA-2010. LNBIP, vol. 118, pp. 47–61. Springer, Heidelberg (2012). doi:10.1007/978-3-642-34200-4_4
Niu, J., Cai, K., Parsons, S., Gerding, E., McBurney, P.: Characterizing effective auction mechanisms: insights from the 2007 TAC Mechanism Design Competition. In: Padgham et al. [18], pp. 1079–1086
Niu, J., Cai, K., Parsons, S., Gerding, E., McBurney, P., Moyaux, T., Phelps, S., Shield, D.: JCAT: a platform for the TAC market design competition. In: Padgham et al. [18], pp. 1649–1650. Demo Paper
Niu, J., Cai, K., Parsons, S., McBurney, P., Gerding, E.: What the 2007 TAC market design game tells us about effective auction mechanisms. J. Auton. Agents Multiagent Syst. 21(2), 172–203 (2010)
Padgham, L., Parkes, D.C., Müller, J.P., Parsons, S. (eds.): 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008), IFAAMAS, Estoril, 12–16 May 2008
Phelps, S., Marcinkiewicz, M., Parsons, S., McBurney, P.: A novel method for automatic strategy acquisition in n-player non-zero-sum games. In: Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multi-agent Systems (AAMAS 2006), pp. 705–712. ACM Press, New York (2006)
Phelps, S., Parsons, S., Sklar, E., McBurney, P.: Using genetic programming to optimise pricing rules for a double auction market. In: Proceedings of the Workshop on Agents for Electronic Commerce, Pittsburgh (2003)
Rosin, C.D.: Coevolutionary search among adversaries. Ph.D. thesis, University of California, San Diego (1997)
Sareni, B., Krähenbühl, L.: Fitness sharing and niching methods revisited. IEEE Trans. Evol. Comput. 2(3), 97–106 (1998)
Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. MIT Press, Cambridge (1998)
Thierens, D., Goldberg, D.E.: Mixing in genetic algorithms. In: Proceedings of the Fifth International Conference on Genetic Algorithms, San Francisco, pp. 38–47. Morgan Kaufmann Publishers Inc. (1993)
Acknowledgments
Support for this work was provided by PSC-CUNY Award 68800-00 46, jointly funded by the Professional Staff Congress and the City University of New York. The authors acknowledge resources from the computational facility at the CUNY High Performance Computing Center, which is operated by the College of Staten Island and funded, in part, by grants from the City of New York, State of New York, CUNY Research Foundation, and National Science Foundation Grants CNS-0958379, CNS-0855217 and ACI 1126113.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Niu, J., Parsons, S. (2017). A Genetic Algorithmic Approach to Automated Auction Mechanism Design. In: Ceppi, S., David, E., Hajaj, C., Robu, V., Vetsikas, I. (eds) Agent-Mediated Electronic Commerce. Designing Trading Strategies and Mechanisms for Electronic Markets. AMEC/TADA AMEC/TADA 2015 2016. Lecture Notes in Business Information Processing, vol 271. Springer, Cham. https://doi.org/10.1007/978-3-319-54229-4_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-54229-4_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-54228-7
Online ISBN: 978-3-319-54229-4
eBook Packages: Computer ScienceComputer Science (R0)