A survey of bargaining models for grid resource allocation

Complex and Concurrent Negotiations for Multiple Interrelated e-Markets

To date, most of the existing bargaining models are designed for supporting negotiation in only one market involving only two types of participants (buyers and sellers). This work devises a complex negotiation mechanism that supports negotiation activities among three types of participants in multiple interrelated markets. The complex negotiation mechanism consists of: 1) a bargaining-position-estimation (BPE) strategy for the multilateral negotiations between consumer and broker agents in a service market and 2) a regression-based coordination (RBC) strategy for concurrent negotiations between broker and provider agents in multiple resource markets. The negotiation outcomes between broker and provider agents in a resource market can potentially influence the negotiation outcomes between broker and consumer agents in a service market. Empirical results show that agents adopting the BPE strategy can better respond to different market conditions than agents adopting the time-dependent strategy because they do not make excessive (respectively, inadequate) amounts of concessions in favorable (respectively, unfavorable) markets. In the concurrent negotiations in multiple resource markets, empirical results show that broker agents adopting the RBC strategy achieved significantly higher utilities, higher success rates, and faster negotiation speed than broker agents adopting the utility-oriented and patient coordination strategies.

BLGAN: Bayesian learning and genetic algorithm for supporting negotiation with incomplete information

Automated negotiation provides a means for resolving differences among interacting agents. For negotiation with complete information, this paper provides mathematical proofs to show that an agent's optimal strategy can be computed using its opponent's reserve price (RP) and deadline. The impetus of this work is using the synergy of Bayesian learning (BL) and genetic algorithm (GA) to determine an agent's optimal strategy in negotiation (N) with incomplete information. BLGAN adopts: 1) BL and a deadline-estimation process for estimating an opponent's RP and deadline and 2) GA for generating a proposal at each negotiation round. Learning the RP and deadline of an opponent enables the GA in BLGAN to reduce the size of its search space (SP) by adaptively focusing its search on a specific region in the space of all possible proposals. SP is dynamically defined as a region around an agent's proposal P at each negotiation round. P is generated using the agent's optimal strategy determined using its estimations of its opponent's RP and deadline. Hence, the GA in BLGAN is more likely to generate proposals that are closer to the proposal generated by the optimal strategy. Using GA to search around a proposal generated by its current strategy, an agent in BLGAN compensates for possible errors in estimating its opponent's RP and deadline. Empirical results show that agents adopting BLGAN reached agreements successfully, and achieved: 1) higher utilities and better combined negotiation outcomes (CNOs) than agents that only adopt GA to generate their proposals, 2) higher utilities than agents that adopt BL to learn only RP, and 3) higher utilities and better CNOs than agents that do not learn their opponents' RPs and deadlines.

Relaxed-criteria G-negotiation for Grid resource co-allocation

Supporting resource co-allocation is essential for realizing the Grid vision because computational intensive applications may require more resources than a single computing machine can provide in one administrative domain. Given that the various stakeholders often have their own requirements and supply-and-demand patterns, successfully obtaining commitments through concurrent negotiations with multiple resource owners to simultaneously access several resources is a very challenging task. This position paper (i) suggests that a relaxed-criteria G-negotiation mechanism may be used to enhance the success rates of negotiation agents in Grid resource co-allocation, (ii) proposes a testbed for realizing the relaxed-criteria G-negotiation mechanism, (iii) discusses experimental designs for evaluating the proposed mechanism, and (iv) discusses previous results obtained from using a relaxed-criteria G-negotiation protocol for Grid resource allocation.

Grid Commerce, Market-Driven G-Negotiation, and Grid Resource Management

Although the management of resources is essential for realizing a computational grid, providing an efficient resource allocation mechanism is a complex undertaking. Since Grid providers and consumers may be independent bodies, negotiation among them is necessary. The contribution of this paper is showing that market-driven agents (MDAs) are appropriate tools for Grid resource negotiation. MDAs are e-negotiation agents designed with the flexibility of: 1) making adjustable amounts of concession taking into account market rivalry, outside options, and time preferences and 2) relaxing bargaining terms in the face of intense pressure. A heterogeneous testbed consisting of several types of e-negotiation agents to simulate a Grid computing environment was developed. It compares the performance of MDAs against other e-negotiation agents (e.g., Kasbah) in a Grid-commerce environment. Empirical results show that MDAs generally achieve: 1) higher budget efficiencies in many market situations than other e-negotiation agents in the testbed and 2) higher success rates in acquiring Grid resources under high Grid loadings.