Skip to content

Fractional Assignment with ℓ1 Preferences

Sep 2026 · arXiv.org · Vol abs/2609.18299 · 0 citations · 27 references
Economics Computer Science

Abstract

We study a fractional assignment setting where $n$ objects are to be assigned to $n$ agents with unit capacity, and each agent specifies an ideal distribution over the objects. Unlike in classic random assignment, these ideal distributions are not necessarily degenerate, as agents may prefer a mixture of objects rather than any single object. We assume that agents seek to minimize the $\ell_1$ distance between their ideal distribution and the distribution they receive, which is equivalent to maximizing the overlap between the two distributions. We propose two mechanisms, one based on water filling (WF) and the other on quadratic programming (QP), and show that both mechanisms are utilitarian-optimal (and hence Pareto efficient), envy-free, strategyproof, and satisfy equal treatment of equals. Moreover, we highlight a distinct advantage of each mechanism: while the WF mechanism satisfies the stronger property of group-strategyproofness, the QP mechanism is more robust in terms of egalitarian overlap welfare.

View source

Similar papers

Preprint Oct 2026

Fair Allocation with Dichotomous Preferences over Item Complements

We study the problem of fair allocation when agents have dichotomous submodular preferences over groups of, rather than individual, items. These preferences naturally extend existing models, and have a natural interpretation in settings such as course allocation. We show that this seemingly minor extension results in c...

Soumyajit Pyne, V. Viswanathan, Wen-Hao Yang et al. · 0 citations
Preprint Oct 2026

Subjective Valuations Make It Hard to be Fair: The Complexity of Resource Allocation to Groups of Agents

We study the parameterized complexity of finding an EF1 allocation of indivisible items in the group-sharing setting, which has received increasing attention in recent years. There, items are not allocated to individual agents but rather to one of two (or possibly more) groups, and agents within that group all share th...

Argyrios Deligkas, E. Eiben, Robert Ganian et al. · 0 citations
Review Oct 2026

Envy-free Allocations with Individual Payments

When an envy-free allocation of indivisible goods does not exist, monetary transfers can restore envy-freeness. Existing work on fair division with subsidies, however, typically assumes that these payments are provided by an external source, an assumption that may be unrealistic in many applications. We address this li...

Robert Bredereck, E. Deltl, Tanmay Inamdar et al. · 0 citations
Preprint Oct 2026

Online Fair Division under Eligibility Constraints

We study fair division of indivisible items under eligibility constraints: each item may be assigned only to a subset of eligible agents. This model coincides with restricted assignment in scheduling, with agents as machines and items as jobs, and captures settings where work or resources must be split among parties wi...

Joes Biburger, Nicole Megow, Golnoosh Shahkarami · 1 citation

Games and Economic Behavior

H. Aziz, Florian Brandl, A. Sydney et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.