Independent Set → Three-agent additive maximal EF1 allocation Complexity open
Unsolved
Why this question matters
This tests whether fairness remains algorithmically accessible when feasibility conflicts and maximality interact, even for three identical agents.
Existence of unconstrained EF1 allocations does not settle maximal partial allocation when every bundle must also satisfy a conflict graph.
The reduction to construct
The source gives a simple graph and an integer threshold. Its outputs are independent sets of at least that size, or NO-SOLUTION.
The target gives goods with a conflict graph and identical nonnegative rational additive values for three agents. Find three disjoint independent bundles forming an EF1 partial allocation that is maximal under adding any single unallocated good to any bundle.
Construct deterministic polynomial-time maps F and G: F sends every legal source instance to a legal target instance, and G(x,y) is a valid source output for every valid output y of F(x). Preserve the stated threshold, domain and promises. The requested complexity conclusion is NP-hardness for the stated target problem.
Maximality is local while EF1 is global. A reduction must handle empty bundles and all ways to leave goods unallocated.
What a complete answer must include
Give explicit construction and recovery algorithms, a general proof for every legal input and every valid target output, and polynomial runtime and encoding-size bounds. Specify finite output encodings and handle NO-SOLUTION outputs when applicable. Tests compare recovered source outputs with independent source solutions.
References
Literature checked 2026-09-16. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.