CS Paper Radar

On best of both worlds allocations with subadditive valuations

Uriel Feige

cs.GT ·submitted 2026-09-27 14:04 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Fair Share Allocations for Almost All Agents

cs.GT ·2026-09-27 ·Tomer Ezra, Tamar Garbuz
similarity 0.79
Abstract

We study fair allocation of indivisible goods among agents with additive valuations. Our main result guarantees every agent her exact AnyPrice Share (APS) whenever the total entitlement is at most $1-\varepsilon$ and each individual entitlement is sufficiently small. For equal entitlements, this yields a $1$-out-of-$(n+O(\sqrt{n\log n}))$ maximin share (MMS) allocation. We also establish two best-of-both-worlds guarantees that preserve proportionality in expectation: each agent receives her full MMS with probability at least $1-O((\log n/n)^{1/3})$, or every agent receives her $1$-out-of-$(n+O(n^{2/3}(\log n)^{1/3}))$ MMS in every outcome. Both guarantees extend to sufficiently small unequal entitlements, with APS replacing MMS. Quantitatively, our deterministic result allows an entitlement cap of order $\varepsilon^2/\log(1/\varepsilon)$, while an impossibility construction shows that any universally sufficient cap must be $O(\varepsilon)$.

0.23

Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee

cs.GT ·2026-09-28 ·Mengfan Ma, Biaoshuai Tao, Fangxiao Wang
similarity 0.77
Abstract

We study the truthful and fair allocation of $m$ indivisible goods to $n$ strategic agents with additive valuations. Babaioff, Feige, and Manaker Morag (FOCS~2026) gave a randomized mechanism that uses only the agents' rankings of the goods, is truthful-in-expectation (TIE), and guarantees every agent $1/(H_{n-1}+2)=Θ(1/\log n)$ of her maximin share (MMS) in every realized allocation, where $H_{n-1}$ is the $(n-1)$th harmonic number; this is nearly the best possible with rankings alone. They conjectured that cardinal information allows TIE mechanisms to achieve a constant ex-post MMS guarantee. We confirm this conjecture: our TIE mechanism gives every agent at least $1/6$ of her truncated proportional share (TPS), and hence of her MMS, in every realized allocation. Moreover, the mechanism is ex-ante envy-free and can be implemented in polynomial time as an explicit lottery over at most $m(n-1)+1$ allocations.

0.04

Fair Allocation with Optional Selling

cs.GT econ.TH ·2026-08-25 ·Uriel Feige, Yotam Gafni
similarity 0.77
Abstract

We consider fair allocation of indivisible goods in a setting in which agents have subjective valuation functions over the set of goods, and in addition, goods may be sold at given market prices. In this setting, a fair allocation involves {deciding which goods to sell, how to allocate the unsold goods, and how to divide the money received from the sold goods.} We adapt to this setting the definitions of share-based fairness notions, such as the maximin share (MMS) and the truncated proportional share (TPS), and comparison-based fairness notions such as EF1 and EFX (which we adapt to SEF1 and SEFX). We show the following results when the utility of each agent is additive both over goods and over money. With two agents, there are allocations that are simultaneously MMS and SEFX. With three agents, there are instances in which no allocation gives every agent more than $\frac{11}{12}$-MMS. With any number of agents, there are $\frac{2}{3}$-MMS allocations. There also are allocations that are simultaneously SEFX and $\frac{n}{2n-1}$-TPS. This latter ratio is best possible, even without the SEFX requirement.

0.32

Weighted Fair Division of Indivisible Mixed Manna

cs.GT ·2026-09-01 ·Nicholas Teh
highly cited similarity 0.76
Abstract

We study weighted fair division of indivisible mixed manna under additive valuations. First, we resolve the general existence open question for weighted envy-freeness up to one item (WEF1), and show that every instance with arbitrary positive entitlements admits a complete WEF1 allocation computable in polynomial time. We then show that existence does not imply any welfare guarantee, i.e., the utilitarian price of WEF1 is infinite, even for two unweighted agents with normalized valuations, common item signs, and singleton values in a fixed four-value set; a welfare-maximizing WEF1 allocation in the construction is fractionally Pareto optimal. Second, suppose each agent $i$ has a number $a_i>0$ such that their valuation for any item is $-a_i$, $0$, or $a_i$. Then, for arbitrary entitlements, a weighted maximin share (WMMS) allocation always exists, is computable in polynomial time, and can be chosen to be fractionally Pareto optimal. An exact formula for each WMMS value leads to a polynomial-time flow algorithm. In this class, every WEF1 allocation satisfies a best possible additive WMMS guarantee whose loss depends on the agent's entitlement relative to the largest entitlement. Thus maximum entitlement agents receive exact WMMS and, under equal entitlements, every WEF1 allocation is also MMS-fair. Allowing a second positive magnitude can violate exact WMMS, while unrestricted entitlement ratios rule out any fixed multiplicative WMMS guarantee compatible with WEF1 for chores.

0.44

Almost Envy-Freeness for Additive Mixed Manna with Entitlements: Deterministic and Randomized Guarantees

cs.GT ·2026-09-02 ·Zehan Lin, Shengxin Liu, Biaoshuai Tao, Shengwei Zhou
hot direction similarity 0.75
Abstract

We investigate the fair allocation of indivisible items among agents with asymmetric entitlements in mixed manna settings, where the items consist of both goods and chores. For additive valuations, we establish that weighted envy-free up to one item (WEF1) allocations always exist and can be computed in polynomial time. We also study fair and efficient allocation and show that weighted envy-freeness up to one transfer (WEF1T) is compatible with fractional Pareto optimality (fPO) for every mixed-manna instance. This relaxation from WEF1 to WEF1T is tight, as demonstrated by our impossibility result. We further show a best-of-both-worlds result via a finite lottery that guarantees weighted envy-freeness (WEF) in expectation, with every realized allocation satisfying WEF1T and achieving the tight characterization complemented by the existing impossibility result.

0.42

Exact MMS Allocations under Personalized Bivalued Valuations: Goods and Chores

cs.GT cs.DS ·2026-08-16 ·Yuhao Zhang
benchmarktheory similarity 0.75
Abstract

The maximin share (MMS) is a central fairness benchmark for allocating indivisible goods and chores. We study additive valuations in the personalized bivalued setting, where each agent assigns one of two agent-specific values to every item. Whether exact MMS allocations always exist in this setting has remained a major open question, as highlighted by Ebadian, Peters, and Shah and by Garg, Huang, and Segal-Halevi. We answer this question affirmatively: we prove that exact MMS allocations always exist for both goods and chores and can be computed in polynomial time. Our proof combines a quota-based reformulation with an envelope relaxation, a sparse extreme-point construction, and flow-based rounding that controls the total rounding loss.

0.40

Maximin Share Allocations Beyond Weakly Lexicographic Valuations

cs.GT ·2026-09-12 ·Nicholas Teh
theory similarity 0.74
Abstract

We study the fair division of indivisible goods among agents with nonnegative additive valuations. An agent's maximin share (MMS) is the value she can guarantee by partitioning the goods into as many bundles as there are agents and receiving a least-valued bundle. We prove the existence of exact MMS allocations for a valuation domain that generalizes several few-valued domains as well as weakly lexicographic valuations. For each agent, the lower-valued goods, after a positive rescaling, may take values in $\{0,1,d,d+1\}$, $\{0,1,2,2e\}$, or $\{0,1,2,3,4\}$, where $d,e\ge 2$ are integers. Above these goods, the valuation may contain arbitrarily many value classes, subject to the condition that a single good in each class is worth at least the total value of all strictly lower-valued goods. The value classes, scaling factors, and parameters may vary across agents. We give an algorithm that computes an MMS allocation in $O(nm\log^2(2+m))$ time, where $n$ is the number of agents and $m$ is the number of goods.

0.34

Simultaneous Envy and Equitability Guarantees

cs.GT cs.AIecon.TH ·2026-08-26 ·Hadi Hosseini, Shraddha Pathak, Lirong Xia, Chengkai Zhang
similarity 0.74
Abstract · 43 pages

Recent work in fair division has focused on either simultaneously satisfying closely related fairness notions or achieving a single notion across the ex-ante and ex-post worlds. We study the compatibility of two fundamentally different fairness notions: envy-freeness and equitability. For indivisible goods-only and chores-only settings, we study the existence and complexity of simultaneously satisfying their relaxations, revealing sharp contrasts between the two settings. For normalized binary goods, we give a polynomial-time algorithm for computing an EF1+EQ1 allocation with at most seven agents, but also construct a normalized instance with a larger number of agents for which no such allocation exists. In sharp contrast, binary chores admit the stronger EFX+EQX guarantee for any number of agents, even without normalization. We further initiate the study of cross-notion ex-ante and ex-post guarantees, asking whether randomized allocations can provide ex-ante guarantees for one notion while preserving ex-post guarantees for another.

0.41