CS Paper Radar

Connected EF1 Allocations Exist in Discrete Chore Cutting

Ankang Sun, Bo Li

cs.GT ·submitted 2026-09-26 12:24 UTC · v1
top venuetheory

Abstract

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.

Comment
Full version of the paper appeared in IJCAI-ECAI 2026

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.GT ·2026-08-11 ·Zehan Lin, Shengxin Liu, Biaoshuai Tao, Shengwei Zhou
similarity 0.72
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.

0.42

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

Online Fair Division of Chores with Upgrade Recourse

cs.GT cs.AI ·2026-10-30 ·Yichen Huang, Nicholas Teh
similarity 0.69
Abstract

We study the online fair division of indivisible chores among $n$ agents under upgrade recourse, where earlier assignments may be revised but each chore previously assigned to an agent must be replaced by a distinct chore that she finds no more costly. We show that a simple adaptation of round robin maintains envy-freeness up to one chore (EF1) together with a $(2-1/n)$-approximation of the maximin share (MMS), and that no deterministic algorithm without predictions can do better, even when all agents rank the chores in the same order. This stands in contrast to the allocation of goods, where the optimal MMS factor vanishes as $n$ grows and cannot be achieved together with EF1. Moreover, knowing only the number of chores modulo a period of length $O(n)$ (and nothing about the costs) suffices to improve upon this factor at the final configuration, while the same algorithm retains a factor below $3$ even if this information is wrong. On the other hand, envy-freeness up to any chore (EFX) essentially requires the exact number of chores: uncertainty between two consecutive values already rules out every finite approximation, and even exact knowledge does not allow EFX to be combined with an MMS guarantee better than the trivial factor of $n$.

0.04

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

cs.GT ·2026-11-11 ·Hadi Hosseini, Shraddha Pathak
theory similarity 0.68
Abstract

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.

0.05

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

cs.GT ·2026-08-17 ·Haris Aziz, Bo Li
theory similarity 0.67
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

Closing Gaps in Temporal Fair Division for Chores

cs.GT ·2026-11-19 ·Nicholas Teh
similarity 0.67
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

Fair Division Under Boolean Valuations: Beyond Normalization

cs.GT ·2026-08-30 ·Nisarg Shah, Paritosh Verma
similarity 0.66
Abstract

We study fair division of indivisible items when agents have arbitrary two-level preferences: the value of each agent for any set of items is Boolean, which need not be monotone or additive. Notably, we do not impose the standard assumption of normalization, i.e., different agents may value the empty set at different Boolean levels. Since the preferences are nonmonotone, envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) each admit several variants, depending on which items are tested for removal and whether they are removed from the envious agent's bundle or the envied agent's bundle. This paper investigates the existence of these variants of EF1 and EFX, on their own and together with economic efficiency, incentive compatibility, feasibility constraints, and lottery-based randomization. Our results highlight that the existence landscape depends crucially on the number of normalized agents, who value the empty bundle at the lower Boolean level. The authors used significant assistance from GPT-5.6-Sol for deriving theoretical results, verified any AI-generated proofs for correctness, and expanded on the exposition and simplified arguments, with the aid of GPT-5.6-Sol and Claude Opus 5.

0.17

Fair Allocation with Optional Selling

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