Resource allocation in decentralised computational systems: an evolutionary market-based approach

Peter R. Lewis, Paul Marrow, Xin Yao

Research output: Contribution to journalArticle

Abstract

We present a novel market-based method, inspired by retail markets, for resource allocation in fully decentralised systems where agents are self-interested. Our market mechanism requires no coordinating node or complex negotiation. The stability of outcome allocations, those at equilibrium, is analysed and compared for three buyer behaviour models. In order to capture the interaction between self-interested agents, we propose the use of competitive coevolution. Our approach is both highly scalable and may be tuned to achieve specified outcome resource allocations. We demonstrate the behaviour of our approach in simulation, where evolutionary market agents act on behalf of service providing nodes to adaptively price their resources over time, in response to market conditions. We show that this leads the system to the predicted outcome resource allocation. Furthermore, the system remains stable in the presence of small changes in price, when buyers' decision functions degrade gracefully.
LanguageEnglish
Pages143-171
Number of pages29
JournalAutonomous Agents and Multiagent Systems
Volume21
Issue number2
Early online date29 Oct 2009
DOIs
Publication statusPublished - Sep 2010

Fingerprint

Resource allocation

Keywords

  • decentralised systems
  • market-based control
  • coevolution
  • load balancing
  • resource allocation
  • self-interested agents

Cite this

@article{ae7e1fe235b84fcdb51066e82711f3af,
title = "Resource allocation in decentralised computational systems: an evolutionary market-based approach",
abstract = "We present a novel market-based method, inspired by retail markets, for resource allocation in fully decentralised systems where agents are self-interested. Our market mechanism requires no coordinating node or complex negotiation. The stability of outcome allocations, those at equilibrium, is analysed and compared for three buyer behaviour models. In order to capture the interaction between self-interested agents, we propose the use of competitive coevolution. Our approach is both highly scalable and may be tuned to achieve specified outcome resource allocations. We demonstrate the behaviour of our approach in simulation, where evolutionary market agents act on behalf of service providing nodes to adaptively price their resources over time, in response to market conditions. We show that this leads the system to the predicted outcome resource allocation. Furthermore, the system remains stable in the presence of small changes in price, when buyers' decision functions degrade gracefully.",
keywords = "decentralised systems, market-based control, coevolution, load balancing, resource allocation, self-interested agents",
author = "Lewis, {Peter R.} and Paul Marrow and Xin Yao",
year = "2010",
month = "9",
doi = "10.1007/s10458-009-9113-x",
language = "English",
volume = "21",
pages = "143--171",
journal = "Autonomous Agents and Multiagent Systems",
issn = "1387-2532",
publisher = "Springer",
number = "2",

}

Resource allocation in decentralised computational systems : an evolutionary market-based approach. / Lewis, Peter R.; Marrow, Paul; Yao, Xin.

In: Autonomous Agents and Multiagent Systems, Vol. 21, No. 2, 09.2010, p. 143-171.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Resource allocation in decentralised computational systems

T2 - Autonomous Agents and Multiagent Systems

AU - Lewis, Peter R.

AU - Marrow, Paul

AU - Yao, Xin

PY - 2010/9

Y1 - 2010/9

N2 - We present a novel market-based method, inspired by retail markets, for resource allocation in fully decentralised systems where agents are self-interested. Our market mechanism requires no coordinating node or complex negotiation. The stability of outcome allocations, those at equilibrium, is analysed and compared for three buyer behaviour models. In order to capture the interaction between self-interested agents, we propose the use of competitive coevolution. Our approach is both highly scalable and may be tuned to achieve specified outcome resource allocations. We demonstrate the behaviour of our approach in simulation, where evolutionary market agents act on behalf of service providing nodes to adaptively price their resources over time, in response to market conditions. We show that this leads the system to the predicted outcome resource allocation. Furthermore, the system remains stable in the presence of small changes in price, when buyers' decision functions degrade gracefully.

AB - We present a novel market-based method, inspired by retail markets, for resource allocation in fully decentralised systems where agents are self-interested. Our market mechanism requires no coordinating node or complex negotiation. The stability of outcome allocations, those at equilibrium, is analysed and compared for three buyer behaviour models. In order to capture the interaction between self-interested agents, we propose the use of competitive coevolution. Our approach is both highly scalable and may be tuned to achieve specified outcome resource allocations. We demonstrate the behaviour of our approach in simulation, where evolutionary market agents act on behalf of service providing nodes to adaptively price their resources over time, in response to market conditions. We show that this leads the system to the predicted outcome resource allocation. Furthermore, the system remains stable in the presence of small changes in price, when buyers' decision functions degrade gracefully.

KW - decentralised systems

KW - market-based control

KW - coevolution

KW - load balancing

KW - resource allocation

KW - self-interested agents

UR - http://www.scopus.com/inward/record.url?scp=77953721608&partnerID=8YFLogxK

U2 - 10.1007/s10458-009-9113-x

DO - 10.1007/s10458-009-9113-x

M3 - Article

VL - 21

SP - 143

EP - 171

JO - Autonomous Agents and Multiagent Systems

JF - Autonomous Agents and Multiagent Systems

SN - 1387-2532

IS - 2

ER -