ABSTRACT

Automated negotiation deals with multiple autonomous agents, where the agents adapt their behaviour depending on the characteristics of other agents and scenarios and reach an agreement. In this paper, we propose the agent named Lightspeed, which can make active negotiations against many different opponents. Our agent employs the time-dependent strategy to compute target utility and also keep track of the opponent’s bid to propose an optimal offer based on their most preferred proposal.                        

1.     INTRODUCTION

The negotiation is based on SOAP(Stacked alternating offers protocol) between two agents (i.e. Bilateral negotiation). According to the protocol, each participant gets the chance to accept, reject or counter offer the bid the other agent is proposing. Agents should accept the offer before the deadline to reach an agreement, or else the negotiation fails [1].

Comparatively to BOA (bidding strategy, opponent model and acceptance strategy) architecture, lightspeed agent makes use of simple opponent modelling by considering the previous offers proposed by the opponent. But to make the proposals, it follows the time-dependent strategy.

2.     AGENT DESIGN

Lightspeed agent deals with preference uncertainty that is the agent will have partial information about the bid space. So to estimate the utility we can override the estimateUtilitySpace function which uses simple counting heuristics to approximate the utility function. This function returns the AbstractUtilitySpace object which is created using the domain and the bid ranking. The ranking of the bid is from low to high utility.

2.1     Bidding Strategy

After the init method is called the receive message method is initiated internally by GENIUS. The functionality of this method is depicted in Algorithm 1. Whenever the opponent is making an offer, it is compared with threshold utility, if the utility is above threshold utility then store the bid in Tree-Map data structure. Then the action is chosen to accept, reject or counter offer the bid based on the algorithm

Algorithm 1 Receive offer from the opponent

1: Input: Opponent’s offer

2: Output: Inject the opponent bid to bid tree

3: Begin

4: if the sender is making an offer

5: OpponentBid ← get the bid from the opponent’s offer

6: if utility of OpponentBid >= thresholdUtility

7: bidSpaceMap ← search for an opponent’s utility bucket in the tree

8: if bidSpaceMap contains utility

9: sb ← update the opponent’s bid

10: else create the new utility bucket and store the bid in bidSpaceMap tree

11: else ignore the opponent’s bid

12: End

2.2     Acceptance strategy

If the utility of the bid proposed by the opponent is higher than the lightspeed’s accepted utility (i.e., target utility) at the time of concession lightspeed agrees the utility and the negotiation ends. The algorithm 2 depicts the acceptance condition.

Algorithm 2 Acceptance of the bid

1: Input: the last received bid of the opponent

2: output: Accept or reject the bid

3: Begin

4: if utility of opponentBid >= acceptUtility

5: return Accept

6: else return reject //And counter-offer bid

7: End

2.3     Time-dependent strategy

Lightspeed agent depends on time-dependent tactics to counter offer the bid which calculates a target utility at each turn according to the current time t. The decision function provides the bid depending on the time with the utility closest to [2-3].

u(t) = Pmin + (Pmax − Pmin) · (1 − F(t)),

where 

F(t) = k + (1 − k) · t1/e

The value of Pmin relates threshold utility, and Pmax relates to maximum bid which is obtained from the negotiation settings. The constants k = 0 determines the first proposal, and the decay rate e is chosen randomly for conceding. For 0 < e < 1 the agents concede slowly, it is called Boulware. And for e > 1 the agent concedes quickly. It is called Conceder [4]. The algorithm 3 shows the calculation to generate the target utility and to construct the best bid.

Algorithm 3 Construct the bid

1: Input: maxUtility, thresholdUtility, decayRate

2: output: my best bid

3: Begin

4: k ← 0, e ← decayRate

5: while the bid is not null do

6: timeElapsed ← get the time from timeLine

7: f_t ← k +(1 – k)* t1/e

8:  u_t ← thresholdUtility + (maxUtility – thresholdUtility)*(1 – f_t)

9:  acceptUtility ← round of u_t

10:  if bidSpaceMap tree contains targetUtility

11: subtree ← get the sorted most occurred utility leaf node

12:  sb ← counteroffer the random bid from the subtree

13: return the bid from sb

14: else generate the randomBid which has the utility greater than equal to target utility

15: End

The challenge is to make the negotiation successful by knowing about the opponent and propose an offer based on the opponent bid. The good opponent model improves the quality of negotiation by reaching win-win agreements [7-8], reduce the cost by disagreement. The bidding strategy differs by keeping track of the opponent’s bid and offer the best bid from similarly preferred opponent’s bid [5-6]. Inspired by the frequency model [9], the opponent bid and its round off utility are stored in the tree in the sorted order. From the table 1, we can conclude that utility 0.7 has the frequency two, so when the target utility is above 0.69 the utility of counteroffered bid will be 0.7 which is most prefered by the opponent. Now consider the agents are dealing with party domain, Lightspeed agent stores utility of opponent bid which is greater than the threshold value (i.e., 0.65). When the agent’s target utility (i.e., 0.82) is noted in utility keys at the time of concession the Lightspeed counteroffer a random bid from the bid tree whose utility is greater than or equal to 0.82. This functionality is defined in algorithm 3.

Table 1. Results of competition with the frequency of offered bid.

Target-util

utility-keys

List info

counter offer Bid

0.82

[0.66, 0.7, 0.82]

[Bid List size: 1, Bid List size: 2, Bid List size: 1]

[Food: Catering, Drinks: Beer Only, Location: Party Room, Invitations: Plain, Music: MP3, Cleanup: Water and Soap]

At the same time, when the target utility is not listed in utility keys, then counter offer the random bid whose utility should be greater than or equal to the target utility. From table 2, the target utility is 0.83, but it is not listed in the bid tree list of utility keys. So the generated random bid has the utility 0.86 which is more than the target value. So like AgentK, Lightspeed also proposes bid randomly which is above the target utility [10].

Table 2. Results of competition with random bid utility greater than target utility.

target-util

utility-keys

Random bid utility

counter offer Bid

0.83

[0.66, 0.82]

0.86

[Food: Catering, Drinks: Handmade Cocktails, Location: Party Room, Invitations: Custom, Printed, Music: MP3, Cleanup: Specialized Materials]

3.     EXPERIMENTS AND ANALYSIS

In this section, we analyze the performance of the lightspeed agent with different domains, preference uncertainty and distance measure with the Nash bargaining solution. Figure 1 shows the results of the experimenting agent by plotting average individual utility against different domains. From the experiments, it is noticed that the utility decreases when there is an increase in domain size.

Figure 1. Results between agents with various domain sizes.

While experimenting with various preference uncertainty, the results from figure 2 show that with low uncertainty (i.e., three-fourths of the bid space is known) of lower domain size the utility is 1. But with higher uncertainty (i.e., only one-fourth of the bid space is known) and higher domain size, the average utility becomes much less when compared to others. Table 3 summarizes the result. So the agent gets higher utility when it deals with lower uncertainty.

Table 3. Results of different domain size with various uncertainty.

Domain

Low_uncertainity

Medium_uncertainity

High_uncertainity

Politics

0.817918

0.7710178

0.753179

Wind_farm

0.706477

0.79346

0.751493

New_sporthal

1

0.97816

0.932877

Figure 2. Results of agents performance against low, high and medium uncertainty.

From figure 3 we can conclude that Lightspeed agent is thriving with a lower distance of agreement with Nash bargaining solution in smaller size domain, but gradually the distance increases when there is an increase in domain size and the success rate also falls under the larger domain. When the lightspeed agent is compared with Agent 8, the distance is higher for our agent because Agent 8 may have a stronger opponent modelling strategy with better heuristics.

Figure 3. Results of domain distance against successful agreements.

4.     CONCLUSION AND FUTURE WORK

In this paper, we have proposed the lightspeed that is an automated negotiating agent based on SOAP protocol. The negotiation is between two agents if both agents accept the bid they reach an agreement. Lightspeed agent follows the time-dependent strategy to estimate the target utility and propose the bid based on the proposed opponent’s bid whose utility is higher than the threshold utility if that target utility is not listed in utility bucket then offer the bid randomly with utility greater than or equal to target utility. It also accepts the opponent bid when the opponent bid’s utility is greater than the lightspeed agents accept utility.

Our agents have some deficiencies, so the solutions to improve the performance of lightspeed agent is discussed in this section. The threshold utility is hardcoded in our program. So this can be improved by first setting the threshold utility to some best utility and gradually decrease over time will help the agents to make agreements in less duration. The utility bucket to store the bid and with its utility is hardcoded to 100. There arises the memory issue when it crosses 100, and if the list of the utility is small, it doesn’t require 100 buckets. So assigning the buckets optimally by incrementing the bucket size when it is needed is the best approach to avoid memory issue. Then the decay rate for conceding is generated randomly at first and uses the same rate till the end. So this can be improved by starting with Boulware strategy, and over time this can be changed into conceder strategy which makes opponent learn our agent’s behaviour. At last, while counter-offering the bid from the tree which contains the history bid of the opponent, we are proposing the same bid repeatedly according to that target utility. So we can keep track of frequently offered issue values and submit the bid with that values can improve our agent.

5.     REFERENCES

[1]     R. Aydo ˘gan, D. Festen, K.V. Hindriks, C.M. Jonker, Alternating offers protocols for multilateral negotiation, in Modern Approaches to Agent-Based Complex Automated Negotiation, ed. by K. Fujita, Q. Bai, T. Ito, M. Zhang, R. Hadfi, F. Ren, R. Aydo ˘gan

[2]     WellmanMP,Wurman PR, Kevin O, Roshan B, de Lin S, Reeves D,WalshWE (2001) Designing the market game for a trading agent competition. IEEE Internet Comput 5(2):43–51

[3]      Rogers AD, Dash RK, Ramchurn SD, Perukrishnen V, Jennings Nicholas R (2007) Coordinating team players within a noisy iterated prisoner’s dilemma tournament. Theor Comput Sci 377(1–3):243–259

[4]      Towards a Quantitative Concession-Based Classification Method of Negotiation Strategies Tim Baarslag, Koen Hindriks, and Catholijn Jonker Man Machine Interaction Group Delft University of Technology {T.Baarslag,K.V.Hindriks,C.M.Jonker}@tudelft.nl

[5]      Baarslag T, Hindriks KV, Jonker CM (2013) A tit for tat negotiation strategy for real-time bilateral negotiations. In: Ito T, Zhang M, Robu V, Matsuo T (eds) Complex automated negotiations: theories, models, and software competitions. Studies in computational intelligence, vol 435. Springer, Berlin, pp 229–233

[6]      Williams CR, Robu V, Gerding EH, Jennings NR (2012) Iamhaggler: a negotiation agent for complex environments. In: Ito T, Zhang M, Robu V, Fatima S, Matsuo T (eds) New trends in agent-based complex automated negotiations. Studies in Computational Intelligence. Springer, Berlin, pp 151–158

[7]      Jazayeriy, H., Azmi-Murad, M., Sulaiman, N., & Udizir, N. I. (2011). The learning of an opponent’s approximate preferences in bilateral automated negotiation. Journal of Theoretical and Applied Electronic Commerce Research, 6(3), 65–84.

[8]      Lin, R., Kraus, S., Wilkenfeld, J., & Barry, J. (2006). An automated agent for bilateral negotiation with bounded rational agents with incomplete information. In Proceedings of the 2006 conference on ECAI 2006: 17th European conference on artificial intelligence (pp. 270–274). The Netherlands: Amsterdam.

[9]      Hao, J. & Leung, H.-F. (2012). ABiNeS: An adaptive bilateral negotiating strategy over multiple items. In Proceedings of the 2012 IEEE/WIC/ACM international joint conferences on web intelligence and intelligent agent technology WI-IAT’12 (Vol. 2, pp. 95–102).Washington, DC: IEEE Computer Society.

[10]   Kawaguchi S, Fujita K, Ito T (2012) AgentK: compromising strategy based on estimated maximum utility for automated negotiating agents. In: Ito T, Zhang M, Robu V, Fatima S, Matsuo T (eds) New trends in agent-based complex automated negotiations, Studies in computational intelligence, vol 383. Springer, Berlin, pp 137–144