Truthful resource allocation

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 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[1] 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.[2]

For the special case of n=2 agents, they show a truthful mechanism that attains at least 0.622 of the utilitarian welfare.[3] 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.[4] They also show an O(m log m) 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 (such as the privatization auction in the Czech republic). The mechanism guarantees to each agent at least p/(p+1) 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/(n+1). This mechanism assigns to each agent a fraction of a single resource.[2]

Cheung[5] 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(partial-allocation,equal-split).
  • Truthful cake-cutting - a variant of the problem in which there is a single heterogeneous resource ("cake"), and each agent has a personal value-measure over the resource.
  • Strategic fair division - the study of equilibria of fair division games when the agents act strategically rather than sincerely.
  • Truthful allocation of two kinds of resources - plentiful and scarce.[6]
  • Truthful one-sided matching.[7]
  • Truthful fair division of indivisible items.[8][9][10]

References
  1. Strategy-proof allocation of multiple items between two agents without payments or priors
  2. Cole, Richard; Gkatzelis, Vasilis; Goel, Gagan (2013). "Mechanism Design for Fair Division: Allocating Divisible Items Without Payments". Proceedings of the Fourteenth ACM Conference on Electronic Commerce. EC '13. New York, NY, USA: ACM: 251–268. arXiv:1212.1522. doi:10.1145/2492002.2482582. ISBN 9781450319621.
  3. Cole, Richard; Gkatzelis, Vasilis; Goel, Gagan (2012-03-20). "Truthfulness, Proportional Fairness, and Efficiency". arXiv:1203.4627 [cs.GT].
  4. Positive results for mechanism design without money
  5. Cheung, Yun Kuen (2016-04-18). "Better Strategyproof Mechanisms without Payments or Prior --- An Analytic Approach". arXiv:1604.05243 [cs.GT].
  6. Cavallo, Ruggiero. Incentive Compatible Two-Tiered Resource Allocation Without Money. CiteSeerX 10.1.1.432.5462.
  7. Abebe, Rediet; Cole, Richard; Gkatzelis, Vasilis; Hartline, Jason D. (2019-03-18). "A Truthful Cardinal Mechanism for One-Sided Matching". arXiv:1903.07797 [cs.GT].
  8. Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis; Kyropoulou, Maria (2009). Rossi, Francesca; Tsoukias, Alexis (eds.). "On Low-Envy Truthful Allocations". Algorithmic Decision Theory. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 5783: 111–119. doi:10.1007/978-3-642-04428-1_10. ISBN 9783642044281.
  9. Amanatidis, Georgios; Birmpas, Georgios; Markakis, Evangelos (2016-05-12). "On Truthful Mechanisms for Maximin Share Allocations". arXiv:1605.04026 [cs.GT].
  10. Amanatidis, Georgios; Birmpas, Georgios; Christodoulou, George; Markakis, Evangelos (2017). "Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness". Proceedings of the 2017 ACM Conference on Economics and Computation - EC '17: 545–562. arXiv:1705.10706. Bibcode:2017arXiv170510706A. doi:10.1145/3033274.3085147.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.