Multiagent and Grid Systems - Volume 4, issue 1

Authors: Sim, Kwang Mong | Zhang, Minjie | Ito, Takayuki

Article Type: Editorial

DOI: 10.3233/MGS-2008-4101

Citation: Multiagent and Grid Systems, vol. 4, no. 1, pp. 1-3, 2008

Authors: An, Bo | Sim, Kwang Mong | Miao, Chun Yan | Shen, Zhi Qi

Article Type: Research Article

Abstract: In dynamic and complex negotiation environments, a negotiation agent can participate or quit negotiation at any time and can potentially reach an agreement with more than one trading partner as the result of the existence of dynamic outside options. Thus, it's important for a negotiation agent to make a decision on when to complete negotiation given its trading partners' current proposals and market dynamics. Rather than explicitly modeling all the trading partners, this paper presents a novel decision making strategy based on a tractable Markov chain model of negotiation process. An agent can use this model to determine whether to …accept the best proposal of its trading partners or let negotiation proceed forward during each round of negotiation. Experimental results suggest that the proposed strategy achieved more favorable negotiation outcomes as compared with the general strategy. Show more

Keywords: Automated negotiation, negotiation agents, Markov Chains

DOI: 10.3233/MGS-2008-4102

Citation: Multiagent and Grid Systems, vol. 4, no. 1, pp. 5-23, 2008

Authors: Tsang, Edward P.K. | Gosling, Tim | Virginas, Botond | Voudouris, Chris | Owusu, Gilbert | Liu, W.

Article Type: Research Article

Abstract: This paper is about business modelling and negotiation protocol design in distributed scheduling, where individual agents have individual (potentially conflicting) interests. It is motivated by BT's workforce scheduling problem, in which multiple service providers have to serve multiple service buyers. The service providers and buyers all attempt to maximize their own utility. The overall problem is a multi-objective optimization problem; for example, one has to maximize completion rates and service quality and minimize travelling distances. Although the work is motivated by BT's business operations, the aim is to develop a general negotiation protocol for staff empowerment. …Standard contract net is a practical strategy in distributed scheduling where agents may have conflicting objectives. In this paper, we have introduced a retractable contract net protocol, RECONNET, which supports hill-climbing in the space of schedules. It is built upon a job-release and compensation mechanism. A system based on RECONNET has been implemented for BT's workforce scheduling problem. The software, which we call ASMCR, allows the management to exert full control over the company's multiple objectives. The manager generates a Pareto set of solutions by defining, for each buyer and seller, the weights given to each objective. ASMCR gives service buyers and sellers ownership of their problem and freedom to maximize their performance under the criteria defined by the management. ASMCR was tested on real-sized problems and demonstrated to meet BT's operational time requirement. It has full potential to be further developed for tackling BT's workforce scheduling problem. Show more

Keywords: Management, negotiation protocols, computational mechanism design, modelling, multi-objective optimization

DOI: 10.3233/MGS-2008-4103

Citation: Multiagent and Grid Systems, vol. 4, no. 1, pp. 25-44, 2008

Authors: Lai, Guoming | Sycara, Katia | Li, Cuihong

Article Type: Research Article

Abstract: This paper presents a decentralized model that allows self-interested agents to reach “win-win” agreements in a multi-attribute negotiation. The model is based on an alternating-offer protocol. In each period, the proposing agent is allowed to make a limited number of offers. The responding agent can select the best out of these offers. In the case of rejection, agents exchange their roles and the negotiation proceeds to the next period. To make counteroffers, an agent first uses the heuristic of choosing the offer on an indifference (or “iso-utility”) curve/surface that is closest to the best offer made by the opponent in …the previous period, and then taking this offer as the seed, chooses several other offers randomly in a specified neighborhood of this seed offer. Experimental analysis shows agents can reach near Pareto optimal agreements in quite general situations following the model where agents may have complex preferences on the attributes and incomplete information. This model does not require the presence of a mediator. Show more

Keywords: Multi-attribute negotiation, pareto optimality, win-win, rational preference, incomplete information, self-interested agents

DOI: 10.3233/MGS-2008-4104

Citation: Multiagent and Grid Systems, vol. 4, no. 1, pp. 45-65, 2008

Authors: Ito, Takayuki | Klein, Mark | Hattori, Hiromitsu

Article Type: Research Article

Abstract: Multi-Issue Negotiation protocols have been studied very widely and represent a promising field since most of negotiation problems in the real-world are complex ones including multiple issues. In particular, in reality issues are constrained each other. This makes agents’ utilities nonlinear. There have been a lot of work on multi-issue negotiations. However, there have been very few work that focus on nonlinear utility spaces. In this paper, we assume agents have nonlinear utility spaces. For the linear utility domain, agents can aggregate the utilities of the issue-values by simple linear summation. In the real world, such aggregations are unrealistic. For …example, we cannot just add up the value of car’s tires and the value of car’s engine when engineers design a car. In this paper, we propose an auction-based multiple-issue negotiation protocol among nonlinear utility agents. Our negotiation protocol employs several techniques, i.e., adjusting sampling, auction-based maximization of social welfare. Our experimental results show that our method can outperform the existing simple methods in particular in the huge utility space that can be often found in the real-world. Further, theoretically, our negotiation protocol can guarantee the completeness if some conditions are satisfied. Show more

Keywords: Multi-issue negotiation, non-linear utility, multi-agent systems

DOI: 10.3233/MGS-2008-4105

Citation: Multiagent and Grid Systems, vol. 4, no. 1, pp. 67-83, 2008

Authors: Bai, Quan | Zhang, Minjie

Article Type: Research Article

Abstract: As social entities, intelligent agents need to collaborate with others regardless of whether they are cooperative or self-interested. Compared with cooperative agents, collaborations among self-interested agents are more complex and dynamic due to the selfish features. Self-interested agents are impelled to cooperate with others by their individual goals. In an agent team composed of self-interested agents, “common” goals of agents may change to be conflict as the environment changes. Especially in open and dynamic environments, if factors such as agent goals, task requirements and resources have been changed, a selfish agent may need to modify or even relieved the collaboration …relationships with its “colleagues”. Otherwise the collaboration would be conflict or even harmful to its individual goal. Therefore, it is important to include rational team forming mechanisms in self-interested multi-agent systems. Without a rational team-forming mechanism, agent teams in a system may have unreasonable or outdated compositions which obstruct (agent) team members to purchase profits or cause unnecessary resource consumptions. Focusing on general self-interested multi-agent systems, this paper suggests a flexible team forming mechanism that can enable agents to select team members with reasonable terms and objects. The flexibility of the mechanism enables agents to form more rational teams that can avoid potential benefit conflicts among self-interested team members. Show more

DOI: 10.3233/MGS-2008-4106

Citation: Multiagent and Grid Systems, vol. 4, no. 1, pp. 85-101, 2008

Authors: Hemaissia-Jeannin, Miniar | Seghrouchni, Amal El Fallah | Labreuche, Christophe

Article Type: Research Article

Abstract: In this paper, a new protocol to address multilateral multi-issue negotiation in a cooperative context is presented. Complex dependencies between multiple issues are considered by modelling the preferences of the agents with a multi-criteria decision aid tool, also enabling to extract relevant information on a proposal assessment. This information is used in the protocol to help in accelerating the search for a consensus between the cooperative agents. In addition, the negotiation procedure is defined to address distributed allocation problem and applied in a crisis management context, with the common objective of the agents considered in the preferences of a mediator …agent. Show more

DOI: 10.3233/MGS-2008-4107

Citation: Multiagent and Grid Systems, vol. 4, no. 1, pp. 103-123, 2008