Maximum Welfare Allocations under Quantile Valuations
For researchers in computational social choice and resource allocation, this work provides a new model that captures richer behavioral preferences beyond additive valuations, with complexity results and algorithms.
This paper introduces a quantile-based valuation model for aggregating preferences over indivisible items, where each agent's bundle value is the quantile of item values. It analyzes the complexity of maximizing utilitarian and egalitarian welfare, showing that balancedness significantly affects complexity, and provides near-optimal approximation algorithms for utilitarian welfare and exact algorithms for egalitarian welfare where possible.
We propose a new model for aggregating preferences over a set of indivisible items based on a quantile value. In this model, each agent is endowed with a specific quantile, and the value of a given bundle is defined by the corresponding quantile of the individual values of the items within it. Our model captures the diverse ways in which agents may perceive a bundle, even when they agree on the values of individual items. It enables richer behavioral modeling that cannot be easily captured by additive valuation functions. We study the problem of maximizing utilitarian and egalitarian welfare within the quantile-based valuation setting. For each of the welfare functions, we analyze the complexity of the objectives. Interestingly, our results show that the complexity of both objectives varies significantly depending on whether the allocation is required to be balanced. We provide near-optimal approximation algorithms for utilitarian welfare, and for egalitarian welfare, we present exact algorithms whenever possible.