Abstract
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.
Introduction
Traditional social choice theory typically focuses on finding a single "consensus" winner to represent an entire population. Conversely, modern recommender systems aim for full personalization, providing each user with their specific top choice. However, many practical scenarios exist in the middle of this spectrum. A decision-maker may be able to offer multiple options but is constrained by a budget. For instance, a city planning committee might have the funds to build three parks, or a company might have the resources to manufacture four variants of a product.
This paper introduces the Budgeted Social Choice (BSC) framework to address these scenarios. The goal is to select a subset of alternatives and assign users to them to maximize overall satisfaction while adhering to a budget that accounts for both fixed costs (e.g., development) and unit costs (e.g., production).
The Budgeted Social Choice Model
The BSC model formalizes the problem of selecting a set of alternatives to maximize social welfare under cost constraints. User satisfaction is quantified using Positional Scoring Functions (PSFs), such as the Borda count, which assigns points based on an item's rank in a user's preference list.
The problem involves two main components:
- Selection: Choosing which alternatives to provide.
- Assignment: Determining which alternative each user should be assigned to (typically their most preferred option among the selected set).
Because the general optimization problem is NP-complete, the authors focus on developing efficient heuristic solutions.
The Popularity-Diversity Gap
A key insight of this research is that standard rank aggregation methods—such as simply picking the top-$K$ winners from a Borda or Kemeny ranking—are fundamentally ill-suited for budgeted social choice. These methods optimize for overall popularity, which often results in selecting very similar items that appeal to the same majority group while leaving minority factions underserved.
The authors mathematically demonstrate a "Top-$k$ Penalty." For Borda rankings, selecting the top $K$ items can result in a social welfare score that is a factor of 2 worse than the optimal diverse slate. For other scoring functions, this gap can widen to a factor of $K$. This highlights that budgeted social choice is essentially a customer segmentation problem: the goal is to find a set of items where every distinct segment of the population has at least one option they highly value.
Algorithmic Solutions
To solve the BSC problem efficiently, the authors propose two primary algorithms:
- SweetSpotGreedy (SSG): Designed for the general BSC problem with both fixed and unit costs. It iteratively selects the alternative and user subset that provides the highest marginal score increase per unit of cost, followed by a backtracking phase to ensure budget compliance.
- Greedy (for Limited Choice): In cases where unit costs are zero and the goal is to pick exactly $K$ items, the problem reduces to constrained submodular maximization. The standard greedy approach provides a theoretical guarantee of reaching at least 63.2% ($1 - 1/e$) of the optimal solution.
Experimental Evaluation
The algorithms were tested on two real-world datasets: the 1980 APA presidential election preferences and a sushi preference dataset.
In the APA dataset, which featured a split between "academic" and "clinician" voters, the Greedy algorithm successfully identified a diverse pair of candidates (one from each faction) that maximized satisfaction, whereas standard Borda methods failed to capture this diversity.
On the Sushi dataset, the Greedy algorithm demonstrated exceptional performance. As shown in the table above, for various values of $K$, the Greedy algorithm consistently achieved the optimal social welfare (a score of 1.0) while running in under one second. In contrast, exact optimization using CPLEX took up to 90 seconds. In the general BSC case with randomized costs, the SSG algorithm maintained 97% to 99% optimality while remaining significantly faster than exact solvers.
Conclusion
The Budgeted Social Choice framework provides a robust method for balancing consensus and personalization. By prioritizing diversity over simple popularity, the proposed greedy algorithms offer near-optimal social welfare with high computational efficiency. Future work includes extending the model to handle incomplete preference data and exploring more complex cost structures or ROI-based objectives.
Summary updated