2025/02/19 by Uriel Feige, Shengyuan Huang, Feige, Uriel +1 · 3 citations
Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #Economic theories and models #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2502.13541
openalex publication_date 2025/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider fair allocation of m indivisible items to n agents of equal entitlements, with submodular valuation functions. Previously, Seddighin and Seddighin [\em Artificial Intelligence 2024] proved the existence of allocations that offer each agent at least a (1)/(c log n loglog n) fraction of her maximin share (MMS), where c is some large constant (over 1000, in their work). We modify their algorithm and improve its analysis, improving the ratio to (1)/(14 log n). Some of our improvement stems from tighter analysis of concentration properties for the value of any subadditive valuation function v, when considering a set S' ⊆ S of items, where each item of S is included in S' independently at random (with possibly different probabilities). In particular, we prove that up to less than the value of one item, the median value of v(S'), denoted by M, is at least two-thirds of the expected value, M ≥ (2)/(3)\E[v(S')] - (11)/(12)maxe ∈ S v(e).