Given $n$ agents, and $m$ items where $v_i(g) \geq 0$ is the value of item $g$ for agent $i$, does there always exist a partition $A_1, ..., A_n$ of the $m$ items into $n$ sets s.t. for all $i, j \in \{1, ..., n\}$: $$ \sum_{g \in A_i} v_i(g) \geq \left(\sum_{g \in A_j} v_i(g)\right) - \left(\min_{g \in A_j} v_i(g)\right) $$ Where if $A_j$ is empty, the min is taken as $0$. In essence this is a fairness property where we allocate all the items to the agents s.t. every agent believes his bundle is worth at least as much as every other player's bundle when removing his least valued item. I want to know whether this always exists.

Extensive computer simulations have yet to yield a counterexample.

  • $\begingroup$ This is at least true if all agents evaluate the items equally, i.e. if $v_i(g) = v_j(g)$ for every $g$ and every $i, j$. Sort the items according to their values, and distribute them to the agents in descending value order. Always distribute an item to the agent who currently has lowest total value. The required property is then satisfied during the whole distribution procedure. $\endgroup$ – WhatsUp Aug 14 '16 at 6:17
  • $\begingroup$ Right, so actually by doing something similar, we can solve the case where agents believe the items have the same ranking in terms of value. Other doable special cases include when $n = 2$, or when $m \leq n + 1$. $\endgroup$ – Daishisan Aug 14 '16 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.