CS Paper Radar

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

Zehan Lin, Shengxin Liu, Biaoshuai Tao, Shengwei Zhou

cs.GT ·submitted 2026-09-02 15:33 UTC · v1
hot direction

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Best-of-Both-Worlds Fairness and Pareto Optimality

cs.GT ·2026-08-10 ·Haris Aziz
similarity 0.86
Abstract

We consider fair allocation of indivisible items among agents with non-negative and additive valuations. The goal is to construct a lottery over deterministic allocations whose induced fractional allocation is envy-free, while every realised allocation is envy-free up to one item and Pareto optimal. We show that this is always possible for two agents. We then prove a stronger result that there always exists a lottery over deterministic allocations whose induced fractional allocation is envy-free, while every realised allocation is envy-free up each one item (EFX) and Pareto optimal. For non-negative integral additive valuations, such a lottery can be computed in pseudo-polynomial time. We also prove that for three agents and four items, there may be no ex-ante envy-free lottery that can be supported on allocations that are simultaneously EFX and Pareto optimal.

0.32

Weighted Fair Division of Indivisible Mixed Manna

cs.GT ·2026-09-01 ·Nicholas Teh
similarity 0.84
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

Best-of-Both-Worlds Fair Division via Subsidies

cs.GT ·2026-10-10 ·Surya Panchapakesan, Rohit Vaish
theory similarity 0.78
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

Simultaneous Envy and Equitability Guarantees

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

To EFX OR to MMS, That is the Question

cs.GT ·2026-08-11 ·Hadi Hosseini, Payas Khurana, Shraddha Pathak, Rohit Vaish
theory similarity 0.77
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.

0.32

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

cs.GT ·2026-09-28 ·Mengfan Ma, Biaoshuai Tao, Fangxiao Wang
similarity 0.76
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

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

cs.GT ·2026-08-10 ·Max Dupré la Tour
theory similarity 0.76
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

Revisiting EFX and fPO Allocations for Binary Chores

cs.GT ·2026-09-12 ·Zehan Lin, Xiaowei Wu, Shengwei Zhou
similarity 0.75
Abstract · 28 pages, no figure

We study fair and efficient allocations of indivisible chores under binary additive costs, with a focus on unequal entitlements and best-of-both-worlds guarantees. While binary valuations have been extensively studied for goods, their chore counterpart remains much less understood. A notable exception is due to Tao et al. (TCS 2025), who established that EFX and fPO are compatible for binary chores with equal entitlements. We revisit binary chores under unequal entitlements and establish the computation of allocations that satisfy WEFX and fPO. Our key technical contribution is a new lexicographic potential function tailored to chores: any allocation minimizing this potential ensures both WEFX and fPO. This potential further guides a polynomial-time local-search algorithm for computing allocations with such fairness and efficiency guarantees. For best-of-both-worlds guarantees, we show that unequal entitlements create a sharp obstruction: even with two agents and identical binary additive costs, no lottery can simultaneously satisfy ex-ante WEF and ex-post WEF1. In contrast, for equal entitlements, we construct in polynomial time a lottery that is ex-ante EF and fPO, while every realization is both EFX and fPO.

0.41