Ordinal Pareto efficiency refers to several adaptations of the concept of Pareto-efficiency to settings in which the agents only express ordinal utilities over items, but not over bundles. That is, agents rank the items from best to worst, but they do not rank the subsets of items. In particular, they do not specify a numeric value for each item. This may cause an ambiguity regarding whether certain allocations are Pareto-efficient or not. As an example, consider an economy with three items and two agents, with the following rankings:
Consider the allocation [Alice: x, George: y,z]. Whether or not this allocation is Pareto-efficient depends on the agents' numeric valuations. For example:
Since the Pareto-efficiency of an allocation depends on the rankings of bundles, it is a-priori not clear how to determine the efficiency of an allocation when only rankings of items are given.
An allocation X = (X1,...,Xn) Pareto-dominates another allocation Y = (Y1,...,Yn), if every agent i weakly prefers the bundle Xi to the bundle Yi, and at least one agent j strictly prefers Xj to Yj. An allocation X is Pareto-efficient if no other allocation Pareto-dominates it. Sometimes, a distinction is made between discrete-Pareto-efficiency, which means that an allocation is not dominated by a discrete allocation, and the stronger concept of Fractional Pareto efficiency , which means that an allocation is not dominated even by a fractional allocation.
The above definitions depend on the agents' ranking of bundles (sets of items). In our setting, agents report only their rankings of items. A bundle ranking is called consistent with an item ranking if it ranks the singleton bundles in the same order as the items they contain. For example, if Alice's ranking is w < x < y < z, then any consistent bundle ranking must have {w} < {x} < {y} < {z]. Often, one makes additional assumptions on the set of allowed bundle rankings, which imposes additional restrictions on consistency. Example assumptions are:
Brams, Edelman and Fishburn [1] : 9 call an allocation Pareto-ensuring if it is Pareto-efficient for all bundle rankings that are consistent with the agents' item rankings (they allow all monotonic and responsive bundle rankings). For example:
Bouveret, Endriss and Lang. [2] : 3 use an equivalent definition. They say that an allocation X possibly Pareto-dominates an allocation Y if there exists some bundle rankings consistent with the agents' item rankings, for which X Pareto-dominates Y. An allocation is called Necessarily-Pareto-efficient (NecPE) if no other allocation possibly-Pareto-dominates it.
The two definitions are logically equivalent:
The NecPE condition remains the same whether we allow all additive bundle rankings, or we allow only rankings that are based on additive valuations with diminishing differences. [3] : Sec.8
NecPE is a very strong requirement, which often cannot be satisfied. For example, suppose two agents have the same item ranking. One of them, say Alice, necessarily receives the lowest-ranked item. There are consistent additive bundle-rankings in which Alices values this item at 0 while George values it at 1. Hence, giving it to Alice is not Pareto-efficient.
If we require that all items have a strictly positive value, then giving all items to a single agent is trivially NecPE, but it very unfair. If fractional allocations are allowed, then there may be no NecPE allocation which gives both agents a positive value. For example, suppose Alice and George both have the ranking x>y. If both get a positive value, then either Alice gets some x and George gets some y, or vice-versa. In the former case, it is possible that Alice's valuations are e.g. 4,2 and George's valuations are 8,1, so Alice can exchange a small amount r of x for a small amount 3r of y. Alice gains 6r-4r and George gains 8r-3r, so both gains are positive. In the latter case, an analogous argument holds.
Brams, Edelman and Fishburn [1] : 9 call an allocation Pareto-possible if it is Pareto-efficient for some bundle rankings that are consistent with the agents' item rankings. Obviously, every Pareto-ensuring allocation is Pareto-possible. In addition:
Bouveret, Endriss and Lang. [2] : 3 use a different definition. They say that an allocation X necessarily Pareto-dominates an allocation Y if for all bundle rankings consistent with the agents' item rankings, X Pareto-dominates Y. An allocation is called Possibly-Pareto-efficient (PosPE) if no other allocation necessarily-Pareto-dominates it.
The two definitions are not logically equivalent:
If X is Pareto-possible then it is PosPE, but the other implication is not (logically) true.[ clarification needed ]
The Pareto-possible condition remains the same whether we allow all additive bundle rankings, or we allow only rankings that are based on additive valuations with diminishing differences. [3] : Sec.8
Bogomolnaia and Moulin [4] : 302–303 present an efficiency notion for the setting of fair random assignment (where the bundle rankings are additive, the allocations are fractional, and the sum of fractions given to each agent must be at most 1). It is based on the notion of stochastic dominance.
For each agent i, A bundle Xiweakly-stochastically dominates(wsd) a bundle Yi if for every item z, the total fraction of items better than z in Xi is at least as large as in Yi (if the allocations are discrete, then Xi sd Yi means that for every item z, the number of items better than z in Xi is at least as large as in Yi). The sd relation has several equivalent definitions; see responsive set extension. In particular, Xi sd Yi if-and-only-if, for every bundle ranking consistent with the item ranking, Xi is at least as good as Yi. [5] A bundle Xistrictly-stochastically dominates(ssd) a bundle Yi if Xi wsd Yi and Xi ≠ Yi. Equivalently, for at least one item z, the "at least as large as in Yi" becomes "strictly larger than in Yi". In [1] the ssd relation is written as "Xi>> Yi".
An allocation X = (X1,...,Xn) stochastically dominates another allocation Y = (Y1,...,Yn), if for every agent i: Xi wsd Yi, and Y≠X (equivalently: for at least one agent i, Xi ssd Yi). In [1] the stochastic domination relation between allocations is also written as "X>> Y". This is equivalent to necessary Pareto-domination.
An allocation is called sd-efficient [6] (also called: ordinally efficient or O-efficient) [4] if there no allocation that stochastically dominates it. This is similar to PosPE, but emphasizes that the bundle rankings must be based on additive utility functions, and the allocations may be fractional.
As noted above, Pareto-possible implies PosPE, but the other direction is not logically true. McLennan [7] proves that they are equivalent in the fair random assignment problem (with strict or weak item rankings). Particularly, he proves that the following are equivalent:
The implications (c) → (b) → (a) are easy; the challenging part is to prove that (a) → (c). McLennan proves it using the polyhedral separating hyperplane theorem. [7]
Bogomolnaia and Moulin [4] : Lem.3 prove another useful characterization of sd-efficiency, for the same fair random assignment setting but with strict item rankings. Define the exchange graph of a given fractional allocation as a directed graph in which the nodes are the items, and there is an arc x→y iff there exists an agent i that prefers x and receives a positive fraction of y. Define an allocation as acyclic if its exchange graph has no directed cycles. Then, an allocation sd-efficient iff it is acyclic.
Fishburn proved the following equivalence on dominance relations of discrete bundles, with responsive bundle rankings: [8] [1] : Lem.2.1
Therefore, the following holds for dominance relations of discrete allocations: X>> Y iff X necessarily Pareto-dominates Y. [1] : 8
If Xi wsd Yi, then |Xi| ≥ |Yi|, that is, the total quantity of objects (discrete or fractional) in Xi must be at least as large as in Yi. This is because, if |Xi| < |Yi|, then for the valuation which assigns almost the same value for all items, v(Xi) < v(Yi).
This means that, if X wsd Y and both X and Y are complete allocations (all objects are allocated), then necessarily |Xi| = |Yi| for all agents i. [1] : Lem.2.2 In other words, a complete allocation X can be necessarily-dominated only by an allocation Y which assigns to every agent the same amount as X does.
This means that, in particular, if X is sd-efficient in the set of all allocations that give exactly 1 unit to each agent, then X is sd-efficient in general.
Cho presents two other efficiency notions for the setting of fair random assignment, based on lexicographic dominance.
An allocation X = (X1,...,Xn) downward-lexicographically (dl) dominates another allocation Y = (Y1,...,Yn), if for every agent i, Xi weakly-dl-dominates Yi, and for at least one agent j, Xj strictly-dl-dominates Yj. An allocation is called dl-efficient if there is no other allocation that dl-dominates it.
Similarly, based on the notion of upward-lexicographic (ul) domination, An allocation is called ul-efficient if there is no other allocation that ul-dominates it.
In general, sd-domination implies dl-domination and ul-domination. Therefore, dl-efficiency and ul-efficiency imply sd-efficiency.
Consider the fair random assignment setting (the bundle rankings are additive, the allocations may be fractional, and the total fraction given to each agent must be 1), with strict item rankings, where there can be more items than agents (so some items may remain unallocated). Cho and Dogan [6] prove that, in this particular case, dl-efficiency and ul-efficiency are equivalent to sd-efficiency. In particular, they prove that if an allocation X is sd/ld/ul efficient, then:
The equivalence does not hold if there are distributional constraints: there are allocations which are sd-efficient but not dl-efficient. [9] : Example 4
Pareto efficiency or Pareto optimality is a situation where no action or allocation is available that makes one individual better off without making another worse off. The concept is named after Vilfredo Pareto (1848–1923), Italian civil engineer and economist, who used the concept in his studies of economic efficiency and income distribution. The following three concepts are closely related:
Competitive equilibrium is a concept of economic equilibrium, introduced by Kenneth Arrow and Gérard Debreu in 1951, appropriate for the analysis of commodity markets with flexible prices and many traders, and serving as the benchmark of efficiency in economic analysis. It relies crucially on the assumption of a competitive environment where each trader decides upon a quantity that is so small compared to the total quantity traded in the market that their individual transactions have no influence on the prices. Competitive markets are an ideal standard by which other market structures are evaluated.
Efficient cake-cutting is a problem in economics and computer science. It involves a heterogeneous resource, such as a cake with different toppings or a land with different coverings, 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, etc. The allocation should be economically efficient. Several notions of efficiency have been studied:
Group envy-freeness is a criterion for fair division. A group-envy-free division is a division of a resource among several partners such that every group of partners feel that their allocated share is at least as good as the share of any other group with the same size. The term is used particularly in problems such as fair resource allocation, fair cake-cutting and fair item allocation.
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.
Efficiency and fairness are two major goals of welfare economics. Given a set of resources and a set of agents, the goal is to divide the resources among the agents in a way that is both Pareto efficient (PE) and envy-free (EF). The goal was first defined by David Schmeidler and Menahem Yaari. Later, the existence of such allocations has been proved under various conditions.
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.
A picking sequence is a protocol for fair item assignment. Suppose m items have to be divided among n agents. One way to allocate the items is to let one agent select a single item, then let another agent select a single item, and so on. A picking-sequence is a sequence of m agent-names, where each name determines what agent is the next to pick an item.
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.
The undercut procedure is a procedure for fair item assignment between two people. It provably finds a complete envy-free item assignment whenever such assignment exists. It was presented by Brams and Kilgour and Klamler and simplified and extended by Aziz.
The AL procedure is a procedure for fair item assignment between two people. It finds an envy-free item assignment of a subset of the items. Moreover, the resulting allocation is Pareto efficient in the following sense: there is no other envy-free allocation which is better for one person and not worse for the other person.
Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is a procedure for fair item assignment. It was developed by Eric Budish.
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).
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 .
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.