CS Paper Radar

To EFX OR to MMS, That is the Question

Hadi Hosseini, Payas Khurana, Shraddha Pathak, Rohit Vaish

cs.GT ·submitted 2026-08-11 02:45 UTC · v2
theory

Abstract

We study the agent-wise disjunction of two central fairness notions for indivisible items, where every agent must be either envy-free up to any item (EFX) or maximin-share (MMS) satisfied. One might expect that having a flexible fairness requirement for individual agents will restore existence, especially because the existence of EFX itself resisted resolution for nearly a decade. Surprisingly, it does not. We construct counterexamples with three agents and eight submodular goods, and with three agents and seven submodular chores, significantly strengthening recent EFX impossibility results. On the positive side, we prove existence for additive mixed items with at most three valuation types when one type is a singleton. Additionally, we obtain polynomial-time approximation schemes for additive goods-only and chores-only instances. We also identify a clean separation between the disjunction and its constituents: For additive chores with two valuation types, EFX and MMS are both known to fail, whereas an EFX $\vee$ MMS allocation always exists. Finally, we show that identical additive valuations even admit the conjunction EFX $\wedge$ MMS for mixed items. Overall, our results show that allowing flexibility in choosing agent-specific fairness certificates expands the frontier of fair solutions while also uncovering surprising impossibilities.

Closest papers

Nearest neighbours by meaning across the whole index.

Fair Allocation with Optional Selling

cs.GT econ.TH ·2026-08-25 ·Uriel Feige, Yotam Gafni
similarity 0.84
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

Simultaneous Envy and Equitability Guarantees

cs.GT cs.AIecon.TH ·2026-08-26 ·Hadi Hosseini, Shraddha Pathak, Lirong Xia, Chengkai Zhang
similarity 0.83
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.23

Best-of-Both-Worlds Fair Division via Subsidies

cs.GT ·2026-10-10 ·Surya Panchapakesan, Rohit Vaish
theory similarity 0.82
Abstract · 16 pages in main body, 1 page appendix

We study the relationship between fair division with $\textit{subsidies}$ and $\textit{best-of-both-worlds}$ (BoBW) fairness for indivisible items. We prove a general reduction of BoBW existence to envy-freeability. Specifically, for any scale-free ex-post property $P$ (e.g., EF1, EFX, PO) and any scale-free valuation class $\mathcal{V}$ (e.g, additive, submodular, subadditive, monotone), if every instance in $\mathcal{V}$ admits a $P$-allocation that can be made envy-free using subsidies, then every such instance admits an ex-ante envy-free lottery supported on $P$-allocations. The proof uses linear programming duality. As applications, the reduction gives alternative proofs of BoBW existence results for additive goods, chores, and mixtures of goods and chores. The converse of our general reduction holds for two agents but fails for three: We provide a four-good counterexample with monotone submodular valuations where an ex-ante envy-free and ex-post EF1 lottery exists, but no allocation is simultaneously EF1 and envy-freeable. For lexicographic valuations, we prove simultaneous EFX, Pareto optimality, and envy-freeability (and hence BoBW guarantees for EFX+PO) for three agents, and show that even EFX and envy-freeability can be incompatible for four agents.

0.16

Resolving Envy by Adding Goods with Bounded Supply: A Type-Count Dichotomy and Two-Agent Hardness

cs.GT cs.DS ·2026-08-10 ·Chuang-Chieh Lin, Guillaume Fertin, Po-An Chen, Stéphane Vialette, Géraldine Jean +2 more
theory similarity 0.81
Abstract

We study envy elimination by adding goods (EEAG) when the additional pool has bounded supply and no separate budget bound. We establish a sharp type-count dichotomy for binary additive valuations. With one additional item type, EEAG is polynomial-time solvable for any number of agents. More generally, our algorithm permits arbitrary nonnegative integer per-copy values. The envy constraints form a system of difference constraints, and Bellman--Ford returns the componentwise least feasible extension. In contrast, with exactly two additional item types, EEAG is \textsf{NP}-complete even when both types have positive finite supply and the approvers of one type form a subset of the approvers of the other. This closes the two-type case left open by Bentert et al. Separately, we prove weak \textsf{NP}-completeness even for two agents with identical additive valuations, one initially endowed good, and a growing number of unit-supply item types. Thus, bounded-supply hardness appears both with two item-types and many agents and with two agents and many item-types.

0.04

Non-Existence of PMMS Allocations and a $4/3$-PMMS Guarantee for Additive Chores

cs.GT ·2026-09-09 ·Xiaohui Bei, Zehan Lin, Shengxin Liu, Rong Luan, Biaoshuai Tao
theory similarity 0.81
Abstract · 23 pages, no figure

We study pairwise maximin share (PMMS) fairness for indivisible items with additive preferences. We give a polynomial-time reduction from chores to goods that preserves the existence of a PMMS allocation. Together with known nonexistence results for chores, this yields nonexistence for additive goods. In addition, we show that deciding if a given instance admits a PMMS allocation is NP-hard. We also give explicit instances whose PMMS factors are $226/227$ for goods and $1.102065$ for chores, certified by exact enumeration. Complementing these impossibility results, we prove that every additive-chore instance admits a $4/3$-PMMS allocation.

0.38

Balanced Fair Division for Three Agents under General Valuations and Laminar Constraints

cs.GT ·2026-08-10 ·Max Dupré la Tour
theory similarity 0.80
Abstract

We study fair allocations of indivisible items under general set valuations. We prove that every instance with three agents and arbitrary real-valued valuations admits a balanced allocation that is envy-free up to one good and one chore (EF$1^c_g$). This directly implies balanced EF$1$ when each valuation is either monotone nondecreasing or monotone nonincreasing. We also show that balanced EF$1$ cannot be guaranteed without monotonicity: there exists an instance with three agents, nine items, and identical nonmonotone valuations that admits no balanced EF$1$ allocation. We then consider a common laminar matroid constraint. Whenever a complete feasible allocation exists, we prove that there is a complete feasible allocation that is balanced and envy-free up to two goods and two chores (EF$2^c_g$) for arbitrary valuations. The allocation can additionally be chosen so that the numbers of items from every laminar set assigned to the three agents differ by at most two. Most proofs in this paper were obtained using GPT-5.6. We subsequently verified the proofs for correctness and refined their exposition and arguments, also with the aid of GPT-5.6.

0.04

Computing EF1 Allocations under Budget Constraints in Polynomial Time

cs.GT cs.DS ·2026-11-09 ·Tingwei Hu, Lili Mei, Guochuan Zhang
similarity 0.80
Abstract

We study the fair allocation of indivisible items to agents with budget constraints and additive valuations. Each agent compares its own bundle with the subsets of another bundle that fit its budget. An allocation is envy-free up to one item (EF1) if, for every agent and every nonempty subset under comparison, removing an item of maximum value to that agent eliminates its envy. We require EF1 both between agents and towards the charity, which contains all unallocated items. EF1 allocations exist, but computing them in polynomial time has remained open even for homogeneous valuations. We resolve this problem with a polynomial-time algorithm for EF1 allocations under heterogeneous valuations. We also prove that detecting an EF1 violation is NP-complete. Equivalently, checking whether a given allocation is EF1 is coNP-complete. Finally, we give polynomial-time algorithms for envy-freeness up to any item (EFX) both when each agent's valuation is proportional to item size and when each agent has a fixed number of distinct positive item values. As an application, for homogeneous valuations and any $\varepsilon>0$, we obtain an EF1 allocation with at least a $(1/2-\varepsilon)$ fraction of the maximum social welfare in time polynomial in the input length and $1/\varepsilon$.

0.04

Tight Maximin Share Guarantees of EFX and PMMS

cs.GT ·2026-08-31 ·Qinghua Qin
benchmarktheory similarity 0.80
Abstract

In the fair division of indivisible goods among autonomous agents, allocations frequently satisfy strong pairwise fairness criteria while failing to guarantee an agent's full maximin share. Maximin share (MMS) is a global benchmark: the value an agent can guarantee by partitioning all goods into $n$ bundles and receiving her least preferred bundle. In contrast, local pairwise fairness notions---most notably envy-freeness up to any good (EFX) and pairwise maximin share (PMMS)---evaluate fairness through bilateral bundle comparisons. We resolve the open question of determining the optimal universal MMS approximation factor guaranteed by either local notion under nonnegative additive valuations, proving that both factors equal exactly $10/17$. For the lower bound, we show that both EFX and PMMS imply a common local residual inequality: the value of any foreign bundle after removing its least valuable item cannot exceed the focal agent's allocated value. We design a continuous piecewise weight function that converts this local constraint into the global $10/17$ MMS guarantee. The same charging argument establishes that $α$-EFX implies $(10α/17)$-MMS. For tightness, we construct an explicit family of complete allocations that simultaneously satisfy PMMS and EFX$_0$, including comparisons involving zero-valued goods, and whose MMS ratios converge to $10/17$. For each fixed number of agents, we also establish exact reciprocal identities connecting fair division to scheduling: the EFX guarantee is the reciprocal of the pure price of anarchy in selfish identical-machine covering, while the PMMS guarantee is the reciprocal of a locality gap for exact repartition of two machines.

0.38