Agents in Electronic Commerce: Component Technologies for Automated Negotiation and Coalition Formation

Automated negotiation and coalition formation among self-interested agents are playing an increasingly important role in electronic commerce. Such agents cannot be coordinated by externally imposing their strategies. Instead the interaction protocols have to be designed so that each agent is motivated to follow the strategy that the protocol designer wants it to follow. This paper reviews six component technologies that we have developed for making such interactions less manipulable and more efficient in terms of the computational processes and the outcomes: 1. OCSM-contracts in marginal cost based contracting, 2. leveled commitment contracts, 3. anytime coalition structure generation with worst case guarantees, 4. trading off computation cost against optimization quality within each coalition, 5. distributing search among insincere agents, and 6. unenforced contract execution. Each of these technologies represents a different way of battling self-interest and combinatorial complexity simultaneously. This is a key battle when multi-agent systems move into large-scale open settings.     

Surplus equivalence of leveled commitment contracts

In automated negotiation systems consisting of self-interested agents, contracts have traditionally been binding. Leveled commitment contracts—i.e., contracts where each party can decommit by paying a predetermined penalty—were recently shown to improve expected social welfare even if agents decommit strategically in Nash equilibrium. Such contracts differ based on whether agents have to declare their decommitting decisions sequentially or simultaneously, and whether or not agents have to pay the penalties if both decommit. For a given contract, these mechanisms lead to different decommitting thresholds, probabilities, and expected social welfare. However, this paper shows that each of these mechanisms leads to the same social welfare when the contract price and penalties are optimized for each mechanism separately. Our derivations allow agents to construct optimal leveled commitment contracts. We show that such integrative bargaining does not hinder distributive bargaining: the surplus can be divided arbitrarily (as long as each agent benefits), e.g., equally, without compromising optimality. Nonuniqueness questions are answered. We also show that surplus equivalence ceases to hold if agents are not risk neutral.     

eMediator: A Next Generation Electronic Commerce Server

This paper presents eMediator , an electronic commerce server prototype that demonstrates ways in which algorithmic support and game–theoretic incentive engineering can jointly improve the efficiency of e–commerce. eAuctionHouse , the configurable auction server, includes a variety of generalized combinatorial auctions and exchanges, pricing schemes, bidding languages, mobile agents, and user support for choosing an auction type. We introduce two new logical bidding languages for combinatorial markets: the XOR bidding language and the OR–of–XORs bidding language. Unlike the traditional OR bidding language, these are fully expressive. They therefore enable the use of the Clarke–Groves pricing mechanism for motivating the bidders to bid truthfully. eAuctionHouse also supports supply/demand curve bidding. eCommitter , the leveled commitment contract optimizer, determines the optimal contract price and decommitting penalties for a variety of leveled commitment contracting mechanisms, taking into account that rational agents will decommit strategically in Nash equilibrium. It also determines the optimal decommitting strategies for any given leveled commitment contract. eExchangeHouse , the safe exchange planner, enables unenforced anonymous exchanges by dividing the exchange into chunks and sequencing those chunks to be delivered safely in alternation between the buyer and the seller.     

Model and control holonic manufacturing systems based on fusion of contract nets and Petri nets

Holonic manufacturing systems (HMS) can be modeled as multi-agent systems to which contract net protocol can be effectively and robustly applied. However, the lack of analysis capability of contract nets makes it difficult to avoid undesirable states such as deadlocks in HMS. This paper presents a framework to model and control HMS based on fusion of Petri net and multi-agent system theory. The main results include: (1) a multi-agent model and a collaboration process to form commitment graphs in HMS based on contract net protocol, (2) a procedure to convert commitment graph to collaborative Petri net (CPN), and (3) feasible conditions and collaborative algorithms to award contracts in HMS based on CPNs.     

Market-Based Task Allocation Mechanisms for Limited-Capacity Suppliers

This paper reports on the design and comparison of two economically inspired mechanisms for task allocation in environments where sellers have finite production capacities and a cost structure composed of a fixed overhead cost and a constant marginal cost. Such mechanisms are required when a system consists of multiple self-interested stakeholders that each possess private information that is relevant to solving a systemwide problem. Against this background, we first develop a computationally tractable centralized mechanism that finds the set of producers that have the lowest total cost in providing a certain demand (i.e., it is efficient). We achieve this by extending the standard Vickrey-Clarke-Groves mechanism to allow for multiattribute bids and by introducing a novel penalty scheme such that producers are incentivized to truthfully report their capacities and their costs. Furthermore, our extended mechanism is able to handle sellers' uncertainty about their production capacity and ensures that individual agents find it profitable to participate in the mechanism. However, since this first mechanism is centralized, we also develop a complementary decentralized mechanism based around the continuous double auction. Again, because of the characteristics of our domain, we need to extend the standard form of this protocol by introducing a novel clearing rule based around an order book. With this modified protocol, we empirically demonstrate (with simple trading strategies) that the mechanism achieves high efficiency. In particular, despite this simplicity, the traders can still derive a profit from the market which makes our mechanism attractive since these results are a likely lower bound on their expected returns     

Time-bound negotiation framework for electronic commerce agents

For efficient and informative coordination of agents especially in electronic commerce environment, a time-bound agent negotiation framework is proposed utilizing a time-based commitment scheme. By attaching commitment duration to agent messages, the traditional contract net protocol is extended to a time-bound negotiation framework (TBNF). The proposed negotiation framework has a new message type which allows for parties to agree upon the extension of a commitment duration, and a novel commitment concept in the form of negative commitment. The semantics of the messages with the commitment duration are interpreted, and then the three typical negotiation protocols are formally defined and compared — nothing-guaranteed protocol, acceptance-guaranteed protocol, and finite-time guarantee protocol — which can be incorporated into TBNF. The TBNF should provide a background for efficient and effective electronic commerce negotiation while accommodating each agent's adaptive negotiation strategy.     

Verifying Compliance with Commitment Protocols

Interaction protocols are specific, often standard, constraints on the behaviors of autonomous agents in a multiagent system. Protocols are essential to the functioning of open systems, such as those that arise in most interesting web applications. A variety of common protocols in negotiation and electronic commerce are best treated as commitment protocols, which are defined, or at least analyzed, in terms of the creation, satisfaction, or manipulation of the commitments among the participating agents.When protocols are employed in open environments, such as the Internet, they must be executed by agents that behave more or less autonomously and whose internal designs are not known. In such settings, therefore, there is a risk that the participating agents may fail to comply with the given protocol. Without a rigorous means to verify compliance, the very idea of protocols for interoperation is subverted. We develop an approach for testing whether the behavior of an agent complies with a commitment protocol. Our approach requires the specification of commitment protocols in temporal logic, and involves a novel way of synthesizing and applying ideas from distributed computing and logics of program.     

基于Bit承诺的合同网模型

在分析现有合同网模型的基础上,针对合同网协商过程中的安全问题,利用Bit承诺协议和RSA算法,给出一个具有安全性的合同网协商模型,保证Agent之间信息的安全传输,防止协作Agent反悔、拒绝履行承诺。该协商模型满足不可否认性和强可验证性,投标价格保密安全,技术简单,通信量小。     

基于BDI的Agent合同网实现

合同网是一个用于分布式问题求解的高层通信协议,本文给出了一个扩充的合同网协议的会话策略和一个BDI精神状态形成模型,并在此基础上将BDI模型用于合同网协议,给出了实现合同同网协议的一系列BDI行为驱动规则。本文在合同网协议的招投标过程中引入了信任度、稳健度和积极程度等精神状态参数,这类参数有助于改善协作质量,从而使系统具有较好的适应性和灵活性。     

Agent-based Cloud service composition

Service composition in multi-Cloud environments must coordinate self-interested participants, automate service selection, (re)configure distributed services, and deal with incomplete information about Cloud providers and their services. This work proposes an agent-based approach to compose services in multi-Cloud environments for different types of Cloud services: one-time virtualized services, e.g., processing a rendering job, persistent virtualized services, e.g., infrastructure-as-a-service scenarios, vertical services, e.g., integrating homogenous services, and horizontal services, e.g., integrating heterogeneous services. Agents are endowed with a semi-recursive contract net protocol and service capability tables (information catalogs about Cloud participants) to compose services based on consumer requirements. Empirical results obtained from an agent-based testbed show that agents in this work can: successfully compose services to satisfy service requirements, autonomously select services based on dynamic fees, effectively cope with constantly changing consumers’ service needs that trigger updates, and compose services in multiple Clouds even with incomplete information about Cloud participants.     

GoCo: planning expressive commitment protocols

This article addresses the challenge of planning coordinated activities for a set of autonomous agents, who coordinate according to social commitments among themselves. We develop a multi-agent plan in the form of a commitment protocol that allows the agents to coordinate in a flexible manner, retaining their autonomy in terms of the goals they adopt so long as their actions adhere to the commitments they have made. We consider an expressive first-order setting with probabilistic uncertainty over action outcomes. We contribute the first practical means to derive protocol enactments which maximise expected utility from the point of view of one agent. Our work makes two main contributions. First, we show how Hierarchical Task Network planning can be used to enact a previous semantics for commitment and goal alignment, and we extend that semantics in order to enact first-order commitment protocols. Second, supposing a cooperative setting, we introduce uncertainty in order to capture the reality that an agent does not know for certain that its partners will successfully act on their part of the commitment protocol. Altogether, we employ hierarchical planning techniques to check whether a commitment protocol can be enacted efficiently, and generate protocol enactments under a variety of conditions. The resulting protocol enactments can be optimised either for the expected reward or the probability of a successful execution of the protocol. We illustrate our approach on a real-world healthcare scenario.     

Coordinating patient preferences through automated negotiation: A multiagent systems model for diagnostic services scheduling

This paper presents a multiagent systems model for patient diagnostic services scheduling. We assume a decentralized environment in which patients are modeled as self-interested agents who behave strategically to advance their own benefits rather than the system wide performance. The objective is to improve the utilization of diagnostic imaging resources by coordinating patient individual preferences through automated negotiation. The negotiation process consists of two stages, namely patient selection and preference scheduling. The contract-net protocol and simulated annealing based meta-heuristics are used to design negotiation protocols at the two stages respectively. In terms of game theoretic properties, we show that the proposed protocols are individually rational and incentive compatible. The performance of the preference scheduling protocol is evaluated by a computational study. The average percentage gap analysis of various configurations of the protocol shows that the results obtained from the protocol are close to the optimal ones. In addition, we present the algorithmic properties of the preference scheduling protocol through the validation of a set of eight hypotheses.     

The Fabricare scheduling prototype suite: Agent interaction and knowledge base

This work presents a prototype system (named Fabricare) for the scheduling of manufacturing orders, based on holonic manufacturing systems using extended logic programming. The system is composed of several holons that cooperate among themselves using an extension to the contract net protocol named contract net with constraint propagation protocol. This protocol enables explicit cooperation among service providers that use constraint propagation in order to guarantee the precedence relationships between the different operations participating in the same task. Some precautions have been taken to avoid conflicts and combinatorial explosion. The complexity analysis of the protocol has been performed. The main agents in this system are task and resource agents; the knowledge bases of these agents are presented. Also, a notation for representation of incomplete information on an agent's knowledge base is presented.     

A learning-enabled infrastructure for electronic contracting agents

With the vigorous development of electronic commerce these years, many experts and scholars have devoted themselves to various fields of research and application. Of these fields, electronic contracting is a new research topic in great demand. In spite of its promise, electronic contracting involves the standardization of ontology and automation of negotiation, which renders the implementation of electronic contracting difficult. In view of the necessity of electronic contracting, we present a learning-enabled agent-based infrastructure and claim that it will be a solution to the problems encountered during the process of electronic contracting by a variety of evaluations. In this infrastructure, the applications of an agent are viewed as a set of application ontologies, each of which is a combination of a context ontology and a object ontology so that the negotiation context and automation of negotiation can be flexibly integrated in this infrastructure. The infrastructure enables the automation of electronic contracting through a general and automatic communication protocol and provides reusability by the componentization of agents. The infrastructure provides personalized multiattribute evaluation and proposal generation by a mechanism, which is a combination of neural networks and genetic algorithms, in order to enable the automatic negotiation ability at agents.     

Exception diagnosis in multiagent contract executions

We propose a diagnosis procedure that agents can use to explain exceptions to contract executions. Contracts are expressed by social commitments associated with temporal constraints. The procedure reasons from the relations among such commitments, and returns one amongst different possible mismatches that may have caused an exception. In particular, we consider two possibilities: misalignment, when two agents have two different views of the same commitment, and misbehavior, when there is no misalignment, but a debtor agent fails to oblige. We also provide a realignment policy that can be applied in case of a misalignment. Our formalization uses a reactive form of Event Calculus. We illustrate the workings of our approach by discussing a delivery process from e-commerce as a case study.     

Developing cooperation mechanism for multi-agent systems with Petri nets

Although the contract net protocol answers some of the questions in cooperative distributed problem solving (CDPS), it raises many others that CDPS researchers are still trying to answer. In contract net protocol, an agent may play the role of a manager or a bidder. Without a coordination mechanism, a manager may acquire excessive resources from the bidders in forming a collaborative network to execute the assigned task and thus hinder the progress of the tasks assigned to other managers due to resource contention. As a result, application of contract net protocol may not always lead to feasible solutions to accomplish tasks effectively. As a general framework for exchanging messages, the original contract net protocol does not prescribe how agents should cooperate. How to develop a collaborative mechanism to effectively perform the tasks is an important issue. This paper aims to improve the insufficiency of the contract net by developing a mechanism to facilitate cooperation of agents to accomplish their tasks while avoiding undesirable states and enhance the overall system performance in manufacturing systems. To achieve these objectives, detail process models about how agents accomplish their tasks are required. Due to the advantages in modeling concurrent, synchronous and/or asynchronous activities, Petri nets are adopted in this paper. Based on Petri net models, we study the information needed for agents to make cooperative decisions, mechanism to make agents cooperate, and how to enhance the performance in the system level by taking advantage of the agents’ cooperation capabilities. To characterize the condition for cooperation, we represent the collaborative networks formed based on the contract net protocol with Petri nets and then find the condition for a collaborative network to be feasible. The feasible condition also serves as a condition for the development of cooperation mechanism for managers. We propose a cooperation mechanism based on the idea of resource donation, including unilateral resource donation and reciprocal resource donation. Implementation architecture has also been proposed to realize our methodology.     

Implicit commitments: Heterogeneous agent coordination for retrieval and assembly of distributed image data

This paper describes a multiple agent system for distributed planning, specifically for intelligent network information retrieval. The system consists of a set of reactive agents located at each information- or capability-provider site plus an agent to track each information request. The agents negotiate with each other to assemble a distributed plan for satisfaction of each information need and each agent also interfaces with local retrieval and data processing functions. The idea of an implicit commitment is presented as providing a way to enable automated coordination of resources (information and capabilities) localized among heterogeneous agents. The advantages of a shared machine implemented by such a commitment protocol are discussed and an implementation called TRACS for retrieval and assembly of satellite image data is presented.This research was carried out at Teleos Research Corporation under a contract with Lockheed Space and Missiles Corporation. I would like to thank Stanley Rosenschein, Marianne Winslett, and two anonymous reviewers for their comments and suggestions.     

带有公平电子合同的交易协议

基于原子的公平匿名交易协议,采用两阶段提交的思想,通过可信第三方TTP(trusted third party)来控制交易的提交。在进行大量交易时,TTP会成为瓶颈。文中在原协议的基础上进行改进,引入了公平电子合同,改变交易提交方式,减少了TTP的工作量,但并没有破坏其原子性和公平匿名性,同时交易后产生的电子合同可具有传统交易合同的作用。     

Negotiating using rewards

Negotiation is a fundamental interaction mechanism in multi-agent systems because it allows self-interested agents to come to mutually beneficial agreements and partition resources efficiently and effectively. Now, in many situations, the agents need to negotiate with one another many times and so developing strategies that are effective over repeated interactions is an important challenge. Against this background, a growing body of work has examined the use of Persuasive Negotiation (PN), which involves negotiating using rhetorical arguments (such as threats, rewards, or appeals), in trying to convince an opponent to accept a given offer. Such mechanisms are especially suited to repeated encounters because they allow agents to influence the outcomes of future negotiations, while negotiating a deal in the present one, with the aim of producing results that are beneficial to both parties. To this end, in this paper, we develop a comprehensive PN mechanism for repeated interactions that makes use of rewards that can be asked for or given to. Our mechanism consists of two parts. First, a novel protocol that structures the interaction by capturing the commitments that agents incur when using rewards. Second, a new reward generation algorithm that constructs promises of rewards in future interactions as a means of permitting agents to reach better agreements, in a shorter time, in the present encounter. We then go on to develop a specific negotiation tactic, based on this reward generation algorithm, and show that it can achieve significantly better outcomes than existing benchmark tactics that do not use such inducements. Specifically, we show, via empirical evaluation in a Multi-Move Prisoners' Dilemma setting, that our tactic can lead to a 26% improvement in the utility of deals that are made and that 21 times fewer messages need to be exchanged in order to achieve this.