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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – JimN
    May 6 at 0:51
  • $\begingroup$ @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)? $\endgroup$ May 6 at 1:14
  • $\begingroup$ 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. $\endgroup$
    – JimN
    May 6 at 2:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.