research-article

Evolutionary dynamics for designing multi-period auctions

Authors:

Gerrit Jan van AheeAuthors Info & Claims

AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 3

Pages 1589 - 1592

Published: 12 May 2008 Publication History

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]

L.-C. Chen and X. Deng. Settling the complexity of two-player Nash equilibrium. In FOCS. IEEE, 2006.

Digital Library

[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.

Digital Library

[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.

Digital Library

[9]

B. Mendoza and J. M. Vidal. Bidding algorithms for a distributed combinatorial auction. In AAMAS, 2007.

Digital Library

[10]

C. H. Papadimitriou. Algorithms, games and the internet. In STOC. ACM, 2001.

Digital Library

[11]

D. Pardoe and P. Stone. Developing adaptive auction mechanisms. ACM SIGecom Exchanges, 5, 2005.

Digital Library

[12]

D. Pardoe, P. Stone, M. Saar-Tsechansky, and K. Tomak. Adaptive mechanism design: A metalearning approach. In ICEC. ACM, 2006.

Digital Library

[13]

S. Phelps, M. Marcinkiewicz, S. Parsons, and P. J. McBurney. A novel method for automatic strategy acquisition in N-player non-zero-sum games. In AAMAS, 2006.

Digital Library

[14]

S. Phelps, P. J. McBurney, S. Parsons, and E. Sklar. Co-evolutionary auction mechanism design: A preliminary report. In AMEC IV. Springer, 2002.

Digital Library

[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]

R. S. Sutton and A. G. Barto. Reinforcement Learning. MIT Press, 1998.

Digital Library

[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.

Digital Library

[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]

M. P. Wellman, J. K. MacKie-Mason, D. M. Reeves, and S. Swaminathan. Exploring bidding strategies for market-based scheduling. In ACM EC. ACM, 2003.

Digital Library

Cited By

Yuan YWang FZeng D(2016)Developing a cooperative bidding framework for sponsored search markets - An evolutionary perspectiveInformation Sciences: an International Journal10.1016/j.ins.2016.07.041369:C(674-689)Online publication date: 10-Nov-2016
https://dl.acm.org/doi/10.1016/j.ins.2016.07.041

Index Terms

Evolutionary dynamics for designing multi-period auctions
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence

Recommendations

Approximately Efficient Two-Sided Combinatorial Auctions
EC '17: Proceedings of the 2017 ACM Conference on Economics and Computation

We develop and extend a line of recent work on the design of mechanisms for two-sided markets. The markets we consider consist of buyers and sellers of a number of items, and the aim of a mechanism is to improve the social welfare by arranging purchases ...
Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation
EC '03: Proceedings of the 4th ACM conference on Electronic commerce

Engineering automated negotiation across the supply chain is a central research challenge for the important problem of supply chain formation. The difficult problem of designing negotiation strategies is greatly simplified if the negotiation mechanism ...
Binary Vickrey auction - A robust and efficient multi-unit sealed-bid online auction protocol against buyer multi-identity bidding

The multi-unit Vickrey-Clark-Groves (VCG) mechanism has two major weaknesses: it has high computational complexity and monotonicity problems [Paul Milgrom. Putting Auction Theory to Work. Cambridge University Press, Cambridge, UK, 2004] such that if ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 3

May 2008

503 pages

ISBN:9780981738123

Sponsors

ACM: Association for Computing Machinery
AAAI: Association for the Advancement of Artifical Intelligence

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 12 May 2008

Check for updates

Author Tags

Qualifiers

Research-article

Conference

AAMAS08

Sponsor:

ACM
AAAI

AAMAS08: 7th International Conference on Autonomous Agents and Multi Agent Systems

May 12 - 16, 2008

Estoril, Portugal

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
139
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yuan YWang FZeng D(2016)Developing a cooperative bidding framework for sponsored search markets - An evolutionary perspectiveInformation Sciences: an International Journal10.1016/j.ins.2016.07.041369:C(674-689)Online publication date: 10-Nov-2016
https://dl.acm.org/doi/10.1016/j.ins.2016.07.041

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents