Triangle Partition → Ternary symmetric justified envy-free triples Complexity open
Unsolved
Why this question matters
This isolates existence complexity in a small-valued symmetric coalition model.
Results for asymmetric preferences, larger utility alphabets or stronger stability notions do not classify the stated ternary symmetric justified-envy predicate.
The reduction to construct
The source gives a simple graph. Its outputs are partitions of its vertices into triples each inducing a triangle, or NO-SOLUTION.
The target has symmetric pair values in {0,1,2} and asks for a partition into triples with no justified envy. An agent envies replacing another when its utility improves and both remaining members strictly prefer the incoming agent.
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.
Every unintended triple must be excluded under the exact justified-envy condition, rather than a stronger stability notion.
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.