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.

Continuous-time negotiation mechanism for software agents

While there are several existing mechanisms and systems addressing the crucial and difficult issues of automated one-to-many negotiation, this paper develops a flexible one-to-many negotiation mechanism for software agents. Unlike the existing general one-to-many negotiation mechanism, in which an agent should wait until it has received proposals from all its trading partners before generating counterproposals, in the flexible one-to-many negotiation mechanism, an agent can make a proposal in a flexible way during negotiation, i.e., negotiation is conducted in continuous time. To decide when to make a proposal, two strategies based on fixed waiting time and a fixed waiting ratio are proposed. Results from a series of experiments suggest that, guided by the two strategies for deciding when to make a proposal, the flexible negotiation mechanism achieved more favorable trading outcomes as compared with the general one-to-many negotiation mechanism. To determine the amount of concession, negotiation agents are guided by four mathematical functions based on factors such as time, trading partners' strategies, negotiation situations of other threads, and competition. Experimental results show that agents guided by the four functions react to changing market situations by making prudent and appropriate rates of concession and achieve generally favorable negotiation outcomes.

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.

A survey of bargaining models for grid resource allocation

Whereas it is noted that various types of auctions, commodity market models, and contract-net (tendering) model are more widely used for managing Grid resources, this paper focuses on discussing bargaining (negotiation) models for Grid resource management. To this end, this survey supplements and complements existing surveys by reviewing, comparing, and highlighting the very few extant research initiatives on applying bargaining as a mechanism for managing Grid resources. The contributions of this paper are (i) discussing the motivations for considering bargaining models for Grid resource management, (ii) discussing the issues in building bargaining mechanisms for Grid resource management, (iii) comparing the strategies and protocols of state-of-the-art bargaining models for Grid resources, and (iv) discussing possible new directions.

Equilibria, prudent compromises, and the "waiting" game

While evaluation of many e-negotiation agents are carried out through empirical studies, this work supplements and complements existing literature by analyzing the problem of designing market-driven agents (MDAs) in terms of equilibrium points and stable strategies. MDAs are negotiation agents designed to make prudent compromises taking into account factors such as time preference, outside option, and rivalry. This work shows that 1) in a given market situation, an MDA negotiates optimally because it makes minimally sufficient concession, and 2) by modeling negotiation of MDAs as a game gamma of incomplete information, it is shown that the strategies adopted by MDAs are stable. In a bilateral negotiation, it is proven that the strategy pair of two MDAs forms a sequential equilibrium for gamma. In a multilateral negotiation, it is shown that the strategy profile of MDAs forms a market equilibrium for gamma.

From market-driven agents to market-oriented grids (position paper)

Providing efficient mechanism for allocation and management of resources is essential for realizing a computational grid. Since resource providers and consumers may be independent bodies in a computing grid platform, negotiation among these participants is necessary. This position paper discusses (i) the design considerations of e-negotiation agents for grid commerce, and (ii) the possible application of Market-driven agents (MDAs) as negotiation mechanisms for managing resources in a computational grid. MDAs are negotiation agents designed with the flexibility of (i) making adjustable amounts of concession taking into account factors such as market rivalry, time preferences, and outside options, and (ii) relaxing trade expectation in the face of intense pressure. In addition to having stable strategies, making prudent compromises and optimizing utility, additional desirable properties of MDAs that are suitable for a computational grid include: adaptivity to changes in market conditions, and flexibility of reaching faster consensus.

Equilibrium analyses of market-driven agents

Market-driven agents (MDAs) are negotiation agents that make adjustable amounts of concession by considering factors such as competition, deadlines, and trading options. While previous work demonstrates the properties of MDAs by experiments, this paper provides mathematical analyses to show that (1) for a given market situation, an MDA makes minimally sufficient concession, and (2) the strategies adopted by MDAs are in equilibrium. The results show that MDAs are stable (stability is an essential evaluation criterion for negotiation agents) and they avoid making excessive or inadequate concession in a market situation.