No-Envy and Egalitarian-Equivalence under Multi-Object-Demand for Heterogeneous Objects

We study the problem of allocating heterogeneous indivisible tasks in a multi-object-demand model (i.e., each agent can be assigned multiple objects) where monetary transfers are allowed. Agents. costs for performing tasks are their private information and depend on what other tasks they are obtained with. First, we show that when costs are unrestricted or superadditive, then there is no envy-free and egalitarian-equivalent mechanism that assigns the tasks efficiently. Then, we characterize the class of envy-free and egalitarian-equivalent Groves mechanisms when costs are subadditive. Finally, within this class, we identify the Pareto-dominant subclass under a bounded-deficit condition. We show that the mechanisms in this subclass are Pareto-undominated by any other Groves mechanism or neutral Weighted-Groves mechanism satisfying the same bounded-deficit condition.