Evolutionary market-based resource allocation in decentralised computational systems

Lewis, Peter Richard (2010). Evolutionary market-based resource allocation in decentralised computational systems. University of Birmingham. Ph.D.


Download (8MB)


This thesis presents a novel market-based method, inspired by retail markets for resource allocation in fully decentralised computational systems where agents are self-interested. The posted offer mechanism used requires no central or regional coordinator or complex negotiation strategies. The stability of outcome allocations, those at equilibrium, is analysed and compared for three buyer behaviour models. The approach is scalable, robust and may be tuned to achieve a range of desired outcome resource allocations. These include a balanced load, allocations reflective of providers’ differing capabilities and those appropriate to heterogeneous buyer preferences over multiple attributes. The behaviour of the approach is studied both game theoretically and in simulation, where novel evolutionary market agents act on behalf of resource providing nodes to adaptively price their resources over time in response to market conditions. Sellers competitively co-evolve their offers online without any need for global market information. This is shown to lead the system to the game theoretically predicted outcome resource allocation when buyers’ decision functions degrade gracefully. Additionally, allocations remain stable in the presence of small changes in price and other more disruptive agents. The posted offer model therefore appears to be a useful mechanism for resource allocation in both homogeneous and heterogeneous decentralised computational systems where nodes are self-interested. Furthermore, evolutionary computation is shown to be a potential approach to realising self-interested adaptive pricing behaviour under the assumption of private information present in the posted offer model.

Type of Work: Thesis (Doctorates > Ph.D.)
Award Type: Doctorates > Ph.D.
College/Faculty: Colleges (2008 onwards) > College of Engineering & Physical Sciences
School or Department: School of Computer Science
Funders: None/not applicable
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
URI: http://etheses.bham.ac.uk/id/eprint/1217


Request a Correction Request a Correction
View Item View Item


Downloads per month over past year