Can the Max-Min Fair Allocation Be Trustful in a Centralized Resource System?

Resource allocation draws much attention from various areas and it is a hot topic to explore trustful allocation mechanisms. In this paper, we study the problem in a centralized resource system where a controller allocates appropriate resources to other nodes according to their demands. The max-min fair allocation enables fairness among the nodes and we explore whether the allocation is trustful when a node behaves strategically. We first introduce a simple but efficient algorithm to generate the max-min fair allocation, and then we analyze how the allocated resources vary when a new node is added to the system. To discuss about the trustfulness of the allocation, we propose two strategic behaviors: misreporting strategy which the new node misreports its resource demand and spitting strategy which the node misrepresents itself by creating several fictitious nodes but keeps the sum of their resource demands the same. Surprisingly, we show that the allocation is trustful against the misreporting strategy while it is not trustful against the spitting strategy. Specifically, we present some illustrative examples to verify the results, and we show that a node can achieve 1.83 times resource if it misrepresents itself as two nodes.