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:
Alice: x > y > z. George: x > z > y. Consider the allocation [Alice: x, George: y,z]. Whether or not this allocation is Pareto-efficient depends on the agents' numeric valuations. For example:
It is possible that Alice prefers {y,z} to {x} and George prefers {x} to {y,z} (for example: Alice's valuations for x,y,z are 8,7,6 and George's valuations are 7,1,2, so the utility profile is 8,3). Then the allocation is not Pareto-efficient, since both Alice and George would be better-off by exchanging their bundles (the utility profile would be 13,7). In contrast, it is possible that Alice prefers {x} to {y,z} and George prefers {y,z} to {x} (for example: Alice's valuations are 12,4,2 and George's valuations are 6,3,4). Then the allocation is Pareto-efficient: in any other allocation, if Alice still gets x, then George's utility is lower; if Alice does not get x, then Alice's utility is lower. Moreover, the allocation is Pareto-efficient even if the items are divisible (that is, it is fractionally Pareto efficient): if Alice yields any amount r of x to George, then George would have to give her at least 3r of y or 6r of z in order to keep her utility at the same level. But then George's utility would change by 6r-9r or 6r-24r, which is negative. 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.
Definitions 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:
Monotonicity: adding an item to a bundle always improves the bundle. This corresponds to the assumption that all items are good. Thus, Alice's bundle ranking must have e.g. {y} < {y,x}. Responsivity: replacing an item with a better item always improves the bundle. Thus, Alice's bundle ranking must have e.g. {w,x} < {w,y} < {x,y} < {x,z}. This is stronger than consistency. Additivity: the agent assigns a value to each item, and values each bundle at the sum of its contents. This assumption is stronger than responsivity. For example, if Alice ranks {x,y}<{z} then she must rank {w,x,y}<{w,z}. Lexicographic:the agent always ranks a bundle that contains some item x above any bundle that contains only items ranked lower than x. In the above example, Alice must rank {w,x,y} < {z}.
Necessary Pareto-efficiency Brams, Edelman and Fishburn 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:
If agents' valuations are assumed to be positive, then every allocation giving all items to a single agent is Pareto-ensuring. If Alice's ranking is x>y and George's ranking is y>x, then the allocation [Alice:x, George:y] is Pareto-ensuring. If Alice's ranking is x>y>z and George's ranking is x>z>y and the allocations must be discrete, then the allocation [Alice: x,y; George: z] is Pareto-ensuring. With the above rankings, the allocation [Alice: x, George: y,z] is not Pareto-ensuring. As explained in the introduction, it is not Pareto-efficient e.g. when Alice's valuations for x,y,z are 8,7,6 and George's valuations are 7,1,2. Note that both these valuations are consistent with the agents' rankings. Bouveret, Endriss and Lang. 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:
"X is Pareto-ensuring" is equivalent to "For every consistent bundle ranking, for every other allocation Y, Y does not Pareto-dominate X". "X is NecPE" is equivalent to "For every other allocation Y, for every consistent bundle ranking, Y does not Pareto-dominate X". Exchanging the order of "for all" quantifiers does not change the logical meaning. 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.
… excerpt ends here. Continue reading the full article.
