CS Paper Radar

Non-Existence of EFX Chore Allocations for Monotone Cost Functions with Binary Marginals

Zehan Lin, Shengxin Liu, Biaoshuai Tao, Shengwei Zhou

cs.GT ·submitted 2026-08-11 07:00 UTC · v1

Abstract

We study the existence of envy-free up to any item (EFX) allocations of indivisible chores when agents have monotone cost functions with binary marginals. For indivisible goods, the corresponding existence question is known to have an affirmative answer for general monotone functions with binary marginals. For chores, however, the existence of EFX allocation was previously known only for more restricted classes, while the general binary-marginal case remained unresolved. In this paper, we provide two counterexamples based on the same 18-agent, 53-chore word gadget, with one cost profile for binary XOS costs and another for binary supermodular costs. In both cases, a complete EFX allocation need not exist. Finally, we formalize and verify our main results in Lean 4.

Closest papers

Nearest neighbours by meaning across the whole index.

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.75
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

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

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

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

Simultaneous Envy and Equitability Guarantees

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

On the Incompatibility of Weighted PROPX and Pareto Optimality for Indivisible Chores

cs.GT ·2026-08-17 ·Haris Aziz, Bo Li
theory similarity 0.73
Abstract

Proportionality (PROP) is one of the simplest fairness criteria for allocating items among agents with additive preferences. With indivisible chores, however, PROP is not always satisfiable. We study proportionality up to any item (PROPX), which requires every agent to satisfy proportionality after any chore is removed from her bundle. Under strictly positive costs, we settle the weighted compatibility question negatively: weighted PROPX and Pareto optimality are incompatible already for two agents and four chores. Moreover, for every $n\geq3$, we give an $n$-agent, $(n+1)$-chore counterexample whose shares can be arbitrarily close to equal. These counterexamples are item-minimal: under strictly positive costs, weighted PROPX and Pareto optimality are always compatible when the number of chores is at most the number of agents, and they are compatible for two agents with at most three chores. Our impossibility result contrasts with the compatibility theorem of Mahara (2026) for weighted envy-freeness up to one item (EF1) and Pareto optimality .

0.04

Best-of-Both-Worlds Fair Division via Subsidies

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

Closing Gaps in Temporal Fair Division for Chores

cs.GT ·2026-11-19 ·Nicholas Teh
similarity 0.72
Abstract

We study the fair division of indivisible chores that must be assigned in a prescribed order. The complete instance is known in advance, but assignments cannot be changed. Temporal envy-freeness up to one chore (TEF1) requires envy-freeness up to one chore after every arrival. For goods, TEF1 allocations need not exist, and deciding whether one exists is NP-hard. For chores, Elkind et al. (AAMAS 2025) showed that TEF1 allocations exist for two agents, but left open whether they always exist, conjecturing that they do not, and whether deciding their existence is hard. We resolve both questions, confirming the conjecture in a strong form: for every $n\ge3$ and every finite factor, some $n$-agent instance admits no allocation satisfying TEF1 even up to that factor. This holds even when all agents have the same multiset of individual chore costs, with nine chores sufficing for three agents. Deciding TEF1 existence is NP-complete for every fixed $n\ge3$, even when all costs lie within a factor $1+2^{-m}$ of one another, where $m$ is the number of chores. Instances without TEF1 allocations exist arbitrarily close to the uniform cost matrix with $O(n\log n)$ chores, and just nineteen for three agents. We then relate fairness to social cost. Even when a TEF1 allocation is supplied, minimizing social cost subject to TEF1 admits no polynomial-time approximation within any factor polynomial in the number of chores unless P$=$NP, already for three agents with strictly positive normalized costs. In contrast, for every fixed number of agents, we give an FPTAS for the optimal temporal EF1 factor, the smallest factor up to which TEF1 can be satisfied, whose output has social cost no larger than that of the cheapest allocation attaining this factor. Thus a slight relaxation of fairness permits a social-cost guarantee that, unless P$=$NP, no polynomial-time algorithm can provide under exact TEF1.

0.27

Connected EF1 Allocations Exist in Discrete Chore Cutting

cs.GT ·2026-09-26 ·Ankang Sun, Bo Li
top venuetheory similarity 0.72
Abstract · Full version of the paper appeared in IJCAI-ECAI 2026

In this paper, we prove the existence of an envy-free up to one item (EF1) division for a discrete chore. Our approach builds on the powerful framework of Simmons-Su, which leverages Sperner's lemma to guarantee the existence of a simplex corresponding to a sequence of similar fractional divisions, ensuring that each agent is satisfied with a different bundle. Bilò et al. [2022] introduced a rounding technique that converts the fractional divisions into a connected integral EF1 division for goods when there are at most four agents, and this method was later extended by Igarashi [2023] to accommodate any number of agents. However, these rounding techniques for goods do not directly apply to chores because the definitions of EF1 differ in the two settings. To overcome this asymmetry, we modify the existing rounding techniques and show that connected EF1 divisions exist for a discrete chore.

0.46