Group envy-freeness
Group envy-freeness
- Group envy-freeness (also called: coalition fairness**) 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]].
Group-envy-freeness is a very strong fairness requirement: a group-envy-free allocation is both envy-free and Pareto efficient, but the opposite is not true.
Definitions Consider a set of n agents. Each agent i receives a certain allocation Xi (e.g. a piece of cake or a bundle of resources). Each agent i has a certain subjective preference relation <i over pieces/bundles (i.e. <math>X <_i Y</math> means that agent i prefers piece X to piece Y).
Consider a group G of the agents, with its current allocation <math>\{X_i\}_{i \in G}</math>. We say that group G prefers a piece Y to its current allocation, if there exists a partition of Y to the members of G: <math>\{Y_i\}_{i \in G}</math>, such that at least one agent i prefers his new allocation over his previous allocation (<math>X_i <_i Y_i</math>), and no agent prefers his previous allocation over his new allocation.
Consider two groups of agents, G and H, each with the same number k of agents. We say that group G envies group H if group G prefers the common allocation of group H (namely <math>\cup_{i \in H}{X_i}</math>) to its current allocation.
An allocation {X1, ..., Xn} is called group-envy-free if there is no group of agents that envies another group with the same number of agents.
Relations to other criteria A group-envy-free allocation is also envy-free, since G and H may be groups with a single agent.
A group-envy-free allocation is also Pareto efficient, since G and H may be the entire group of all n agents.
Group-envy-freeness is stronger than the combination of these two criteria, since it applies also to groups of 2, 3, ..., n-1 agents.
Existence In resource allocation settings, a group-envy-free allocation exists. Moreover, it can be attained as a competitive-equilibrium with equal initial endowments.
Alternative definition Aleksandrov and Walsh use the term "group envy-freeness" in a weaker sense. They assume that each group G evaluates its combined allocation as the arithmetic mean of its members' utilities, i.e.:<blockquote> <math>u_G(X_G) := \frac{1}\sum_{i\in G} u_i(X_i)</math></blockquote> and evaluates the combined allocation of every other group H as the arithmetic mean of valuations, i.e.:<blockquote><math>u_G(X_H) := \frac{1}\sum_{i\in G}\sum_{j\in H}u_i(X_j)</math></blockquote>By their definition, an allocation is g,h-group-envy-free (GEFg,h) if for all groups G of size g and all groups H of size h:<blockquote><math>u_G(X_G) \geq u_G(X_H)</math></blockquote>GEF1,1 is equivalent to envy-freeness; GEF1,n is equivalent to proportionality; GEFn,n is trivially satisfied by any allocation. For each g and h, GEFg,h implies GEFg,h+1 and GEFg+1,h. The implications are strict for 3 or more agents; for 2 agents, GEFg,h for all g,h are equivalent to envy-freeness.
By this definition, group-envy-freeness does not imply Pareto-efficiency. They define an allocation X as k-group-Pareto-efficient (GPEk) if there is no other allocation Y that is at least as good for all groups of size k, and strictly better for at least one group of size k, i.e., all groups G of size k: <blockquote><math>u_G(Y_G) \geq u_G(X_G)</math></blockquote>and for at least one groups G of size k: <blockquote><math>u_G(Y_G) > u_G(X_G)</math>.</blockquote>GPE1 is equivalent to Pareto-efficiency. GPEn is equivalent to utilitarian-maximal allocation, since for the grand group G of size n, the utility uG is equivalent to the sum of all agents' utilities. For all k, GPEk+1 implies GPEk. The inverse implication is not true even with two agents. They also consider approximate notions of these fairness and efficiency properties, and their price-of-fairness.