Group Recommendation for Smart Applications: a Multi-agent View of the Problem Francesco Barile Antonio Caso Silvia Rossi Dipartimento di Fisica, Dipartimento di Fisica, Dipartimento di Ingegneria Elettrica Università degli Studi di Napoli Università degli Studi di Napoli e Tecnologie dell’Informazione, “Federico II”, via Cintia MSA, “Federico II”, via Cintia MSA, Università degli Studi di Napoli 80126 Napoli, Italy 80126 Napoli, Italy “Federico II”, via Claudio 21, francesco.barile@unina.it antonio.caso@unina.it 80125 Napoli, Italy silvia.rossi@unina.it Abstract—The widespread use of social networks is modifying evaluate the group members’ weights, in terms of individual our way to live our cities and to plan/decide our activities. The members’ importance or influence in a group, for movie long-term goal of our research is to provide users with group recommendations. recommendation and decision support systems for smart city ap- plications that rely on the analysis of the users’ behaviors on social In this work, we provide a general overview on the lit- networks/media. In this paper, we provide an overview of the erature on group recommendations from a multi-agent/game group recommendation literature from a game-theoretical/multi- theoretical point of view. Finally, we present a practical ex- agent system classical point of view, and we present a practical ample where a classical social choice mechanism is extended example where a social choice mechanism is extended with social with social information extracted from the analysis of the information extracted from the analysis of the interactions, within interactions, among members of small groups, in a social small groups of users, on a social network. network. Differences between the classical implementation of the function and its extended version are evaluated with a user I. I NTRODUCTION study. The widespread use of social networks is modifying our way to live our cities and to plan/decide our activities. In II. P ROBLEM D EFINITION particular, the way we plan a travel, select places to visit In our work, we are interested in providing recommenda- or choose a restaurant, is influenced by the information we tions to groups of friends, intended as sets of people that meet, can access on social media. In this direction, the long-term interact, or have some actual common bond in the physical goal of our research is to provide users with recommenda- world, since they are planning real activities to perform to- tion and decision support systems for smart city applications gether. Moreover, the identity of the group members has to be that rely on the analysis of the users’ behaviors on social dynamically determined, since the actual members of a group networks/media. Examples of such applications are city tour can be established only according to the activity to perform planners or activities recommendation systems. Moreover, an (i.e., a travel, a movie, and so on). automatic outdoor planning system of a city tour has to take into account that, potentially, groups of users (and not a single Following these requirements, we decided to focus on user) jointly select the activities to perform. Hence, it is neces- group recommendation systems that aggregate the recommen- sary to choose activities, or, more generally speaking, certain dations considered for the single users. This approach will Points of Interest (POI) that maximize the group satisfaction, provide us the flexibility required in the group formation considering that the members’ preferences can be different. process (single user’s profile and recommendations are build independently from the group’s members) and to dynamically The problem of group recommendation has been widely account group relationships, at the time of providing the group studied in the fields of information retrieval, mathematics, recommendations (the users’ recommendations are merged economics and multi-agent systems. Group recommendation only once the group is formed). Finally, our system will not approaches rely either on building a single group profile, have to provide a single item recommendation, but sequences resulting from the combination of the profiles of all the users, or sets, as required by the touristic application domain. or on merging the recommendation lists generated for each individual users, at runtime, using different group decision More formally, given a set of n friends (F = {1, . . . , n}) strategies. Nevertheless, many of these techniques do not and a set of m POI (P = {1, . . . , m}), each user i ∈ F consider social relationships among the group members [1], has a preference profile i over P (i = {ri (1), . . . , ri (m)}) while the design and implementation of group recommendation with ri (x) ∈ R, which represents the user i rank for the systems, and, more generally, of decision support systems, x POI, and is is evaluated by a single user recommenda- should take into account the type of control in the group tion agent. Our goal is to design a mechanism to obtain decision-making process [2]. PolyLens [3] has been one of F = {rF (1), . . . , rF (m)}, where rF (x) is the correspondent the first approaches to include social characteristics within ranking for the x POI, as evaluated for the group, and that will a group recommendation system. A more recent example is help the group decision by simplifying the consensus making represented by the work of [1], where the Authors started to process. III. A M ULTI - AGENT V IEW f) Most Pleasure Strategy: if some user really likes one activity that is acceptable for other group members it should In this section, we provide an overview on the multi- be rational to use, as group rating, the greatest given rating for agent system (MAS) literature dealing with the problem of the activity. group recommendation. In this context, we can model the members of the group as agents, and they interact together B. Negotiation to find the best compromise for the whole group. There are several approaches proposed in literature, which include Another way, proposed in literature, to address the group classical game theory, voting, coalition making, social choice recommendation problem, is the use of Negotiation method- analysis and negotiation. ology. In general, a set of agents act on behalf of human group members, participating in a cooperative negotiation for generating the group recommendations. A. Social Choice In [9] there is a negotiation agent for each group member. An individual recommendation system gives recommendation A typical approach for merging user rankings is the def- for a set of items, and, in addition to this, an individual inition of Social Choice functions. Social Choice strategies, utility of each product for each user is evaluated, introducing according to [4], can be classified as majority-based strategies a user preference model. The Negotiation protocol is different (mainly implemented as voting mechanisms to determine the according to the cardinality of the group. For groups of two most popular choices among alternatives), consensus-based people, the used protocol is of alternating offers, while for strategies (that try to average among all the possible choices groups of more people, it uses a merging ranks protocol, and preferences), and role-based strategies (that explicitly with a mediator agent that has strategies to help in choosing takes into account possible roles and hierarchical relationships among proposals and by offering an agreement to the group among members). In the rest of this section, we briefly (i.e, by maximizing the average utilities of group members summarize the main strategies for each category, providing or maximizing the utility of the least happy member). The references for further details. framework is tested by simulating the negotiation protocols. a) Average Strategy: as described in [5], [1], this ap- Another approach is proposed in [10], where an alternat- proach consists in computing the group rating for an activity ing offers protocol is used. In this approach there is not a as the average of all group members’ ratings. It is commonly mediation, but groups size is restricted at two users. There used as a benchmark for comparison or as base to define more is an agent for each user, and there is a two-level user complex approaches. profiling, which includes a recommendation profile, containing personal information and preferences, and a negotiation profile, b) Fairness Strategy: this strategy, described in [6], [5], used to distinguish agent behaviors in the negotiation among needs of an ordering among the users of the group. In the three degree of collaboration (self-interested, collaborative and simplest case this ordering can be random. The first user is highly collaborative). If the negotiation process finishes with selected and his k best rated activities are taken into account. an agreement among all the agents, the result is a list of From them, the activity that guarantees the less misery to the constraints that match the preferences of the group members. other group members is chosen. The process is iterated on the other users until k activities are selected. The original idea was then developed in a subsequent work [11], where user agents are configurable in order to c) Borda Count Strategy: this strategy, as explained in exhibit the desired behavior of the corresponding user. The [6], [7], [8], consists into two phases. Initially, users’ ratings negotiation model is a multi-party negotiation that centralize are replaced with scores, assigned in this way: the activity with the communications through a negotiator agent, acting as the lowest rate for a user gets zero score, the next one gets mediator. It receives the proposals of the user agents, combines one, and so on. If two or more activities have the same rating them into a single proposal, which is later broadcasted by they are assigned with the average of the scores that should the negotiator agent and analyzed by the user agents. The have. After that, an additive or an average strategy can be used system uses a domain ontology to describe the user’s likes on those scores to obtain the group recommendation. and the items to recommend. The user agent is responsible of building and updating a user profile, of obtaining the individual d) Plurarity Voting Strategy: as for the fairness strategy, preference model, of participating in the negotiation process also in this case a sorting among users is necessary. Starting and of informing the user about the result of the negotiation. from the first user, his/her k top rated activities are considered. Besides, there are two support agents that help in computing In this case, however, among these the activity more voted by the individual preference model (preferences agent) and in other users is selected. The strategy is explained in [6], [8]. selecting the list of items that satisfy the group preferences, given the group preference model (items selector agent). The e) Least Misery Strategy: this strategy, used in [3] for protocol used in the negotiation is a generalization of the a group recommendation system for movie, PolyLens, can be bilateral alternating offers protocol [12] for the multi-party used when one or more users give a rating particularly low negotiation. for some activities. In case of small groups, it is reasonable to assume that the satisfaction of the group that performs C. Coalitions an activity could decrease if one or more components really dislike the activity. Least Misery Strategy consists in assigning Differently from the previous cases, the use of coalitions in to each activity the minimum of its ratings. the field of group recommendation is not straightforward, since coalitions require the groups formation at run-time. The idea is to capture both the preferences of the group members but also to organize group members into smaller and cohesive groups, these key factors in the group decision process [1]. so it is possible to provide more effective recommendations to each of them. In [13] the problem is modeled as a coalitional On the basis of these considerations it appears necessary game, where people are grouped into disjoint coalitions to to integrate information from the social relationships among maximize the social welfare function of the group. The payoff group members with the classical MAS techniques and so to function considers the similarity between coalition members’s derive new strategies more applicable to the considered set- ratings, and a weighting factor for the coalition size. The tings. The most common approach is to remodel the utility of approach is compared with a classic K-Means clustering, the agents by applying weights derived from social interactions on randomly formed groups, and the results shows better between the members of the group. performances in the formation of larger coalitions. In some For example, the work of [1] starts to evaluate the group cases, however, this approach is not applicable, because it is members weights, in terms of individual group members im- not possible to reorganize the group into more cohesive sub- portance or influence for movie recommendations. The defined groups, but it is necessary to provide a recommendation for group consensus function relies on the concept of “expertise” the whole group of users. and “group dissimilarity”. Also, it introduces the idea of diversifying the social choice strategy to use on the basis D. Normal Games of the characteristics of the group. The Authors calculate a “social value” on the basis of social interactions between group In some cases, group members could have more different members, and then use this value to discriminate the strategy interests conflicting with each other. In case of great het- to apply for the group. Both expertise and social interaction erogeneity, the attempt to resolve the conflict by applying a values are derived from questionnaires. cooperative approach can lead to a failure in the negotiation [14]. In this scenario, it can be reasonable to apply non- Another way to use interactions between group members cooperative approaches. The idea is that users can be viewed as is presented in [15]. Here, the authors introduce the concept self-interested agents and the recommendation system can be of empathetic utility on social networks: the satisfaction of modeled as a classical non-cooperative game in normal form. an individual depends from both his intrinsic utility and his empathetic utility deriving from the happiness of his neighbors In [14] an alternative approach based on non-cooperative in the social network [15]. Based on this idea, individual games is proposed. In this case, group members are viewed as preferences are aggregated in a weighted social choice function the players of the game, the items to recommend are viewed that takes into account local relationships with neighborhoods as game actions, and the recommendation problem is modeled in the network. However, in [15] the Authors do not specify as a problem of finding the Nash Equilibrium for the game. how to evaluate such numerical relationships, while they focus This approach is compared with other state-of-art aggregation on computational aspects of scaling up with large networks of strategies, Average, Least misery (LM) and Plurality Voting friends. (PV). Average strategy shows the best performance, but the proposed strategy performs better with respect to LM and PV Both these approaches have the same gap, because they do when the groups become more heterogeneous and wider. not provide a way to automatically retrieve social information. An idea to address this problem is showed in the next section, where we illustrate a way to retrieve social information from E. Weighted Utilities Online Social Networks (OSNs). In the previous sections, we presented the main MAS tech- niques used to address the group recommendation problem. IV. A L EADERSHIP W EIGHTED M ODEL The results presented in the literature showed that there is no In [16] we presented a simple “non semantic” approach to strategy can be defined as the “best”, but different approaches obtain information about users’ leadership values in decision are better suited in different scenarios, depending from the making, by analyzing the popularity of each user within the characteristics of the specific group. Besides, traditionally group. Such popularity values are obtained implementing an MAS techniques do not seem to capture all the features of extension of the well-known PageRank algorithm [17] starting real-world scenarios. For example, automatic voting/ranking from the users’ mutual interactions on the social network mechanisms often require that all the agents involved have the facebook.com. In fact, Online Social Networks analysis can same influence on the decision procedure, while real group provide a viable way to obtain, without intruding the users with interactions take into account intra-group roles and mutual questionnaires, information about the users and their social re- influences. Again, some members of the group could have lationships within communities and groups. More in detail, this a particular influence on the others, based on their personal approach defines a centrality measure that takes into account experiences or on the strength of their mutual relationship. the degree of activity of a person and the directionality of Furthermore, there may be situations where the participants specific communication activities between pairs of users, using follow a democratic process in order to find a possible solution, a combination of data collected from the OSN. Furthermore, and cases where the group is supported by a human leader. as in the classic PageRank, each user inherits a portion of Usually the decision of a group member whether or not to popularity from other users. accept a given recommendation may depend not only on his/her own evaluation of the content of the recommendation, In this paper, we use such evaluation to weight an Average but also on his/her beliefs about the evaluations of the other Satisfaction strategy. According to [18], users involved in real group members [6]. Recommendation systems for groups need interaction seem to care about fairness and to avoid misery, Fig. 2. A four people group taking the final decision. Fig. 1. A screen-shot of the web page used to select the activities to perform. select, from a checklist of ten items, only three activities (i.e., while averaging among choices get good results. Inspired by places to visit) for the day. After that, it was asked to select the works of [1], [19], we defined a strategy that takes into two restaurants (from a check list of eight). Since we do not account the leadership values as weights for the POI rankings, want the users to be involved in strategic reasoning, we did provided by the users (note that the sum of the leadership not ask the users to express ratings and preferences among the values among a group is equal to one). The proposed strategy selected choices. A screen-shot of the interface used to select to evaluate the group rF (x) rating for the POI x is the the activities to perform is shown in Figure 1. For each i ∈ F following: a vector i = {ri (1), . . . , ri (m)}, with ri (x) ∈ {0, 1}, and m = 18, representing the user choices, is stored, such that P n ri (x) = 5. 1X x∈P ravg (x) = (R(i) · ri (x)) (1) n i=1 The group was, then, asked to discuss, face-to-face, in order to obtain a shared and unique decision for the group. This where n is the number of users in the group F , R(i) is final decision corresponds to the Ground Truth vector GT the leadership value of user i, calculated as in [16]. Hence, used to evaluate our functions. Figure 2 shows a group while Equation 1 is a function that evaluates the average of all the discussing the final choices with the support of a personal i users rankings ri (x) weighted by the i-th leadership value computer. R(i). A. Results The set avg = {ravg (1), . . . , ravg (m)}, which is the set of group’s rankings computed for each item, is then used to The average number of analyzed users’ interactions, within get the final decision: the first k activities x (with k equals to the entire group, is 1079 with a standard deviation of 1254. A the number of activities to propose) with the higher ravg (x) very high standard deviation means that, for the specific class values are selected for the recommendation. Moreover, in order of users involved in the study (i.e., groups of close friends), to evaluate our function, we also implemented the standard on the considered OSN, the groups’ (and members’) behaviors version of a simple averaging function (rst.avg (x)) on the same were very different, and hence, they cover a wide range of data: possible users. Firstly, the similarity of the proposed weighted version of n 1X rst.avg (x) = ri (x) (2) n i=1 V. A P RACTICAL E XAMPLE We conducted a pilot study with real users involved in the task of planning a trip in a city. We evaluated only the users’ behaviors in the decision making process and the impact of our consensus function on a simple case of binary selection of POI (i.e., yes or no decisions on a POI, without expressing an explicit ranking among activities). The behavior of 14 groups composed, in the average, of 3.36 close friends is evaluated. 46 users took part in the experimentation (26 men and 20 women). The average age was 27.3 with a graduate education. We asked each user to register on a specific web site using the credentials of facebook.com. Once registered, he/she was Fig. 3. An example of web application that implements the proposed asked to imagine to plan a one-day visit in a specific city and to approach. Fig. 4. rst.avg and ravg results for each group. % Similarity rst.avg ravg rLeader ri mean 64 ± 16 74 ± 12 61 ± 17 59 ± 11 VI. C ONCLUSION TABLE I. P ERCENTAGES OF SIMILAIRTY RESULTS IN THE USER STUDY. The smarter cities paradigm relies on a massive use of technologies and big data analysis to enhance and facilitate human-environment interactions in a pervasive way. In order to be easily accessed and retrieved all these data has to be filtered and selected according to user behaviors and profiles. the average satisfaction function (ravg ) with respect to the In particular, in this paper, we introduced the problem of group groups’ ground truth (rGT ) was evaluated. Such similarity is recommendation, as required in the developments of automatic computed as a percentage of the ravg choices that were already and intelligent tools for activities scheduling. selected in the group final choices rGT . We also evaluated the similarity of the groups’ ground truth with respect to The problem of group recommendation has been widely the standard implementation of such function (i.e., rst.avg as studied in different fields; here, we presented this issue as a typical averaging function on users’ choices). Aggregated approached from MAS literature of view. Nevertheless, only results are reported in Table I and, for each of the 14 groups, few of the presented approaches started to consider social ravg and rst.avg values are reported in Figure 4. With respect relationships among group members in the design of group to their standard implementation, the function that takes into recommendation, while almost all of these do not provide a account social relationships perform slightly better (74% w.r.t. mechanism to automatically retrieve this information. 64%). The ravg consensus function often guesses 4 on 5 activities. In detail, as shown in Figure 4, taking into account Finally, in this paper, we presented a simple social choice the similarity of values for each group, the ravg results are function that uses “non-semantic” information extracted from always better or equal with respect to rst.avg results. real interactions on a social network to weight users’ rat- ings/choices. We provided an evaluation of the strategy with Moreover, we evaluated the similarity of rGT with respect respect to its standard implementation. Results showed that, to the leader’s choices (rLeader ) of each group, and the even for very simple aggregation functions, the introduction similarity of rGT with respect to the remaining users’ choices of social relationships data might provide improvements in the in the group (ri ). The leader of each group was evaluated as the recommendation process. member with the highest R(i) score according to leadership value calculated as indicated in [16]. Table I summarizes the cumulative data (mean values and standard deviations) of ACKNOWLEDGMENT all groups involved in the experiment for such similarities. The research leading to these results has received funding Considering the average similarity of each ri with respect to from the Italian Ministry of University and Research and EU the rGT , the groups show a good value of cohesion (59%). under the PON OR.C.HE.S.T.R.A. project (ORganization of Moreover, considering the aggregated data, the average simi- Cultural HEritage for Smart Tourism and Real-time Accessi- larity value of the leaders’ choices is 61%, which is comparable bility). with the ri similarity value. This behavior is in accordance with our requirement to analyze close groups without any dictatorial user, or strong hierarchical relationships. R EFERENCES At last, we implemented the proposed approach to calculate [1] M. Gartrell, X. Xing, Q. Lv, A. Beach, R. Han, S. Mishra, and K. Seada, “Enhancing group recommendation by incorporating social relationship POI recommendations for small groups of friends in a touristic interactions,” in Proceedings of the 16th ACM International Conference web application. Figure 3 shows a user logged-in with face- on Supporting Group Work, ser. GROUP ’10. ACM, 2010, pp. 97–106. book.com credentials and that selected two friends to create [2] M. T. Jelassi and A. Foroughi, “Negotiation support systems: an a group; the application, then, elaborates the global ranks for overview of design issues and existing software,” Decision Support the group and filters the POI to show. Systems, vol. 5, no. 2, pp. 167 – 181, 1989. [3] M. O’Connor, D. Cosley, J. A. Konstan, and J. Riedl, “Polylens: [11] I. Garcia and L. Sebastia, “A negotiation framework for heterogeneous A recommender system for groups of users,” in Proceedings of the group recommendation,” Expert Systems with Applications, vol. 41, Seventh Conference on European Conference on Computer Supported no. 4, pp. 1245–1261, 2014. Cooperative Work, ser. ECSCW’01. Kluwer Academic Publishers, [12] A. Rubinstein, “Perfect equilibrium in a bargaining model,” Economet- 2001, pp. 199–218. rica: Journal of the Econometric Society, pp. 97–109, 1982. [4] C. Senot, D. Kostadinov, M. Bouzid, J. Picault, A. Aghasaryan, and [13] L. A. M. Carvalho and H. T. Macedo, “Generation of coalition structures C. Bernier, “Analysis of strategies for building group profiles,” in to provide proper groups’ formation in group recommender systems,” in User Modeling, Adaptation, and Personalization, ser. Lecture Notes in Proceedings of the 22Nd International Conference on World Wide Web Computer Science, P. Bra, A. Kobsa, and D. Chin, Eds. Springer Companion, ser. WWW ’13 Companion. International World Wide Berlin Heidelberg, 2010, vol. 6075, pp. 40–51. Web Conferences Steering Committee, 2013, pp. 945–950. [5] J. Masthoff, “Modeling a group of television viewers,” in Proceedings [14] L. A. M. C. Carvalho and H. T. Macedo, “Users’ satisfaction in recom- of the Workshop Future tv, in Intelligent Tutoring Systems Conference, mendation systems for groups: An approach based on noncooperative 2002, pp. 34–42. games,” in Proceedings of the 22Nd International Conference on World [6] I. Cantador and P. Castells, “Group recommender systems: New per- Wide Web Companion, ser. WWW ’13 Companion. International World spectives in the social web.” in Recommender Systems for the Social Wide Web Conferences Steering Committee, 2013, pp. 951–958. Web, ser. Intelligent Systems Reference Library, J. J. P. Arias, A. F. [15] A. Salehi-Abari and C. Boutilier, “Empathetic social choice on social Vilas, and R. P. D. Redondo, Eds. Springer, 2012, vol. 32, pp. 139– networks,” in 13th International Conference on Autonomous Agents and 157. Multiagent Systems, 2014, pp. 693–700. [7] S. Ghosh, M. Mundhe, K. Hernandez, and S. Sen, “Voting for movies: [16] A. Caso and S. Rossi, “Users ranking in online social networks to The anatomy of a recommender system,” in Proceedings of the Third support pois selection in small groups,” in Extended Proceedings of the Annual Conference on Autonomous Agents, ser. AGENTS ’99. New 22nd Conference on User Modelling, Adaptation and Peronalization - York, NY, USA: ACM, 1999, pp. 434–435. UMAP 2014, 2014, pp. 5–8. [8] J. Masthoff, “Group modeling: Selecting a sequence of television items [17] S. Brin and L. Page, “The anatomy of a large-scale hypertextual web to suit a group of viewers,” in Personalized Digital Television. Springer, search engine,” Computer Networks and {ISDN} Systems, vol. 30, no. 2004, pp. 93–141. 17, pp. 107 – 117, 1998, proceedings of the Seventh International World [9] P. Bekkerman, S. Kraus, and F. Ricci, “Applying cooperative negotiation Wide Web Conference. methodology to group recommendation problem,” in Proceedings of [18] J. Masthoff, “Group recommender systems: Combining individual Workshop on Recommender Systems in 17th European Conference on models,” in Recommender Systems Handbook, F. Ricci, L. Rokach, Artificial Intelligence (ECAI 2006). Citeseer, 2006, pp. 72–75. B. Shapira, and P. B. Kantor, Eds. Springer US, 2011, pp. 677–702. [10] I. Garcia, L. Sebastia, and E. Onaindia, “A negotiation approach for [19] S. Amer-Yahia, S. B. Roy, A. Chawlat, G. Das, and C. Yu, “Group rec- group recommendation.” in Proceedings of the 2009 International ommendation: Semantics and efficiency,” Proc. VLDB Endow., vol. 2, Conference on Artificial Intelligence, Las Vegas Nevada, USA. CSREA no. 1, pp. 754–765, Aug. 2009. Press, 2009, pp. 919–925.