OpenAlex ·
On best of both worlds allocations with subadditive valuations
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.33588
- Original
- Read it at the publisher
- Topics
Abstract
We consider allocation of indivisible goods to agents with equal entitlements and subadditive valuations. As an ex-post fairness notion we consider the maximin share (MMS), and as an ex-ante fairness notion we consider the maximum expectation share (MES), which is always at least as large as the MMS, and sometimes much larger. We present a simple transformation that for every $0 < ρ\le 1$, given any algorithm that produces $ρ$-MMS allocations, transforms it into a randomized allocation algorithm that offers $ρ$-MMS ex-post simultaneously with $η$-MES ex-ante. We prove several new properties of MES, and use them to show that $η\ge \min[\fracρ{2 + ρ}, \frac{1}{4}]$. We also present cases in which the transformation results in a higher value of $η$. Applying our transformation to currently known allocation algorithms shows for subadditive valuations the existence of randomized allocations that are simultaneously $Ω(\frac{1}{\log\log n})$-MES ex-ante and $Ω(\frac{1}{\log\log n})$-MMS ex-post, and for XOS valuations the existence of randomized allocations that are simultaneously $\frac{4}{27}$-MES ex-ante and $\frac{4}{17}$-MMS ex-post.
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 Computational Complexity
The Complexity of Nash Equilibrium in Network Congestion and Coordination Games
AI-based matching improves refugee employment in a double-blind randomized trial
Representation Risk in Pretrained Image Encoders
PriceBench: A Diagnostic Benchmark for Price, Quality, and Brand Preferences in LLM Booking Agents
Fluctuations and multifractality in stochastic models of interface growth and population dynamics
Get the few papers worth your time in Computational Complexity 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.