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.
With two agents and one item, it is possible to attain fairness using the following simple algorithm (which is a variant of cut and choose):
The algorithm always yields an envy-free allocation. If the agents have quasilinear utilities, that is, their utility is the value of items plus the amount of money that they have, then the allocation is also proportional. If George thinks that Alice's price is low (he is willing to pay more than p), then he takes the item and pay p, and his utility is positive, so he does not envy Alice. Alice, too, does not envy George since his utility - in her eyes - is 0. Similarly, if George thinks that Alice's price is high (he is willing to pay p or more), then he leaves the item to Alice and does not envy, since Alice's utility in his eyes is negative.
The paid money p can later be divided equally between the players, since an equal monetary transfer does not affect the relative utilities. Then, effectively, the buying agent pays p/2 to the selling agent. The total utility of each agent is at least 1/2 of his/her utility for the item. If the agents have different entitlements, then the paid money p should be divided between the partners in proportion to their entitlements.
There are various works extending this simple idea to more than two players and more complex settings. The main fairness criteria in these works is envy-freeness . In addition, some works consider a setting in which a benevolent third-party is willing to subsidize the allocation, but wants to minimize the amount of subsidy subject to envy-freeness. This problem is called the minimum-subsidy envy-free allocation.
Unit-demand agents are interested in at most a single item.
A special case of this setting is when dividing rooms in an apartment between tenants. It is characterized by three requirements: (a) the number of agents equals the number of items, (b) each agent must get exactly one item (room), (c) the total amount of money paid by the agents must equal a fixed constant, which represents the total apartment rent. This is known as the Rental Harmony problem.
In general, in the economics literature, it is common to assume that each agent has a utility function on bundles (a bundle is a pair of an object and a certain amount of money). The utility function should be continuous and increasing in money. It does not have to be linear in money, but does have to be "Archimedean", i.e., there exists some value V such that, for every two objects j and k, the utility of object j plus V should be larger than the utility of object k (alternatively, the utility of getting object j for free is larger than the utility of getting object k and paying V). Quasilinear utility is a special case of Archimedean utility, in which V is the largest value-difference (for the same agent) between two objects.
Svensson [1] first proved that, when all agents are Archimedean, an envy-free allocation exists and is Pareto-optimal.
Demange, Gale and Sotomayor [2] showed a natural ascending auction that achieves an envy-free allocation using monetary payments for unit demand agents.
Maskin [3] proved the existence of a Pareto-optimal envy-free allocation when the total money endowment is more than (n-1)V. The proofs use competitive equilibrium.
Note that a subsidy of (n-1)V may be required: if all agents value a single object at V and the other objects at 0, then envy-freeness requires a subsidy of V for each agent who does not receive the object.
Tadenuma and Thomson [4] study several consistency properties of envy-free allocation rules.
Aragones [5] characterizes the minimum amount of subsidy required for envy-freeness. The allocation that attains this minimum subsidy is almost unique: there is only one way to combine objects with agents, and all agents are indifferent among all minimum-subsidy allocations. It coincides with the solution called the "money-Rawlsian solution" of Alkan, Demange and Gale. [6] It can be found in polynomial time, by finding a maximum-weight matching and then finding shortest paths in a certain induced graph.
Klijn [7] presents another polynomial-time algorithm for the same setting. His algorithm uses the polytope of side-payments that make a given allocation envy-free: this polytope is nonempty iff the original allocation is Pareto-efficient. Connectivity of the undirected envy graph characterizes the extreme points of this polytope. This implies a method for finding extreme envy-free allocations.
Additive agents may receive several objects, so the allocation problem becomes more complex - there are many more possible allocations.
The first procedure for fair allocation of items and money was invented by Bronislaw Knaster and published by Hugo Steinhaus. [8] [9] This auction works as follows, for each item separately:
The utility of every agent is at least 1/n of the value he attributes to the entire set of objects, so the allocation is proportional. [10] Moreover, the allocation maximizes the sum of utilities, so it is Pareto efficient.
Knaster's auction is not strategyproof. Some researchers analysed its performance when agents play strategically:
Knaster's auction has been adapted to fair allocation of wireless channels. [13]
Matthias G. Raith [14] presented a variant on Knaster's auction, which he called "Adjusted Knaster". As in Knaster's auction, each item is given to the highest bidder. However, the payments are different. The payments are determined as follows:
To illustrate the difference between Knaster's auction and Raith's auction, consider a setting with two items and two agents with the following values:
Item 1 | Item 2 | Sum | |
---|---|---|---|
Alice | 10 | 10 | 20 |
George | 60 | 120 | 180 |
In both auctions, George wins both items, but the payments are different:
In experiments with human subjects, [15] it was found that participants prefer the Raith's auction (Adjusted Knaster) to Divide-and-Choose and to Proportional Knaster (a variant in which each winner pays 1/n of the winning to each loser; in the above example, George pays 90 to Alice, and the net utilities are 90, 90).
Haake, Raith and Su [16] present the Compensation Procedure. Their procedure allows arbitrary constraints on bundles of items, as long as they are anonymous (do not differentiate between partners based on their identity). For example, there can be no constraint at all, or a constraint such as "each partner must receive at least a certain number of items", or "some items must be bundled together" (e.g. because they are land-plots that must remain connected), etc. The "items" can have both positive or negative utilities. There is a "qualification requirement" for a partner: the sum of his bids must be at least the total cost. The procedure works in the following steps.
When there are many item and complex constraints, the initial step - finding a maxsum allocation - may be difficult to calculate without a computer. In this case, the Compensation Procedure may start with an arbitrary allocation. In this case, the procedure might conclude with an allocation that contains envy-cycles. These cycles can be removed by moving bundles along the cycle, as in the envy-graph procedure. This strictly increases the total sum of utilities. Hence, after a bounded number of iterations, a maxsum allocation will be found, and the procedure can continue as above to create an envy-free allocation.
The Compensation Procedure might charge some partners a negative payment (i.e., give the partners a positive amount of money). The authors say:
Some works assume that a benevolent third-party is willing to subsidize the allocation, but wants to minimize the amount of subsidy subject to envy-freeness. This problem is called the minimum-subsidy envy-free allocation.
Halpern and Shah [17] study subsidy minimization in the general item-allocation setting. They consider two cases:
Brustle, Dippel, Narayan, Suzuki and Vetta [18] improve the upper bounds on the required subsidy:
Caragiannis and Ioannidis [19] study the computational problem of minimizing the subsidy:
Note that an envy-free allocation with subsidy remains envy-free if a fixed amount is taken from every agent. Therefore, similar methods can be used to find allocations that are not subsidized:
Alkan, Demange and Gale [6] showed that an envy-free allocation always exists when the amount of money is sufficiently large. This is true even when items may have negative valuations.
Meertens, Potters and Reijnierse [20] prove the existence of envy-free and Pareto-optimal allocations under very mild assumptions on the valuations (not necessarily quasilinear).
Cavallo [21] generalizes the traditional binary criteria of envy-freeness, proportionality, and efficiency (welfare) to measures of degree that range between 0 and 1. In the canonical fair division settings, under any allocatively-efficient mechanism the worst-case welfare rate is 0 and disproportionality rate is 1; in other words, the worst-case results are as bad as possible. He looks for a mechanism that achieves high welfare, low envy, and low disproportionality in expectation across a spectrum of fair division settings. The VCG mechanism is not a satisfactory candidate, but the redistribution mechanism of Bailey [22] and Cavallo [23] is.
When selling objects to buyers, the sum of payments is not fixed in advance, and the goal is to maximize either the seller's revenue, or the social welfare, subject to envy-freeness. Additionally, the number of objects may be different than the number of agents, and some objects may be discarded. This is known as the Envy-free Pricing problem.
Often, some other objectives have to be attained besides fairness. For example, when assigning tasks to agents, it is required both to avoid envy, and to minimize the makespan (- the completion time of the last agent). Mu'alem presents a general framework for optimization problems with envy-freeness guarantee that naturally extends fair item allocations using monetary payments. [24]
Aziz [25] aims to attain, using monetary transfers, an allocation that is both envy-free and equitable. He studies not only additive positive utilities, but also for any superadditive utilities, whether positive or negative:
Adjusted Winner (AW) is an algorithm for envy-free item allocation. Given two parties and some discrete goods, it returns a partition of the goods between the two parties that is:
Entitlement in fair division describes that proportion of the resources or goods to be divided that a player can expect to receive. In many fair division settings, all agents have equal entitlements, which means that each agent is entitled to 1/n of the resource. But there are practical settings in which agents have different entitlements. Some examples are:
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:
Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by any other agent. In other words, no person should feel envy.
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.
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.
Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is a procedure for fair item assignment. It was developed by Eric Budish.
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).
Various experiments have been made to evaluate various procedures for fair division, the problem of dividing resources among several people. These include case studies, computerized simulations, and lab experiments.
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.
Maximin share (MMS) is a criterion of fair item allocation. Given a set of items with different values, the 1-out-of-n maximin-share is the maximum value that can be gained by partitioning the items into parts and taking the part with the minimum value. An allocation of items among agents with different valuations is called MMS-fair if each agent gets a bundle that is at least as good as his/her 1-out-of-n maximin-share. MMS fairness is a relaxation of the criterion of proportionality - each agent gets a bundle that is at least as good as the equal split ( of every resource). Proportionality can be guaranteed when the items are divisible, but not when they are indivisible, even if all agents have identical valuations. In contrast, MMS fairness can always be guaranteed to identical agents, so it is a natural alternative to proportionality even when the agents are different.
Round robin is a procedure for fair item allocation. It can be used to allocate several indivisible items among several people, such that the allocation is "almost" envy-free: each agent believes that the bundle he received is at least as good as the bundle of any other agent, when at most one item is removed from the other bundle. In sports, the round-robin procedure is called a draft.
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.
Egalitarian item allocation, also called max-min item allocation is a fair item allocation problem, in which the fairness criterion follows the egalitarian rule. The goal is to maximize the minimum value of an agent. That is, among all possible allocations, the goal is to find an allocation in which the smallest value of an agent is as large as possible. In case there are two or more allocations with the same smallest value, then the goal is to select, from among these allocations, the one in which the second-smallest value is as large as possible, and so on. Therefore, an egalitarian item allocation is sometimes called a leximin item allocation.
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.
In computer science and operations research, the envy minimization problem is the problem of allocating discrete items among agents with different valuations over the items, such that the amount of envy is as small as possible.
In economics and computer science, the house allocation problem is the problem of assigning objects to people with different preferences, such that each person receives exactly one object. The name "house allocation" comes from the main motivating application, which is assigning dormitory houses to students. Other commonly used terms are assignment problem and one-sided matching. When agents already own houses, the problem is often called a housing market. In house allocation problems, it is assumed that monetary transfers are not allowed; the variant in which monetary transfers are allowed is known as rental harmony.
The welfare maximization problem is an optimization problem studied in economics and computer science. Its goal is to partition a set of items among agents with different utility functions, such that the welfare – defined as the sum of the agents' utilities – is as high as possible. In other words, the goal is to find an item allocation satisfying the utilitarian rule.