热门搜索:

  • /?150
  • 下载费用:20 金币 ?

Evolutionary_Mechanism_Design.pdf

关?键?词:
EVOLUTIONARY_MECHANISM_DESIGN
资源描述:

Evolutionary Mechanism Design Thesis submitted in accordance with the requirements of the University of Liver- pool for the degree of Doctor in Philosophy by Stephen George Phelps. July 2007iiThis thesis is dedicated to Margaret Phelps, who made it possible.ivAcknowledgements I am indebted to many people for their support and collaboration in the course of my Ph.D. research. Firstly I thank my supervisors Peter McBurney and Simon Parsons for their unwavering support and guidance over a long journey. A special thanks goes to Jinzhong Niu, Kai Cai and Marek Marcinkiewicz at the City University of New York for their collaboration on the JASA simulation software. In this respect, I would also like to thank Leigh Tesfatsion and Igor A. Walter for contributing bug reports, and Thierry Moyaux for his many contributions. I would also like to thank the many people who have contributed feedback and discussion to my research, amongst them, in no particular order: Michael Phelps, Andrew Byde, Enrico Gerding, Dave Cliff, Sam Hough, Alvin Roth, Tim Miller, Carles Sierra, Karl Tulys, Sieuwert van Otterloo, Seth Bullock, Elizabeth Sklar, Sevan Ficici, John Cartlidge, Omar Baqueiro Espinosa and William Walsh. I would like to especially thank Mike Wooldridge for his enduring patience, and Ruth Melville for her support and guidance beyond the call of duty. My research was partially funded by EPSRC grant GR/T10671/01 - Market Based Control of Complex Computational Systems: Techniques for Automated Mechanism Design, and by the E.U. I.S.T. Programme through the SLIE project. vvi AcknowledgementsContents 1 Introduction 1 1.1 The Double-Auction . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Auction Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Literature Review 7 2.1 Summary and Contribution . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 A Generic Model of the Double-Auction 13 3.1 A model of a commodity-exchange market . . . . . . . . . . . . . . . 14 3.1.1 The resource allocation problem . . . . . . . . . . . . . . . . 14 3.1.2 Optimal Allocations and the Equilibrium Price . . . . . . . . 17 3.1.3 The Role of the Auctioneer . . . . . . . . . . . . . . . . . . . 21 3.1.4 Mechanism design . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 The auction model . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2.1 Rounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2.2 Shouts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2.3 Active Traders . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2.4 Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2.5 The end of round event . . . . . . . . . . . . . . . . . . . . . 25 3.2.6 Shout processing . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2.7 Quotes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2.8 Trading Days . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2.9 The clearing operation . . . . . . . . . . . . . . . . . . . . . 27 3.3 The clearing-house double auction . . . . . . . . . . . . . . . . . . . 28 3.3.1 Uniform pricing . . . . . . . . . . . . . . . . . . . . . . . . 28 3.3.2 Discriminatory pricing . . . . . . . . . . . . . . . . . . . . . 28 3.3.3 In-order discriminatory pricing . . . . . . . . . . . . . . . . . 29 3.3.4 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.4 The continuous double-auction . . . . . . . . . . . . . . . . . . . . . 29 4 Trading Strategies 33 4.1 Non-Adaptive Strategies . . . . . . . . . . . . . . . . . . . . . . . . 33 4.1.1 The Truth-Telling Strategy . . . . . . . . . . . . . . . . . . . 33 viiviii CONTENTS 4.1.2 The Equilibrium-Price Strategy . . . . . . . . . . . . . . . . 34 4.1.3 The Pure Simple Strategy . . . . . . . . . . . . . . . . . . . 34 4.1.4 The Zero-Intelligence Constrained Strategy . . . . . . . . . . 35 4.2 Adaptive Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2.1 The Zero-Intelligence Plus Strategy . . . . . . . . . . . . . . 36 4.2.2 Kaplan’s Sniping Strategy . . . . . . . . . . . . . . . . . . . 37 4.2.3 The Gjerstad-Dickhaut strategy . . . . . . . . . . . . . . . . 39 4.2.4 Reinforcement-learning Strategies . . . . . . . . . . . . . . . 41 4.3 Summary and Contribution . . . . . . . . . . . . . . . . . . . . . . . 45 5 Simulation Framework 47 5.1 An overview of multi-agent simulation . . . . . . . . . . . . . . . . . 47 5.1.1 Simulating a MAS verses implementing a MAS . . . . . . . . 47 5.1.2 Different approaches to simulating time . . . . . . . . . . . . 49 5.1.3 Continuous time models . . . . . . . . . . . . . . . . . . . . 49 5.1.4 Discrete-event simulation . . . . . . . . . . . . . . . . . . . 50 5.1.5 Agent decision functions . . . . . . . . . . . . . . . . . . . . 50 5.1.6 Extensibility and integration . . . . . . . . . . . . . . . . . . 51 5.1.7 Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.1.8 Software listing . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.1.9 Choice of toolkit . . . . . . . . . . . . . . . . . . . . . . . . 55 5.1.10 Choice of language . . . . . . . . . . . . . . . . . . . . . . . 55 5.2 Engineering Methodology . . . . . . . . . . . . . . . . . . . . . . . 57 5.2.1 Unit testing . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.2.2 Replication of existing experiments . . . . . . . . . . . . . . 58 5.2.3 Open-source . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.3 Design overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.3.1 The shout matching algorithm . . . . . . . . . . . . . . . . . 61 5.3.2 Auction mechanisms . . . . . . . . . . . . . . . . . . . . . . 61 5.3.3 Agents and trading strategies . . . . . . . . . . . . . . . . . . 61 5.3.4 Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.4 Summary and contribution . . . . . . . . . . . . . . . . . . . . . . . 64 6 Replication Experiments 65 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 6.2 Control Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . 65 6.3 Nicolaisen’s Electricity Market and the Roth-Erev strategy . . . . . . 66 6.4 Cliff’s Zero-Intelligence Plus Strategy . . . . . . . . . . . . . . . . . 69 6.5 Summary and Contribution . . . . . . . . . . . . . . . . . . . . . . . 71 7 Empirical Game Theory 73 7.1 Nash Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 7.2 Beyond Nash equilibrium . . . . . . . . . . . . . . . . . . . . . . . . 74 7.3 Co-evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 7.4 Empirical Game-Theory . . . . . . . . . . . . . . . . . . . . . . . . 76CONTENTS ix 8 Analysing Auction Mechanisms 79 8.1 The CH verses the CDA . . . . . . . . . . . . . . . . . . . . . . . . 79 8.1.1 Choice of heuristic strategies . . . . . . . . . . . . . . . . . . 81 8.2 Experimental setup . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 8.3 Dynamic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 8.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 8.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 8.6 Summary and Contribution . . . . . . . . . . . . . . . . . . . . . . . 92 9 Searching the Space of Strategies 95 9.1 Strategy Acquisition . . . . . . . . . . . . . . . . . . . . . . . . . . 97 9.1.1 Strategy space . . . . . . . . . . . . . . . . . . . . . . . . . 97 9.1.2 Search algorithm . . . . . . . . . . . . . . . . . . . . . . . . 98 9.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 9.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 9.4 Summary and Contribution . . . . . . . . . . . . . . . . . . . . . . . 103 10 Searching the Space of Mechanisms 105 10.1 A review of earlier work . . . . . . . . . . . . . . . . . . . . . . . . 105 10.2 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 10.3 Experimental setup . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 10.3.1 Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 10.4 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . 112 10.4.1 Mapping the landscape . . . . . . . . . . . . . . . . . . . . . 112 10.4.2 Evolving pricing rules . . . . . . . . . . . . . . . . . . . . . 113 10.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 10.6 Summary and Contribution . . . . . . . . . . . . . . . . . . . . . . . 118 11 Conclusion and Future Work 119 11.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 11.2 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 11.3 Extensions and further work . . . . . . . . . . . . . . . . . . . . . . 120 11.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 A UML Diagrams 123 Bibliography 130x CONTENTSChapter 1 Introduction Much work in the design of multi-agent systems (MAS) has focused on the design and engineering of individual agents; for example, the problems of designing and im- plementing effective trading strategies for agents participating in e-commerce market places, or the design of effective learning algorithms for adaptive agents. However, increasingly attention is being turned to the design of the infrastructure, or the environ- ment, underlying the interactions between individual agents in a MAS; for example, the problem of designing rules governing the operation of an e-commerce market in- stitution, or the design of interaction protocols governing agent argumentation. The justi?cation for the latter approach is that often as MAS designers we are responsible for engineering open systems, in which we do not have control over the exact behavior of the agents connecting to our system; these agents are, after all, autonomous. Rather, we build a set of standards and protocols with which our agents are free to interact, and if we have designed our infrastructure robustly, the system as a whole will exhibit our desired design properties despite the fact that it consists of possibly millions of au- tonomous agents interacting with each other in ways we have not prescribed in advance [94]. Such systems are known as self-organising complex systems (SOCS). Examples of such systems are market places, ecosystems, nervous systems, neural networks, co-evolving systems, and of course, multi-agent systems. They are complex, in the sense that they consist of many parts with many interactions between them and ex- hibit non-linear, hard-to-predict behaviour, and they are self-organising in the sense that macro-level stabilities emerge despite the underlying complexity. As an example, consider a stock market consisting of hundreds of thousands of traders. Each trader is an autonomous agent, free to trade using whatever strategy they want. Individual prices at any given time are determined by the trading behaviour of all of other agents trading in the market; thus the actions of each agent can potentially in?uence all other agents; there are many interactions between the components of the system. Many as- pects of the market’s behaviour are chaotic or hard to predict, for example the price of an individual stock, or the pro?ts of an individual trader. Yet despite this complexity, the variables that the stock-market “designer” is interested in, for example the overall market ef?ciency, remain at consistently satis?cing values. Additionally, such systems 12 CHAPTER 1. INTRODUCTION are robust to exogenous perturbation; for example, after the stock market has been sub- jected to a shock, such as a market crash, the system eventually settles back into a state in which the design variables, for example market ef?ciency, are held at desirable val- ues despite the fact that there is no explicit top-down control mechanism for achieving this. Such self-healing or homeostatic behaviour is typical of SOCS in general. These systems possess state-space dynamics with attractors and stable states (also known as equilibria) that lead the system to homeostatic states– that is, states in which our design variables are maximised or held within desirable ranges. As designers of a multi-agent system, we are therefore tasked with ensuring that the complex system embodied by our MAS possesses attractors or equilibria in which our design objectives are met. But how can we affect the dynamics of our system if we are not allowed to prescribe the behaviour of individual agents — what free variables are at our disposal? The answer, of course is outlined above; in MAS design prob- lems we typically have some control over the environment or infrastructure in which third-party agents interact. This can take the form of, for example, rules governing an auction mechanism, or the protocols used by agents for argumentation. Small changes in these rules or standards can have dramatic effects on the behaviour of the agents using these rules, and can radically alter the underlying dynamics of the system in sur- prising ways. By altering the underlying dynamics, we are sometimes able to adjust the system so that the stable states of the system exhibit the homeostatic properties we desire. For example, in a market-design context, by tweaking the rules of the market, we are sometimes able to design systems in which optimal allocative-ef?ciency is an emergent stable macro-property of the system. Economists have studied similar design problems in the context of auction theory and mechanism design. In a mechanism design problem, the task of the designer is to choose the rules of the auction in such a way that the designer’s objectives are met when agents play their optimal strategies. One of the main dif?culties in solving this problem is computing the optimal strategies, as the best strategy to play depends on what strategies are being played by other agents; the number of agents can vary signi?- cantly, and the strategy space can be very large. The standard technique is to view each possible set of auction rules as de?ning a particular game, and then to use game theory to “solve” this game by ?nding the set of strategies comprising a Nash equilibrium of the game — the set of strategies that are best responses to each other. 1.1 The Double-Auction A double-auction mechanism is a generalization of an auction in which there are mul- tiple sellers as well as multiple buyers, and both buyers and sellers are allowed to exchange offers simultaneously. Since double-auctions allow dynamic pricing on both the supply side and the demand side of the marketplace, their study is of great im- portance, both to theoretical economists, and those seeking to implement real-world market places. On the one hand, economists who are interested in theories of price formation in

? 汽车智库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:Evolutionary_Mechanism_Design.pdf
链接地址:http://www.autoekb.com/p-1513.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

copyright@ 2008-2018 mywenku网站版权所有
经营许可证编号:京ICP备12026657号-3?

收起
展开