Market-driven Bargaining Strategy and
Relaxed-criteria Protocol for Grid Resource Allocation
by Dr. (Ben) Kwang-Mong SIM

Abstract

Whereas resource management is central to the operations of a computational Grid, providing efficient resource allocation mechanisms is a complex undertaking. Since providers and consumers of Grid resources may be independent bodies with different goals, policies, preferences and supply-and-demand patterns, negotiation among these participants is necessary for resolving their differences. Through negotiation, players in a Grid marketplace (providers and consumers) are given the opportunity to maximize their return-on-investment and minimize their cost (the price they pay), respectively. This research (which was published in a survey article by K. M. Sim and numerous of his papers in IEEE Transactions/International journals) is one of the earliest works that consider bargaining mechanisms for Grid resource management. The impetus and contribution of this work are (i) formulating market-driven bargaining strategies that specify the amount of concession that a G-negotiation (Grid resource negotiation) agent should make at each stage of bargaining, and (ii) devising a G-negotiation protocol that specifies the rules of the negotiation.

Since the bargaining position of a G-negotiation agent changes as resources are constantly being added/removed from a Grid, market factors such as opportunity and competition should be considered because the number of consumers competing for resources and the number of available alternatives for acquiring resources can significantly influence an agent's decision on determining the amount of concession that would optimize its revenue. Additionally, in response to different job deadlines, a G-negotiation agent should adopt different strategies in making concession with respect to time. Market-driven G-negotiation agents (MDGAs) are designed to make prudent compromises in different market situations by taking into account market factors such as market rivalry, outside option, and constraint such as deadline to avoid making excessive concessions in favorable markets and inadequate concessions in unfavorable markets. Theoretical results show that MDGAs negotiate optimally in different market situations by making minimally sufficient concessions. Empirical results demonstrate that market-driven G-negotiation agents generally achieved better negotiation outcomes (i.e., higher utilities) than other negotiation agents that did not consider market factors.

Another novel feature of this work is that MDGAs representing consumers (respectively, resource providers) are programmed to slightly relax their bargaining criteria under intense pressure (e.g., when the Grid loading is high and few resources are available (respectively, when there are very few requests for resources)) with the hope of enhancing their chance of successfully acquiring resources (respectively, leasing out their resources). Two sets of fuzzy rules representing the relaxation criteria for providers and consumers respectively are developed. Augmented with a fuzzy decision controller, MDGAs follow a relaxed-criteria G-negotiation protocol. Ideas of the relaxed-criteria G-negotiation protocol were implemented in an agent-based testbed. Empirical results obtained from simulations carried out using the testbed suggest that by slightly relaxing their bargaining terms under intense negotiation pressure, agents (i) achieved higher success rates in negotiation and (ii) required fewer negotiation rounds (without sacrificing much of their utilities).

This seminar presents (i) the motivation for considering a bargaining mechanism for Grid resource allocation, (ii) some of the design considerations of G-negotiation mechanisms, (iii) highlights of the market-driven G-negotiation strategy, and the relaxed-criteria G-negotiation protocol, (iv) a simulation testbed for G-negotiation consisting of various types of negotiation agents, and (v) empirical results comparing MDGAs to other negotiation agents.

Biography

(Ben) Kwang-Mong Sim is an Editor and a Guest Editor of many international journals. Currently serving his second term as an Associate Editor of the IEEE Transactions on Systems, Man, and Cybernetics, Part C, he is also the sole Guest Editor of an upcoming special issue on Grid Resource Management in the IEEE Systems Journal, the official journal of the IEEE Systems Council (formed by 15 IEEE Societies). In addition, he also serves as an Associate Editor of the International Journal of Applied Systemic Studies, and an Editorial board member of the International Journal of Hybrid Intelligent Systems. He is the sole Guest Editor/Lead Guest Editor of five special journal issues in Grid computing and automated negotiation. As the sole Guest Editor, he single-handedly managed and coordinated the review processes for three special journal issues on (i) game-theoretic analysis and stochastic simulation of negotiation agents (IEEE Transactions on SMC, IEEE, USA), (ii) learning approaches for negotiation agents (International Journal of Intelligent Systems (Wiley, USA)), and (iii) Agent-based Grid Computing, (Applied Intelligence Journal (Springer, USA)). He is currently editing two special journal issues: a special issue on negotiation agent and Grid system in the Multiagent and Grid Systems Journal (IOS Press, NL), and a special issue on Grid Resource Management in the IEEE Systems Journal. He is a senior member of IEEE and starting January 2007, he will be a member of the IEEE SMC Society's Technical Committee on Distributed Intelligent Systems.

As an active researcher in agent-based grid computing, automated negotiation, game-theoretic approaches of multi-agent systems, Grid economics, and Grid Commerce, he recently set up the Agent-based Grid Computing and Automated Negotiation (ABGC-AN) Group – a joint research initiative between the Hong Kong Baptist University and the University of Wollongong, Australia. ABGC-AN received funding from national funding agencies in Australia, Hong Kong and Taiwan. In addition to attracting many research grants, he has contributed many scholarly surveys, technical papers in IEEE/ACM/IEE journals, journal guest editorials as well as position papers in Agent-based Grid Computing and Automated Negotiation. He is a referee for many national research grant councils, including the National Science Foundation, USA, RGC in Hong Kong, ASTAR in Singapore and NSC in Taiwan. He is also a referee for Routledge Economics Book Series on Game Theory (Taylor & Francis), and has served as session chair and PC member for many international conferences, and has supervised over 30 researchers/graduate students regionally. Under his active supervision many researchers and graduate students rapidly published articles in IEEE Transactions/IEE Proceedings and many of his graduate students received distinctions in their dissertations. Additionally, he is also an external dissertation examiner for many universities regionally.

He has international work experience in six countries spanning the continents of North America, Europe and Asia. Prior to joining the Hong Kong Baptist University, he was an Associate Professor at the Department of Information Engineering, Chinese University of Hong Kong and a senior faculty member at Academia Sinica (Taiwan 's premier research institute formerly headed by Nobel Laureate YT Lee). Originating from Singapore, he received his Ph.D. and M.Sc. degrees from the University of Calgary (previously, home of the International Journal of Human-Computer Studies, and Knowledge Acquisition Journal), AB, Canada, and graduated Summa Cum Laude with a B.Sc.(Hon) degree from the University of Ottawa, ON, Canada.