arXiv preprint ·
Fair Allocation with Dichotomous Preferences over Item Complements
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 computational intractability barriers: computing a utilitarian or Nash-optimal allocation with item complements is NP-hard. However, when agents' complementary bundles have size at most $k$, there exist poly-time algorithms that compute $\frac1k$-$\texttt{maxUSW}$ allocations and approximate Nash-welfare-maximizing allocations. While PO+EF-1 allocations may not exist in the complementary preference setting, it is possible to compute $\frac1{k+1}$-approximately $\texttt{maxUSW}$ EF-X allocations in polynomial time; furthermore, these allocations offer each agent $i$ a utility of at least $\frac{\texttt{MMS}_i - k}{k+1 + \frac1n}$, where $\texttt{MMS}_i$ is agent $i$'s maximin share guarantee. While the standard dichotomous binary submodular setting admits simple sequential techniques for computing fair and efficient allocations, our results for the complements setting require more complex tools from combinatorial optimization.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
Do Rollups Self-Organize? Multi-Agent Reinforcement Learning in the EIP-4844 Blob Fee Market
Improved Combinatorial Auctions with and without Samples
Representation Theorems for Actual Powers over Two-Agent General Concurrent Game Frames
Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking
Improving the Bounds on Approximating Weighted Maximin Share for Chores
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.