The Price of Strategyproofness in Fair Multi-Resource Allocation for Cloud Computing

Abstract

We study fair and strategy-proof allocation of multiple divisible resources with Leontief utilities, motivated by cloud computing. The canonical mechanism, Dominant Resource Fairness (DRF), satisfies sharing incentive (SI), envy-freeness (EF), strategy-proofness (SP), and Pareto optimality (PO), but can be highly inefficient in terms of utilitarian social welfare. Under the classical approximation benchmark, no mechanism satisfying even one of SI, EF, and SP can improve on the trivial worst-case guarantee. We therefore adopt the recently introduced \emph{fair-ratio} benchmark, which compares a mechanism only with the welfare-maximizing allocation that itself satisfies SI and EF. For two resources, we first introduce Adaptive-Speed Fairness (ASF), a unified parametric framework that captures previous mechanisms as special or boundary cases. Every ASF mechanism satisfies SI, EF, and PO, and we derive a general sufficient condition that guarantees SP. Optimizing within this framework yields a strategy-proof mechanism with asymptotic fair-ratio $2/(2\sqrt{2}-1)\approx 1.094$, substantially improving the previous best guarantee $3-\sqrt{3}\approx1.268$. We complement this upper bound with a lower bound of $1.0789$ for all ASF mechanisms. To overcome this limitation, we introduce Corrected Resource Balancing (CRB), which uses the full resource-load structure together with a one-agent incentive correction. CRB satisfies SI, EF, SP, and PO and achieves fair-ratio at most $1+1/n$. Together with a general $1+\Omega(1/n)$ lower bound, this establishes the optimal asymptotic order $1+\Theta(1/n)$ for two resources. Finally, for every $m\ge3$, any deterministic mechanism satisfying SI and SP has fair-ratio exactly $m$. The same lower bound holds for randomized mechanisms satisfying ex-post SI and truthfulness in expectation.