-The pervasive use of web technologies and online cooperation tools is posing new challenges in the design of recommender systems, requiring now a rapid move from individual to group recommendations. In this paper, a multi-agent system to provide support to small groups of users in their decisionmaking process is presented. In detail, the addressed problem is to find a common solution for a group, represented by a set of activities in the touristic domain, among a huge set of possible alternatives, that meets the preferences of each member. The proposed system uses an automatic negotiation process that incrementally builds a candidate solution for the whole group according to the individual lists of each group member. Since the negotiation mechanism involves the real users to take part in the decision-making process, the proposed approach tries to limit the agreement search space during the negotiation process in order to minimize the user direct intervention. The proposed solution relies on negotiating agents that simulate the users' behavior while trading by using different conflict resolution styles, obtained by applying the Thomas Kilmann model. The results obtained with both simulated and real users' behavior show that the proposed system achieves a high probability of success, finding a shared solution, in most cases, in a relatively small number of rounds of negotiation. In addition, end users were satisfied with the received recommendations.
The problem of taking decisions shared by groups of people
is becoming a crucial aspect when using social networks
[
The main problem of these approaches is that they do
not seem to reflect many aspects of real decision-making
processes, where factors like mutual influences, personality of
group’s members [
In the present work, a Group Decision Support System
(GDSS) is designed to recommend a set of POI to a group
of users. Each member of the group is represented by a
software agent, and the process of building up a shared
decision is modeled as an automated negotiation among agents.
Individual preferences are explicitly specified by end users, and
they are used by the corresponding agents in the negotiation
phase. During the negotiation, agents have different behaviors
corresponding to different conflict resolution styles that are
based on the widely used Thomas-Kilmann Conflict Mode
Instrument (TKI) [
The proposed system has been evaluated through experimental tests in order to assess how the different behaviors and heuristics impact the process of finding a solution. In addition, the system has been used by real users that provided, through online questionnaires, a measure of their level of satisfaction regarding the system usability, and the quality of the received recommendations with respect to their preferences.
II.
The proposed Group Decision Support System relies on the design of a multi-agent system to help end-users belonging to a group to find a shared solution consisting of a set of tourist attractions to visit in a reasonable time. The multiagent system is composed of a set of agents (called useragents) each one acting on behalf of a group member and of a special agent acting as a mediator (called mediator-agent) that interacts with the others to build a solution in an autonomous way by minimizing the users’ intervention. At the end of the process, the end-users would be requested to approve or not the solution proposed by the system.
A crucial step in the implementation of a GDSS is the definition of the decision-making strategy to use. For example, a voting mechanism could be deployed, which provides an efficient solution in terms of decision speed, and it allows to avoid deadlocks problems. However, no fair voting mechanism exists, and one-shot mechanisms may not allow for the complete exploration of the solution space, whereas outcomes that satisfy also the minority of the users may exist. A second possibility is to design a consensus strategy, where group members try to reach an agreement on an outcome. This criterion usually requires a higher involvement by each member in the decisionmaking process and longer computational times, but it ensures a good solution quality because every decision is based on the whole community consensus.
Here, we propose to implement a consensus mechanism based on an automated negotiation mechanism where useragents try to reach an agreement by involving the users only in providing their preferences on items (to obtain reliable data), and in the final approval decision. It is assumed that there is a group U of n users, a set I of t POI, and a set R of evaluations (also called ratings), given by the individual users to some of the POI in the system. A user u ∈ U can evaluate an item i ∈ I, as ru,i (with ru,i ∈ {1, 2, 3, 4, 5}), so Ui is the set of users who evaluated the item i, and Iu is the set of items evaluated by the user u. A suggested solution is a subset of I with size m ≤ t, that represents a compromise among the individual users’ preferences, i.e. that maximizes the group satisfaction also guaranteeing a minimum utility value for each member of the group.
The proposed decision-making process is based on an alternation of a Merging Ranks step, made by the mediatoragent, to aggregate preferences and compute a subset of POI to propose to the group, and a Negotiation step, where each user-agent may accept the received proposal or reply to the suggested solution with an alternative one. In detail, such alternating protocol is composed of the following steps: 1) 2) 3) the mediator generates a suggested solution for the group according to the individual preference lists of each group member; each user agent can accept/reject the received proposal; 2.1) if the proposal is rejected, the user-agent generates a counteroffer; if the proposed solution is accepted by all the useragents, such solution is proposed to the end users; 3.1) otherwise the mediator aggregates the received counteroffers, and it generates a new solution for the group.
If all the allowed negotiation rounds take place without reaching an agreement, the process ends by proposing a solution to the end user that maximize the Social Welfare in the mediator current POI domain. In the following subsections, the GDSS functioning is described starting from the users’ preferences collection, to the steps that take place to build suggested recommendations for the group.
The mediator-agent is responsible for building and sending proposals to the group members, i.e. a set of POI P = {p1, ..., pm}, that, if accepted by all members, becomes the group solution. In order to build a proposal, the mediator refers to the set of POI it is aware of, i.e. the set PG that have been rated by all the users, known as the Mediator Domain.
We define the POI list PG for a specific group G as follows: PG = [ Iu u∈G
Therefore, it represents the set of POI obtained from the aggregation of the individual preference lists of the different group members. The mediator agent is in charge of collecting and aggregating the users’ preferences. The PG set constitutes the initial solution space for the mediator agent. This space could change (increase) during the decision-making process.
In principle, in order for the mediator to search for a solution, each group member should evaluate all the POI that have been evaluated by the other members, but not by him/herself (PG \ Iu). However, this process would potentially require each user to be involved in a long process to provide all the needed information, so an upper bound to the number of POI to be rated is mandatory. Typically, in recommender systems, this upper bound is set around 20. In order to create the PG set taking into account the users’ preferences (i.e., the items they evaluated with the higher rates), the k-best rated POI for each user are selected from the corresponding Iu. So, the k value depends on the number of users in a group (k = 20/n). Subsequently, whenever the mediator will require additional information to proceed, additional ratings could be requested to the users.
In order to build the first proposal, the mediator calculates
a group rate rG,j for each POI j ∈ PG, as follows:
rG,j =
u∈U
X ru,j · pj
n
that represents a weighted mean of the individual ratings, and
the weight pj ∈ [
The first proposal is composed by selecting the m POI with the highest group rank, so it is the solution that maximizes the Social Welfare (i.e., the weighted sum of the individual utilities). Once the first proposal is computed, the mediator sends it to all user agents that privately evaluate it according to their own utility function.
In case the proposal is rejected, the mediator receives a number of counteroffers, each one composed of a possible new set of m POI (Oi = {pi1 , ..., pim }) from each user agent i that rejected the proposal. If a counteroffer contains POI that are not in the Mediator Domain PG, the mediator asks the user-agents to provide ratings for them (interacting with the real users). Then, the mediator generates a new proposal on the new domain PG, by applying the same strategy used to build the first proposal. If the new proposal is different from the previous one, it is sent to the user agents; otherwise the mediator modifies it, according to the received counteroffers, by replacing the POI that in its previous solution was discharged by the highest number of user-agents (when the counteroffers were generated), with the one that had the highest number of new occurrences in the generated counteroffers.
In literature, several models of conflict management have
been proposed. In particular, in 1974 H. Kilmann and W.
Thomas [
For each user agent, an individual optimal value (i.e., the value corresponding to the solution with the highest utility) and a reservation value are set. Given Iu the set if POI evaluated by the user u, and Iu(m) the set of m POI with the highest rank for the user u, then the optimal value, at time 0, is given by:
OP Tu(0) =
X
i∈Iu(m)
reu,i
m
where reu,i is the rating the user u assigned to the POI i
normalized in [
When the user agent receives an offer P t from the mediator, at the negotiation round t, it evaluates the utility of the received offer as follows: Uu(P t) = Pi∈P t remu,i . This value is compared with the agent utility value of the previous negotiation round, OP Tu(t − 1). The decision strategy is implemented as follows: 1) 2) 3) if Uu(P t) ≥ OP Tu(t − 1), then the agent accepts the offer and sets OP Tu(t) = Uu(P t); if Uu(P t) ≥ OP Tu(t − 1) − Δu(t), then the agent accepts the offer by conceding in its utility by a value that is smaller or equal of Δu(t), and it sets OP Tu(t) = Uu(P t); in all the other cases, the agent rejects the offer and it makes a counteroffer either by randomly conceding in utility (OP Tu(t) = OP Tu(t − 1) − Δu(t)) or by not conceding (OP Tu(t) = OP Tu(t − 1)).
Δu(t) is the utility concession value at time t that depends
on the user profile in the conflict resolution style modeled
according to the considered Thomas Kilmann user profiles [
TABLE I. Accommodating, it is not assertive and cooperative, and it accommodates the objectives of the other group members, so helping them in finding a shared solution by conceding of a constant value during all negotiation rounds, so being the most collaborative profile; Competing, it is assertive, and it prioritizes agent’s own objectives, by conceding of low values at the beginning of the negotiation, while increasing the concession value at the end of negotiation to try to reach an agreement before a negotiation failure occurs; Compromising, it is a compromise between assertive and cooperative, and it tries to find a solution that accommodates the objectives of all involved parties, by conceding high concession values at the beginning and at the end of the negotiation, while conceding of a constant value in the intermediate rounds.
Collaborative, it is both assertive and cooperative, by
trying to make all to work together to find a common
solution. The Ludwig studies [
More specifically, for each profile three concession steps
are defined by the model [
Finally, in the case of a rejection, the user agent generates a counteroffer whose utility value is calculated taking into account whether a concession takes place or not. Once fixed a utility value, there could be potentially many POI combinations that result having the same utility values. So, in order to compute a counteroffer, we defined two different heuristic strategies to reduce the search space, the Search in Domain and the Reference Point ones that will be introduced next. Moreover, the system allows the mediator-agent to communicate with the user-agents to suggest which strategy to use with respect to the negotiation stage (e.g., the number of rounds or the number of conflicts in the offers).
1) Search in Domain: With this heuristic, the user-agent orders the items of the proposal received by the mediator P t according to its own ranking, and it generates a counteroffer by modifying the proposal to obtain an admissible proposal (i.e., a proposal with the required utility) by making the fewest possible substitutions searching in its private domain.
2) Reference Point: This strategy applies when there is only one agent conflicting with a given proposal, that, on the contrary, is admissible for all other members of the group. In such a case, the mediator sends a proposal to that agent that represents a reference point for the agent to build a counteroffer. In that case, the user-agent adapts as much as possible its counteroffer to the received one. So the conflicting agent is required to adapt its objectives to the proposal satisfying all the other members of the group.
The realized system is composed of a Web Application
that allows users to interact with the system compiling the
TKI questionnaire, providing the ratings for the POI, and
indicating the group’s composition, and of an Automatic
Negotiation Module, that represents the core of the system (see
Figure 1). The module is developed using Jade [
In the realized Multi-Agent System there is a Jade Agent for each user in the system, that acts on his/her behalf during the negotiation, according to the Conflict Resolution Style, and a Jade Agent for the Mediator, that manages the negotiation process. All agents are executed within a Jade Container, that provides all the features for agents creation, execution, synchronization and exchange of messages. When the users complete the TKI questionnaire, the agents are instantiated and the negotiation process can start. The Web Application and the Negotiation Module communicates through a shared database. During the negotiation, in case it is necessary to ask for new ratings, the negotiation process is interrupted and the rating request is saved in the database. The Web Applications periodically queries the database and, if there is a request for 1FIPA specifications are available http://www.fipa.org/repository/ standardspecs.html at the website ratings the Web Application of the corresponding user will request him/her to provide an evaluation of the POI. The same mechanism is used at the end of the process to communicate the results of the negotiation.
In order to evaluate the proposed system performances in terms of the generated recommendations, a first preliminary analysis was carried out on a simulated data set, i.e. by assigning random values of rating to the POI. POI were extracted from the social network Foursquare. Successively, the same experiments were executed in a pilot study by using real data provided by groups of real end users, and asking them to compile a questionnaire concerning the goodness of the recommendation, and the usability of the system.
The performances of the heuristics, the Search in Domain
and the Reference Point, for the generation of counteroffers
were evaluated, together with the negotiation success rate in
case of complete knowledge, i.e. in our application domain,
the mediator directly knows all the rating for all the POI in
the dataset. The generated recommendations were evaluated
in different experimental settings by varying the number of
available POI in the dataset, from 20 to 1000, the group size n
from 3 to 5 members, and the number m of POI in the solution
from 1 to 5. The size of a group is kept within the chosen range
because the focus of the present work is to test decision making
support for small groups that rely on different mechanisms
(e.g., interpersonal relationships and mutual influences) with
respect to the ones adopted for large groups [
Each algorithm is executed 100 times for each possible configuration, and for each execution, the users’ behaviors, i.e. their conflict resolution styles, are randomly generated. The maximum number of allowed negotiation round was set to 30. Fig. 3. Average execution time to reach an agreement.
The success rate for the first heuristic is 99%, against 77% of the second one. In Figure 2, we plotted the average number of rounds to reach an agreement, varying the number of available POI, discharging the cases of negotiation failures. As shown in Figure 2, the Reference Point heuristic requires a greater number of rounds to reach an agreement with respect to the Search in Domain case, reaching similar performances when the number of POI is greater than 1000. Therefore, the Reference Point does not represent a feasible solution for sets of POI that vary from 20 to 1000, by complicating the search of user-agent counteroffers, and bringing to failure the negotiation process. Moreover, notice that by increasing the number of POI up to 500, the number of rounds necessary to reach an agreement increases, as expected, because of the increased dimension of the solution search space. On the contrary, by further increasing the number of POI the number of rounds to reach an agreement decreases because the available chances to generate acceptable counteroffers increases, so potentially leading to a reduction of the number of conflicts.
The execution time of the Reference Point algorithm is slightly greater than the Search in Domain one, as reported in Figure 3. Moreover, the trend of execution time differs from the one of negotiation rounds. While, for a number of POI greater than 500, the number of rounds to reach an agreement starts to decrease, the average execution time increases. In this case, in fact, it is the time required to compute a counteroffer that impacts more on the execution time.
In the pilot study, the system is evaluated in a realistic
case study, i.e., with groups of users having to choose a set
of restaurants with respect to the preferences of each group’s
member. Notice that, a key factor to implement an effective
GDSS is to rely on reliable available data [
We conducted the study on 10 groups, composed of 2 or 3 users. For each group, the required solution is composed of a number of restaurants varying from 1 and 3. The maximum number of rounds for each negotiation is set to 30. The used dataset contains 521 POI of the city of Naples, obtained using the Foursquare API. After using the system, each user is asked to fill a questionnaire concerning the evaluation of the goodness of the recommendations and of the usability of the system. The questionnaire is composed of two sets of statements that the users are asked to rate with a score ranging from 1 to 5 (respectively, strongly disagree, disagree, neutral, agree, strongly agree). The first set concerns the evaluation of the user interaction with the system, while the second one concerns the evaluation of the quality of the proposed recommendations.
• •
Q3 The system does not require several user interaction steps to produce a recommendation; Q4 The number of required ratings is fair;
Q7 The system allowed discovering new POI.
The users’ answers percentages, as reported in Table II, show that the system is user-friendly, rapid, easy to use, and effortless. The only point showing conflicting opinions concerns the number of ratings required by the system to the end users (Q4), so this parameter could slightly be reduced in future works.
Regarding, the evaluation of the recommendations, we initially observed that the agents always fond an agreement during the negotiation process. The evaluations assigned by the users to the provided recommendations show a great satisfaction, with the 70% of the users strongly satisfied, and the remainder 30% simply satisefid. In addition, the users positively replied to the question regarding if the system helped them in discovering new points of interest.
The problem of defining the proper decision strategy is
crucial in group decision support systems. In Choicla [
Negotiation for group recommendation was already used
in some approaches. For example, in [
VI.
CONCLUSION
In this work, we presented a Group Recommendation System that uses an automatic negotiation mechanism among software agents to provide the final decision for the group, i.e. a decision that meets the requirements/preferences of the group members. There is an agent for each group’s member that acts on user’s behalf during the negotiation, modeling his/her behavior in a conflict situation. The user’s conflict resolution styles are obtained through the well-known Thomas Kilmann Instrument, a questionnaire compiled by each user after the registration in the system. The negotiation is managed by a Mediator agent that generates proposals of solutions, and it evaluates the counteroffers received by the other agents. The Mediator decides also the heuristic to use in the generation of the new proposals.
We analyzed the system by conducting two experiments, one with simulated data, and one with a real pilot study. The results show that the system provides high success rate in finding a solution with a number of negotiation rounds lower than 30. The pilot study reported satisfying results in terms of the negotiation success rate, and of the quality of the recommendations provided.
These results seem to be very interesting and suggest some possible way to extend the work. One possibility is to automate the steps where an interaction with the user is required, so avoiding the compilation of TKI questionnaires and the ratings requests during the negotiation, estimating these ratings with an individual recommendation system.