Surplus sharing is a kind of a fair division problem where the goal is to share the financial benefits of cooperation (the "economic surplus") among the cooperating agents. As an example, suppose there are several workers such that each worker i, when working alone, can gain some amount ui. When they all cooperate in a joint venture, the total gain is u1+...+un+s, where s>0. This s is called the surplus of cooperation, and the question is: what is a fair way to divide s among the n agents?
When the only available information is the ui, there are two main solutions:
Kolm [1] calls the equal sharing "leftist" and the proportional sharing "rightist".
Chun [2] presents a characterization of the proportional rule.
Moulin [3] presents a characterization of the equal and proportional rule together by four axioms (in fact, any three of these axioms are sufficient):
Any pair of these axioms characterizes a different family of rules, which can be viewed as a compromise between equal and proportional sharing.
When there is information about the possible gains of sub-coalitions (e.g., it is known how much agents 1,2 can gain when they collaborate in separation from the other agents), other solutions become available, for example, the Shapley value.
A bankruptcy problem, also called a claims problem, is a problem of distributing a homogeneous divisible good among people with different claims. The focus is on the case where the amount is insufficient to satisfy all the claims.
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:
In social choice theory, a dictatorship mechanism is a rule by which, among all possible alternatives, the results of voting mirror a single pre-determined person's preferences, without consideration of the other voters. Dictatorship by itself is not considered a good mechanism in practice, but it is theoretically important: by Arrow's impossibility theorem, when there are at least three alternatives, dictatorship is the only ranked voting electoral system that satisfies unrestricted domain, Pareto efficiency, and independence of irrelevant alternatives. Similarly, by Gibbard's theorem, when there are at least three alternatives, dictatorship is the only strategyproof rule.
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.
Resource monotonicity is a principle of fair division. It says that, if there are more resources to share, then all agents should be weakly better off; no agent should lose from the increase in resources. The RM principle has been studied in various division problems.
In economics and mechanism design, a cost-sharing mechanism is a process by which several agents decide on the scope of a public product or service, and how much each agent should pay for it. Cost-sharing is easy when the marginal cost is constant: in this case, each agent who wants the service just pays its marginal cost. Cost-sharing becomes more interesting when the marginal cost is not constant. With increasing marginal costs, the agents impose a negative externality on each other; with decreasing marginal costs, the agents impose a positive externality on each other. The goal of a cost-sharing mechanism is to divide this externality among the agents.
Fair random assignment is a kind of a fair division problem.
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).
Egalitarian equivalence (EE) is a criterion of fair division. In an egalitarian-equivalent division, there exists a certain "reference bundle" such that each agent feels that his/her share is equivalent to .
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.
In mathematics, leximin order is a total preorder on finite-dimensional vectors. A more accurate, but less common term is leximin preorder. The leximin order is particularly important in social choice theory and fair division.
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.
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.
Coherence, also called uniformity or consistency, is a criterion for evaluating rules for fair division. Coherence requires that the outcome of a fairness rule is fair not only for the overall problem, but also for each sub-problem. Every part of a fair division should be fair.
Constrained equal awards(CEA), also called constrained equal gains, is a division rule for solving bankruptcy problems. According to this rule, each claimant should receive an equal amount, except that no claimant should receive more than his/her claim. In the context of taxation, it is known as leveling tax.
Constrained equal losses(CEL) is a division rule for solving bankruptcy problems. According to this rule, each claimant should lose an equal amount from his or her claim, except that no claimant should receive a negative amount. In the context of taxation, it is known as poll tax.
The proportional rule is a division rule for solving bankruptcy problems. According to this rule, each claimant should receive an amount proportional to their claim. In the context of taxation, it corresponds to a proportional tax.
A strategic bankruptcy problem is a variant of a bankruptcy problem in which claimants may act strategically, that is, they may manipulate their claims or their behavior. There are various kinds of strategic bankruptcy problems, differing in the assumptions about the possible ways in which claimants may manipulate.
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.