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

1 Introduction

• All-good EFX existence is known in several restricted settings but remains open for general additive valuations with four or more agents.The paper's support-based results concern RI ownership and its certificate class, not general EFX0 existence.Source: §1 · p. 1
• Rival-injective endpoint ownership is equivalent to proper list coloring of the graph joining goods whose positive supports overlap in at least two agents.This makes support overlap an exact structural representation of RI ownership.Source: §1 · pp. 2–3
• For pair-supported goods with exceptional goods, fixing exceptional owners yields an exact completion test through three directed pair-capacity inequalities and an owner CSP.With two surviving candidates per exceptional good, the CSP has a 2-SAT special case.Source: §1 · pp. 2–3
• Specified injective maximum-singleton anchors and residual list degeneracy construct RI allocations with maximum-singleton dominance, which suffices for all-good EFX0.Given the anchors, verification and construction take O(nm^2) time.Source: §1 · pp. 2–3
• The paper studies recognition of maximum-anchor certificates, with polynomial fixed-n, XP-by-active-agents, and FPT-by-maximum-tie-surplus results, but leaves general recognition unresolved.A fixed anchor map is accepted exactly when its generalized residual core is empty.Source: §1 · p. 3
• The two witness families include a nonempty, relatively open 22-dimensional EFX0 cone on a fixed 4 × 10 support face and a family for every n ≥ 4.Both fail unanchored list degeneracy and are not implied by the explicit pure-multigraph and high-girth/controlled-multiplicity hypotheses examined in the paper.Source: §1 · p. 3
• The paper distinguishes its support-derived mechanisms from generic tools and cautions that failure of a prior sufficient hypothesis does not show all methods from that work fail on a family.The elementary RI–dominance implication organizes the construction rather than serving as an independent novelty claim.Source: §1 · p. 3

2 Model and two EFX notions

• With nonnegative additive valuations, a complete allocation partitions the goods among the agents.The formal model distinguishes positive-support goods from goods valued at zero by every agent.Source: §2 · pp. 3–4
• EFX+ tests deletion only of goods valued positively by the observer, whereas EFX0 tests deletion of every rival good, including zero-valued goods.Thus EFX0 is stronger on instances containing zero values; terminology in prior work varies, so the paper follows displayed definitions [10].Source: §2 · p. 4
• Comparisons with external hypergraph results must account for every admissible zero-endpoint padding, since positive support is minimal but may not be the only allowed representation.Excluding a sufficient hypothesis only shows that it does not directly imply the instance, not that another argument from the same work cannot apply.Source: §2 · p. 4

3 Rival injectivity and support-list coloring

• Every RI owner map extends to a complete EFX+ allocation, and support-list degeneracy is a polynomially recognizable sufficient condition for such an allocation.Repeatedly delete a good whose induced degree is below its support-list size, then color in reverse deletion order.Source: §3 · pp. 4–5
• RI ownership is equivalent to proper list coloring of the two-overlap conflict graph using each good’s positive support as its color list.Equivalently, for a fixed owner, the support traces after removing that owner are pairwise disjoint.Source: §3 · pp. 4–5

Pair capacities

• For each unordered pair, fixed exceptional owners permit an RI completion exactly when Lij ≤ 1, Lji ≤ 1, and µij + Lij + Lji ≤ 2.Different unordered pairs use disjoint ordered resources, so their completions are independent.Source: §4 · p. 6

Exceptional-owner CSP

• The exceptional-owner CSP is exact: choose one candidate per exceptional good, subject to the stated at-most-one constraints on forbidden pair resources.Candidates touching a pair of multiplicity two are removed first.Source: §4 · p. 6

Algorithmic consequences

• When each exceptional good has at most two candidates, RI feasibility is decidable in polynomial time by 2-SAT.The encoding uses exactly-one clauses for candidate choices and negative binary clauses for forbidden pairs.Source: §4 · p. 6
• With t exceptional goods having more than two candidates, enumerating their owners and solving the residual 2-SAT instances is polynomial for fixed t, but gives an XP bound.The number of 2-SAT calls is the product of the candidate-set sizes for those wide exceptions.Source: §4 · p. 6

RI–dominance bridge

• An RI endpoint owner map yields EFX0 when the resulting complete allocation has maximum-singleton dominance.RI limits each observer to at most one positively valued good in another agent’s bundle; zero-support goods can be restored arbitrarily.Source: §5 · p. 7

Maximum-anchor certificate

• A-LD requires every nonempty residual vertex set to contain a good whose induced degree is strictly below its residual-list size.The quantified condition makes the certificate independent of any preselected peeling order.Source: §5 · p. 7
• A specified injective maximum-anchor map satisfying A-LD yields an RI allocation with maximum-singleton dominance, hence EFX0, in O(nm^2) time.Given the anchors, the certificate is verified and the allocation constructed within that bound.Source: §5 · p. 8

Scope

• These are sufficient certificate layers: A-LD need not extend every maximum matching, and the paper does not guarantee polynomial-time discovery of a successful anchor map.RI, maximum anchors, and A-LD are each sufficient but not necessary for the corresponding broader property.Source: §5 · p. 8

Fixed-anchor recognition

• For fixed anchors, A-LD holds exactly when the order-independent residual core K(h) is empty.The core is the unique maximum residual set satisfying the stated lower-degree bounds.Source: §6 · p. 9

Complexity bounds

• Recognition and search take O(ma poly(|I|)) and O(2^p poly(|I|)) time, respectively, giving XP in active agents and FPT in tie surplus p.The input uses supports and maximum-good sets; the bounds are polynomial for every fixed number of agents.Source: §6 · pp. 8–9

Special cases

• With at most two active agents, a certificate exists exactly when a saturating maximum-good matching exists and, for two agents, at most two goods have universal support.For zero or one active agent, existence of the required top choice is sufficient.Source: §6 · p. 9

Sufficient subclass

• If the full support instance is list-degenerate and color-safe top edges have a matching saturating the active agents, that matching is a maximum-anchor A-LD certificate.Color safety preserves every supported residual color, so the original list-degeneracy condition applies.Source: §6 · p. 10

Limitations

• A top-good matching alone may fail A-LD: the example leaves adjacent residual goods with identical singleton lists despite unanchored list degeneracy.The general recognition problem is in NP, but the paper does not determine whether it is polynomial-time solvable or NP-hard.Source: §6 · p. 10

Support construction

• The fixed support face has ten goods, including two support-three goods and pair-supported goods on the stated supports.The pair multiplicities leave Cx = {1} and Cy = {2}; one RI owner map uses each of the twelve ordered observer–owner resources exactly once.Source: §7 · p. 10

The M-cone

• Every valuation in the cone has a complete EFX0 allocation, and the cone is nonempty and full-dimensional relative to the 22-dimensional support face.Assigning value 4 to each anchor coordinate and 1 to every other positive coordinate gives an interior point.Source: §7 · pp. 10–11

Anchor certificate

• The construction uses anchors h1 = x, h2 = y, h3 = b23, and h4 = b14; its residual conflict graph has only the edge a34b34, so A-LD holds.Theorem 5.4 then gives EFX0.Source: §7 · p. 11

Comparison scope

• The witness is not a pure multigraph and fails unanchored support-list degeneracy; it also fails the compared explicit high-girth/controlled-multiplicity predicate.These are separations from displayed sufficient hypotheses, not from every known EFX class.Source: §7 · pp. 10–11

Construction

• For n ≥4, the family has m=(n−1)(n−2)+2 goods, including two universal-support goods and two goods on each internal pair among agents 3,…,n.It also has one {1,i} good and one {2,i} good for each i≥3, and no {1,2} pair good.Source: §8 · p. 11

Theorem 8.1: XOR ownership and saturated RI

• Either universal-owner choice, (1, 2) or (2, 1), extends to an RI owner map using every ordered observer–owner resource exactly once.The surviving owner sets for both universal goods are {1, 2}.Source: §8 · p. 12
• Doubled internal pairs prune every candidate owner k ≥3 for either universal good, while the universal goods cannot share an owner without duplicating resources.The construction completes either surviving owner choice by assigning cross-pair goods to their third agent and splitting doubled internal pairs between their two agents.Source: §8 · p. 12

Theorem 8.2: Relative-open EFX0 cone

• For strict rowwise maximum anchors, the construction gives a nonempty relatively open EFX0 cone of dimension 2n^2−4n+4.Residual lists are singletons for p2i and isolated two-agent edges for doubled internal pairs, so A-LD holds.Source: §8 · p. 12

Structural properties

• The family has two high-degree overlap hubs but only Θ(m) conflict edges, and its full vertex set fails unanchored list degeneracy.It is incidence-2-connected and not a pure multigraph; U4 has eight goods, so it is not the four-agent, ten-good separator.Source: §8 · p. 12

General additive and valuation-restricted results

• Complete all-good EFX is known for three additive agents and for four additive agents with at most nine goods, as well as under several valuation restrictions.The listed restrictions include common rankings, personalized bivalued rows, at most three valuation types, and at most two item types.Source: §9 · pp. 12–13

Graphs and multigraphs

• For additive pure-pair instances, arbitrary-multigraph results already imply existence; the paper’s RI capacity and CSP results instead characterize a stricter completion certificate after exceptional owners are fixed.Support-derived machinery is aimed at incorporating genuine high-support goods.Source: §9 · p. 13

Orientations and parameterized complexity

• EFX orientation results and the paper’s fixed-anchor recognition problem address different tasks, despite neighboring graph and algorithmic tools.The binary symmetric orientation method’s two-state encoding and core are not the exceptional-good owner CSP or fixed-anchor threshold core.Source: §9 · p. 13

Hypergraphs and separation

• The displayed witness families fail the explicit high-girth/controlled-multiplicity hypotheses, but that separation does not place them outside every known EFX class.The comparison uses an all-padding convention because the compared models may include endpoints valuing a good at zero.Source: §9 · p. 13

Sparse-bundle reasoning

• The local one-visible-good plus dominance motif also appears in prior EFX proofs, so the paper treats its RI–dominance step as an expository bridge rather than an independent novelty claim.The cited high-girth construction derives sparsity differently, and EFL’s sparse-bundle condition is not equivalent to RI.Source: §9 · pp. 13–14

Favorite goods, coloring, and terminology

• The paper’s maximum-anchor condition plus residual support-list degeneracy differs from prior favorite-good and favorite-tier conditions.Its graph is derived from support overlap, and proper list colorings correspond to RI owner maps.Source: §9 · p. 14

Certificate boundaries

• RI is sufficient but not necessary for EFX+ or EFX0, and maximum-singleton dominance and maximum anchors are likewise sufficient steps rather than necessary conditions.A-LD is one sufficient way to extend an anchor precoloring, not a necessary condition.Source: §10 · p. 14
• The exact capacity CSP characterizes RI completion, not general EFX0 existence.Source: §10 · p. 14

Recognition complexity

• The general complexity of finding a maximum-anchor map satisfying A-LD remains unresolved.The paper does not determine whether recognition is polynomial-time solvable or NP-hard; it notes membership in NP.Source: §10 · p. 14

Witness scope

• The M-cone is full-dimensional only within its fixed 22-dimensional support face, not in the ambient 40-dimensional valuation space.Source: §10 · p. 14
• The family U_n has two high-support goods and Θ(m), rather than Θ(m^2), conflict edges.Source: §10 · p. 14

Open existence questions

• The paper does not solve unrestricted 4×10, unrestricted four-agent all-good EFX0, or general additive all-good EFX0.The general additive existence question remains open for four or more agents.Source: §10 · p. 14

Literature boundary

• The literature search cannot establish absolute priority, and forward-citation evidence for recent orientation work remains incomplete.Source: §10 · p. 14

Open problems

• Next steps include classifying recognition complexity, finding wider precoloring-extension conditions, and constructing families with more high-support goods as n grows.Source: §10 · p. 15

Conclusion

• Support-derived RI ownership is exactly represented by list coloring, while pair-capacity completion and owner CSP make exceptional-good choices explicit.Source: §11 · p. 15
• Maximum-anchor A-LD certificates construct RI allocations with the dominance needed for all-good EFX0, separating the fairness check from the construction.Source: §11 · p. 15
• The witness families show robustness beyond the compared pure-multigraph and high-girth/controlled-multiplicity hypotheses, but do not solve unrestricted EFX0.Source: §11 · p. 15

• The positive-support incidence graph is bipartite, with agents and positive-support goods as vertices and an edge when an agent belongs to a good’s support.Source: A Separation details · p. 15
• The Block–Hall predicate requires each nontrivial incidence-graph block to have a matching saturating all its good vertices.Source: A Separation details · p. 15
• The predicate is included only as a secondary benchmark for the two constructions, not as a frontier condition from the cited literature.Source: A Separation details · p. 15

A.1 The 4 × 10 support

• The 4 × 10 incidence graph is one 2-connected block, and its ten good vertices cannot be saturated by four agents, so the Block–Hall predicate fails.The construction also fails unanchored list degeneracy; zero-endpoint padding violates the cited multiplicity bound and repeats patches, excluding the simple-hypergraph branch.Source: §A.1 · p. 15

A.2 The universal family

• In the universal family, the incidence graph is 2-connected with more goods than agents, so its single block fails the Block–Hall saturation condition.The conflict graph fails unanchored list degeneracy, and padding forces all goods to share one patch, violating the cited multiplicity bound even if the underlying simple hypergraph has infinite girth.Source: §A.2 · pp. 15–16

B Finite verification and provenance

• Finite scripts check the 4 × 10 witness and allocations for n = 4, . . . , 8; the all-n claims rest on Theorems 8.1 and 8.2, not finite no-hits.The 4 × 10 checks include 262,144 zero-endpoint paddings.Source: B Finite verification and provenance · p. 16

Human direction, AI contribution, and responsibility

• The author selected the research direction, contribution package, standards, and final content, and retains responsibility for the manuscript.Source: Human direction, AI contribution, and… · p. 16
• AI workflows developed the structural route, proof drafts, checkers, searches, literature audits, and manuscript; their outputs were treated as candidate research material, not authority.Source: Human direction, AI contribution, and… · pp. 16–17
• Independent human domain-expert review was being sought for the pre-submission version and should not be inferred from agent reviews.Source: Human direction, AI contribution, and… · p. 17