Allocating indivisible heirlooms

1. Flood^{[1]: case 4} describes a division of a gift containing 5 parcels: whiskey, prunes, eggs, suitcase, etc. The division was done using the Knaster auction. The resulting division was fair, but in retrospect it was found that coalitions could gain from manipulation.

2. When Mary Anna Lee Paine Winsor died at the age of 93, her estate included two trunks of silver, that had to be divided among her 8 grandchildren. It was divided using a decentralized, fair and efficient allocation procedure, which combined market equilibrium and a Vickrey auction. Although most participants did not fully understand the algorithm or the preference information desired, it handled the major considerations well and was regarded as equitable.^[2]

Allocating unused classrooms

In California, the law says that public school classrooms should be shared fairly among all public school pupils, including those in charter schools. Schools have dichotomous preferences: each school demands a certain number of classes, it is happy if it got all of them and unhappy otherwise. A new algorithm^[3] allocates classrooms to schools using a non-trivial implementation of the randomized leximin mechanism. Unfortunately it was not deployed in practice, but it was tested using computer simulations based on real school data. While the problem is computationally-hard, simulations show that the implementation scales gracefully in terms of running time: even when there are 300 charter schools, it terminates in a few minutes on average. Moreover, while theoretically the algorithm guarantees only 1/4 of the maximum number of allocated classrooms, in the simulations it satisfies on average at least 98% of the maximum number of charter schools that can possibly be satisfied, and allocates on average at least 98% of the maximum number of classrooms that can possibly be allocated.^[3]

The partial collaboration with the school district lead to several practical desiderata in deploying fair division solutions in practice. First, the simplicity of the mechanism, and the intuitiveness of the properties of proportionality, envy-freeness, Pareto optimality, and strategyproofness, have made the approach more likely to be adopted. On the other hand, the use of randomization, though absolutely necessary in order to guarantee fairness in allocating indivisible goods such as classrooms, has been a somewhat harder sell: the term "lottery" raised negative connotations and legal objections.

Resolving international conflicts

The adjusted winner procedure is a protocol for simultaneously resolving several issues under conflict, such that the agreement is envy-free, equitable, and Pareto efficient. It has been commercialized through the FairOutcomes Archived 2019-03-05 at the Wayback Machine website. While there are no account of it actually being used to resolve disputes, there are several counterfactual studies checking what would have been the results of using this procedure to solve international disputes:

• For the Camp David Accords, the authors construct approximate numeric valuation functions for Israel and Egypt, based on the relative importance of each issue for each country. They then run the AW protocol. The theoretical results are very similar to the actual agreement, which leads the authors to conclude that the agreement is as fair as it could be.^[4]
• For the Israeli-Palestinian conflict, the author constructs the valuation functions based on a survey of expert opinions, and describes the agreement that would result from running the AW protocol with these valuations.^[5]
• For the Spratly Islands dispute, the authors construct a two-phase procedure for settling the dispute, and present its (hypothetic) outcome.^[6]

Allocating rooms and rent

Rental harmony is the problem of simultaneously allocating rooms in an apartment and the rent of the apartment among the housemates. It has several solutions. Some of these solutions were implemented in the Spliddit.org website^[7] and tested on real users.^[8]

Sharing cooperation surplus

When different agents cooperate, there is an economic surplus in welfare. Cooperative game theory studies the question of how this surplus should be allocated, taking into account the various coalitional options of the players. Several cases of such cooperation has been studied, in light of concepts such as the Shapley value.^[9]

Fair Bargaining

Flood^[1] analyzed several cases of bargaining between a buyer and a seller on the price of purchasing a good (e.g. a car). He found that the "split-the-difference" principle was acceptable by both participants. The same cooperative principle was found in more abstract non-cooperative games. However, in some cases, bidders in an auction did not find a cooperative solution.

Fair Load-Shedding

Olabambo et al^[10] develop heuristic algorithms for fair allocation of electricity disconnections in developing countries. They test the fairness and welfare of their algorithms on electricity usage data from Texas, which they adapt to the situation in Nigeria.

Fair cake-cutting

Walsh^[11] developed several algorithms for online fair cake-cutting. He tested them using a computerized simulation: valuation functions for each agent were generated by dividing the cake into random segments, and assigning a random value to each segment, normalizing the total value of the cake. The egalitarian welfare and the utilitarian welfare of various algorithms were compared.

Shtechman, Gonen and Segal-Halevi^[12] simulated two famous cake-cutting algorithms - Even–Paz and Last diminisher - on real land-value data from New Zealand and Israel. The agents' valuations were generated by taking the market value of each land-cell and adding a random "noise" based on two different noise models: uniform noise and hot-spot noise. They showed the algorithms perform better than two alternative processes for dividing land, namely selling the land and dividing the proceeds, and hiring a real-estate assessor.

Welfare redistribution mechanism

Cavallo^[13] developed an improvement of the Vickrey–Clarke–Groves mechanism in which money is redistributed in order to increase social welfare. He tested his mechanism using simulations. He generated piecewise-constant valuation functions, whose constants were selected at random from the uniform distribution. He also tried Gaussian distributions and got similar results.

Fair item assignment

Dickerson, Goldman, Karp and Procaccia^[14] use simulations to check under what conditions an envy-free assignment of discrete items is likely to exist. They generate instances by sampling the value of each item to each agent from two probability distributions: uniform and correlated. In the correlated sampling, they first sample an intrinsic value for each good, and then assign a random value to each agent drawn from a truncated nonnegative normal distribution around that intrinsic value. Their simulations show that, when the number of goods is larger than the number of agents by a logarithmic factor, envy-free allocations exist with high probability.

Segal-Halevi, Aziz and Hassidim^[15] use simulations from similar distributions to show that, in many cases, there exist allocations that are necessarily fair based on a certain convexity assumption on the agents' preferences.

Important concepts

James Konow^[16] reviewed hundreds of experiments, done by phone interviews or written surveys, aimed at eliciting people's preferences and ideas regarding "what is fair?". Most experiments were done by presenting short stories (vignettes) to people and asking them whether the outcome is fair or unfair. The experiments revolved around four aspects of justice:

1. Equality and Need: egalitarianism, Rawls' theory and the Social contract and Marxism. Konow claims that there is little evidence for these as a general fairness principle, except when considering the basic needs. He calls it the Principle of Need: just allocations provide for basic needs equally across individuals.
2. Utilitarian and Welfare economics: utilitarianism, Pareto efficiency, envy-freeness. There is evidence that people want to maximize total surplus, even when it comes at a personal cost to them. This leads to the Principle of Efficiency: aiming to maximize the sum of derived values.
3. Equity and moral Desert: Nozick's theory of choice, Buchanan's theory of moral desert, and the theory of equity, which says that the rewards should be proportional to the contributions. He defines the Principle of Equity, which generalizes the equity formula to the entitlement formula: the entitlement of each agent is based on his inputs, outputs, endowments and costs. His allocation should be proportional to the variables he controls, but not to exogeneous variables of which he has no control.
4. Context: experiments show that the weighing of the above three principles depends on context. Aspects of context include past transactions (existing prices are usually considered "fair", particularly if they are stable and competitive). The endowment effect affects fairness: reducing someone's endowment is considered unfair. There are also information and framing effects: subjects may respond differently depending on what kind of information they are given on the situation. Theories of local justice say that people solve each instance of fair division locally, based on fairness principles relevant for that instance, emphasizing procedural fairness. Experiments find effects of scope, that is, determining the set of agents and the set of allocations to compare. There are differences between countries and cultures in the relative weight they assign to different fairness principles, as well as to related principles such as self-interest, love, altruism, and reciprocity.

Fairness vs. efficiency - what outcome is better?

Sometimes, there are only two possible allocations: one is fair (e.g. envy-free division) but inefficient, while the other is efficient (e.g. Pareto-optimal) but unfair. Which division do people prefer? This was tested in several lab experiments.

1. Subjects were given several possible allocations of money, and were asked which allocation they prefer. One experiment^[17] found that the most important factors were Pareto-efficiency and Rawlsian motive for helping the poor (maximin principle). However, a later experiment found that these conclusions only hold for students of economics and business, who train to acknowledge the importance of efficiency. In the general population, the most important factors are selfishness and inequality aversion.^[18]

2. Subjects were asked to answer questionnaires regarding the division of indivisible items between two people. The subjects were shown the subjective value that each (virtual) person attaches to each item. The predominant aspect considered was equity - satisfying each individual's preferences. The efficiency aspect was secondary. This effect was slightly more pronounced in economics students, and less pronounced in law students (who chose a Pareto-efficient allocation more frequently).^[19]

3. Subjects were divided into pairs and asked to negotiate and decide how to divide a set of 4 items between them. Each combination of items had a pre-specified monetary value, which was different between the two subjects. Each subject knew both his own values and the partner's values. After the division, each subject could redeem the items for their monetary value. The items could be divided in several ways: some divisions were equitable (e.g., giving each partner a value of 45), while other divisions were Pareto efficient (e.g., giving one partner 46 and another partner 75). The interesting question was whether people prefer the equitable or the efficient division. The results showed that people preferred the more efficient division only if it was not "too unfair". A difference of 2-3 value units was considered sufficiently small for most subjects, so they preferred the efficient allocation. But a difference of 20-30 units (such as in the 45:45 vs. 46:75 example) was perceived as too large: 51% preferred the 45:45 division. The effect were less pronounced when the subjects were only shown the rank of the item combinations for each of them, rather than the full monetary value. This experiment also revealed a recurring process which was used during the negotiation: subjects first find the most equitable division of the goods. They take it as a reference point and try to find Pareto improvements. An improvement is implemented only if the inequality it causes is not too large. This process is called CPIES: Conditioned Pareto Improvement from Equal Split.^[20]

Intra-personal vs. inter-personal fairness - which is more important?

What is the importance of intra-personal fairness criteria (such as envy-freeness, where each person compares bundles based only on his own utility-function), vs. inter-personal fairness criteria (such as equitability, where each person views the utilities of all other agents)? Using a free-form bargaining experiment, it was found that inter-personal fairness (e.g. equitability) is more important. Intra-personal fairness (such as envy-freeness) are relevant only as a secondary criterion.^[21]

Fairness vs. simplicity

Divide and choose (DC) is a fair and very simple procedure. There are more sophisticated procedures that have better fairness guarantees. The question of which were more satisfactory was tested in several lab experiments.

1. Divide-and-choose vs Knaster-Brams-Taylor. Several pairs of players had to divide among them 3 indivisible goods (a ballpoint pen, a lighter and a mug) and some money. Three procedures were used: the simple DC, and the more complicated Adjusted Knaster (an improvement of adjusted winner) and Proportional Knaster. The authors asked the subjects to select their favorite procedure. Then, they let them play the procedure in two modes: binding (strict adherence to the protocol rules) and non-binding (possible renegotiation afterwards). They compared the procedures performance in terms of efficiency, envy-freeness, equitability and truthfulness. Their conclusions are: (a) The sophisticated mechanisms are advantageous only in the binding case; when renegotiation is possible, their performance drops to the baseline level of DC. (b) The preference for a procedure depends not only on the expected utility calculations of the negotiators, but also on their psychological profile: the more "antisocial" a person is, the more likely he is to opt for a procedure with a compensatory mechanism. The more risk-averse a person is, the more likely he is to opt for a straightforward procedure like DC. (c) The final payoff of a participant in a procedure depends a lot on the implementation. If participants cannot divide the goods under a procedure of their own choice, they are more eager to maximize their payoff. A shortened time horizon is equally detrimental.^[22]

2. Structured procedures vs. Genetic algorithms. Two pairs of players had to divide between them 10 indivisible goods. A genetic algorithm was used to search for the best division candidates: out of the 1024 possible divisions, a subset of 20 divisions was shown to the players, and they were asked to grade their satisfaction about the candidate division on a scale ranging from 0 (not satisfied at all) to 1 (fully satisfied). Then, for each subject, a new population of 20 divisions was created using a genetic algorithm. This procedure continued for 15 iterations until a best surviving allocation was found. The results were compared to five provably-fair division algorithms: Sealed Bid Knaster, Adjusted Winner, Adjusted Knaster, Division by Lottery and Descending Demand. Often, the best divisions found by the genetic algorithm were rated as more mutually satisfactory than the ones derived from the algorithms. Two possible reasons for that were: (a) Temporal fluctuation of preferences - the valuations of humans change from the point they report their valuations to the point they see the final allocation. Most fair division procedures ignore this issue, but the genetic algorithm captures it naturally. (b) Non-additivity of preferences. Most division procedures assume that valuations are additive, but in reality they are not; the genetic algorithm works just as well with non-additive valuations.^[23]

3. Simple procedures vs. Strongly-fair procedures. 39 player-pairs were given 6 indivisible gift-certificates of the same value ($10) but from different vendors (e.g. Esso, Starbucks, etc.). Before the procedure, each participant was shown all the 64 possible allocations, and was asked to grade the satisfaction and fairness of each of them between 0 (bad) and 100 (good). Then, they were taught seven different procedures, with different levels of fairness guarantees: Strict Alternation and Balanced Alternation (no guarantees), Divide and Choose (only envy-freeness), Compensation Procedure and Price Procedure (envy-freeness and Pareto-efficiency), Adjusted Knaster and Adjusted Winner (envy-freeness, Pareto-efficiency and equitability). They practiced each of these against a computer. Then, they did an actual division against another human subject. After the procedure, they were asked again to grade the satisfaction and fairness of the outcome; the goal was to distinguish procedural fairness from distributional fairness. The results showed that: (a) procedural fairness had no significant impact; satisfaction was mainly determined by distributional fairness. (b) the results of simpler procedures (strict alternation, balanced alternation and DC) were considered fairer and more satisfactory. They explain this couter-intuitive result by showing that humans care about object equality - giving each agent the same number of objects (though this does not entail any mathematical fairness criterion).^[24]

Efficiency vs. strategy

Consider two agents that have to bargain on a deal, such as how to divide goods among them. Often, if they sincerely reveal their preferences, they can attain a win-win deal. However, if they strategically misrepresent their preferences in an attempt to gain, they might actually lose the deal. What negotiation procedure is most efficient in terms of attaining good deals? Several bargaining procedures were studied in the lab.

1. Sealed bid auction: a simple one-shot negotiation procedure. In the lab, information-advantaged players aggressively exploited asymmetric information, and drastically misrepresented their true valuation through strategic bidding. This often resulted in a reduced bargaining zone, forgone deals and low economic efficiency. In one experiment, deals were made on only 52% of all trials, while 77% of all trials had a positive bargaining zone.^[25]

2. Bonus procedure: a procedure that gives a bonus was given to participants making a deal. This bonus is calculated such that it is optimal for players to reveal their true preferences. Lab experiments show that this does not help: subjects still strategize, although it is bad for them.^[26]

3. Adjusted Winner (AW): a procedure that allocates divisible objects in order to maximize the total utility. In the lab, subjects bargained in pairs over two divisible objects. Each of the two objects was assigned a random value drawn from a commonly known prior distribution. Each player had complete information about their own values, but incomplete information about their co-bargainer’s values. There were three information conditions: (1) Competing Preferences: Players know that the preferences of their co-bargainer are similar to their own; (2) Complementary Preferences: Players know that the preferences of their co-bargainer are diametrically opposed to their own; (3) Unknown (Random) Preferences: Players do not know what their co-bargainer values most relative to their own preferences. In condition (1), the bilateral decisions converge toward efficient outcomes, yet only one-third are "envy-free". In condition (2), while players dramatically misrepresent their true valuation for objects, both efficiency and envy-freeness approach maximum levels. In condition (3), pronounced strategic bidding emerges, yet the result is twice as many envy-free outcomes, with increased levels of efficiency (relative to condition 1). In all cases, the structured AW procedure was quite successful in attaining a win-win solution - about 3/2 times more than unstructured negotiation. The key to its success is that it forces players out of the ‘fixed pie myth’.^[27]

4. Conflict-resolution algorithm: Hortala-Vallve and lorente-Saguer describe a simple mechanism for solving several issues simultaneously (analogous to Adjusted Winner). They observe that equilibrium play increases over time, and truthful play decreases over time - agents manipulate more often when they learn their partners' preferences. Fortunately, the deviations from equilibrium do not cause much damage to the social welfare - the final welfare is close to the theoretic optimum.^[28]

5. Fair cake-cutting algorithms: Ortega, Kyropoulou and Segal-Halevi^[29] tested algorithms such as Divide and choose, Last diminisher, Even–Paz and Selfridge–Conway between laboratory subjects. It is known that these procedures are not strategyproof, and indeed, they found that subjects often manipulate them. Moreover, the manipulation was often irrational - subjects often used dominated strategies. Despite the manipulations, the algorithms for envy-free cake-cutting produced outcomes with less envy, and were considered fairer.

Children

In the lab, children were paired to "rich" and "poor" and were asked to share objects. There were differences in the perception of "initial belongings" vs. "things that have to be shared": young children (up to 7) did not distinguish them while older children (above 11) did.^[30]