Reducing Untruthful Manipulation in Envy-Free Pareto Optimal Resource Allocation

Abstract

A natural requirement of a resource allocation system is to guarantee fairness to its participants. Fair allocation can be achieved either by distributed protocols known as cake-cutting algorithms or by centralized approaches, which first collect the agents' preferences and then decide on the allocation. Compared with cake-cutting algorithms, centralized approaches ageless restricted and can therefore achieve more favorable allocations. Our work uses as a starting point a recent centralized algorithm that achieves an envy-free (i.e., fair) and Pareto optimal (i.e., efficient) allocation of multiple divisible goods. In fair allocation algorithms, agents who do not follow the protocol cannot prevent other agents from being allocated a fair share, but in certain situations, agents can increase their own allocation by submitting untruthful preferences. A recent article has shown that the only mechanisms that do not allow such manipulations (i.e., the only incentive-compatible mechanisms) are dictatorial. Nevertheless, we present a method that reduces possible gains from untruthful manipulation. Our mechanism uses a heuristic to approximate optimal manipulations, and compensates agents who submitted suboptimal preferences by increasing their allocation. We empirically demonstrate that when our method is used, the additional benefit that agents can achieve by untruthful manipulation is insignificant, hence they have insignificant incentives to lie.