In this paper, we propose a unified framework and an algorithm for the problem of group recommendation where a fixed number of items or alternatives can be recommended to a group of users. The problem of group recommendation arises naturally in many real world contexts, and is closely related to the budgeted social choice problem studied in economics. We frame the group recommendation problem as choosing a subgraph with the largest group consensus score in a completely connected graph defined over the item affinity matrix. We propose a fast greedy algorithm with strong theoretical guarantees, and show that the proposed algorithm compares favorably to the state-of-the-art group recommendation algorithms according to commonly used relevance and coverage performance measures on benchmark dataset.
In economics, group recommendation is studied as a special case of the budgeted social choice problem @cite_1 @cite_19 . The budgeted consensus recommendation is often considered as a trade-off between pure personalized recommendation and pure consensus recommendation. In group recommendation, the budget is specified as a function of the recommendation size, keeping the other cost components constant. Most of the work on budgeted social choice theory assumes that user preferences for the items are strict, i.e. every user derives benefit from at most one item that has the highest preference score (utility score), and preference scores are often derived using positional scoring rules like Borda count. lu2011budgeted ( lu2011budgeted ) proposed a greedy algorithm using knapsack heuristics, but it worked very poorly on group recommendation tasks with positional scoring rules. piotr15_collect ( piotr15_collect ) extended the theoretical framework for limited choice models with positional scoring rules using the ordered weighted average (OWA) operators.
@cite_19 @cite_1
2952061453 1238745702
We consider the following problem: There is a set of items (e.g., movies) and a group of agents (e.g., passengers on a plane); each agent has some intrinsic utility for each of the items. Our goal is to pick a set of @math items that maximize the total derived utility of all the agents (i.e., in our example we are to pick @math movies that we put on the plane's entertainment system). However, the actual utility that an agent derives from a given item is only a fraction of its intrinsic one, and this fraction depends on how the agent ranks the item among the chosen, available, ones. We provide a formal specification of the model and provide concrete examples and settings where it is applicable. We show that the problem is hard in general, but we show a number of tractability results for its natural special cases. We develop a general framework for social choice problems in which a limited number of alternatives can be recommended to an agent population. In our budgeted social choice model, this limit is determined by a budget, capturing problems that arise naturally in a variety of contexts, and spanning the continuum from pure consensus decision making (i.e., standard social choice) to fully personalized recommendation. Our approach applies a form of segmentation to social choice problems-- requiring the selection of diverse options tailored to different agent types--and generalizes certain multiwinner election schemes. We show that standard rank aggregation methods perform poorly, and that optimization in our model is NP-complete; but we develop fast greedy algorithms with some theoretical guarantees. Experiments on real-world datasets demonstrate the effectiveness of our algorithms.