CS Paper Radar

Rival-Injective Allocations: Support-List Structure and Maximum-Anchor EFX$_0$ Certificates

Junshuo Wang

cs.GT ·submitted 2026-08-31 03:33 UTC · v1
hot direction

Abstract

We study complete allocations under nonnegative additive valuations through the positive supports of goods, focusing on the all-good form of envy-freeness up to any good (EFX$_0$). We define rival-injective (RI) endpoint ownership: every good with nonempty positive support is assigned to an agent who values it positively, and every ordered observer--owner pair is used by at most one good. RI ownership is exactly proper list coloring of the graph joining goods whose positive supports overlap in at least two agents. For pair-supported goods with arbitrary exceptional goods, fixing the exceptional owners yields a necessary-and-sufficient pair-capacity criterion and an exact finite-domain owner constraint satisfaction problem (CSP). Every RI allocation in which each agent's own bundle is worth at least her maximum-valued singleton is all-good EFX$_0$. A specified injective choice of maximum-singleton anchors, together with residual support-list degeneracy, constructs such an allocation by reverse greedy coloring in $O(nm^2)$ time. We give two explicit witness families: a nonempty relatively open, 22-dimensional cone on a fixed $4\times10$ support face, and a family for every $n\ge4$ with two universal-support goods and $m=(n-1)(n-2)+2$ goods. Both fail unanchored list degeneracy and are not implied by the explicit pure-multigraph or published high-girth/controlled-multiplicity hypotheses compared here. We also study recognition of the maximum-anchor certificate class, leaving its general complexity unresolved. The exact list-coloring and pair-capacity results concern RI ownership, not general EFX$_0$ existence; unrestricted four-agent, ten-good all-good EFX$_0$ remains unresolved.

Comment
18 pages, no figures. Includes a statement on human direction, AI contributions, verification, and author responsibility

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

Computing EF1 Allocations under Budget Constraints in Polynomial Time

cs.GT cs.DS ·2026-11-09 ·Tingwei Hu, Lili Mei, Guochuan Zhang
similarity 0.74
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

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

Simultaneous Envy and Equitability Guarantees

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

Envy-Free Allocation of Indivisible Goods under Leontief Preferences

cs.GT cs.CC ·2026-09-23 ·Tanmay Inamdar, Pallavi Jain, Pranjal Pandey
theory similarity 0.72
Abstract

Envy-freeness is a fundamental notion of fairness in the allocation of indivisible goods. In this paper, we study envy-free allocation under Leontief preferences, which model perfect complements. Although Leontief preferences have been extensively studied in the context of allocating divisible goods and market equilibria, they have received comparatively little attention for the allocation of indivisible goods. We show that, unlike additive valuations in cardinal preferences, an envy-free allocation always exists for Leontief preferences when there are at least two goods. In contrast, envy-free allocations may fail to exist when there is a single good, however it can be decided in polynomial time. We next study the problem of computing a welfare-maximizing envy-free allocation. We prove that this problem is NP-hard in general, whereas it is polynomial-time solvable when there is only a single good or agents have identical demands. Finally, we investigate the parameterized complexity of this problem.

0.03

Envy-Free Chore Allocation with Unit Subsidies under Negative Dichotomous Valuations

cs.GT ·2026-09-13 ·Mainak Sarkar, Soumyarup Sadhukhan
theory similarity 0.71
Abstract · Revised version: Added a unit-subsidy guarantee for objective mixed instances with signed binary marginals, along with additional results on…

We study the allocation of indivisible chores with subsidies under negative dichotomous valuations, where the marginal disutility of every chore is either zero or one. This is the chore analogue of the dichotomous goods model of Barman et al. (2022), for which a subsidy of at most one unit per agent is known to suffice for envy-freeness. Our main contribution is to show that the same optimal guarantee holds for chores under no structural assumption beyond binary marginals. For every instance with negative dichotomous valuations, there exists a complete allocation $\mathcal{A}$ and a subsidy vector $p\in\{0,1\}^n$ with $\sum_{i\in N} p_i\le n-1$ such that $(\mathcal{A},p)$ is envy-free. Moreover, $\mathcal{A}$ is EF1 even before subsidies are paid. The subsidy bound is tight, and both the allocation and the subsidies can be computed in polynomial time in the value-oracle model. Unlike in the corresponding goods setting, a natural incremental extension approach does not work for chores. Our proof instead exploits key properties of an envy-free partial allocation and its associated equality graph to complete the allocation and determine which agents require subsidies. As a further extension of the main theorem, we establish the same optimal unit-subsidy guarantee for objective mixed instances with signed binary marginals, where every item is a good for all agents or a chore for all agents; these valuations need not be additive. The key step is to prove that the goods-side extension argument of Barman et al.~\cite{BKNS22} remains valid even when the previously allocated bundles contain chores. Finally, even for negative dichotomous chore valuations, we show that the unit-subsidy guarantee cannot, in general, be maintained if Pareto optimality is also required.

0.14

Fair Division Under Boolean Valuations: Beyond Normalization

cs.GT ·2026-08-30 ·Nisarg Shah, Paritosh Verma
similarity 0.70
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

Tight Maximin Share Guarantees of EFX and PMMS

cs.GT ·2026-08-31 ·Qinghua Qin
benchmarktheory similarity 0.70
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