Xinfeng Yang, School of Information Technology, Griffith University, QLD 9726 Australia. Email: X.Yang@griffith.edu.au
Anne T-A Nguyen, School of Information Technology, Griffith University, QLD 9726 Australia. Email: A.Nguyen@griffith.edu.au
Decision-making strategy for mobile agents in e-business applications has received much attention in recent years. In contrast to many existing approaches, which apply pre-defined business rules or soft computing techniques to deal with various e-business situations, this paper introduces an online competitive algorithm to achieve flexibility. A dynamic decision-making scheme based on an optimised competitive ratio is developed to guide a mobile agent's behaviour in an online fashion. In addition, the proposed approach extends push-based technology in order to benefit both the agent owner and its potential clients. The algorithm comparison and simulation results demonstrate the advantages and applicability of this approach for mobile agent based e-business systems.
Keywords: Mobile agent, e-business, competitive algorithm, decision-making.
Decision-making strategy always plays an important role in mobile agent system design. One possible reason is that when a mobile agent travels around the Internet and working for its owner, it is expected to deal with all types of uncertainties along the way by itself. Addressing problems with imprecise and uncertain information is regarded as an important capability for mobile agents working in a real e-business environment. Successful examples could be found in many existing mobile agent-based e-business applications such as the Kasbah market proposed by Chaves and Maes (1996), the MAgNET system presented by Dasgupta et al (1998), the utility driven computational market suggested by Bredin et al (1999).
It could be noted that the majority of the current works have focused on taking advantages of business rules and regulations to improve a mobile agent's decision-making capabilities in a dynamic e-business environment. Actually, most business rules are merely the summarisation of regularities for the ordinary business activities. It assumes that the decision-maker has the complete knowledge of all the potential sequence of requests, or that the future request pattern conforms to certain summarised regularity. For situations where a player has no secure knowledge of future events or encounters distribution irregularity, it is difficult to expect the agent player have a satisfactory performance.
This paper suggests employing competitive algorithm to address the online decision-making problem. A TAFTA (Travelling Agent For Travel Agency) problem is identified, and a TAB (Travel Agency Booking) algorithm is derived. In the problem-solving strategy, an online player is capable of making a timely decision without any assumption about future requests or request patterns. The suggested online algorithm works well compared with the associated optimal offline algorithm of the same request sequences. Sets of simulation and algorithm comparisons are carried out to demonstrate the feasibility and effectiveness of the proposed solution in both theoretical and practical e-business environments.
This paper is organised as follows. Section 2 outlines related works on various soft-computing techniques for addressing problems under uncertainty and presents basic terminology related to online problems and competitive algorithms. Section 3 introduces a TAFTA problem. A detailed analysis and a proposed competitive solution are given in Section 4 while an optimised competitive ratio is discussed in Section 5. Section 6 presents a series of simulations and associated algorithm comparisons. Finally, a conclusion is given in Section 7.
A review of uncertainty in online decision-making
Traditional methods for addressing problems with imprecision, uncertainty, partial truth and approximation information are called Soft Computing (SC) techniques, a consortium name for a group of relevant technologies. The basic principle of SC, as Fortuna et al (2001) argued, is "combining use of various computation techniques to achieve a higher tolerance level towards imprecision and approximation, and thereby new software/hardware products can be had at lower cost to be integrated in the real world". Fuzzy Logic (FL), Neural Network (NN), and Genetic Algorithm (GA) are three principal members in the SC family that have been successfully used in agent-mediated e-business area.
The fuzzy logic technique tries to deal with the concept of partial truth where the truth-value is between completely true and completely false. Different degrees of truth are represented by different degree of memberships in a fuzzy set. A collection of membership functions and fuzzy rules forms the basis for a fuzzy expert system to reason about data. General inference process could be summarised as fuzzification, inference, composition and defuzzification (optional). Successful examples that employ fuzzy logic for agent-mediated e-business include the fuzzy e-negotiation agents suggested by Kowalczyk (2002), the fuzzy e-auction agents proposed by He et al (2003), and the fuzzy-logic based business-forecasting agents presented by Shen et al (2002). For the neural network technology, a collection of neurons is organised into layers or clusters, with each processing unit having a small amount of local memory. The inter-neuron connection strengths (or synaptic weights) are used to store knowledge. Neural network is especially useful to solve problems where hard and fast rules are not easily applied, but function approximation and imprecision tolerance capability are desired and there are enough data and computing resources for training (Haykin 1994). Some agent-mediated e-business applications based on NN technology include the financial analysing agents proposed by Yen et al (1999), the investment advising agents presented by Zhang et al (2001), and the foreign exchange market modelling method suggested by Grothmann (2002). For the genetic algorithm, concepts of many operators come from the biological field, such as population, fitness, reproduction, recombination, mutation. There is always a population of structures with each individual in the population assigned a measure of fitness to indicate its competence in the environment. Multi-dimensional searching and optimisation is a major application suitable for this algorithm. Three essential steps observable in the implementation cycle include: evaluating the fitness of all initial individuals of the population, generating a new population through crossover, recombination and mutation, and finally replacing the old population with the new one. Associated examples in this specific area could be found in (Shapcott 1992), (Welstead 1994) and (Chen et al 1998).
Although the above three techniques address problems under uncertainty through different ways, they share one common characteristic, namely, the assumption that the decision-maker has the full knowledge about the requests. Based on such complete knowledge, a distribution pattern of the request sequence could be established. Taking neural network technique as an example, the knowledge of the artificial neuron comes from the training process which is actually a process of learning from examples. In order to carry out a successful training, one has to provide enough training data and enough computer time otherwise it is hard for a neural network to acquire necessary knowledge. Although the initial aim for using neural networks is trying to get some generalisation knowledge from training data and produce some roughly correct results for new cases, it has to be acknowledged that one can not expect neural networks to magically create information which is not included in the training set. By contrast, another kind of uncertainty problem could be found frequently in the computing and business world -- that is the online problem.
Online fashion can be found in many research areas such as data structuring, task scheduling or resource allocation. In a data-structuring problem, it is desired to access elements in a given data structure at low cost, without knowing which element will have to be accessed in the future. For the paging problem in a two-level memory system, it is necessary to decide which referenced pages have to be taken out of fast memory while not knowing which page will be requested next. In a multi-processor network, it is a challenging job to serve the accesses in the network with lower communication costs through dynamically reallocating files but without any knowledge of future accesses. All these problems are characterized by satisfying requests before knowing what the future requests will be, but if the decision-maker chose an unsuitable strategy carelessly, the unexpected request sequence would always influence the system performance in a serious way. An extensive study of the online problem started in the 1980s when Sleator and Tarjan (1985) suggested that the competitive algorithm is a powerful tool for addressing online problems. In a study of the competitive snoopy caching problem, Karlin et al (1988) compared the performance of an online algorithm 
to an optimal offline strategy 
. Taking a measurement of the cost, their study focused on minimising the worst case ratio of the online cost to the optimal offline cost. For any possible sequence of request 
, letting 
and 
denote online cost and offline cost respectively, the algorithm 
is called 
-competitive if formula (1) holds:
(1)
is a constant for initialization, while is called the competitive ratio for the algorithm.
Employing competitive analysis to address problems associated with economics and financial games has been proved successful. One important reason is because many problems in the business field are inherently online. For example, foreign currency exchange problem, mortgage refinancing problem, and portfolio selection problem. A market operator has to make decisions and carry out transactions without secure knowledge about market conditions in the future, and sometimes even some probabilistic assumptions also become impractical. Based on El-Yaniv's (1998) observation, at least three kinds of problems are identified as applicable for competitive solutions: leasing and replacement, randomised searching and one-way trading, and portfolio selection and two-way trading.
In the leasing and replacement problems, the following scenario is considered. A player who wants to use certain equipment has to face two choices each day, renting the equipment or buying it. Clearly, buying would be a better idea if he/she decides to use the equipment for a long time, otherwise renting would be better. The online leasing problem could be expressed as when to stop renting and choose buying with the aim of a minimised overall spending cost on that equipment. The game would be over immediately after the player purchases the equipment. A set of competitive solutions has been suggested, such as the generalised deterministic algorithm offered by Irani and Ramanathan (1998), a cumulative distribution-function-based algorithm presented by Phillips and Westbrook (1999), and an interesting-rate-involved optimal algorithm proposed by El-Yaniv et al (1999). The randomised-searching problem describes another interesting scenario. An online player is searching for the highest price in a sequence of offers. At each period of time he/she obtains a price quotation with a sampling cost. The player has to decide whether accepting the current offer or continuing to ask for more sampling costs. The game is over immediately after the player accepts an offer with the aim of achieving the highest total return. Promising solutions for this specific online problem include the RPP (Reservation-Price-Policy) algorithm given by Borodin and El-Yaniv (1998), the randomised EXPO (EXPOnential threshold) algorithm suggested by Levin (El-Yaniv 1998), and the optimal threat-based algorithm presented by El-Yaniv et al (2001). In contrast to the above two online problems, the portfolio selection problem has slightly gone beyond the traditional competitive analysis and employed some basic methodology from the mathematical finance field. It considers that an investor has certain initial wealth and wishes to invest securities in the market. He/she has to decide how to rearrange the current investment at the beginning of each trading time in order to maximise the total wealth at the end of the entire game. For more information about this specific online problem and associated solutions, please refer to (Raghavan 1991), (Chou et al 1995) and (Borodin et al 2000).
This paper tries to invest some efforts on the applicability of employing competitive algorithm for mobile agent-mediated e-business problems. The initial idea comes from two intuitive observations. First, a mobile agent decision-maker is always facing the problem such as where and when to go for accomplishing a given task, with an improved overall performance and minimised computation and communication cost. It is just the aim for a competitive algorithm to achieve -- minimised online cost compared to the corresponding optimal offline cost, against all possible request sequences. Second, viewing e-business as an online version of conducting traditional business activity in the cyber space, mobile agents are expected to perceive various market conditions autonomously, making decisions based on their knowledge and adjusting their strategies accordingly. Competitive analysis seems to be a good candidate for a free travelling agent to improve its adaptability on a changing environment. Based on the above observations, this paper originally identifies a TAFTA (Travelling Agent For Travel Agency) problem. Consider the following scenario, a mobile agent works for a travel agency travelling around the Internet to market its holiday plan to a group of potential clients, as illustrated in Figure 1.
Figure 1: A working model for the online TAFTA problem
Three working stages involved in this online problem model are summarised below.
(a) Early-bird registration collection
This is the first stage of the whole working process. A travelling agent working for a travel agency is dispatched to the network to visit its potential customers sequentially. At each destination, it demonstrates a pre-designed holiday plan with an early-bird registration rate 
to its client. If the client is satisfied with this offer and would like to take it, the travelling agent will help finalising the registration formality for the customer and continue its journey to its next destination. This process would not stop until the early-bird rate is invalid.
(b) Standard registration collection
At this stage, the travelling agent travels around the network performing the same task as it did in the first stage. However, since the early-bird rate is not valid, it would present a standard rate 
to its potential customer. 
is expected to be higher than 
. If the customer is satisfied with the standard offer and wishes to take it, the travelling agent will help finalising the registration procedure, and then continue its journey. This stage would not stop until the last minute of the whole plan.
(c) Online decision-making
This stage actually takes place between the above two phases. The travel agency has to pay the third-party service provider, such as hotels, or airplane companies. For these costs, two different rates might exist correspondingly, an early-bird rate 
and a standard rate 
. Therefore, what the travel agency needs to do at this stage is trying to reserve some places with the lower cost 
. If the number of clients registering at the first stage is 
, while the agent estimates that more clients will join in and the total number could reach 
, reserving
places with the lower cost 
might be a good strategy because it will get additional profits 
at the end. However, if the travelling agent reserved 
places based on such assumption, but finally there is no client registering at the second stage at all, unclaimed 
places have to be released to the service provider, and unfortunately it has to pay the fine, say, 
for each place. Therefore the online TAFTA problem could be expressed as follows. Given the number of clients registering at the first stage 
and the possible maximum number at both stages 
, and all potential costs (
and 
are the early-bird and standard registration rate for the customer. 
and 
are corresponding rate for the travel agency. 
is the fine for releasing each unclaimed place), what is the best number of places that should be reserved by the travelling agent in order to maximise profit for the travel agency?
Competitive analysis and proposed online solution
Most examples discussed in section 2 are cost minimisation problems. A competitive algorithm focuses on minimising the worst case ratio of the online cost to the optimal offline cost, as given in relation (1). For the profit maximisation problem, the competitive ratio could be re-defined analogously (El-Yaniv 1998). If for any possible sequence of requests, let 
denote the profits of an online algorithm 
, and 
the profits of an optimal offline algorithm 
, the algorithm 
is called 
-competitive if the following relation holds:
(2)
where is the competitive ratio, is an additive constant for initialisation. When is equal to zero, is called strictly -competitive, and the above equation can be expressed as 
. Algorithm 
is efficient if competitive ratio is small.
In order to conduct a competitive analysis and work out an online solution, it is necessary to consider how profits are generated for both an online algorithm and an optimal offline algorithm. If the number of clients at the first stage is 
and the total number of clients at both stages is 
, 
, it is not hard to see that the optimal offline algorithm would reserve exact 
places at the decision-making stage, the final profit for this specific request is 
. If the entire request sequence is denoted as 
, where 
is the actual request number on the 
- th round, the optimal offline profits can be expressed as follows.
(3)
where 
and 
are the early-bird and standard registration rate offered to the customer, 
is the early-bird reservation fee payable to the third party service provider.
Facing the same requests, an online player does not know the exact number of clients 
, so it has to estimate a possible number 
and reserve 
places after the first stage. Because the actual number of clients 
might be less than or greater than 
, calculating profits for the online player would become complicated. At first, suppose 
meaning the places reserved by the agent are more than the total number of clients, so 
places have to be released and paying the fine 
. In that case, the profits for the online player can be expressed as 
. Otherwise if the places reserved at the first stage are less than the total number of clients, 
places have to be paid the standard cost to the third party provider. The profits for the online player can be calculated as
Combining the above two cases, it is not difficult to derive the profits of an online algorithm 
for the same request sequence 
, as follows.
(4)
where 
is the standard reservation rate for the travel agency and 
is the fine for returning each unclaimed place. So, the profit maximisation problem for the competitive algorithm 
is trying to reserve the optimal places 
in order to achieve a minimised competitive , which can be calculated as
.
Proof: In order to get an online solution facing all possible request sequences, it is necessary to consider two possible worst request sequences in the given TAFTA problem. An offline adversary might choose these requests to minimise the profits of the online player, thus maximising the competitive ratio. Two natural worst request sequences that could be observed: 
and 
, where 
and 
are the maximum and minimum number of clients registered in both stages.
Let 
and 
denote the online and optimal offline profits respectively when 
occurs, according to equations (3) and (4), the competitive ratio can be calculated as follows.
(5)
Similar reasoning process can be used in the case of 
. Let 
and 
denote the online and optimal offline profits, the corresponding competitive ratio can be expressed in equation (6).
(6)
Because 
and 
are the two possible worst cases in the given problem, it seems that 
can be chosen to balance the maximum of the bounds from these two cases. From equations (5) and (6),
In order to simplify the above expression, let 
, 
, 
, 
and 
, the best number 
that an online player should choose for the TAFTA problem can be easily worked out. Theorem 1 summarises the result from the above analysis. It is thereafter termed as Travel Agency Booking (TAB) algorithm.
Theorem 1: For the given TAFTA problem, the best reserving number for the online agent to choose is
(7)
where 
is the number of clients registered at the first stage, 
the maximum number of clients joining in both stages, and 
, 
, 
, 
, 
.
Competitive ratio and its lower bound
After obtaining the best reserving number 
, the corresponding competitive ratio for the TAB algorithm can be derived by substituting the result in (7) into equations (5) and (6). The resulting competitive ratio can be summarised in Theorem 2.
Theorem 2: For the competitive TAB algorithm given in Theorem 1, the competitive ratio is
(8)
or it can be said that TAB is a 
-competitive algorithm.
This means the profits of an optimal offline algorithm are at most times those of the online TAB algorithm, in other words, the latter are at least 
those of the former for the same requests. In fact, not all online competitive algorithms are optimal. So in order to demonstrate that the proposed TAB algorithm is an optimal one, we need to prove that for the given TAFTA problem, 
is the lower bound for the achievable competitive ratio.
Proof: The above problem can be translated as follows, 'if the online player chooses a different reserving number from the value of 
in equation (7), 
, the competitive ratio would get worse'. A two-step proof follows.
First, assume that 
, we need to prove that if the offline adversary chose the request sequence 
, the competitive ratio in equation (8) can not be achieved. According to equation (6),
(9)
From this it is observed that if then 
.
Second, assume that 
, we need to prove that if the offline adversary chose request sequence 
, the suggested competitive ratio can not be achieved either. According to (5),
(10)
From the above expression, it can be seen that if 
then 
. The proof is therefore completed. The whole analysis in the above two cases can be concluded in Theorem 3 as follows.
Theorem 3: In the given TAFTA problem, 
is the lower bound of the achievable competitive ratio.
Analysing the algorithm expressed in Theorem 1 and 2 further, we can get a series of meaningful corollaries that will be helpful to understand how the proposed solution can be simplified in particular cases. Corollary 1 and 2 focus on special values of registration rates and , while Corollary 3 presents a specific solution related to the fluctuation rate. Proofs of three corollaries are similar to what was expressed for Theorem 2 as they are merely special cases.
Corollary 1: In the online TAFTA problem, if 
, that is 
or 
, the best reservation number for the online agent to choose will be
(11)
and the corresponding competitive ratio will be
(12)
The significance of assuming is as follows. The travel agency presents the same offer to the potential clients at both early bird and standard stages although it has to pay different rates to the third-party service provider. In fact, 
and 
represent different profit-generation methods at different stages, so when , such difference is eliminated and the profit maximisation problem turns out to be a simplified cost minimisation problem.
Corollary 2: In the online TAFTA problem, if 
, that is 
, the best reservation number for the online agent to choose will be
(13)
and the corresponding competitive ratio will be
(14)
Recall that 
and 
are the early-bird and standard reservation rate for the travel agency, in this case the travel agency completely shifts off the difference on early-bird and standard rates introduced by the third-party service provider to its clients.
Corollary 3: If the fluctuation rate is denoted as 
in the online TAFTA problem, the best reservation number for the online agent to choose will depend on 
when other parameters remain constant.
(15)
and corresponding competitive ratio will depend on too. When gets smaller, gets better.
(16)
From this corollary, it can be noted that the number of clients registering at the first stage 
is known before the travelling agent has to make a decision, and all other parameters except the fluctuation rate is constant for a given TAFTA problem. So, the best reservation number and corresponding competitive ratio will depend on only. If the fluctuation rate were estimable in certain applications, the calculation of the best reservation number would become much easier.
Experimental results and algorithm comparison
In order to evaluate the effectiveness of the proposed TAB algorithm, a series of simulation experiments are conducted which can be classified into two types. The first set of experiments deals with theoretical issues and the second, practical considerations. In a theoretical environment, an adaptive offline adversary (ADOF) is employed, which is regarded as the strongest among all kinds of adversaries (namely, adaptive offline, adaptive online and oblivious adversary) (Ben-David et al 1994). Because there is no constraint applied on its request sequence selection, the ADOF adversary can select the worst possible input to maximise its rivals’ competitive ratios based on the knowledge of their individual strategies. However, in a practical environment, the offline adversary is forced to generate request sequences randomly, and all candidate algorithms will face the same sequences equally.
Three other algorithms are explicitly introduced for comparison. They are the average algorithm, follower algorithm and random algorithm. Each will compete with the ADOF adversary one by one in a theoretical environment, but deal with the same randomised request sequence in the practical environment. A detailed explanation of the three algorithms will be given below.
For the given TAFTA problem, the reservation number 
that an average algorithm will choose each time is the arithmetic mean of 
and 
, namely, 
, where 
is the number of clients registering at the first stage, and 
is the possible maximum in total.
Follower algorithm chooses the same number as what happened in its previous time, namely, 
.
Random algorithm chooses a number 
ranging from 
to 
randomly each time.
In order to evaluate the performance of each suggested algorithm quantitatively, it is necessary to define all the parameters in the proposed TAFTA problem specifically. For now, there is no real data available from exactly the same scenario, therefore a group of simulation data is selected with the aim of approaching the real data as reasonable as possible. The selected simulation data are as follows. The number of clients registering at the first stage, 
, the maximum number of clients registered at both stages, 
. The early-bird and standard registration rates quoted to the customer, 
,
. The early-bird and standard reservation rates for the travel agency to pay its third party service provider, 
, 
. The fine for releasing each unclaimed place 
. Performance of each selected algorithm against ADOF adversary is given as follows.
Based on Theorem 1 and 2 and the above simulation parameters, the best reservation number that an online TAB algorithm would choose is 
. In order to maximise the competitive ratio of the online player, the ADOF adversary selects the request sequence 
or 
. As proved in the previous section, TAB algorithm can get an optimal competitive ratio of 
.
Given the above simulation parameters, the average algorithm chooses 
as the best reservation number. Facing the online average strategy, the ADOF adversary chooses 
as the inputs because they will lead to a worse competitive ratio 
.
The follower algorithm chooses an average number for the first time and subsequently follows the number that appeared in the previous time. To conquer this algorithm, the ADOF adversary introduces an adaptive strategy. It chooses 
at the first time and choose 
at the second time, and then 
forever. The competitive ratio will then get worse. Table 1 shows the simulation results after 100 trials.
|
No. of trials |
10 |
20 |
30 |
40 |
50 |
60 |
70 |
80 |
90 |
100 |
|
|
1.237 |
1.248 |
1.253 |
1.255 |
1.256 |
1.257 |
1.257 |
1.258 |
1.258 |
1.258 |
Table 1: Simulation results of the follower algorithm facing the ADOF adversary
Facing the random algorithm, which chooses a random number each time, the ADOF adversary will employ a more tricky strategy. If 
, it will choose 
, otherwise, it will choose 
. The competitive ratio will get worse too. Table 2 shows the simulation results after 100 trials.
|
No. of trials |
10 |
20 |
30 |
40 |
50 |
60 |
70 |
80 |
90 |
100 |
|
|
1.199 |
1.191 |
1.189 |
1.191 |
1.181 |
1.181 |
1.183 |
1.183 |
1.183 |
1.186 |
Table 2: Simulation results of the random algorithm facing the ADOF adversary
From the above simulation, it can be noted that the ADOF enjoys a distinct advantage that it might choose the request sequence after the online player has made a decision, and might be adapted to each individual player. Although it is customary in the literature to conduct competitive analysis on this basis, it can be argued that the comparison is biased in favour of the adversary. Therefore it can be reasonable to ask whether these candidate algorithms may in fact perform better in a real e-business environment. Keeping all the parameters chosen the same as given above, in a practical environment the request sequences are generated randomly, and all the candidate algorithms would be treated equally. Corresponding simulation results of 100 trails are given in Table 3 and Figure 2.
|
|
Online TAB |
Average |
Random |
Follower |
|
10 trials |
1.089 |
1.069 |
1.076 |
1.104 |
|
20 |
1.052 |
1.056 |
1.095 |
1.092 |
|
30 |
1.050 |
1.055 |
1.093 |
1.083 |
|
40 |
1.048 |
1.058 |
1.090 |
1.085 |
|
50 |
1.046 |
1.053 |
1.090 |
1.087 |
|
60 |
1.043 |
1.049 |
1.089 |
1.088 |
|
70 |
1.047 |
1.054 |
1.081 |
1.084 |
|
80 |
1.045 |
1.052 |
1.081 |
1.085 |
|
90 |
1.044 |
1.052 |
1.077 |
1.085 |
|
100 |
1.045 |
1.053 |
1.078 |
1.084 |
Table 3: Simulation results of all the candidate algorithms in a practical environment after 100 trials
From table 3 and figure 2, it can be seen that performance of all the candidate algorithms become better than that in the tough theoretical environment. The online TAB algorithm works better than other three algorithms except for the 10 trails mark. The follower's performance is similar to the random algorithm's result. It happened because the request sequence is generated randomly and the follower simply adopts the random number occurred in previous time.
Figure 2: Performance comparison of four algorithms in a practical environment
The aim of the last simulation is to test the conclusion given in Corollary 3, where the relationship between the optimal reservation number 
and the fluctuation rate 
is examined. The number of clients 
is observable before the online player makes a decision, and the fluctuation rate may be estimable from experience or historical data. Given knowledge about 
and , for example, the number of clients registered at the first stage varies from time to time but the fluctuation rate is comparatively fixed, the performance of the suggested algorithm would be improved. In the following simulation, let the value of 
varies in a range of 
, and the fluctuation rate 
is fixed, simulation results are shown in Table 4.
|
|
Online TAB |
Average |
Random |
|
10 trials |
1.043 |
1.031 |
1.123 |
|
20 |
1.070 |
1.079 |
1.084 |
|
30 |
1.052 |
1.063 |
1.093 |
|
40 |
1.054 |
1.064 |
1.087 |
|
50 |
1.050 |
1.060 |
1.086 |
|
60 |
1.047 |
1.056 |
1.090 |
|
70 |
1.046 |
1.055 |
1.092 |
|
80 |
1.045 |
1.055 |
1.090 |
|
90 |
1.046 |
1.054 |
1.088 |
|
100 |
1.045 |
1.054 |
1.085 |
Table 4: Simulation results of three algorithms when is fixed
In the above simulation, request sequences are generated randomly. The follower algorithm is no longer included since it might be out of range and become meaningless frequently. Performance of the three algorithms in this practical environment are generally better than that in the theoretical situation. Overall, the online TAB algorithm works better than other two candidates, especially in the long run. The results given in Table 4 are presented graphically in Figure 3.
Figure 3: Performance comparison of three algorithms when 
is fixed
This paper presents a competitive algorithm for online decision making by mobile agents in e-applications. To overcome the limitations of current approaches, which lack the flexibility of dynamically adjusting a mobile agent's behaviour in an online environment, we propose to improve the agent's adaptability based on a guided decision-making scheme in terms of an optimised competitive ratio. The proposed Travel Agency Booking algorithm has been tested through a series of simulation experiments, and comparison with existing methods demonstrates its feasibility and potentials in an e-business environment.
Ben-David, S., Borodin, A., Karp, R. M., Tardos, G. and Wigderson, A. (1994), ‘On the Power of Randomization in On-Line Algorithms’, Algorithmica, Vol. 11, No. 1, pp. 2-14.
Borodin, A. and El-Yaniv, R. (1998), Online Computation and Competitive Analysis Cambridge University Press.
Borodin, A., El-Yaniv, R. and Gogan, V. (2000), ‘On the Competitive Theory and Practice of Online Portfolio Selection’, Proceedings of the Latin American Theoretical Informatics, Lecture Notes in Computer Science Vol. 1776, eds G. H. Gonnet, D. Panario and A. Viola, Springer-Verlag, pp. 173-196.
Bredin, J., Kotz, D. and Rus, D. (1999), ‘Mobile-Agent Planning in a Market-Oriented Environment’, Technical Report PCS-TR99-345, Department of Computer Science, Dartmouth College, USA.
Chavez, A. and Maes, P. (1996), ‘Kasbah: An Agent Marketplace for Buying and Selling Goods’, Proceedings of the 1st International Conference on the Practical Application of Intelligent Agents and Multi-Agent Technology, London, pp. 75-90.
Chen, H., Chung, Y. M., Ramsey, M. and Yang, C. C. (1998), ‘An Intelligent Personal Spider (Agent) for Dynamic Internet/Intranet Searching’, Decision Support Systems, Vol. 23, No. 1, pp. 41-58.
Chou, A., Cooperstock, J., El-Yaniv, R., Klugerman, M. and Leighton, T. (1995), ‘The Statistical Adversary Allows Optimal Money-Making Trading Strategies’, Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, pp. 467-476.
Dasgupta, P., Narasimhan, N., Moser, L. E. and Melliar-Smith, P. M. (1998), ‘A Supplier-Driven Electronic Marketplace using Mobile Agents’, Proceedings of the 1st International Conference on Telecommunications and Electronic Commerce, Nashville, USA, pp. 42-50.
El-Yaniv, R. (1998), ‘Competitive Solutions for Online Financial Problems’, ACM Computing Surveys, Vol. 30, No. 1, pp. 28-69.
El-Yaniv, R., Fiat, A., Karp, R. M. and Turpin, G. (2001), ‘Optimal Search and One-Way Trading Online Algorithms’, Algorithmica, Vol. 30, pp. 101-139.
El-Yaniv, R., Kaniel, R. and Linial, N. (1999), ‘Competitive Optimal On-Line Leasing’, Algorithmica, Vol. 25, pp. 116-140.
Fortuna, L., Rizzotto, G., Lavorgna, M., Nunnari, G., Xibilia, M. G. and Caponetto, R. (2001), Soft Computing: New Trends and Applications, Springer-Verlag.
Grothmann, R. (2002), ‘Multi-Agent Market Modeling Based On Neural Networks’, PhD Thesis, Faculty of Economics, University of Bremen, Germany.
Haykin, S. (1994), Neural Networks: A Comprehensive Foundation, Macmillan, New York, p. 2.
He, M., Leung, H. and Jennings, N. R. (2003), ‘A Fuzzy-Logic Based Bidding Strategy for Autonomous Agents in Continuous Double Auctions’, IEEE Transactions on Knowledge and Data Engineering, Vol. 15, No. 6, pp. 1345-1363.
Irani, S. and Ramanathan, D. (1998), ‘The Problem of Renting versus Buying’, Technical Report TR-9309456, Department of Information and Computer Science, University of California, Available Online:
[HREF1] [2004 Jan. 28].Karlin, A. R., Manasse, M. S., Rudolph, L. and Sleator, D. D. (1988), ‘Competitive Snoopy Caching’, Algorithmica, Vol. 3, pp. 79-119.
Kowalczyk, R. (2002), ‘Fuzzy E-Negotiation Agents’, Soft Computing, Vol. 6, No. 5, pp. 337-347.
Mandry, T., Pernul, G. and Rohm, W. A. (1999), ‘Mobile Agents on Electronic Markets Opportunities, Risks and Agent Protection’, Proceedings of the 12th International Bled Electronic Commerce Conference, Bled, Slovenia, pp.1-13.
Phillips, S. and Westbrook, J. (1999), ‘On-Line Algorithms: Competitive Analysis and Beyond’, in Algorithms and Theory of Computation Handbook, ed. M. J. Atallah, CRC Press, Boca Raton, pp. 152-180.
Raghavan, P. (1991), ‘A Statistical Adversary for On-Line Algorithms’, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 7, pp. 79-83.
Shapcott, J. (1992), ‘Index Tracking: Genetic Algorithms for Investment Portfolio Selection’, Technical Report EPCC-SS92-24, Edinburgh Parallel Computing Centre, The University of Edinburgh, UK.
Shen, Z., Gay, R., Miao, C. (2002), ‘Goal-Based Modeling for Intelligent Business Forecasting Agents’, Proceedings of the 1st International Conference on Fuzzy Systems and Knowledge Discovery, Singapore, pp. 534-538.
Sleator, D. D. and Tarjan, R. E. (1985), ‘Amortized Efficiency of List Update and Paging Rules’, Communications of the ACM, Vol. 28, pp. 202-208.
Welstead, S. T. (1994), Neural Network and Fuzzy Logic Applications in C/C++, John Wiley & Sons, pp. 395-421.
Yang, X. and Nguyen, A. (2003), ‘E-Business Models with Agent Technology’, Proceedings of the Pan-Pacific Conference XX 2003, Shanghai, China, pp. 187-189.
Yen, J., Chung, A., Ho, H., Tam, B., Lau, R., Chua, M. and Hwang, K. (1999), ‘Collaborative and Scalable Financial Analysis with Multi-agent Technology’, Proceedings of the 32nd Annual Hawaii International Conference on System Sciences, Maui, USA, Vol. 5, p. 5021.
Zhang, C., Zhang, Z. and Li, Y. (2001), ‘A Multi-Agent Framework for Financial Investment Planning’, International Journal of Knowledge-based Intelligent Engineering Systems, Vol. 5, No. 4, pp. 290-300.