Incentives in Dominant Resource Fair Allocation Under Dynamic Demands

Every computer system performs resource allocation across system users. The defacto allocation policies used in most of these systems are max-min fairness for single resource settings and dominant resource fairness for multiple resources. These allocation schemes guarantee desirable properties like incentive compatibility, envy-freeness, and Pareto efficiency. Assuming that user demands are static (time-independent) the allocation is also fair. However, in modern real-world production systems, user demands are dynamic, that is, vary over time. As a result, there is now a fundamental mismatch between the resource allocation goals of computer systems and the properties enabled by classical resource allocation policies. This paper aims to bridge this mismatch. When demands are dynamic, instant-by-instant max-min fairness can be extremely unfair over a longer period of time, i.e., lead to unbalanced user allocations, as previous large allocations have no effect in the current time step. We consider a natural generalization of the classic algorithm for max-min fair allocation and dominant resource fairness for multiple resources when users have dynamic demands. This algorithm guarantees Pareto optimality while ensuring that resources allocated to users are as max-min fair as possible up to any time instant, given the allocation in previous periods. While this dynamic allocation scheme remains Pareto optimal and envy-free, unfortunately, it is not incentive compatible. We study the strength of the incentive to misreport; our results show that the possible increase in utility by misreporting demand is bounded and, since this misreporting can lead to a significant decrease in overall useful allocation, this suggests that it is not a useful strategy.