Currently, to solve the problem of modeling negotiations between supply chain participants, multi-agent systems with more than two agents are used. To formalize the negotiation process between agents, the monotonic concession protocol was used, which was modified to allow the use of more than two agents. As a strategy, the Zeuthen strategy for the protocol was used, which was modified to allow the use of more than two agents, and also the choice of the agreement option for the conceding agent for this strategy was formalized. The agreement, the utility function and the risk of going into conflict for the protocol were formalized, which allows us to consider the distribution of tasks between agents as a modified assignment problem, in which all agents should receive approximately the same income from solving problems. The proposed approach can be used in various multi-agent systems for modeling negotiations. Zeuthen strategy Multi-agent systems, negotiation modeling, supply chains, monotonic concession protocol, [12-14].
modeled only between them.
2022 Copyright for this paper by its authors. To model negotiations [15-17] the following are used: 1. Approach of the Nash. It is assumed that two prerequisites are met: in case of refusal to negotiate, the parties receive zero utility and both agents know each other's utility functions. The goal of negotiations should be to maximize the product of the utilities of both agents. 2. Approach of the Rubinstein. A negotiation protocol is followed and the behavior of agents, who act according to this protocol, is analyzed. Negotiations can last an unlimited number of rounds, but in order to reach an agreement as soon as possible, it is assumed that in each round of negotiations, agents bear fixed costs and the usefulness of the result obtained decreases with each round.
For both approaches, a common disadvantage is that there can be only two agents [18]. Further improvements of these approaches [19-21], increasing the number of agents, led to high computational complexity.
In studies devoted to the negotiation problem, two types of strategies can be found: timedependent [7, 22, 23], and behavior-dependent [24-25].
Time-dependent strategies are divided into: • conservative (the agent continues to insist on his initial offer until the deadline, and then quickly makes concessions up to the minimum acceptable price); • linear (the agent has a linear utility function); • compliant (at the beginning of negotiations, the agent quickly makes concessions up to the minimum acceptable price).
In time-dependent strategies, the behavior of the agent does not depend on the actions of the second agent. The disadvantage of these strategies is that agents, like people, usually come to an agreement gradually.
Behavior-dependent strategies are based on the behavior of the second agent. These strategies require knowledge of the utility function of the second agent. The disadvantage of these strategies is the need to analyze the sequence of actions of the agent.
For strategies that depend on time or behavior, a common disadvantage is that there can be only two agents. In this regard, the modeling of negotiations, which will eliminate the indicated drawback, is relevant.
The aim of the work is to model negotiations between supply chain participants based on a multiagent system. To achieve the goal, the following tasks were set and solved: • propose a protocol defining the rules for negotiations between agents; • propose a strategy based on the developed protocol that agents use during negotiations; • perform numerical studies.
Let the finite set of admissible variants of agreements on how agents distribute the tasks to be solved among themselves be denoted as . Depending on the problem, one agent can solve both a single task and several tasks, both individually and jointly.
In this paper, a variant of the agreement lt , lt , which was proposed by the l th agent in the
t th round of negotiations on the distribution of tasks to be solved, is presented in the form
lt = [xltij ] , xltij {0,1} , i {1,...,m}, j {1,...,n} ,
(
t xlij indicates that the i th agent solves or does not solve the j th problem.
Let the conflicting agreement be defined as c , c .
In this paper, the utility function of the variant of the agreement, which is proposed by the l th agent in the t th round of negotiations, for the i th agent is defined as income from the performance of the tasks by this agent 2.3.
In this paper, we propose an extended Zeuthen strategy for multiple agents.
1. In the first round of negotiations, all agents simultaneously propose the most preferred
agreement options for them, i.e.
(
if i : j 1, m u j ( it ) = u j ( tj ) , then negotiations conclude and the option of the agreement will be selected it . 4. If in the t th round the agents did not agree, i.e. i : j 1, m u j ( it ) u j ( tj ) , but there is an agent i* willing to make a concession, then negotiations continue. In round t +1 the conceding agent i* can offer other agents only such a variant of the agreement it*+1 , for which the concession condition is satisfied. 5. If in the t th round the agents did not agree, i.e. i : j 1, m u j ( it ) u j ( tj ) , and there is no agent willing to make a concession, then negotiations end in a conflicting agreement c .
n ui ( lt ) = wij xltij ,
j=1 where wij – income from the solution by the i th agent of the j th task.
Such utility function satisfies two constraints: 1. The function is monotonous, that is, adding the tasks to be solved never diminishes the utility. 2. If there are no tasks to be solved, then the utility is zero.
In this paper, the risk of making a conflict (unwillingness to make concessions) for the i th agent in the t th round of negotiations is defined as rit = uk ( it ) , k {1,...,m}/{i} .
k 2.2.
Extended monotonic concession protocol for multiple agents i1 = arg max ui ( ) , i 1, m . 2. If in the t th round of negotiations the agents did not agree, but the concession of one of them is possible, then the conceding agent is defined as the agent who has the least risk of going into a conflict, i.e.
If there are several agents with the same minimal risk rit , then agent i* is randomly selected from among them.
For all agents except agent i* , tj+1 = tj . 4.
The conceding agent i* proposes a variant of the agreement it*+1 in the round t +1 . The following choice of the variant of the agreement it*+1 is proposed, which will increase the risk for the agent i* to enter into a conflict, that is
ti* = uk ( ) rit* , , k {1,...,m}/{i*} , k ~ ti* = arg max ui ( ) ,
ti*
it*+1 = arg ma~txi* k uk ( ) , k {1,..., m}/{i*} .
(
If there are several options for agreements, then option it*+1 is randomly selected from them.
Let the number of tasks be n =4.
Let the number of agents m =2.
Let the task can be solved by only one agent, but one agent can solve several tasks. Let the finite set of admissible variants of agreements be defined as
0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 = 1 1 1 1 , 0 0 0 0 , 0 1 1 1 , 1 0 0 0 , 1 0 0 1
, 0 1 1 0 1 0 1 1
, 0 0
Next, we will step by step execute the extended monotonic concession protocol. 1. In the first round of negotiations, both agents simultaneously propose the most preferable agreement options for them, i.e.
1 1 1 1 11 = arg max u1( ) = , 0 0 0 0 0 0 0 0 21 = arg max u2 ( ) = .
1 1 1 1 of negotiations, both 2. In the first
round i : j 1,2 u j ( i1) u j ( 1j ) , where
u1(11) = 60 , u2 (11) = 0 , u2 ( 21) = 60 , u1( 21) = 0 .
Therefore, the concession of one of them is possible. To determine the conceding agent, the risks of going into conflict are calculated, i.e. agents did not agree, since 12 = 0 1 1 1
be chosen.
1 0 0 0 4. In the second round of negotiations, both agents did not agree, since i : j 1,2 u j ( i2 ) u j ( 2j ) , where u1(12 ) = 50 , u2 (12 ) = 20 , u2 ( 22 ) = 60 , u1( 22 ) = 0 . Therefore, the concession of one of them is possible. To determine the conceding agent, the risks of going into conflict are calculated, i.e.
r12 = u2 (12 ) = 20 , r22 = u1( 22 ) = 0 , and the agent with the lowest risk is determined, i.e.
i* = arg min ri2 = 2 .
i1,2 Then 13 = 12 . 5. In the third round of negotiations, the conceding agent 2 randomly chooses an agreement option from the set ~22 = 10 10 10 10 , 10 10 10 10 . For example, let the agreement option 23 = 0 1 0 0 be chosen.
1 0 1 1 6. In the third round of negotiations, both agents did not agree, since i : j 1,2 u j ( i3 ) u j ( 3j ) , where u1(13) = 50 , u2 (13) = 20 , u2 ( 23) = 50 , u1( 23) = 20 . Therefore, a concession of one of them is possible. To determine the conceding agent, the risks of conflict are calculated, i.e.
r13 = u2 (13 ) = 20 , r23 = u1( 23) = 20 , and the agent with the lowest risk is determined, i.e.
arg min ri3 = {1,2} .
i1,2 Since there are two such agents, the conceding agent i* will be randomly selected from among them. For example, let i* =1, then 24 = 23 . 7. In the fourth round of negotiations, the conceding agent 1 chooses the only agreement option 14 = 10 10 10 10 from the set ~31 = 10 10 10 10 . 8. In the fourth round of negotiations, both agents did not agree, since i : j 1,2 u j ( i4 ) u j ( 4j ) , where u1(14 ) = 40 , u2 (14 ) = 40 , u2 ( 24 ) = 50 , u1( 24 ) = 20 . Therefore, a concession of one of them is possible. To determine the conceding agent, the risks of conflict are calculated, i.e.
r14 = u2 (14 ) = 40 , r24 = u1( 24 ) = 20 , and the agent with the lowest risk is determined, i.e.
i* = arg min ri2 = 2 .
i1,2 9. In the fifth round of negotiations, the conceding agent 2 chooses the only agreement option 10. In the fifth round of negotiations, both agents agreed, since i : j 1,2 u j ( i5 ) = u j ( 5j ) , where u1(15) = 40 , u2 (15) = 40 , u2 ( 25) = 40 , u1( 25) = 40 . Therefore, the negotiations are completed and a variant of the agreement will be randomly selected from the set { 5j} . For example, let it be 15 .
The resulting agreement 15 will be the maximum point on the discrete set of the discrete function (k) = (u1( k ) − u1( c ))(u2( k ) − u2( c )) , k = {1,...,| |} , k , and is the Nash solution of the negotiation task. 3.2. Extended monotonic concession protocol and Zeuthen strategy in the case of three agents
Let the number of tasks be n =3.
Let the number of agents m =3.
Let the task can be solved by only one agent, but one agent can solve several tasks. Let the finite set of admissible variants of agreements be defined as
0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 1 0 = 0 0 0 , 1 1 1 , 0 0 0 , 1 0 0 , 0 0 0 , 0 1 0 , 0 0 0 , 1 1 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 , 0 0 0 , 0 1 1 , 0 1 1 , 1 0 1 , 1 0 1 , 1 1 0 , 1 1 0 , 1 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 0 1 0 0 0 1 0 0 0 , 1 0 0 , 0 0 0 , 0 1 0 , 0 0 0 , 0 0 1 , 0 0 1 , 0 1 0 , 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 , 1 0 0 , 0 1 0 , 1 0 0 . 0 1 0 0 1 0 0 0 1 0 0 1 Let the conflicting agreement be defined as
1 0 0 c = 0 0 1 .
0 1 0 Let the income matrix from solving tasks by agents be defined as
5 5 20 W = 5 20 5 .
20 5 5 Next, we will step by step execute the extended monotonic concession protocol. 1. In the first round of negotiations, three agents simultaneously offer their preferred options for agreements, i.e. u1( 21) = 0 , u3( 21) = 0 , u3 ( 31) = 30 , u1( 31) = 0 , u2 ( 31) = 0 . Therefore, a concession of one of them is possible. To determine the conceding agent, the risks of conflict are calculated, i.e.
r11 = u2 (11) + u3(11) = 0 , r21 = u1( 21) + u3( 21) = 0 , r31 = u1( 31) + u2 ( 31) = 0 , and the agent with the lowest risk is determined, i.e.
arg min ri1 = {1,2,3} .
i1,3 Since there are three such agents, a conceding agent i* will be randomly selected from among them. For example, let i* =1, then 22 = 21 , 32 = 31. 3. In the second round of negotiations, the conceding agent 1 randomly chooses an agreement 0 1 1 1 0 1 option from the set ~11 = 0 0 0 , 0 1 0 . For example, let the agreement option 1 0 0 0 0 0 0 1 1 12 = 0 0 0 be chosen.
1 0 0 4. In the second round of negotiations, three agents did not agree, because i : j 1,3 u j ( i2 ) u j ( 2j ) , where u1(12 ) = 25 , u2 (12 ) = 0 , u3(12 ) = 20 , u2 ( 22 ) = 30 , u1( 22 ) = 0 , u3 ( 22 ) = 0 , u3( 32 ) = 30 , u1( 32 ) = 0 , u2 ( 32 ) = 0 . Therefore, a concession of one of them is possible. To determine the conceding agent, the risks of conflict are calculated, i.e.
r12 = u2 (12 ) + u3(12 ) = 20 , r22 = u1( 22 ) + u3( 22 ) = 0 , r32 = u1( 32 ) + u2 ( 32 ) = 0 , and the agent with the lowest risk is determined, i.e.
arg min ri2 = {2,3} .
i1,3 Since there are two such agents, a conceding agent i* will be randomly selected from among them. For example, let i* =2, then 13 = 12 , 33 = 32 . 5. In the third round of negotiations, the conceding agent 2 randomly chooses an agreement 0 0 1 0 0 0 option from the set ~22 = 1 1 0 , 0 1 1 . For example, let the agreement option 0 0 0 1 0 0 0 0 0 23 = 0 1 1 be chosen.
1 0 0 u1( 23) = 0 , u3( 23) = 20 , u3( 33) = 30 , u1( 33) = 0 , u2 ( 33 ) = 0 . Therefore, a concession of one of them is possible. To determine the conceding agent, the risks of conflict are calculated, i.e.
r13 = u2 (13) + u3(13) = 20 , r23 = u1( 23) + u3( 23) = 20 , r33 = u1( 33) + u2 ( 33) = 0 , and the agent with the lowest risk is determined, i.e.
i* = arg min ri3 = 3 .
i1,3 Then 14 = 13 , 24 = 23 . 7. In the fourth round of negotiations, the conceding agent 3 randomly chooses an agreement 0 0 1 0 0 0 option from the set ~33 = 0 0 0 , 0 1 0 . For example, let the agreement option 1 1 0 1 0 1 0 0 1 34 = 0 0 0 be chosen.
1 1 0 8. In the fourth round of negotiations, three agents did not agree, since i : j 1,3 u j ( i4 ) u j ( 4j ) , where u1(14 ) = 25 , u2 (14 ) = 0 , u3(14 ) = 20 , u2 ( 24 ) = 25 , u1( 24 ) = 0 , u3( 24 ) = 20 , u3( 34 ) = 25 , u1( 34 ) = 20 , u2 ( 34 ) = 0 . Therefore, a concession of one of them is possible. To determine the conceding agent, the risks of conflict are calculated, i.e.
r14 = u2 (14 ) + u3(14 ) = 20 , r24 = u1( 24 ) + u3( 24 ) = 20 , r34 = u1( 34 ) + u2 ( 34 ) = 20 , and the agent with the lowest risk is determined, i.e.
arg min ri4 = {1,2,3} .
i1,3 Since there are three such agents, a conceding agent i* will be randomly selected from among them. For example, let i* =1, then 25 = 24 , 35 = 34 . 9. In the fifth round of negotiations, the conceding agent 1 chooses the only agreement option 0 0 1 0 0 1 15 = 0 1 0 from the set ~41 = 0 1 0 .
1 0 0 1 0 0 10. In the fifth round of negotiations, three agents did not agree, since i : j 1,3 u j ( i5 ) u j ( 5j ) , where u1(15 ) = 20 , u2 (15 ) = 20 , u3(14 ) = 20 , u2 ( 25 ) = 25 , u1( 25) = 0 , u3( 25 ) = 20 , u3( 35 ) = 25 , u1( 35 ) = 20 , u2 ( 35 ) = 0 . Therefore, a concession of one of them is possible. To determine the conceding agent, the risks of conflict are calculated, i.e.
r15 = u2 (15) + u3(15) = 40 , r25 = u1( 25) + u3( 25) = 20 , r35 = u1( 35) + u2 ( 35) = 20 , and the agent with the lowest risk is determined, i.e.
arg min ri5 = {2,3} .
i1,3 Since there are two such agents, a conceding agent i* will be randomly selected from among them. For example, let i* =2, then 16 = 15 , 36 = 35 . 11. In the sixth round of negotiations, the conceding agent 2 chooses the only agreement option 0 0 1 0 0 1
~ 26 = 0 1 0 from the set 52 = 0 1 0 .
1 0 0 1 0 0 12. In the sixth round of negotiations, three agents did not agree, since i : j 1,3 u j ( i6 ) u j ( 6j ) , where u1(16 ) = 20 , u2 (16 ) = 20 , u3(16 ) = 20 , u2 ( 26 ) = 20 , u1( 26 ) = 20 , u3( 26 ) = 20 , u3( 36 ) = 25 , u1( 36 ) = 20 , u2 ( 36 ) = 0 . Therefore, a concession of one of them is possible. To determine the conceding agent, the risks of conflict are calculated, i.e.
r16 = u2 (16 ) + u3(16 ) = 40 , r26 = u1( 26 ) + u3( 26 ) = 40 , r36 = u1( 36 ) + u2 ( 36 ) = 20 , and the agent with the lowest risk is determined, i.e.
i* = arg min ri6 = 3 .
i1,3 Then 17 = 16 , 27 = 26 . 13. In the seventh round of negotiations, the conceding agent 3 chooses the only agreement option 0 0 1 0 0 1 37 = 0 1 0 from the set ~63 = 0 1 0 .
1 0 0 1 0 0 14. In the seventh round of negotiations, the three agents agreed because i : j 1,3 u j ( i7 ) = u j ( 7j ) , where u1(17 ) = 20 , u2 (17 ) = 20 , u3(17 ) = 20 , u2 ( 27 ) = 20 , u1( 27 ) = 20 , u3( 27 ) = 20 , u3( 37 ) = 20 , u1( 37 ) = 20 , u2 ( 37 ) = 20 . Therefore, negotiations are completed and an agreement variant from the set { 7j} will be randomly selected. For example, let it be 17 .
The resulting agreement 17 will be the maximum point on the discrete set of the discrete function (k) = (u1( k ) − u1( c ))(u2 ( k ) − u2 ( c ))(u3( k ) − u3( c )) , k = {1,...,| |} , k , and is the Nash solution of the negotiation task.
Figure 1 shows the dependence of the discrete function (k) on the number of acceptable variants of the agreement k. The resulting agreement 17 corresponds to the number of the acceptable variant of the agreement k=23.
To solve the problem of modeling negotiations between supply chain participants, the existing approaches to modeling negotiations were investigated. These studies have shown that the use of multi-agent systems with more than two agents is currently relevant.
The proposed formalization of the modified agreement, the utility function and the risk of going into conflict made it possible to formalize the modified protocol of monotonous concessions and the Zeuthen strategy for negotiating and expand the problem of modeling negotiations between two selfish agents to many agents, which allows solving a wider range of problems.
The proposed approach has the following features: • the utility functions of a set of selfish agents are compared (one-to-many comparison) to determine an agreement that satisfies all agents. In contrast to the classical assignment problem, the main objective is not the achievement of the extremum of the sum of the values of the utility functions of all agents (that are altruistic), but the proximity of the values of the utility functions of all selfish agents; • the agreement variant matrix reflects the distribution of tasks between a set of selfish agents and is similar to the variant of the task distribution matrix between a set of agents (that are altruistic) for the classical assignment problem; • the yielding agent (the agent with the least risk of conflict) is selected from a set of agents. In contrast to the classical assignment problem, the main objective is not the achievement of an extremum of the sum of the values of the utility functions of all agents (that are altruistic), but the minimum deterioration in the value of the utility function of the yielding agent.
This allows us to consider the problem of modeling negotiations between participants in supply chains as a variant of the assignment problem in the case of selfish agents.
The proposed approach can be used in various multi-agent systems for modeling negotiations (for example, the manufacture of goods by different firms or employees, the delivery of goods by different firms or drivers, the distribution of goods between bases, etc.).
[10] S. Latré, P. Leroux, T. Coenen, B. Braem, P. Ballon, P. Demeester, City of things: An integrated and multi-technology testbed for IoT smart city experiments, in: Proceedings of the IEEE 2nd International Smart Cities Conference: Improving the Citizens Quality of Life, 2016, 16355341. doi: 10.1109/ISC2.2016.7580875 [11] A. S. Palau, M. H. Dhada, K. Bakliwal, A. K. Parlikad, An Industrial Multi Agent System for real-time distributed collaborative prognostics, Engineering Applications of Artificial Intelligence 85 (2019) 590–606. doi.org/10.1016/j.engappai.2019.07.013 [12] L. Males, D. Marcetic, S. Ribaric, A multi-agent dynamic system for robust multi-face tracking,
Expert Systems with Applications 126 (2019) 246–264. doi:10.1016/j.eswa.2019.02.008 [13] K. Sycara, T. Dai, Agent reasoning in negotiation, in: D. Kilgour and C. Eden (Eds.), Handbook of Group Decision and Negotiation, Springer Netherlands, 2010, pp. 437–451. doi: 10.1007/97890-481-9097-3_26. [14] S. Wang, J. Wan, D. Zhang, D. Li, C. Zhang, Towards smart factory for industry 4.0: A selforganized multi-agent system with big data based feedback and coordination, Computer Networks 101 (2016) 158–168. doi.org/10.1016/j.comnet.2015.12.017 [15] M. Wu, M. M. de Weerdt, H. L. Poutre, Efficient methods for multi-agent multi-issue negotiation: Allocating resources, in: J.-J. Yang, M. Yokoo, T. Ito, Z. Jin, and P. Scerri (Eds.), Proceedings of the PRIMA, volume 5925 of Lecture Notes in Computer Science, Springer, 2009, pp. 97–112. doi:10.1007/978-3-642-11161-7_7. [16] G. Villarrubia, J.F. de Paz, D. H. de la Iglesia, J. Bajo, Combining multi-agent systems and wireless sensor networks for monitoring crop irrigation, Sensors 17 (2017) 1775. doi.org/10.3390/s17081775 [17] A. Rubinstein, Settling the complexity of computing approximate two-player Nash equilibria, in: I. Dinur (Ed.), IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016, pp. 258–265. doi: 10.1109/FOCS.2016.35 [18] N. Parrish, A. J. Llorens, The any-combiner for multi-agent target classification, in: Proceedings of the 16th International Conference on Information Fusion, 2013; pp. 166–173. [19] S. Hart, N. Nisan, The query complexity of correlated equilibria, Games and Economic Behavior 108 (2018) 401-410. doi:10.1016/j.geb.2016.11.003 [20] A. Torreño, E. Onaindia, A. Komenda, M. Štolba, Cooperative multi-agent planning: A survey //
ACM Computing Surveys 50 (2018) 84. doi.org/10.1145/3128584 [21] X. Chen, Y. Cheng, B. Tang. Well-supported vs. approximate nash equilibria: Query complexity of large games, ITCS 57 (2017). doi: 10.4230/LIPIcs.ITCS.2017.57. [22] C. Amato, G. Konidaris, G. Cruz, C. A. Maynor, J. P. How, L. P. Kaelbling, Planning for decentralized control of multiple robots under uncertainty, in: Proceedings of the 2015 IEEE International Conference on Robotics and Automation, 2015, pp. 1241–1248. doi.org/10.1109/ICRA.2015.7139350 [23] A. Dukeman, J. A. Adams, Hybrid mission planning with coalition formation, Autonomous
Agents and Multi-Agent Systems 31 (2017) 1424–1466. doi.org/10.1007/s10458-017-9367-7 [24] S. Chen, G. Weiss, An efficient and adaptive approach to negotiation in complex environments, in: Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012), volume 242, 2012, pp. 228–233. doi:10.3233/978-1-61499-098-7-228. [25] M. Hendriks, T. Hendriks, C. Jonker, The benefits of opponent model in negotiation, in: IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT ’09), 2009, pp. 439–444.