0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 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$
    – Doc Stories
    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

0

Reset to default

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.