Fair allocation of items and money

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.

Two agents and one item

With two agents and one item, it is possible to attain fairness using the following simple algorithm :

Alice says a price p that she is willing to pay for the item.
George chooses whether to take the item and pay p, or leave the item to Alice so that Alice pays p.

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, 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, 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

Unit-demand agents are interested in at most a single item.

Rental harmony

A special case of this setting is when dividing rooms in an apartment between tenants. It is characterized by three requirements: the number of agents equals the number of items, each agent must get exactly one item, 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.

More general settings

In general, in the economics literature, it is common to assume that each agent has a utility function on bundles. 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. Quasilinear utility is a special case of Archimedean utility, in which V is the largest value-difference between two objects.
Svensson first proved that, when all agents are Archimedean, an envy-free allocation exists and is Pareto-optimal.
Demange, Gale and Sotomayor showed a natural ascending auction that achieves an envy-free allocation using monetary payments for unit demand agents.
Maskin proved the existence of a Pareto-optimal envy-free allocation when the total money endowment is more than V. The proofs use competitive equilibrium.
Tadenuma and Thomson study several consistency properties of envy-free allocation rules.
Aragones 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. It can be found in polynomial time, by finding a maximum-weight matching and then finding shortest paths in a certain induced graph.
Klijn 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

Additive agents may receive several objects, so the allocation problem becomes more complex - there are many more possible allocations.

Knaster's auction

The first procedure for fair allocation of items and money was invented by Bronislaw Knaster and published by Hugo Steinhaus. This auction works as follows, for each item separately:

Each agent submits a bid over the item.
The item is given to the highest bidder.
The winner pays /n of his bid;
Each of the other agents receives 1/n of his bid;
Since the winner is the highest bidder, there is a non-negative surplus; the surplus is divided equally among the agents.

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. 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:

Essen proves that the equilibrium allocation is still Pareto-efficient, but may not be proportional ex-post. However, on average, agents receive the same outcome as if everyone were truthful. That is, the mechanism is proportional ex-ante.
Fragnelli and Marina show that, even agents who are infinitely risk-averse, may a safe gain via a joint misreporting of their valuations, regardless of the declarations of the other agents.

Knaster's auction has been adapted to fair allocation of wireless channels.

Raith's auction

Matthias G. Raith 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:

Each agent winning an item pays his bid for this item;
The total amount of money paid by the agents is partitioned between them in proportion to their bids.

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:
In both auctions, George wins both items, but the payments are different:

In Knaster's auction, George pays 90, Alice receives 10, and the difference of 80 is divided equally, so the net utilities are 50, 130.
In Raith's auction, George pays 180 and it is divided in ratio 20:180 = 1:9, that is, Alice gets 18 and George gets 162. Note that the payments are computed to all items at once - not for each item separately.

In experiments with human subjects, it was found that participants prefer the Raith's auction to Divide-and-Choose and to Proportional Knaster.

Compensation procedure

Haake, Raith and Su present the Compensation Procedure. Their procedure allows arbitrary constraints on bundles of items, as long as they are anonymous. 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", 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.

Find a maxsum allocation - an allocation with a highest sum-of-utilities that satisfies the constraints on bundles of items. If there are no constraints, then an allocation that gives each item to the partner with the highest valuation is maxsum. If there are constraints, then a maxsum allocation might be more difficult to find.
Charge from each partner the value of the bundle allocated to him. This creates the initial pool of money.
Pay the cost from the initial pool. If all partners satisfy the qualification requirement, then the money in the pool is sufficient, and there may be some remaining surplus.
Eliminate envy by compensating envious partners. There are at most rounds of compensation. The procedure is fully descriptive and says explicitly which compensations should be made, and in what order. Moreover, it is simple enough to be carried out without computer support.
The sum of compensations made in all rounds is the smallest sum that is required to eliminate envy, and it never exceeds the surplus. If some surplus remains, it can be divided in any way that does not create envy, e.g., by giving an equal amount to each partner.

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. The authors say: