Evolutionary market-based resource allocation in decentralised computational systems

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.

Name dc:type.qualificationname

d_ph

Level dc:type.qualificationlevel

d_ph

Grantor dc:publisher.institution

University of Birmingham

Year dc:date.issued

2010

Author dc:creator

• Lewis, Peter Richard

• QA75 Electronic computers. Computer science