Evolutionary Market Agents for Resource Allocation in Decentralised Systems Peter R. Lewis*, Paul Marrow† and Xin Yao* [email protected] [email protected] [email protected] †BT PLC *University of Birmingham Abstract We introduce self-interested evolutionary market agents, which act on behalf of service providing nodes in a large decentralised market-based system, to adaptively price their resources over time. Our agents competitively co-evolve in the live market, driving it towards the Bertrand equilibrium, the non-cooperative Nash equilibrium, at which all sellers share the market equally. We demonstrate that this outcome results in even load-balancing between the service providers. Background Problem Formulation Emerging paradigms for the development and deployment of massively distributed computational systems allow resources to span many locations, organisations and platforms, connected through the Internet [1] . It has been predicted that the majority of transactions over the Internet will, in the future, be carried out by autonomous agents on behalf of their owners [2] . In this scenario, neither control nor even full knowledge of key resources may be assumed. There is therefore a need to find novel ways to understand and autonomically manage and control these large, decentralised and dynamic systems. Externality pricing has been proposed for the provision of otherwise virtually zero cost per-use computational services [3] . It is argued that this approach, where service users self-select their quantity based on price, is a more preferable approach to the alternative of provider-side enforced quantity limits. We consider a scenario consisting of a set of service providing nodes, S, each member of which provides an equivalent, quantitatively divisible service, the resource π, which may vary only in price. We assume that each member of S has an equal capacity for the provision of π, and that they cannot be relied upon to cooperate. We then imagine a large population of service users or buyers, B, each member of which aims to consume some of the resource π, at regular intervals. We use q ij to denote the quantity of π purchased by from seller i by buyer j at a given instant. The quantity of π sold by a given seller s i ∈ S at a given time, its load, ls , is therefore: i Our objective is to balance the load, such that all the service providers in S are providing an equal amount of π across the population of service users. Though this is a trivial problem when cooperation may be assumed, we wish to achieve this using self-interest, with no central control. Note that we are not modelling service providing nodes owned by competing businesses in the real-world, since then load-balancing would not be desirable; self-interested competition is instead artificially created in order to serve the purposes of the system owner. We observe the evenness of the load using a normalised measure of mean absolute distance from the ideally even load (NMA distance). Hence a high NMA distance indicates an uneven load, while a perfectly even load leads to a value of zero. We propose the use of autonomous evolutionary market agents as an approach to achieving this. Our Approach Evolutionary Market Agents Service Users (Buyers) Service Providers (Sellers) Each iteration, each service provider advertises π at the price p πs per unit. An evolutionary market agent acts on behalf of each service providing node. £2.41 £4.27 £1.22 i £3.94 Similarly, unlike the majority of market-based systems [5] , there is no central auctioneer or market-maker. Each agent makes use of an evolutionary algorithm, maintaining a population of prices. To test its fitness, a price is quoted to the live market, treating it as a black box. £1.25 Each iteration, probabilistic tournament selection is used to select parents. Sellers have the ability to advertise their prices through a broadcast mechanism. The payoff returned from the use of the quoted price, becomes that individual's fitness . An offspring is created through crossover and mutation. Each buyer buys exactly one unit of π per time-step. Alternatively, if no offer is attractive, they may purchase nothing. It has no point which is weaker than any other, and is hence both scalable and robust to failure. The offspring replaces the weakest individual from the tournament selection. £7.87 £1.75 Each of the service users, the buyers, purchases some of the resource π, should it be in their interest to do so at the price offered. Unlike traditional load-balancing [4] , our approach does not rely on a central controlling node. £1.95 £3.24 Buyer Behaviour Service providing agents require no knowledge of the size of the marketplace or any history. Unlike other decentralised load-balancing mechanisms [6,7] , our approach does not assume or require cooperation between peers. Its power lies in the self-interested competition of service-providing nodes. For simplicity at this stage, our model assumes that the system proceeds in discrete time-steps, and that each and every service provider has suffcient quantity of π available to satisfy all the buyers in B should it be so requested. The price encoded by the offspring is then quoted to the live market. A Baseline Scenario First, we consider a small scenario with two service providers, such that S = {s 1 , s 2}, each providing the resource π, at prices pπ1 and pπ2 respectively. Both s 1 and s 2 make use of an evolutionary market agent in order to determine these prices at each time-step. We begin with 10 buyers (the service users), with identical linear utility functions. Initially, the distance drops sharply. Our approach has the ability to Following exploratory fluctuations, the distance stabilises as the populations converge. At this point, the load-balance is highly equal. The graph shows the normalised mean absolute distance from the ideal load, between s 1 and s 2, over time. The mean and standard deviation are shown across 30 independent runs. [1] Singh, M.P., Huhns, M.N.: Service-Oriented Computing: Semantics, Processes, Agents. John Wiley and Sons, Chichester (2005). [2] He, M., Jennings, N.R., Leung, H.: On agent-mediated electronic commerce. IEEE Transactions on Knowledge and Data Engineering 15(4), 985–1003 (2003). [3] Gupta, A., Stahl, D.O., Whinston, A.B.: The economics ofnetwork management. Communications ofthe ACM 42(9), 57–63 (1999). [4] Ardellini, V.C., Olajanni, M.C., Yu, P.S.: Dynamic load balancing on web server systems. IEEE Internet Computing 3(3), 28–39 (1999) . Our buyers are risk-averse, spreading their purchases across a number of sellers. Looking at the available offers, each buyer purchases a proportion of their total desired resource from each seller, relative to the expected utility gain from selecting the offer from that seller. A More Complex Scenario Next, we examine a similar, but much larger scenario, with 1,000 service providers and 10,000 service users. Here results are of a similar form to the simpler scenario. quickly achieve a roughly even load between the two service providers. Buyers are self-interested but do not behave in an all-or-nothing manner in favour of the instantaneously most attractive option, since this behaviour may expose the buyer to a degree of risk. Our approach is distributed and fully decentralised, and is therefore highly scalable. Again, the graph shows the normalised mean absolute distance from the ideal load, between the service providers, over time. The mean and standard deviation are shown across 30 independent runs. Larger populations of agents appears to lead to more reliable results. Clearly, the approach scales well. [5] Clearwater, S.H. (ed.): Market-Based Control: A Paradigm for Distributed Resource Allocation. World Scientific, Singapore (1996). [6] Alfano, R., Caprio, G.D.: Turbo: an autonomous execution environment with scalability and load-balancing features. In: Proceedings ofthe IEEE Workshop on Distributed Intelligent Systems: Collective Intelligence and its Applications (DIS 2006), pp. 377–382 (2006). [7] Kuwabara, K., Ishida, T., Nishibe, Y., Suda, T.: An equilibratory market-based approach for distributed resource allocation and its applications to communication network control. In: [5], pp. 53–73. World Scientific, Singapore (1996). This shows the power of our approach to achieve load-balancing in a large, decentralised system where no individual has any desire in favour of this behaviour. Our approach is highly suited to this scenario, since it accounts for self-interested utility maximising individuals; no cooperation is assumed. This research has been jointly funded by the UK Engineering and Physical Sciences Research Council (EPSRC) and BT PLC, whose support is gratefully acknowledged.