USING SHADOW PRICES FOR RESOURCE ALLOCATION IN A COMBINATORIAL GRID WITH PROXY-BIDDING AGENTS

Michael Schwind, Oleg Gujo

2006

Abstract

Our paper presents an agent-based simulation environment for task scheduling in a distributed computer systems (grid). The scheduler enables the simultaneous allocation of resources like CPU time, communication bandwidth, volatile, and non-volatile memory while employing a combinatorial resource allocation mechanism. The resources are allocated by an iterative combinatorial auction with proxy-bidding agents that try to acquire their desired resource allocation profiles with respect to limited monetary budget endowments. In order to achieve an efficient bidding process, the auctioneer provides information on resource prices to the bidding agents. The calculation of explicit resource prices in a combinatorial auction is computationally demanding, especially if the the bid bundles exhibit complementarities or substitutionalities. We therefore propose a new approximate pricing mechanism using shadow prices from a linear programming formulation for this purpose. The efficiency of the shadow price-based allocation mechanism is tested in the context of a closed loop grid system in which the agents can use monetary units rewarded for the resources they provide to the system for the acquisition of complementary capacity. Two types of proxy-bidding agents are compared in terms of efficiency (received units of resources, time until bid acceptance) within this scenario: An aggressive bidding agent with strongly rising bids and a smooth bidding agent with slowly increasing bids.

Paper Citation

in Harvard Style

Schwind M. and Gujo O. (2006). USING SHADOW PRICES FOR RESOURCE ALLOCATION IN A COMBINATORIAL GRID WITH PROXY-BIDDING AGENTS . In Proceedings of the Eighth International Conference on Enterprise Information Systems - Volume 4: ICEIS, ISBN 978-972-8865-44-3, pages 11-18. DOI: 10.5220/0002461500110018

in Bibtex Style

@conference{iceis06,
author={Michael Schwind and Oleg Gujo},
title={USING SHADOW PRICES FOR RESOURCE ALLOCATION IN A COMBINATORIAL GRID WITH PROXY-BIDDING AGENTS},
booktitle={Proceedings of the Eighth International Conference on Enterprise Information Systems - Volume 4: ICEIS,},
year={2006},
pages={11-18},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002461500110018},
isbn={978-972-8865-44-3},
}

in EndNote Style

TY - CONF
JO - Proceedings of the Eighth International Conference on Enterprise Information Systems - Volume 4: ICEIS,
TI - USING SHADOW PRICES FOR RESOURCE ALLOCATION IN A COMBINATORIAL GRID WITH PROXY-BIDDING AGENTS
SN - 978-972-8865-44-3
AU - Schwind M.
AU - Gujo O.
PY - 2006
SP - 11
EP - 18
DO - 10.5220/0002461500110018