Group envy-freeness

Consider a set of n agents. Each agent i receives a certain allocation X_i (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. ${\displaystyle X<_{i}Y}$ means that agent i prefers piece X to piece Y).

Consider a group G of the agents, with its current allocation ${\displaystyle \{X_{i}\}_{i\in G}}$. 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: ${\displaystyle \{Y_{i}\}_{i\in G}}$, such that at least one agent i prefers his new allocation over his previous allocation (${\displaystyle X_{i}<_{i}Y_{i}}$), 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 ${\displaystyle \cup _{i\in H}{X_{i}}}$) to its current allocation.

An allocation {X₁, ..., X_n} is called group-envy-free if there is no group of agents that envies another group with the same number of agents.

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.

In resource allocation settings, a group-envy-free allocation exists. Moreover, it can be attained as a competitive equilibrium with equal initial endowments.[3][4][2]

In fair cake-cutting settings, a group-envy-free allocation exists if the preference relations are represented by positive continuous value measures. I.e., each agent i has a certain function V_i representing the value of each piece of cake, and all such functions are additive and non-atomic.[1]

Moreover, a group-envy-free allocation exists if the preference relations are represented by preferences over finite vector measures. I.e., each agent i has a certain vector-function V_i, representing the values of different characteristics of each piece of cake, and all components in each such vector-function are additive and non-atomic, and additionally the preference relation over vectors is continuous, monotone and convex.[5]

Aleksandrov and Walsh[6] use the term "group envy-freeness" is used in a weaker sense. They assume that each group G evaluates its combined allocation as the arithmetic mean of its members' utilities, i.e.:

${\displaystyle u_{G}(X_{G}):={\frac {1}{|G|}}\sum _{i\in G}u_{i}(X_{i})}$

and evaluates the combined allocation of every other group H as the arithmetic mean of valuations, i.e.:

${\displaystyle u_{G}(X_{H}):={\frac {1}{|G|\cdot |H|}}\sum _{i\in G}\sum _{j\in H}u_{i}(X_{j})}$

By their definition, an allocation is g,h-group-envy-free (GEF_g,h) if for all groups G of size g and all groups H of size h:

${\displaystyle u_{G}(X_{G})\geq u_{G}(X_{H})}$

GEF_1,1 is equivalent to envy-freeness; GEF_1,n is equivalent to proportionality; GEF_n,n is trivially satisfied by any allocation. For each g and h, GEF_g,h implies GEF_g,h+1 and GEF_g+1,h. The implications are strict for 3 or more agents; for 2 agents, GEF_g,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 (GPE_k) 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:

${\displaystyle u_{G}(Y_{G})\geq u_{G}(X_{G})}$

and for at least one groups G of size k:

${\displaystyle u_{G}(Y_{G})>u_{G}(X_{G})}$.

GPE₁ is equivalent to Pareto-efficiency. GPE_n is equivalent to utilitarian-maximal allocation, since for the grand group G of size n, the utility u_G is equivalent to the sum of all agents' utilities. For all k, GPE_k+1 implies GPE_k. 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.