A fair and scalable mechanism for resource allocation: the multilevel QPQ approach

In this paper the problem of distributing resources among a collection of users (or players) is explored. These players have independent preferences to get these resources and can be dishonest about their preferences in order to increase their utility (their preference for the resources they are allocated). The objective is design a mechanism to allocate resources to players so that all of them get the same amount of resources (fair), the total utility is maximized (optimal), and no player has incentive to be dishonest (strategy proof). Santos et al. proposed the Quid Pro Quo (QPQ) mechanism to solve this problem. In this paper a generalization of the QPQ mechanism is proposed that, in addition to the above properties, has a very high degree of scalability. The proposed multilevel QPQ mechanism divides the players into disjoint clusters and runs a mechanism similar to QPQ inside each cluster and across selected players in each cluster. As a consequence the amount of communication required is drastically reduced. Similarly, the storage used by the mechanism by each player is also significantly reduced, which in a practical setting can be used to improve the ability to detect dishonest players.