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 15:29, 25 November 2019. 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 Nash individual welfare. The latter is defined as the utility that each individual agent receives in the Nash-optimal allocation - the allocation maximizing the product of agents' utilities (also known as the Proportionally-Fair solution, or competitive equilibrium from equal incomes).

Algorithms

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 n=2 agents, they show a truthful mechanism that attains at least 0.622 of the utilitarian welfare.[2] They later improved the ratio to 2/3.[3] They also show an O(m log m) algorithm for computing the max-product allocation. They also show that the Nash-optimal allocation itself attains at least 0.933 of the utilitarian welfare.

For many agents, with valuations that are homogeneous functions, they show a truthful and envy-free mechanism that guarantees to each agent at least 1/e ≈ 0.368 of his/her utility in the max-product allocation, and show that no truthful mechanism can guarantee more than 0.5 of the max-product utility. Their mechanism is based on discarding a carefully-chosen subset of the resources. Discarding resources induces truthfulness in a setting without money, in a similar manner to the monetary payments in the VCG mechanism. They also show a mechanism called Strong Demand Matching, with a performance that becomes better when the demand to resources increases. This fraction is at least n/(n+1) when there are two resources. When there are more resources, the approximation factor becomes better as the competitive-equilibrium prices increase.[4]

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]

References

  1. ^ Strategy-proof allocation of multiple items between two agents without payments or priors
  2. ^ Cole, Richard; Gkatzelis, Vasilis; Goel, Gagan (2012-03-20). "Truthfulness, Proportional Fairness, and Efficiency". arXiv:1203.4627 [cs].
  3. ^ Positive results for mechanism design without money
  4. ^ 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.
  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; 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=927907891"