|
|
1.INTRODUCTIONAs a new business operation mode, e-commerce has great practical value. Negotiation is not only a common method to solve problems in human society, but also a key link in e-commerce. In e-commerce, negotiations in the form of “multiple to multiple” (multiple sellers and multiple buyers) are more common. At home and abroad, automatic negotiation in ecommerce environment has been studied in different aspects and depths, and many effective methods have been proposed. Apart from these, there has also been automatic negotiation systems that can support online negotiations. For instance, Faratin et al. proposed several structured negotiation algorithms based on interaction between participants1,2. These negotiation systems can handle bilateral and multi-attribute negotiation through interaction between agents. Park and Yang proposed a multilateral efficient negotiation system3 in pervasive computing environment, and used sorting method to match, achieving good results. Mandeep Mittal et al. proposed a bilateral optimized model for negotiation between buyer and seller through a mediator agent to negotiate on the issue price and the quantity for multi-item4. Domestically, Shangwen Xing studied e-commerce automatic negotiation by using Agent negotiation theory and game theory5. And Chongping Chen proposed automatic negotiation strategy and utility function6 based on time. Liu Jinpeng modeled the online business market and designed an adaptive compromise negotiation mechanism in a dynamic environment7. In terms of improving the efficiency of the negotiation model, Gao8 combined the Agent matching of e-commerce automatic negotiation with the process of artificial bee colony algorithm, Tang9 introduced a metric that is able to evaluate the efficiency of the negotiation process, proposing a novel meta-strategy, Cao et al.10 constructed a mass customization operation model in an e-commerce environment. Practice has proved that the combination strategy is used to guide the agent to negotiate bids, which is more conducive to improving the negotiation efficiency. In terms of transaction profits, the average matching obtained is relatively high by the existing methods, but the total profit of the whole system is not high enough, and the number of pairings is also not enough3. Based on the second-hand car trading system, we construct a multilateral multi-attribute fair negotiation model on how to maximize the overall profit and improve the matching number, and use the Hungarian solution to solve it. 2.PREPARATORY KNOWLEDGE2.1Multilateral multi-attribute fair negotiationMultilateral and multi-attribute negotiation has always been an important field of e-commerce research. Multilateral refers to the negotiation between multiple buyers and multiple sellers, which has more practical value than bilateral negotiation in reality. Multi-attribute negotiation means that the two sides weigh different attributes in the negotiation scheme under the condition that they have a complete understanding of preferences, so that the two sides can achieve a win-win situation. In the actual production and life, multilateral multi-attribute negotiation is very common. The negotiation system of this paper adopts the conceptual mechanism of confidentiality to ensure fair negotiations. The Intermediary agent received things from buyers and sellers, but buyers and sellers kept secret in their peers. For the entire negotiation system, the intermediary agent can find a mutually beneficial agreement, and select a suitable threshold according to the characteristics of the system, so that the intermediary does not bias any participant, thus ensuring the feasibility and fairness of the negotiation. 2.2.0-1 assignment problem2.2.10-1 assignment issues raised.In this question, N Individuals are responsible for N tasks. Each person has different efficiency for different tasks. One person can only complete one task and one task can only be completed by one person. The purpose is to make the total efficiency of task completion as high as possible. The 0-1 assignment problem is similar to the multilateral negotiation problem to some extent. N individuals just assume N tasks, corresponding to that one buyer can only complete the transaction with one seller. Each person has different efficiency for different tasks. One person can only complete one task, and one task can only be completed by one person. The purpose of this study is to make the total efficiency of task completion as high as possible, and then extend to make the success rate and profit of the transaction as large as possible. 2.2.2The general form of 0-1 assignment problem.Let n resources (people or machines, etc.) A1, A2, …, An, assign to do n things B1, B2, …, Bn, require that each thing is completed with only one resource, and the completed resources will not be used by other things. It is known that the efficiency of Ai to do Bj is cij. Making the overall efficiency best through reasonable assignment is the problem to be solved by 0-1 assignment. (cij)n×n is called efficiency matrix. the mathematical model of the problem is 2.3Hungarian solution2.3.1Related theorems and concepts of the Hungarian solution.In 1955, Kuhn proposed a new assignment problem algorithm, called Hungarian algorithm, by using the independent zero element theorem in matrices proposed by Hungarian mathematician11. The Hungarian solution has two related theorems: Theorem 2.1 Suppose C=(Cij)n×n is an efficiency matrix. If n C=cij corresponding to n 1 of feasible solution X*=xij, is 0, X*is the optimal solution. (If all cij are 0, the final cost is 0, so X*is the optimal). Theorem 2.2 For the assignment problem, the new assignment problem obtained by subtracting (or adding) one same number from any row (or column) of the efficiency matrix is the same as the original problem. Theorem 2.1 and Theorem 2.2 are the principles of the Hungarian solution. These principles convert some elements of the efficiency matrix into 0 by certain operations. If there is a set of 0 elements, it satisfies:
Then this group of zero corresponding allocation is the optimal solution, we call this group of 0 elements as independent zero elements. The definition of the independent zero elements is given as follows: Definition 2.1 The independent zero elements are the 0 elements in matrix C which are located in neither the same row nor the same column. The minimum number of lines required to cross out all 0 elements in matrix C is equal to the number of independent zero elements in matrix C, that is, the maximum number of 0 selected of different rows and columns. 2.3.2The steps of Hungarian solution.The steps of the Hungarian solution are as follows:
3.MULTILATERAL MULTI-ATTRIBUTE FAIR NEGOTIATION MODEL3.1Scene descriptionBecause the second-hand car trading system has good consumption tendency attribute, this paper studies the multilateral fair consultation model under this background. In this system, more than one seller will be selling the same model of car, thus will negotiating with different customers according to the different attribute values of each vehicle - price, mileage, year of production, warranty date. Both the buyer and the seller have their own emphasis on different attributes, namely weight values, with prices, years of production, mileage, and warranty options weighing respectively 0.5, 0.2, 0.1, and 0.2. In Table 1, Preq and Mreq are the seller’s request values for the price and the mileage (the maximum that the participant wants in the negotiation). And in Table 2, Paw and Mreq are the buyer’s allowable values for price and mileage (the maximum that the participant can bargain for). In this paper, we want to explore how to negotiate to maximize the profit of the whole system and match successfully as many as possible. The negotiation information range of 50 buyers and 50 sellers simulated by computers are shown in Tables 1 and 2. Table 1.The scope of negotiation information generation of the seller.
Table 2.The scope of negotiation information generation of the seller.
3.2Establishment of the model3.2.1Evaluation of profits.In this paper, the participants’ profits are evaluated using the multi-attribute utility theory (MAUT)12. The utility function, which can be thought of as a buyer’s or buyer’s profit, is represented by the weight value wi of the attribute and the evaluation function Exi. A participant’s profit can be expressed as the following equations: Among these, n represents the serial number of the attribute, xi represents the variable value of attribute, and wi means the weight value of the i-th attribute. The allow_valuei and request_valuei are respectively the allow value and request value of the i-th attribute. Therefore, when xi changes between the allow_valuei and the request_valuei, the corresponding Exi range from 0 to 1. Exi now represents the satisfaction of attribute xi, which is set to 0 if the value of Exi is less than 0. And if the value of Exi is greater than 1, then it should be set to 1. The Ri buyer in equation (6) represents the scope of the buyer’s negotiation, Ri seller in equation (6) represents the seller’s negotiation scope, and CNRi represents the intersection of the buyer’s and seller’s negotiating scope for the i-th attribute. In order to improve the efficiency of the algorithm, we firstly pretreat the data. We pick the group impossible to match, that is, the two attribute ranges intersect empty, set the corresponding profit matrix P elements to 0, and for the three attribute intersections are non-empty, set the corresponding profit matrix P elements to 0.05 (a constant that is not 0). It’s more convenient for calculating. And in the next MATLAB profit matrix calculation program13, they will be discussed further. Since each element of the profit corresponds to a pair of matching optimal profit values, each match is equivalent to a bilateral negotiation. If a pair matches such as the profit P(i,j) corresponding profit is 0, it is not possible to match; if the corresponding profit is not 0, then we take the s-th seller and the t-th buyer for example: Equations (7) and (8) represents the profit of seller Profitsseller(xi) and the profit of the buyer Profitsbuyer(xi). A, B, C, D, E, F, G, H are the request and allowable values of the seller in Table 3 for the four properties in turn. In the same way, A1, B1, C1, D1, E1, F1, G1, H1 represents the request and allowable values of the buyer’s four attributes in turn. Table 3.MATLAB running result.
3.2.2Establishment of the negotiation model.This paper takes the attribute of negotiation as the variable, and establishes the bilateral reciprocal negotiation model as follows: In equations (9) and (10), z is the best profit value, the sum of the profits of the buyer and seller, n is the quantity of the product attribute, and δ is the threshold for the difference in profits between the buyer and the seller. Considering the characteristics of negotiation, this paper sets an appropriate threshold δ=0.01, which means that the profit bias between a buyer and a seller is not more than 1%. 3.2.3Establishment of allocation model.Similarly, we can draw an analogy between matching in a system and determining assignment in a 0-1 assignment problem. The objective function of the distribution model is to obtain the maximum profit income of the total system. In this paper, the maximum value of each pair of possible matches can be regarded as a new attribute of both parties, and the optimal value of all possible matches between all buyers and all sellers is formed into a profit matrix. In this matrix, the corresponding value of the impossible match is set to 0. The following allocation model is established: In the equations above, w is the total profit value of the system, a maximum of w is required in this paper. The i-th line j-th column element in the matrix C represents the maximum profit value that the i-th seller can achieve by matching the j-th buyer (that is, the z value obtained by the i-th seller and the j-th buyer in the negotiation model), m means the number of buyers and sellers. Decision variables are xij, the relationship is shown in equation (15): Equations (12) and (15) indicate that a seller can match only one buyer at most. Equations (13) and (15) indicate that a buyer can only match one seller at most. If when xij corresponding cij value is 0, then the i-th seller and the j-th buyer made a “virtual match”, which means no match. And this distribution model is supposed to match the same number of buyers and sellers. Of course, it’s possible to include “virtual matches”, which will continue to be discussed later in the program. 4.SIMULATION EXPERIMENT4.1Experimental resultsWhat we want is the maximum value of equation (9) under the given conditions. According to the function of solving the linear planning problem in MATLAB as the optimal profit value z, i.e. the element value corresponding to the profit matrix P(s,t), which makes up the 50×50 profit matrix. And it is matched by the classic Hungarian solution in the 0-1 assignment problem. Results solved by MATLAB is shown in Table 3. Sanghyun Park proposed in 2008 in the multilateral consultative system3 in the distribution, in which the use of profit sorting method spent most of the time of the whole algorithm. Its time complexity is O(NlogN), where N is the number of consultations. The time complexity of the Hungarian solution mentioned in this paper is O(N2). Although the sorting algorithm is better than the Hungarian algorithm when N→∞, the total profit of this paper must be optimal, and the matching logarithm is guaranteed. 4.2Effects of changes in relevant parameters on experimental resultsWe set δ=0.01 in this paper, and the experimental results have been obtained. But by changing the threshold δ=0.005, 0.02, 0.05, the results are not remarkably different. Four sets of data were compared, as shown in Table 4. Table 4.The influence of threshold on data.
5.CONCLUSIONIn this paper, we study the multilateral fair negotiation model based on e-commerce environment, mainly for the secondhand car trading system, establishing the multilateral fair negotiation model and calculating the profit matrix, considering the integrity of the trading system, choosing the Hungarian solution to solve the distribution model. Through numerical experiments and analysis, the maximum total profit and as many matching numbers can be obtained by the method proposed in this paper. Therefore, it has great research value for the actual trading system. Further research may include improving the stability of matching parties, average profit and simplified solution. ACKNOWLEDGMENTSThis work was supported in part by the Fundamental Research Funds for Central University under Grant N2005011, and in part by the Scientific Research Funds of Educational Department of Liaoning Province under Grant LT2020008. REFERENCESFaratin, P., Sierra, C., Jennings, N. R., ,
“Designing responsive and deliberative automated negotiators,”
in Proc. of the AAAI Work. on Negotiation: Settling Conflicts and Identifying Opportunities,
12
–18
(1999). Google Scholar
Faratin, P., Sierra, C. and Jennings, N. R.,
in Using similarity criteria to make negotiation trade-offs Proc. of the 4th Inter. Conf. on Multi-Agent Systems,
119
–126
(2000). Google Scholar
Park, S. and Yang, S. B.,
“An efficient multilateral negotiation system for pervasive computing environments,”
Engineering Applications of Artificial Intelligence, 21
((4)), 633
–643
(2008). https://doi.org/10.1016/j.engappai.2007.07.005 Google Scholar
Mittal, M., Gaba, D., Rana, H. and Swain, P. R.,
“An optimized multi-item bilateral negotiation model,”
in Amity Inter. Conf. on Artificial Intelligence (AICAI),
566
–570
(2019). Google Scholar
Xing, S., Research on Design of Bilateral E. Commerce Automatic Negotiation System Based on Agent, Shandong University of Science and Technology, Qingdao
(2014). Google Scholar
Chen, C., Research on Multi-attribute Negotiation and Guarantee Options of E-commerce Mass Customization Based on Agent], Xiamen University, Xiamen
(2013). Google Scholar
Liu, J., Research on Market Modeling, Allocation and Pricing Mechanism of Online Commerce], Yangzhou University, Jiangsu
(2017). Google Scholar
Gao, S., Ma, L. and Zhang, H.,
“Multi-Agent automated negotiation model for E-commerce based on the artificial bee colony algorithm,”
CAAI Transactions on Intelligent Systems,
((3)), 476
–481
(2015). Google Scholar
Tang, X., Moustafa, A. and Ito, T.,
“The design of meta-strategy that can obtain higher negotiating efficiency,”
in Thirteenth Inter. Conf. on Knowledge, Information and Creativity Support Systems (KICSS),
1
–6
(2018). Google Scholar
Cao, M., Chen, C. and Wang, G.,
“Study on automated negotiation with combined strategy in e-commerce oriented customization,”
Chinese Journal of Management, 16
((11)), 1712
–1718
(2019). Google Scholar
Hu, Y. and Guo, Y., [Operational Research Course], 135
–147 Tsinghua University Press, Beijing
(2007). Google Scholar
Barbuceanu, M. and Lo, W. K.,
“A multi-attribute utility theoretic negotiation architecture for electronic commerce,”
in Proc. of the 4th Inter. Conf. on Autonomous Agents,
239
–246
(2000). Google Scholar
Wu, Q., Zheng, Z. and Deng, W., [Operations Research and Optimization MATLAB Programming], 72
–84 Machinery Industry Press, Beijing
(2009). Google Scholar
|
