We propose a declarative approach for prototyping automated negotiations in multi-agent systems. Our approach is demonstrated by using Jason agent programming language to describe English and Dutch auctions.
Automated negotiations are common in multi-agent systems (MAS)
– e.g. bargaining, auctions [
Although there are many methods of automated negotiations, they generally fail to properly address the reusability and the extensibility of the proposed approaches. In most applications the negotiation mechanism is very specific and hard coded, making the reusability of research results difficult.
In order to treat these issues we have set up a research project aiming to develop a generic, reusable negotiation framework. One of the key insights of our approach is that an (automated) negotiation has two main components: the protocol which governs agents’ interaction during negotiation and the strategy of participating agents. While the analysis and design of specific negotiations mechanisms and the development of appropriate strategies with desired properties (e.g. stability, equilibrium, efficiency, a.o) has received a lot of attention in the context of particular situations, they have not been properly addressed with regard to reusability and extensibility.
This paper is a follow-up of our initial proposal [
The system architecture is based on our work [
Conceptually, the declarative specification of a negotiation is composed of three essential ingredients: (i) Generic Negotiation Protocol (GNP) which defines and governs the interaction between the agents that are part of the system and it is the same for all of them, independently of their role in the negotiation (i.e. buyer, seller); (ii) Declarative Negotiation Mechanism (DNM) is specific to a given negotiation type and it serves to customize the GNP for representing the specific conditions and events that enable the permissible actions of specific AP agents; and (iii) Custom Negotiation Strategy (CNS) is specific to a given AP and must be consistent with the DNM. It is used by the AP to select and configure a specific negotiation action that could be most useful in a given negotiation context.
Based on the three features described above we can define the following metaphorical equations that more succinctly describe the agents present in our framework:
AH = GNPhost + DN Mhost
AP = GNPparticipant + DN Mparticipant + CNS
These ingredients can be consistently bound into descriptions of
AH and respectively AP behaviors by making them to refer a
common core vocabulary of terms that can be used for defining and
parameterizing the space of negotiation types [
registered(info(Sum,Increment), status(Offer, Left_items, State))). +fold[source(A)] : registered(A) <- -registered(A); .send(A, tell, not_registered). +bid(Offer,Items)[source(A)] : check_protocol(A) & check_proposal(Offer,Items) & not(terminate(Offer,Items)) <- -+state(processing); !update_status(A,Offer,Items); !inform_participants(A,Offer); -+state(bidding). +!close : check_winner <- ?initiator(I); -+state(closed); ?bidders(A); .send(I, tell, winner(A)); .send(A, tell, winner).
The GNP describes the permissible conversations involving a set of negotiation agents comprising the following generic roles: (i) role of AH; there is a single agent playing this role in a negotiation; and (ii) role of AP; there are one or more agents playing this role in a negotiation. Thus the GNP is agnostic of any details that are specific to a particular negotiation type. Consequently, it must only expose the basic negotiation actions that are common to as many negotiation types, leaving unspecified the specific details of a certain negotiation type. Those details can be captured and declaratively represented with the help of the DNM.
We have identified the following set of actions as sufficient for the purpose of introducing our proof-of-concept implementation: (1) register used by an AP to register itself with a specific AH; (2) bid used to place a bid; (3) tell/ask depending on the push/pull semantics, the protocol can expose information to the participants either automatically or on request; (4) fold used by an AP to get out of an auction; (5) close used by the AH to notify the APs about the auction termination; and (6) winner used by the AH to notify the winner participants.
Jason is probably the best known example of agent programming language that follows the Belief-Desire-Intention (BDI) model. It supports a declarative programming style, closer to logic programming. We chose Jason as we believe that the mix of declarative, goal-oriented and knowledge representation features of Jason make it a good candidate implementation language for our prototype. Furthermore its meta-programming features (e.g. representing programs as code) has helped with our implementation.
Our implementation provides an internal action that loads the rules for a specific negotiation type. This has to be called by agents before they start the negotiation in order to customize their GNP. Once loaded, the rules can be used like any other rule defined in the Jason agent source file.
The Jason implementation of the AH role of the GNP, presented in listing 1, closely follows the definition of the GNP outlined above. Very briefly, the plan for +register registers a participant and sends it the current quote (i.e. the value of the outstanding bid) – this presumes push semantics; the +bid plan updates the quote and pushes messages with the new value to all the participants; the +close plan ends the auction and notifies any winner if there is one. All the plans keep track of the current state the agent is in.
Note that the plans make use of rules that are defined by the
DNM, which we will discuss next. While an AS conceptually implements a type of auction, an AH is spawned for each new auction started by the AS. When initially started the AH loads the DNM specific to the auction implemented by the AS and a further message from the AIP is responsible for initializing the parameters of the DNM with appropriate values.
We chose a rule-based representation for our DNM, which builds
on our previous approach presented in [
Listing 2 shows the rules used to customize the AH for our running example, an English auction. Note that these rules illustrate the DNM from the AH perspective.
Besides their formal parameters, the rules are also implicitly parameterized by the current state of the negotiation process – here we are using the annotations mechanism from Jason to achieve this, e.g. the [state(bidding)] annotation on the check_proposal rule makes it applicable only when the agent is in the bidding state. 5.
We have presented our approach on developing a generic negotiation mechanism (as part of a generic negotiation framework) using the Jason programming language. We believe the solution is elegant and promising, due to its declarative nature and modular nature. Basically the GNP is independent of the negotiation type, negotiation rules are used to customize it.
One of the necessary next steps is to find a suitable serialization format for the rules used to customize the GNP, such as RuleML.2 Another direction, as mentioned earlier, is to define a suitable CNO for the negotiation framework. Yet a third research direction is to factor out the GNP so that it can be used in multiple platforms–e.g. Jason, Java+JADE. 6.
The work of Alex Muscar was supported by the strategic grant POSDRU / CPP107 / DMI1.5 / S / 78421, Project ID 78421 (2010), co-financed by the European Social Fund Investing in People, within the Sectoral Operational Programme Human Resources Development 2007 - 2013. The work of Costin Ba˘dica˘ was supported by the multilateral agreement on academic cooperation in 2012 between Serbia (Novi Sad), Romania (Craiova), and Poland (Warsaw and Gdansk) on “Agent Technologies, Tools, Environments, Applications”. 2RuleML – http://ruleml.org/ // Dutch auction check_proposal(Offer,Items) [state(bidding)] :asked_price(AskedPrice) & items(Left_items) & Left_items>=Items &
Offer <= AskedPrice. +!update_status(A,Offer,Items) <- .time(H,M,Sec2); ?items(I); ?increment(Increment); ?asked_price(AskedPrice); ?bidders(B); -+last_offer(Offer); -+items(I-Items); -+bidders([A|B]); -+asked_price(AskedPrice+Increment); -+last_update(Sec2). // English auction check_proposal(Offer,Items) [state(bidding)] :increment(Increment) & last_offer(Quote) & items(Left_items) & Left_items>=Items &
Offer >= Quote + Increment. +!update_status(A,Offer,Items) <- -+last_offer(Offer); -+bidders([A]).