Truthful resource allocation

Last updated

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.

Contents

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" (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:

The most common fairness objectives are:

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:

It is possible to mix these two mechanisms, and get a truthful mechanism that is partly-fair and partly-efficient. [1] 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 [1] 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.

There are analogous impossibility results for agents with ordinal utilities:

See also: Truthful one-sided matching. [4]

Approximation Algorithms

There are several truthful algorithms that find a constant-factor approximation of the maximum utilitarian or Nash welfare.

Guo and Conitzer [5] 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. [6]

For the special case of n=2 agents, they show a truthful mechanism that attains at least 0.622 of the utilitarian welfare. [7] 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. [8] They also show an 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. [6]

Cheung [9] improved the competitive ratios of previous works:

Related Research Articles

<span class="mw-page-title-main">Fair cake-cutting</span> Fair division problem

Fair cake-cutting is a kind of fair division problem. The problem involves a heterogeneous resource, such as a cake with different toppings, that is assumed to be divisible – it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible. The division should be unanimously fair – each person should receive a piece believed to be a fair share.

Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

Utilitarian cake-cutting is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different cardinal utility functions, such that the sum of the utilities of the partners is as large as possible. It is a special case of the utilitarian social choice rule. Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is often in conflict with fair cake-cutting.

Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem.

Fair division of a single homogeneous resource is one of the simplest settings in fair division problems. There is a single resource that should be divided between several people. The challenge is that each person derives a different utility from each amount of the resource. Hence, there are several conflicting principles for deciding how the resource should be divided. A primary conflict is between efficiency and equality. Efficiency is represented by the utilitarian rule, which maximizes the sum of utilities; equality is represented by the egalitarian rule, which maximizes the minimum utility.

Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.

Fair random assignment is a kind of a fair division problem.

Random priority (RP), also called Random serial dictatorship (RSD), is a procedure for fair random assignment - dividing indivisible items fairly among people.

A simultaneous eating algorithm(SE) is an algorithm for allocating divisible objects among agents with ordinal preferences. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies SD-efficiency - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for at least one vector of additive utility functions consistent with the agents' item rankings).

Combinatorial participatory budgeting,also called indivisible participatory budgeting or budgeted social choice, is a problem in social choice. There are several candidate projects, each of which has a fixed costs. There is a fixed budget, that cannot cover all these projects. Each voter has different preferences regarding these projects. The goal is to find a budget-allocation - a subset of the projects, with total cost at most the budget, that will be funded. Combinatorial participatory budgeting is the most common form of participatory budgeting.

Strategic fair division studies problems of fair division, in which participants cooperate to subdivide goods or resources fairly, from a point of view in which the participants are assumed to hide their preferences and act strategically in order to maximize their own utility, rather than playing sincerely according to their true preferences.

Truthful cake-cutting is the study of algorithms for fair cake-cutting that are also truthful mechanisms, i.e., they incentivize the participants to reveal their true valuations to the various parts of the cake.

The Partial Allocation Mechanism(PAM) is a mechanism for truthful resource allocation. It is based on the max-product allocation - the allocation maximizing the product of agents' utilities (also known as the Nash-optimal allocation or the Proportionally-Fair solution; in many cases it is equivalent to the competitive equilibrium from equal incomes). It guarantees to each agent at least 0.368 of his/her utility in the max-product allocation. It was designed by Cole, Gkatzelis and Goel.

When allocating objects among people with different preferences, two major goals are Pareto efficiency and fairness. Since the objects are indivisible, there may not exist any fair allocation. For example, when there is a single house and two people, every allocation of the house will be unfair to one person. Therefore, several common approximations have been studied, such as maximin-share fairness (MMS), envy-freeness up to one item (EF1), proportionality up to one item (PROP1), and equitability up to one item (EQ1). The problem of efficient approximately fair item allocation is to find an allocation that is both Pareto-efficient (PE) and satisfies one of these fairness notions. The problem was first presented at 2016 and has attracted considerable attention since then.

Proportional item allocation is a fair item allocation problem, in which the fairness criterion is proportionality - each agent should receive a bundle that they value at least as much as 1/n of the entire allocation, where n is the number of agents.

In economics and computer science, Fractional Pareto efficiency or Fractional Pareto optimality (fPO) is a variant of Pareto efficiency used in the setting of fair allocation of discrete objects. An allocation of objects is called discrete if each item is wholly allocated to a single agent; it is called fractional if some objects are split among two or more agents. A discrete allocation is called Pareto-efficient (PO) if it is not Pareto-dominated by any discrete allocation; it is called fractionally Pareto-efficient (fPO) if it is not Pareto-dominated by any discrete or fractional allocation. So fPO is a stronger requirement than PO: every fPO allocation is PO, but not every PO allocation is fPO.

Online fair division is a class of fair division problems in which the resources, or the people to whom they should be allocated, or both, are not all available when the allocation decision is made. Some situations in which not all resources are available include:

Fair allocation of items and money is a class of fair item allocation problems in which, during the allocation process, it is possible to give or take money from some of the participants. Without money, it may be impossible to allocate indivisible items fairly. For example, if there is one item and two people, and the item must be given entirely to one of them, the allocation will be unfair towards the other one. Monetary payments make it possible to attain fairness, as explained below.

Budget-proposal aggregation (BPA) is a problem in social choice theory. A group has to decide on how to distribute its budget among several issues. Each group-member has a different idea about what the ideal budget-distribution should be. The problem is how to aggregate the different opinions into a single budget-distribution program.

Dominant resource fairness (DRF) is a rule for fair division. It is particularly useful for dividing computing resources in among users in cloud computing environments, where each user may require a different combination of resources. DRF was presented by Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker and Ion Stoica in 2011.

References

  1. 1 2 Zhou, Lin (1990-10-01). "On a conjecture by gale about one-sided matching problems". Journal of Economic Theory. 52 (1): 123–135. doi:10.1016/0022-0531(90)90070-Z. ISSN   0022-0531.
  2. ↑ Bogomolnaia, Anna; Moulin, Hervé (2001). "A New Solution to the Random Assignment Problem". Journal of Economic Theory. 100 (2): 295. doi:10.1006/jeth.2000.2710.
  3. ↑ Katta, Akshay-Kumar; Sethuraman, Jay (2006). "A solution to the random assignment problem on the full preference domain". Journal of Economic Theory. 131: 231–250. doi:10.1016/j.jet.2005.05.001.
  4. ↑ 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].
  5. ↑ Guo, Mingyu; Conitzer, Vincent (2010-05-10). "Strategy-proof allocation of multiple items between two agents without payments or priors". Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: Volume 1 - Volume 1. AAMAS '10. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 881–888. ISBN   978-0-9826571-1-9.
  6. 1 2 Cole, Richard; Gkatzelis, Vasilis; Goel, Gagan (2013). "Mechanism design for fair division". Proceedings of the fourteenth ACM conference on Electronic commerce. EC '13. New York, NY, USA: ACM. pp. 251–268. arXiv: 1212.1522 . doi:10.1145/2492002.2482582. ISBN   9781450319621.
  7. ↑ Cole, Richard; Gkatzelis, Vasilis; Goel, Gagan (2012-03-20). "Truthfulness, Proportional Fairness, and Efficiency". arXiv: 1203.4627 [cs.GT].
  8. ↑ Cole, Richard; Gkatzelis, Vasilis; Goel, Gagan (2013-05-06). "Positive results for mechanism design without money". Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems. AAMAS '13. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 1165–1166. ISBN   978-1-4503-1993-5.
  9. ↑ Cheung, Yun Kuen (2016-04-18). "Better Strategyproof Mechanisms without Payments or Prior --- An Analytic Approach". arXiv: 1604.05243 [cs.GT].
  10. ↑ Cavallo, Ruggiero. Incentive Compatible Two-Tiered Resource Allocation Without Money. CiteSeerX   10.1.1.432.5462 .
  11. ↑ Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis; Kyropoulou, Maria (2009). "On Low-Envy Truthful Allocations". In Rossi, Francesca; Tsoukias, Alexis (eds.). Algorithmic Decision Theory. Lecture Notes in Computer Science. Vol. 5783. Springer Berlin Heidelberg. pp. 111–119. doi:10.1007/978-3-642-04428-1_10. ISBN   9783642044281.
  12. ↑ Amanatidis, Georgios; Birmpas, Georgios; Markakis, Evangelos (2016-07-09). "On truthful mechanisms for maximin share allocations". Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. IJCAI'16. New York, New York, USA: AAAI Press: 31–37. arXiv: 1605.04026 . ISBN   978-1-57735-770-4.
  13. ↑ 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. pp. 545–562. arXiv: 1705.10706 . Bibcode:2017arXiv170510706A. doi:10.1145/3033274.3085147. ISBN   9781450345279. S2CID   27249301.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.