Jump to content

Truthful resource allocation

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Erel Segal (talk | contribs) at 13:29, 29 November 2019 (→Algorithms). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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:

  • Attains as high as possible utilitarial social welfare (defined as the sum of agents' utilities).
  • Attains as high as possible max-product utility. The latter is defined as the utility that each individual agent receives in the max-product allocation - the allocation maximizing the product of agents' utilities (also known as the Nash-optimal allocation, Proportionally-Fair solution, or 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 Nash-optimal 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 more than 0.5 of the Nash-optimal 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, and attains at least 2/3 of the optimal welfare.[4] They also show an O(m log m) algorithm for computing the Nash-optimal 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 guarnatees 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 with a partial-allocation mechanism.
  • 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. ^ a b 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. 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].
  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].
  6. ^ Cavallo, Ruggiero. Incentive Compatible Two-Tiered Resource Allocation Without Money.
  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].
  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. 5783. Springer Berlin Heidelberg: 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].
  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. doi:10.1145/3033274.3085147.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Truthful_resource_allocation&oldid=928476412"