Abstract
The advent of large-scale distributed systems poses unique engineering challenges. In open systems such as the internet it is not possible to prescribe the behaviour of all of the components of the system in advance. Rather, we attempt to design infrastructure, such as network protocols, in such a way that the overall system is robust despite the fact that numerous arbitrary, non-certified, third-party components can connect to our system. Economists have long understood this issue, since it is analogous to the design of the rules governing auctions and other marketplaces, in which we attempt to achieve socially-desirable outcomes despite the impossibility of prescribing the exact behaviour of the market participants, who may attempt to subvert the market for their own personal gain. This field is known as “mechanism design”: the science of designing rules of a game to achieve a specific outcome, even though each participant may be self-interested. Although it originated in economics, mechanism design has become an important foundation of multi-agent systems (MAS) research. In a traditional mechanism design problem, analytical methods are used to prove that agents’ game-theoretically optimal strategies lead to socially desirable outcomes. In many scenarios, traditional mechanism design and auction theory yield clear-cut results; however, there are many situations in which the underlying assumptions of the theory are violated due to the messiness of the real-world. In this paper we review alternative approaches to mechanism design which treat it as an engineering problem and bring to bear engineering design principles, viz.: iterative step-wise refinement of solutions, and satisficing instead of optimization in the face of intractable complexity. We categorize these approaches under the banner of evolutionary mechanism design.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Anderson, R. (2001). Why information security is hard: An economic perspective. In Proceedings of the 17th annual computer security applications conference (p. 358). Los Alimos, CA, USA: IEEE Computer Society.
Andrews M., Prager R. (1994) Genetic programming for the acquisition of double auction market strategies. In: Kinnear K. E., Jr (eds) Advances in genetic programming, chap 16. MIT Press, USA, pp 355–368
Angeline, P. J., & Pollack, J. B. (1993). Competitive environments evolve better solutions for complex tasks. In: S. Forrest (Ed.), Genetic algorithms: Proceedings of the fifth international Conference (GA93).
Axelrod R. (1997) The complexity of cooperation: Agent-based models of competition and collaboration. Princeton University Press, USA
Beck K. (1999) Extreme programming explained: Embrace change. Addison-Wesley, London
Bendor J., Swistak P. (1997) The evolutionary stability of cooperation. American Political Science Review 91(2): 290–307
Bittner K., Spence I. (2006) Managing iterative software development projects. Addison-Wesley, London
Boutilier C., Shoham Y., Wellman M. P. (1997) Editorial: Economic principles of multiagent systems. Artificial Intelligence 94: 1–6
Bryant W. D. A. (2000) Information, adjustment and the stability of equilibrium, Tech. Rep. 6/2000. Department of Economics, Macquarie University, Sydney, Australia
Bullock, S. (1997). Evolutionary simulation models: On their character, and application to problems concerning the evolution of natural signalling systems. PhD thesis, University of Sussex.
Byde, A. (2003). Applying evolutionary game theory to auction mechanism design. In Proceedings of the ACM conference on electronic commerce 2003 (pp. 192–193).
Chatterjee K., Samuelson W. (1983) Bargaining under incomplete information. Operations Research 31(5): 835–851
Clarkson G. P. E., Simon H. A. (1960) Simulation of individual and group behavior. American Economic Review 50: 920–932
Cliff, D. (1998). Evolving parameter sets for adaptive trading agents in continuous double-auction markets. In G. J. Karakoulas (Ed.), Agents-98 workshop on artificial societies and computational markets, Minneapolis, MN, (pp. 38–47). http://www.cs.toronto.edu/~grigoris/ascma.htm.
Cliff D. (2001) Evolution of market mechanism through a continuous space of auction-types, Tech. Rep. HPL-2001-326. HP Labs, California
Cliff, D., & Bruten, J. (1997). Minimal-intelligence agents for bargaining behaviors in market-based environments. Tech. Rep. HPL-07-91. Bristol: HP Labs.
Conitzer, V., & Sandholm, T. (2002). Complexity of mechanism design. In Proceedings of the 18th annual conference on uncertainty in artificial intelligence (UAI-02) (pp. 103–110).
Conitzer, V., & Sandholm, T. (2007). Incremental mechanism design. In Proceedings of the international joint conference on artificial intelligence (IJCAI).
Dash, R., Parkes, D., & Jennings, N. (2003). Computational mechanism design: A call to arms. IEEE Intelligent Systems, 18(6), 40–47, http://www.citeseer.ist.psu.edu/dash03computational.htm.
d’Aspremont C., Gérard-Varet L. (1979) Incentives and incomplete information. Journal of Public Economics 11: 25–45
David, E., Rogers, A., Schiff, J., Karus, S., & Jennings, N. R. (2005). Optimal design of english auctions with discrete bid levels. In Proceedings of the 6th ACM conference on electronic commerce (EC’05) (pp 98–107). Canada: Vancouver.
Dawid, H. (1999). The convergence of genetic learning in a double auction market. Journal of Economic Dynamics and Control, 23, 1545–1567, http://www.citeseer.nj.nec.com/438397.htm.
Dawkins R., Krebs J. R. (1979) Arms races between and within species. Proceedings of the Royal Society of London B 205: 489–511
Dutta P. K. (2001) Strategies and games: Theory and practice. MIT Press, USA
Engle-Warnick J. (2003) Inferring strategies from observed actions: A nonparametric, binary tree classification approach. Journal of Economic Dynamics and Control 27: 2151–2170
Engle-Warnick J., Ruffle B. (2001) Inferring buyer strategies and their impact on monopolist pricing, Tech. Rep. 2001-W28. Economics Group, University of Oxford, Nuffield College, Oxford
Erev I., Roth A. E. (1998) Predicting how people play games: Reinforcement learning in experimental games with unique, mixed strategy equilibria. American Economic Review 88(4): 848–881
Ficici, S.G. (2004). Solution concepts in coevolutionary algorithms, PhD thesis. Brandeis University, USA.
Ficici, S. G., & Pollack, J. B. (1998). Challenges in coevolutionary learning: Arms-race dynamics, open-endedness, and mediocre stable states. In Proceedings of of ALIFE-6.
Ficici, S. G., & Pollack, J. B. (2000). A game-theoretic approach to the simple coevolutionary algorithm. In S. Marc, D. Kalyanmoy, R. Günter, Y. Xin, L. Evelyne, & H. P. S. Juan Julian Merelo, (Eds.) Parallel problem solving from nature—PPSN VI 6th international conference. Paris, France: Springer Verlag.
Ficici, S. G., & Pollack, J. B. (2003). A game-theoretic memory mechanism for coevolution. In ECP et al. (Eds.) LNCS 2723 (pp. 286–297). France: Springer-Verlag.
Fisher F. M. (1983) Disequilibrium foundations of equilibrium economics. Cambridge University Press, UK
Flood M. M. (1952) Some experimental games, Tech. Rep. RM-789. RAND Corporation, Santa, Monica
Friedman, D., & Rust, J. (Eds.) (1991). The double auction market: Institutions, theories, and evidence: Proceedings of the workshop on double auction markets held June 1991 in Santa Fe. New Mexico: Westview.
Fudenberg, D., Mobius, M. M., & Szeidl, A. (2003). Existence of equilibrium in large double auctions. Working paper, Department of Economics, Harvard University, Littauer Center, Cambridge, MA 02138.
Gintis H. (2000) Game theory evolving: A problem-centered introduction to modeling strategic interaction. Princeton University Press, USA
Gjerstad S., Dickhaut J. (2001) Price formation in double auctions. Lecture Notes in Computer Science 2033: 106
Gode D. K., Sunder S. (1993) Allocative efficiency of markets with zero-intelligence traders: Market as a partial substitute for individual rationality. Journal of Political Economy 101(1): 119–137
Goeree J. K., Holt C. A. (2001) Ten little treasures of game theory and ten intuitive contradictions. American Economic Review 91(5): 1492–1524
Greenwald A. R., Stone P. (2001) Autonomous bidding agents in the trading agent competition. IEEE Internet Computing 5(2): 52
Harsanyi J.C. (1967) Games with incomplete information played by Bayesian players: Part i. Management Science 41: 159–182
Hillis, W. D. (1990). Co-evolving parasites improve simulated evolution as an optimization procedure. Physica D: Nonlinear Phenomena 42(1–3), 228–234. doi:10.1016/0167-2789(9090076-2.
Hsu, W., & Soo, V. (2001). Market performance of adaptive trading agents in synchronous double auctions. In S. T. Yuan, & M. Yokoo (Eds.), Intelligent agents, specification, modeling and applications, Lectures notes in computer science, vol 2132 (pp. 108–121). Berlin: Springer.
Huang, P., Scheller-Wolf. A., & Sycara, K. (2002). A strategy-proof multiunit double auction mechanism. In Proceedings of the first international joint conference on autonomous agents and multi-agent systems (pp. 166–167). Bologna, Italy.
Jackson M. O. (2003) Mechanism theory. In: Devigs U. (eds) Optimization and operations research, the Encyclopedia of life support science. EOLSS Publishers, Oxford, UK
Jackson M. O., Swinkels J. M. (2001) Existence of equilibrium in single and double private value auctions. California Institute of Technology, Mimeo
Jackson M. O., Swinkels J. M. (2005) Existence of equilibrium in single and double private value auctions. Econometrica 73(1): 93–139
Jordan, P., Vorobeychik, Y., & Wellman M. P. (2008). Searching for approximate equilibria in empirical games. In Padgham, Parkes, Müller, Parsons (Eds.), Proceedings of the 7th international conference on autonomous agents and multiagent systems, Estoril, Portugal.
Jordan, P. R., Kiekintveld, C., & Wellman, M. P. (2007). Empirical game-theoretic analysis of the TAC supply chain game. In Proceedings of the sixth international joint conference on autonomous agents and Multiagent Systems (pp. 1188–1195). Honolulu, Hawaii.
Kadan O. (2004) Equilibrium in the two player, k-double auction with affiliated private values, Tech. Rep. 12.2004. Nota di Lavoro, Germany
Kagel J.H., Roth A.E. (Eds.). (1995). The handbook of experimental economics. USA: Princeton University Press
Klemperer P. (2002) How (not) to run auctions: The European 3G telecom auctions. European Economic Review 46: 829–845
Klemperer P. (2004) Auctions: Theory and practice. Princeton University Press, USA
Klemperer P. (2004) Why every economist should learn some auction theory. In: Crémer J. (eds) Auctions: Theory and practice. Princeton University Press, USA
Koza J. R. (1993) Genetic programming: On the programming of computers by means of natural selection. MIT Press, USA
Krishna V. (2002) Auction theory. Harcourt Publishers Ltd, New York
Lyapunov A. M. (1966) Stability of motion. Academic Press, New York and London
MacKenzie D. A. (2003) An equation and its worlds: Bricolage, exemplars, disunity and performativity in financial economics. Social Studies of Science 33: 831–868
Maynard-Smith J. (1982) Evolution and the theory of games. Cambridge University Press, Cambridge
McAfee R. P. (1992) A dominant strategy double auction. Journal of Economic Theory 56: 434–450
Medio A., Gallo G. (1992) Chaotic dynamics: Theory and applications to economics. Cambridge University Press, Cambridge
Mirowski P. (2001) Machine dreams: Economics becomes a cyborg science. Cambridge University Press, Cambridge
Myerson R. B., Satterthwaite M. A. (1983) Efficient mechanisms for bilateral trading. Journal of Economic Theory 28: 265–281
Nash, J. (1950). Equilibrium points in n-person games. In Proceedings of the national academy of sciences, vol 36 (pp. 48–49).
Nicolaisen J., Petrov V., Tesfatsion L. (2001) Market power and efficiency in a computational electricity market with discriminatory double-auction pricing. IEEE Transactions on Evolutionary Computation 5(5): 504–523
Nik-Khah E. (2005) Designs on the mechanism: Economics and the FCC Auctions, Ph.D. University of Notre Dame, Notre Dame, Indiana, USA
Niu, J., Cai, K., Gerding, E., McBurney, P., & Parsons, S. (2008) Characterizing effective auction mechanisms: Insights from the 2007 TAC mechanism design competition. In P. Padgham, P. Müller (Eds.), Proceedings of the 7th international conference on autonomous agents and multiagent systems (pp. 1079–1086). Estoril, Portugal.
Noble, J., & Watson, R. A. (2001). Pareto coevolution: Using performance against coevolved opponents in a game as dimensions for pareto selection. In Proceedings of the genetic and evolutionary computation conference, GECCO-2001 (pp. 493–50). San Fancisco, California: Morgan Kauffman.
Papadimitriou, C. H. (2001). Algorithms, games, and the internet. In Proceedings of the 33rd symposium on theory of computing (pp. 749–753). ACM Press.
Pardoe, D., Stone, P., Saar-Tsechansky, M., & Tomak, K. (2005). Adaptive auctions: Learning to adjust to bidders. In Proceedings of the fifteenth annual workshop on information technologies and Systems.
Phelps, S. (2008). Evolutionary mechanism design. PhD thesis, Liverpool, UK: University of Liverpool. submitted July 2007.
Phelps, S., Parsons, S., McBurney, P., & Sklar, E. (2002a). Co-evolution of auction mechanisms and trading strategies: Towards a novel approach to microeconomic design. In Proceedings of the bird of a feather workshops, genetic and evolutionary computation conference (pp. 65–72). New York: AAAI.
Phelps S., Parsons S., McBurney P., Sklar E. (2002) Co-evolutionary mechanism design: A preliminary report. In: Padget J., Shehory O., Parkes D., Sadeh N., Walsh W. E. (eds) Agent-mediated electronic commerce IV: Designing mechanisms and systems. Springer Verlag, New York, pp 123–143
Phelps, S., Parsons, S., Sklar, E., & McBurney, P. (2003). Using genetic programming to optimise pricing rules for a double auction market. In Proceedings of the workshop on Agents for Electronic Commerce. PA: Pitsburgh.
Phelps S., Marcinkiewicz M., Parsons S., McBurney P. (2006) A novel method for automatic strategy acquisition in n-player non-zero-sum games. In: Nakashima H, Wellman M. P., Weiss G., Stone P. (eds) Proceedings of the 5th international joint conference on autonomous agents and multiagent systems (AAMAS 2006). ACM, Hajodate, Japan, pp 705–712
Phelps S., Parsons S., McBurney P. (2006) An evolutionary game-theoretic comparison of two double-auction market designs. In: Faratin P., Rodriguez-Aguílar J. A. (eds) Agent-mediated electronic commerce VI. Springer Verlag, New York, pp 101–114
Phelps, S., Parsons, S., & McBurney, P. (2008). A novel method for strategy acquisition and its application to a double-auction market. IEEE Transactions on Systems, Man, and Cybernetics: Part B (Forthcoming).
Plott C. R. (1997) Laboratory experimental testbeds: Application to the PCS auction. Journal of Economics and Management Strategy 6(3): 605–638
Pollack J. B., Blair A. D. (1998) Co-evolution in the successful learning of backgammon strategy. Machine Learning 32: 225–240
Preist C., van Tol M. (2003) Adaptive agents in a persistent shout double auction market, Tech. Rep. HPL-2003-242. HP Laboratories, Bristol
Price T. C. (1997) Using co-evolutionary programming to simulate strategic behaviour in markets. The Journal of Evolutionary Economics 7: 219–254
Reeves D. M., MacKie-Mason J. K., Wellman M. P., Osepayshvili A. (2005) Exploring bidding strategies for market-based shceduling. Decision Support Systems, USA
Reny P.J., & Perry M. (2003). Toward a strategic foundation for rational expectations equilibrium, Working paper. Chicago: University of Chicago.
Rosenschein J. S., Zlotkin G. (1994) Rules of encounter: Designing conventions for automated negotiation among computers. MIT press, USA
Roth A. E. (2002) The economist as engineer: Game theory, experimentation, and computation as tools for design economics. Econometrica 70(4): 1341–1378
Roth A. E., Ockenfels A. (2002) Last-minute bidding and the rules for ending second-price auctions: Evidence from ebay and amazon auctions on the internet. Americon Economic Review 92(4): 1093–1103
Russell S., Norvig P. (2003) Artificial intelligence: A modern approach, 2nd edn. Prentice Hall, New Jersey
Rustichini A., Satterthwaite M. A., Williams S. R. (1994) Convergence to efficiency in a simple market with incomplete information. Econometrica 62(5): 1041–1063
Sandholm, T. (2003). Automated mechanism design: A new application area for search algorithms. In Proceedings of the international conference on principles and practice of constraint programming (CP).
Satterthwaite M., Williams S. (1993) The Bayesian theory of the k-double auction. In: Friedman R. (eds) The double auction market: Institutions, theories and evidence, Santa Fe studies in the sciences of complexity, chap 4. Westview, England, pp 99–125
Smith V. L. (1962) An experimental study of competitive market behavior. Journal of Political Economy 70: 111–337
Spence M. (1973) Job market signaling. The Quarterly Journal of Economics 87(3): 355–374
Surowiecki J. (2004) The wisdom of crowds: Why the many are smarter than the few and how collective wisdom shapes business, economies, societies, and nations. Doubleday, USA
Tesauro, G., & Bredin, J. L. (2002). Strategic sequential bidding in auctions using dynamic programming. In Proceedings of the first international joint conference on autonomous agents and multi-agent systems (pp. 591–598). ACM.
Tesauro, G., & Das, R. (2001). High-performance bidding agents for the continuous double auction. In Proceedings of the third ACM conference on electronic commerce (pp. 206–209). Florida, USA: Tampa.
Tesfatsion L. (2002) Agent-based computational economics: Growing economies from the bottom up. Artificial Life 8(1): 55–82
Valen L. V. (1973) A new evolutionary law. Evolutionary Theory 1: 1–30
Varian, H.R. (1995). Economic mechanism design for computerized agents. In Proceedings of the first USENIX workshop on electronic commerce (pp. 13–21).
Vickrey W. (1961) Counterspeculation, auctions and competitive sealed tenders. Journal of Finance 16: 8–37
Vickrey, W. (1962). Auctions and bidding games. In Recent advances in game theory, no. 29 in Princeton Conference Series (pp. 15–27). Princeton, NJ: Princeton University Press.
Walsh, W.E., Das, R., Tesauro, G., & Kephart, J.O. (2002). Analyzing complex strategic interactions in multi-agent games. In AAAI-02 workshop on hame theoretic and decision theoretic agents.
Walsh W.E., Parkes, D., & Das, R. (2003). Choosing samples to compute heuristic-strategy nash equilibrium. In Faratin, P., Parkes, D. C., Rogdríguez-Aguilar, J. A., & Walsh, W. E. (Eds.), Agent-Mediated electronic commerce V: designing mechanisms and systems, LNAI, vol 3048 (pp. 109–123). Melbourne, Australia: Springer. http://www.citeseer.ist.psu.edu/walsh03choosing.html
Watkins J. C. H., Dayan P. (1992) Qlearning. Machine Learning 8: 279–292
Weibull J. W. (1997) Evolutionary game theory, first mit press edn. MIT Press, USA
Wellman M.P. (1995) The economic approach to artificial intelligence. ACM Computing Surveys 27(3): 360–362
Wellman M. P., Wurman P. R., O’Malley K., Bangera R., Lin S., Reeves D., Walsh W. E. (2001) Designing the market game for a trading agent competition. IEEE Internet Computing 5(2): 43–51
Wellman, M. P., Reeves, D. M., Lockner, K. M., Suri, R. (2005). Searching for walverine. In Proceedings of the IJCAI-05 workshop on trading agent design and analysis (TADA-05). Scotland: Edinburgh.
Williams, S.R. (1988). The nature of equilibria in the buyer’s bid double auction. Discussion Paper 793, Department of Economics, Northwestern University.
Williams S. R. (1991) Existence and convergence of equilibria in the buyer’s bid double auction. The Review of Economic Studies 58: 351–374
Wolfers J., Zitzewitz E. (2004) Prediction markets. The Journal of Economic Perspectives 18(2): 107–126
Wurman P. R., Walsh W. E., Wellman M. P. (1998) Flexible double auctions for electronic commerce: theory and implementation. International Journal of Decision Support Systems 24: 17–27
Wurman P. R., Walsh W. E., Wellman M. P. (2001) A parameterisation of the auction design space. Games and Economic Behaviour 35: 304–338
Young H. P. (2001) Individual strategy and social structure. Princeton University Press, USA
Zahavi A., Zavahi A. (1997) The handicap principle: A missing piece of Darwin’s puzzle. Oxford University Press, Oxford
Zhan, W., & Friedman, D. (2005). Markups in double auction markets. Tech. rep., LEEPS, Santa Cruz: Department of Economics, University of Santa Cruz.
Author information
Authors and Affiliations
Corresponding author
Additional information
We are grateful for financial support received from the UK EPSRC through the Market-Based Control of Complex Computational Systems Project (GR/T10657/01), and from the US National Science Foundation under grant NSF IIS-0329037 Tools and Techniques for Automated Mechanism Design.
Rights and permissions
About this article
Cite this article
Phelps, S., McBurney, P. & Parsons, S. Evolutionary mechanism design: a review. Auton Agent Multi-Agent Syst 21, 237–264 (2010). https://doi.org/10.1007/s10458-009-9108-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10458-009-9108-7