Evolutionary dynamics for designing multi-period auctions

ABSTRACT

Mechanism design (MD) has recently become a very popular approach in the design of distributed systems of autonomous agents. A key assumption required for the application of MD is that agents behave rationally in the mechanism or game, since this provides the predictability of agent behavior required for optimal design of the mechanism. In many cases, however, we are confronted with the intractability both of establishing rational equilibrium behavior, as well as of designing optimal mechanisms even if rational agent behavior can be assumed.

In this paper, we study both sides of the problem simultaneously by designing and analyzing a 'meta-game' involving both the designer of the mechanism (game, multi-agent system) and the agents interacting in the system. We use coupled replicator dynamics to investigate equilibrium out-comes in this game. In addition, we present an algorithm for determining the expected payoffs required for our analysis, thus sidestepping the need for extensive simulations as in previous work. Our results show the validity of the algorithm, some interesting conclusions about multi-period auction design, and the general feasibility of our approach.

REFERENCES

• 1: T. Börgers and R. Sarin. Learning through reinforcement and replicator dynamics. Journal of Economic Theory, 77, 1997.
• 2: Xi Chen , Xiaotie Deng, Settling the Complexity of Two-Player Nash Equilibrium, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.261-272, October 21-24, 2006 [doi>10.1109/FOCS.2006.69]
• 3: D. Cliff. Explorations in evolutionary design of online auction market mechanisms. ECR&A, 2, 2003.
• 4: V. Conitzer and T. W. Sandholm. Complexity of mechanism design. In UAI, 2002.
• 5: L. Devroye. Non-Uniform Random Variate Generation. Springer, 1986.
• 6: J. Hofbauer and K. Sigmund. Evolutionary game dynamics. Bulletin of the AMS, 40, 2003.
• 7: V. Krishna. Auction Theory. Academic Press, 2002.
• 8: M. Kunigami and T. Terano. Analyzing and taming collective learning of a multiagent system with connected replicator dynamics. In JSAI 2003/2004. Springer, 2007.
• 9: Benito Mendoza , José M. Vidal, Bidding algorithms for a distributed combinatorial auction, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329251]
• 10: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 11: 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]
• 12: David Pardoe , Peter Stone , Maytal Saar-Tsechansky , Kerem Tomak, Adaptive mechanism design: a metalearning approach, Proceedings of the 8th international conference on Electronic commerce: The new e-commerce: innovations for conquering current barriers, obstacles and limitations to conducting successful business on the internet, August 13-16, 2006, Fredericton, New Brunswick, Canada [doi>10.1145/1151454.1151480]
• 13: S. Phelps , M. Marcinkiewicz , S. Parsons, A novel method for automatic strategy acquisition in N-player non-zero-sum games, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160760]
• 14: Steve Phelps , Peter McBurney , Simon Parsons , Elizabeth Sklar, Co-evolutionary Auction Mechanism Design: A Preliminary Report, Revised Papers from the Workshop on Agent Mediated Electronic Commerce on Agent-Mediated Electronic Commerce IV, Designing Mechanisms and Systems, p.123-142, July 16, 2002
• 15: Y. Sato, E. Akiyama, and J. D. Farmer. Chaos in learning a simple two-person game. PNAS, 99, 2002.
• 16: Y. Sato and J. P. Crutchfield. Coupled replicator equations for the dynamics of learning in multiagent systems. Phys. Rev. E, 67, 2003.
• 17: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 18: K. Tuyls, A. Nowé, T. Lenaerts, and B. Manderick. An evolutionary game theoretic perspective on learning in multi-agent systems. Synthese, 139, 2004.
• 19: P. Vytelingum, D. Cliff, and N. R. Jennings. Evolutionary stability of behavioral types in the continuous double auction. In TADA/AMEC 2007. Springer, 2007.
• 20: W. E. Walsh, R. Das, G. Tesauro, and J. O. Kephart. Analyzing complex strategic interactions in multi-agent systems. In AAAI GTDT Workshop, 2002.
• 21: Michael P. Wellman , Jeffrey K. MacKie-Mason , Daniel M. Reeves , Sowmya Swaminathan, Exploring bidding strategies for market-based scheduling, Proceedings of the 4th ACM conference on Electronic commerce, p.115-124, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779943]

INDEX TERMS

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

General Terms:
Design, Economics, Experimentation

Keywords:
auctions, evolutionary game theory, mechanism design, replicator dynamics