Truthful resource allocation is the problem of allocating resources among agents with different valuations over the resources, such that agents are incentivized to reveal their true valuations over the resources.
Model
There are m resources that are assumed to be homogeneous and divisible. Examples are:
There are n agents. Each agent has a function that attributes a numeric value to each "bundle". It is often assumed that the agents' value functions are linear, so that if the agent receives a fraction rj of each resource j, then his/her value is the sum of rj *vj.
Design goals
The goal is to design a truthful mechanism, that will induce the agents to reveal their true value functions, and then calculate an allocation that maximizes some global objective. The two most studied objectives are:
Utilitarial social welfare --- defined as the sum of agents' utilities. An allocation maximizing this sum is called utilitarian or max-sum.
Nash social welfare --- defined as the product of agents' utilities. An allocation maximizing this product is called Nash-optimal or max-product or proportionally-fair, and in many cases it is equivalent to the competitive equilibrium from equal incomes.
Algorithms
The simplest truthful fair mechanism is the equal split mechanism - it gives each agent exactly 1/n of each resource. Since the bundle of each agent is fixed, the mechanism is truthful. However, it is not very efficient. Guo and Conitzer studied the special case of n=2 agents. For the case of m=2 resources, they showed a truthful mechanism attaining 0.828 of the maximum utilitarian welfare, and showed an upper bound of 0.841. For the case of many resources, they showed that all truthful mechanisms of the same kind approach 0.5 of the maximum utilitarian welfare. Their mechanisms are complete - they allocate all the resources. Cole, Gkatzelis and Goel studied mechanisms of a different kind - based on the max-product allocation. For many agents, with valuations that are homogeneous functions, they show a truthful mechanism called Partial Allocation that guarantees to each agent at least 1/e ≈ 0.368 of his/her utility in the max-product allocation. Their mechanism is envy-free when the valuations are additive linear functions. They show that no truthful mechanism can guarantee to all agents more than 0.5 of their max-product utility. For the special case of n=2 agents, they show a truthful mechanism that attains at least 0.622 of the utilitarian welfare. They also show that the mechanism running the equal-split mechanism and the partial-allocation mechanism, and choosing the outcome with the highest social welfare, is still truthful, since both agents always prefer the same outcome. Moreover, it attains at least 2/3 of the optimal welfare. They also show an O algorithm for computing the max-product allocation, and show that the Nash-optimal allocation itself attains at least 0.933 of the utilitarian welfare. They also show a mechanism called Strong Demand Matching, which is tailored for a setting with many agents and few resources. The mechanism guarantees to each agent at least p/ of the max-product utility, when p is the smallest equilibrium price of a resource when each agent has a unit budget. When there are many more agents than resources, the price of each resource is usually high, so the approximation factor approaches 1. In particular, when there are two resources, this fraction is at least n/. This mechanism assigns to each agent a fraction of a single resource. Cheung improved the competitive ratios of previous works:
The ratio for two agents and two resources improved from 0.828 to 5/6 ≈ 0.833 with a complete-allocation mechanism, and strictly more than 5/6 with a partial-allocation mechanism. The upper bound improved from 0.841 to 5/6+epsilon for a complete-allocation mechanism, and to 0.8644 for a partial mechanism.
The ratio for two agents and many resources improved from 2/3 to 0.67776, by using a weighted average of two mechanisms: partial-allocation, and max.
Truthful cake-cutting - a variant of the problem in which there is a single heterogeneous resource, and each agent has a personal value-measure over the resource.
