Valkenhoef, G.H.M. van (2009) Dealing with execution uncertainty in the continuous double auction. Master's Thesis / Essay, Artificial Intelligence.
|
Text
AI-MAI-2009-G.H.M.van.Valkenhoef.pdf - Published Version Download (1MB) | Preview |
Abstract
With the advent of Grid computing, peer-to-peer systems and ad-hoc networks, distributed systems are becoming increasingly open and operate at a much larger scale in terms of the number of computational entities in the system. This poses new challenges for computational resource allocation. Specifically, a resource allocation mechanism must now deal with the increased size of the allocation problem, as well as the fact that computational entities may be controlled by different parties, with conflicting interests. Finally, there is an increased risk that a computational entity will fail to perform its assigned tasks: there is execution uncertainty. Traditional resource allocation mechanisms are inadequate in this setting. Thus, a new mechanism is required. To this end, in this work an agent-based system is developed that can solve the resource allocation problem in large-scale, open, distributed systems. Specifically, we develop the Trust-Based CDA (T-CDA), a decentralised market-based resource allocation mechanism. In this system, computational entities are modelled as agents that may buy or sell the use of resources. The T-CDA is an extension of the Continuous Double Auction (CDA) mechanism, which is a decentralised market-based resource allocation system. This means that the CDA can deal with the first two challenges of large-scale, open, distributed systems: its decentralised nature allows it to deal with large allocation problems, while market-based mechanisms can deal with different agents having conflicting interests. Now, to meet the execution uncertainty challenge, the T-CDA additionally allows agents to use a trust model in deciding whether or not to trade with a certain other agent. Specifically, an additional step is introduced in the trading process that allows agents commit to trades they believe will maximise their expected utility. We empirically evaluate the mechanism with Zero-Intelligence (ZI) agents, both against the optimal solution given complete and perfect information and against the standard CDA. We show the T-CDA consistently outperforms the traditional CDA as execution uncertainty increases in the system. Furthermore, we investigate the robustness of the mechanism to unreliable trust information and find that performance degrades gracefully as information quality decreases. Now, because in a decentralised mechanism the individual agent behaviours are an important determinant in overall system behaviour, we also develop Trust-Based ZIP (T-ZIP), a rudimentary trading strategy for the T-CDA. The T-ZIP strategy is empirically evaluated and shown to outperform ZI in specific conditions, showing an increase of efficiency of up to 80%. However, the T-ZIP is shown to fail in other conditions and thus is not a general trading strategy for the T-CDA. Insights are provided into the failure of T-ZIP in these conditions and ways to design a generally applicable strategy are identified.
| Item Type: | Thesis (Master's Thesis / Essay) |
|---|---|
| Degree programme: | Artificial Intelligence |
| Thesis type: | Master's Thesis / Essay |
| Language: | English |
| Date Deposited: | 15 Feb 2018 07:28 |
| Last Modified: | 15 Feb 2018 07:28 |
| URI: | https://fse.studenttheses.ub.rug.nl/id/eprint/8520 |
Actions (login required)
 |
View Item |