# Envy-Free Allocation is NP-Hard

If we consider the class fair division problem where we have a set of $$n$$-agents and a set $$M$$ of $$m$$-items, where each agent has a valuation function defined on the set of items $$v_i : 2^m \rightarrow \mathbb{R}$$

The problem is to find an allocation across the $$n$$ agents $$(A_1, ..., A_n)$$ such that no agent envies another: $$v_i(A_i) \ge v_i(A_j)$$ for any pair of agents $$i,j \in [n]$$.

Online, there are many instances that cite this problem is trivially NP-hard but I can't seem to find a concrete proof of this fact. How do we formally reduce from say the Set Partition problem to envy-free allocation?

• To show the hardness of this problem, you do not reduce envy-free allocation to Set Partition, but you reduce Set Partition to envy-free allocation.
– JimN
May 6 at 0:51
• @JimN right. So the idea is just to take a set of integers and treat them as the valuations for two agents on a set of items. Then, if I could find an envy-free allocation for the two agents I would have also solved SetPartition (since both sets have value of at least equal value)? May 6 at 1:14
• This is the correct idea and direction. To show envy-free allocation is hard, imagine that you have a solver for envy-free allocation and see what already-known hard problem could be solved with your hypothetical solver. I suggest you edit the original post to change your reduction statement's use of to to from . Whether your described reduction from Set Partition is correct or not, I can't determine that.
– JimN
May 6 at 2:27