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:
Materials, such as wood or metal; Virtual resources, such as CPU time or computer memory; Financial resources, such as shares in firms. There are n agents. Each agent has a function that attributes a numeric value to each "bundle" (combination of resources). 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 satisfies some fairness and efficiency objectives. The common efficiency objectives are:
Pareto efficiency (PE); Utilitarian social welfare — defined as the sum of agents' utilities. An allocation maximizing this sum is called utilitarian or max-sum; it is always PE. 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; it is always PE. When agents have additive utilities, it is equivalent to the competitive equilibrium from equal incomes. The most common fairness objectives are:
Equal treatment of equals (ETE) — if two agents have exactly the same utility function, then they should get exactly the same utility. Envy-freeness — no agent should envy another agent. It implies ETE. Egalitarian in lieu of equitable markets are analogous to laissez-faire early-stage capitalism, which form the basis of common marketplaces bearing fair trade policies in world markets' market evaluation; financiers can capitalise on financial controls and financial leverage and the concomitant exchange.
Trivial algorithms Two trivial truthful algorithms are:
The equal split algorithm — which gives each agent exactly 1/n of each resource. This allocation is envy-free (and obviously ETE), but usually it is very inefficient. The serial dictatorship algorithm — which orders the agents arbitrarily, and lets each agent in turn take all resources that he wants, from among the remaining ones. This allocation is PE, but usually it is unfair. It is possible to mix these two mechanisms, and get a truthful mechanism that is partly-fair and partly-efficient. But the ideal mechanism would satisfy all three properties simultaneously: truthfulness, efficiency and fairness.
At most one object per agent In a variant of the resource allocation problem, sometimes called one-sided matching or assignment, the total amount of objects allocated to each agent must be at most 1. When there are 2 agents and 2 objects, the following mechanism satisfies all three properties: if each agent prefers a different object, give each agent his preferred object; if both agents prefer the same object, give each agent 1/2 of each object (It is PE due to the capacity constraints). However, when there are 3 or more agents, it may be impossible to attain all three properties. Zhou proved that, when there are 3 or more agents, each agent must get at most 1 object, and each object must be given to at most 1 agent, no truthful mechanism satisfies both PE and ETE.
When there are multiple units of each object (but each agent must still get at most 1 object), there is a weaker impossibility result: no PE and ETE mechanism satisfies Group strategyproofness. He leaves open the more general resource allocation setting, in which each agent may get more than one object. There are analogous impossibility results for agents with ordinal utilities:
For agents with strict ordinal utilities, Bogomolnaia and Moulin prove that no mechanism satisfies possible-PE, necessary-truthfulness, and ETE. For agents with weak ordinal utilities, Katta and Sethuraman prove that no mechanism satisfies possible-PE, possible-truthfulness, and necessary-envy-freeness. See also: Truthful one-sided matching.
… excerpt ends here. Continue reading the full article.
