-The widespread use of social networks is modifying our way to live our cities and to plan/decide our activities. The long-term goal of our research is to provide users with group recommendation and decision support systems for smart city applications that rely on the analysis of the users' behaviors on social networks/media. In this paper, we provide an overview of the group recommendation literature from a game-theoretical/multiagent system classical point of view, and we present a practical example where a social choice mechanism is extended with social information extracted from the analysis of the interactions, within small groups of users, on a social network.
The widespread use of social networks is modifying our way to live our cities and to plan/decide our activities. In particular, the way we plan a travel, select places to visit or choose a restaurant, is influenced by the information we can access on social media. In this direction, the long-term goal of our research is to provide users with recommendation and decision support systems for smart city applications that rely on the analysis of the users’ behaviors on social networks/media. Examples of such applications are city tour planners or activities recommendation systems. Moreover, an automatic outdoor planning system of a city tour has to take into account that, potentially, groups of users (and not a single user) jointly select the activities to perform. Hence, it is necessary to choose activities, or, more generally speaking, certain Points of Interest (POI) that maximize the group satisfaction, considering that the members’ preferences can be different.
The problem of group recommendation has been widely
studied in the fields of information retrieval, mathematics,
economics and multi-agent systems. Group recommendation
approaches rely either on building a single group profile,
resulting from the combination of the profiles of all the users,
or on merging the recommendation lists generated for each
individual users, at runtime, using different group decision
strategies. Nevertheless, many of these techniques do not
consider social relationships among the group members [
In this work, we provide a general overview on the literature on group recommendations from a multi-agent/game theoretical point of view. Finally, we present a practical example where a classical social choice mechanism is extended with social information extracted from the analysis of the interactions, among members of small groups, in a social network. Differences between the classical implementation of the function and its extended version are evaluated with a user study.
In our work, we are interested in providing recommendations to groups of friends, intended as sets of people that meet, interact, or have some actual common bond in the physical world, since they are planning real activities to perform together. Moreover, the identity of the group members has to be dynamically determined, since the actual members of a group can be established only according to the activity to perform (i.e., a travel, a movie, and so on).
Following these requirements, we decided to focus on group recommendation systems that aggregate the recommendations considered for the single users. This approach will provide us the flexibility required in the group formation process (single user’s profile and recommendations are build independently from the group’s members) and to dynamically account group relationships, at the time of providing the group recommendations (the users’ recommendations are merged only once the group is formed). Finally, our system will not have to provide a single item recommendation, but sequences or sets, as required by the touristic application domain.
More formally, given a set of n friends (F = f1; : : : ; ng) and a set of m POI (P = f1; : : : ; mg), each user i 2 F has a preference profile i over P ( i= fri(1); : : : ; ri(m)g) with ri(x) 2 R, which represents the user i rank for the x POI, and is is evaluated by a single user recommendation agent. Our goal is to design a mechanism to obtain
F = frF (1); : : : ; rF (m)g, where rF (x) is the correspondent ranking for the x POI, as evaluated for the group, and that will help the group decision by simplifying the consensus making process.
A MULTI-AGENT VIEW
In this section, we provide an overview on the multiagent system (MAS) literature dealing with the problem of group recommendation. In this context, we can model the members of the group as agents, and they interact together to find the best compromise for the whole group. There are several approaches proposed in literature, which include classical game theory, voting, coalition making, social choice analysis and negotiation.
A typical approach for merging user rankings is the definition of Social Choice functions. Social Choice strategies, according to [4], can be classified as majority-based strategies (mainly implemented as voting mechanisms to determine the most popular choices among alternatives), consensus-based strategies (that try to average among all the possible choices and preferences), and role-based strategies (that explicitly takes into account possible roles and hierarchical relationships among members). In the rest of this section, we briefly summarize the main strategies for each category, providing references for further details.
a) Average Strategy: as described in [
b) Fairness Strategy: this strategy, described in [
c) Borda Count Strategy: this strategy, as explained in
[
also in this case a sorting among users is necessary. Starting
from the first user, his/her k top rated activities are considered.
In this case, however, among these the activity more voted by
other users is selected. The strategy is explained in [
e) Least Misery Strategy: this strategy, used in [3] for a group recommendation system for movie, PolyLens, can be used when one or more users give a rating particularly low for some activities. In case of small groups, it is reasonable to assume that the satisfaction of the group that performs an activity could decrease if one or more components really dislike the activity. Least Misery Strategy consists in assigning to each activity the minimum of its ratings.
f) Most Pleasure Strategy: if some user really likes one activity that is acceptable for other group members it should be rational to use, as group rating, the greatest given rating for the activity.
Another way, proposed in literature, to address the group recommendation problem, is the use of Negotiation methodology. In general, a set of agents act on behalf of human group members, participating in a cooperative negotiation for generating the group recommendations.
In [9] there is a negotiation agent for each group member. An individual recommendation system gives recommendation for a set of items, and, in addition to this, an individual utility of each product for each user is evaluated, introducing a user preference model. The Negotiation protocol is different according to the cardinality of the group. For groups of two people, the used protocol is of alternating offers, while for groups of more people, it uses a merging ranks protocol, with a mediator agent that has strategies to help in choosing among proposals and by offering an agreement to the group (i.e, by maximizing the average utilities of group members or maximizing the utility of the least happy member). The framework is tested by simulating the negotiation protocols.
Another approach is proposed in [
The original idea was then developed in a subsequent
work [
Differently from the previous cases, the use of coalitions in the field of group recommendation is not straightforward, since coalitions require the groups formation at run-time. The idea is to organize group members into smaller and cohesive groups, so it is possible to provide more effective recommendations to each of them. In [13] the problem is modeled as a coalitional game, where people are grouped into disjoint coalitions to maximize the social welfare function of the group. The payoff function considers the similarity between coalition members’s ratings, and a weighting factor for the coalition size. The approach is compared with a classic K-Means clustering, on randomly formed groups, and the results shows better performances in the formation of larger coalitions. In some cases, however, this approach is not applicable, because it is not possible to reorganize the group into more cohesive subgroups, but it is necessary to provide a recommendation for the whole group of users.
In some cases, group members could have more different interests conflicting with each other. In case of great heterogeneity, the attempt to resolve the conflict by applying a cooperative approach can lead to a failure in the negotiation [14]. In this scenario, it can be reasonable to apply noncooperative approaches. The idea is that users can be viewed as self-interested agents and the recommendation system can be modeled as a classical non-cooperative game in normal form.
In [14] an alternative approach based on non-cooperative games is proposed. In this case, group members are viewed as the players of the game, the items to recommend are viewed as game actions, and the recommendation problem is modeled as a problem of finding the Nash Equilibrium for the game. This approach is compared with other state-of-art aggregation strategies, Average, Least misery (LM) and Plurality Voting (PV). Average strategy shows the best performance, but the proposed strategy performs better with respect to LM and PV when the groups become more heterogeneous and wider.
In the previous sections, we presented the main MAS
techniques used to address the group recommendation problem.
The results presented in the literature showed that there is no
strategy can be defined as the “best”, but different approaches
are better suited in different scenarios, depending from the
characteristics of the specific group. Besides, traditionally
MAS techniques do not seem to capture all the features of
real-world scenarios. For example, automatic voting/ranking
mechanisms often require that all the agents involved have the
same influence on the decision procedure, while real group
interactions take into account intra-group roles and mutual
influences. Again, some members of the group could have
a particular influence on the others, based on their personal
experiences or on the strength of their mutual relationship.
Furthermore, there may be situations where the participants
follow a democratic process in order to find a possible solution,
and cases where the group is supported by a human leader.
Usually the decision of a group member whether or not to
accept a given recommendation may depend not only on
his/her own evaluation of the content of the recommendation,
but also on his/her beliefs about the evaluations of the other
group members [
On the basis of these considerations it appears necessary to integrate information from the social relationships among group members with the classical MAS techniques and so to derive new strategies more applicable to the considered settings. The most common approach is to remodel the utility of the agents by applying weights derived from social interactions between the members of the group.
For example, the work of [
Another way to use interactions between group members is presented in [15]. Here, the authors introduce the concept of empathetic utility on social networks: the satisfaction of an individual depends from both his intrinsic utility and his empathetic utility deriving from the happiness of his neighbors in the social network [15]. Based on this idea, individual preferences are aggregated in a weighted social choice function that takes into account local relationships with neighborhoods in the network. However, in [15] the Authors do not specify how to evaluate such numerical relationships, while they focus on computational aspects of scaling up with large networks of friends.
Both these approaches have the same gap, because they do 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 Online Social Networks (OSNs).
IV.
In [16] we presented a simple “non semantic” approach to
obtain information about users’ leadership values in decision
making, by analyzing the popularity of each user within the
group. Such popularity values are obtained implementing an
extension of the well-known PageRank algorithm [
In this paper, we use such evaluation to weight an Average
Satisfaction strategy. According to [
n ravg(x) = 1 X(R(i) ri(x)) n
i=1 where n is the number of users in the group F , R(i) is the leadership value of user i, calculated as in [16]. Hence, Equation 1 is a function that evaluates the average of all the i users rankings ri(x) weighted by the i-th leadership value R(i).
The set avg= fravg(1); : : : ; ravg(m)g, which is the set of group’s rankings computed for each item, is then used to get the final decision: the first k activities x (with k equals to the number of activities to propose) with the higher ravg(x) values are selected for the recommendation. Moreover, in order to evaluate our function, we also implemented the standard version of a simple averaging function (rst:avg(x)) on the same data: n rst:avg(x) = 1 Xri(x) n
i=1 V.
A PRACTICAL EXAMPLE
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 asked to imagine to plan a one-day visit in a specific city and to (1) (2) select, from a checklist of ten items, only three activities (i.e., places to visit) for the day. After that, it was asked to select two restaurants (from a check list of eight). Since we do not want the users to be involved in strategic reasoning, we did not ask the users to express ratings and preferences among the selected choices. A screen-shot of the interface used to select the activities to perform is shown in Figure 1. For each i 2 F a vector i= fri(1); : : : ; ri(m)g, with ri(x) 2 f0; 1g, and m = 18, representing the user choices, is stored, such that P ri(x) = 5. x2P
The group was, then, asked to discuss, face-to-face, in order to obtain a shared and unique decision for the group. This final decision corresponds to the Ground Truth vector GT used to evaluate our functions. Figure 2 shows a group while discussing the final choices with the support of a personal computer.
The average number of analyzed users’ interactions, within the entire group, is 1079 with a standard deviation of 1254. A very high standard deviation means that, for the specific class of users involved in the study (i.e., groups of close friends), on the considered OSN, the groups’ (and members’) behaviors were very different, and hence, they cover a wide range of possible users.
Firstly, the similarity of the proposed weighted version of
An example of web application that implements the proposed the average satisfaction function (ravg) with respect to the groups’ ground truth (rGT ) was evaluated. Such similarity is computed as a percentage of the ravg choices that were already selected in the group final choices rGT . We also evaluated the similarity of the groups’ ground truth with respect to the standard implementation of such function (i.e., rst:avg as a typical averaging function on users’ choices). Aggregated results are reported in Table I and, for each of the 14 groups, ravg and rst:avg values are reported in Figure 4. With respect to their standard implementation, the function that takes into account social relationships perform slightly better (74% w.r.t. 64%). The ravg consensus function often guesses 4 on 5 activities. In detail, as shown in Figure 4, taking into account the similarity of values for each group, the ravg results are always better or equal with respect to rst:avg results.
Moreover, we evaluated the similarity of rGT with respect to the leader’s choices (rLeader) of each group, and the similarity of rGT with respect to the remaining users’ choices in the group (ri). The leader of each group was evaluated as the 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 all groups involved in the experiment for such similarities. Considering the average similarity of each ri with respect to the rGT , the groups show a good value of cohesion (59%). Moreover, considering the aggregated data, the average similarity value of the leaders’ choices is 61%, which is comparable 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.
At last, we implemented the proposed approach to calculate POI recommendations for small groups of friends in a touristic web application. Figure 3 shows a user logged-in with facebook.com credentials and that selected two friends to create a group; the application, then, elaborates the global ranks for the group and filters the POI to show.
VI.
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. In particular, in this paper, we introduced the problem of group recommendation, as required in the developments of automatic and intelligent tools for activities scheduling.
The problem of group recommendation has been widely studied in different fields; here, we presented this issue as approached from MAS literature of view. Nevertheless, only few of the presented approaches started to consider social relationships among group members in the design of group recommendation, while almost all of these do not provide a mechanism to automatically retrieve this information.
Finally, in this paper, we presented a simple social choice function that uses “non-semantic” information extracted from real interactions on a social network to weight users’ ratings/choices. We provided an evaluation of the strategy with respect to its standard implementation. Results showed that, even for very simple aggregation functions, the introduction of social relationships data might provide improvements in the recommendation process.
The research leading to these results has received funding from the Italian Ministry of University and Research and EU under the PON OR.C.HE.S.T.R.A. project (ORganization of Cultural HEritage for Smart Tourism and Real-time Accessibility).