arXiv:2611.15582 · v1

The Golden Ratio: EF1 and Ordinal-MMS for Additive Goods

首次提交 2026-11-11 23:04

版本更新 2026-11-11 23:04

雷达观测 2026-11-13 14:16

摘要

Every complete allocation that is envy-free up to one good (EF1) guarantees each of the $n$ agents her $1$-out-of-$(2n-1)$ maximin share. Can we construct allocations that satisfy EF1 together with stronger ordinal maximin share guarantees? For additive valuations, we prove that there always exists a complete allocation that is simultaneously EF1 and ($1$-out-of-$\lfloor\varphi n\rfloor$)-MMS, where $\varphi=(1+\sqrt{5})/2$ is the golden ratio. For bivalued valuations, where each agent may have her own two non-negative values for the goods, we obtain a complete allocation that is simultaneously envy-free up to any good (EFX) and ($1$-out-of-$\lceil(7n-1)/6\rceil$)-MMS.