EF1 and EFX

Dependencies:

1. Fair division
2. Submodular function

In fair division of indivisible goods (equal entitlements), an allocation $A$ is said to be

• EF1-fair to agent $i$ iff \[ v_i(A_i) ≥ \max_{j ≠ i} \begin{cases} \min_{g \in A_j} v_i(A_j \setminus \{g\}) & \textrm{ if } A_j \neq \emptyset \\ 0 & \textrm{ if } A_j = \emptyset\end{cases}. \]
• EFX-fair to agent $i$ iff \[ v_i(A_i) ≥ \max_{j ≠ i} \begin{cases} \max_{g \in A_j} v_i(A_j \setminus \{g\}) & \textrm{ if } A_j \neq \emptyset \\ 0 & \textrm{ if } A_j = \emptyset\end{cases}. \]

Furthermore, if agent $i$'s valuation function is submodular, we say that $A$ is EFX⁰-fair to agent $i$ iff \[ v_i(A_i) ≥ \max_{j ≠ i} \begin{cases} \max_{g \in A_j: v_i(g) > 0} v_i(A_j \setminus \{g\}) & \textrm{ if } A_j \neq \emptyset \textrm{ and } v_i(g) > 0 \textrm{ for some } g \in A_j \\ 0 & \textrm{ otherwise} \end{cases}. \]

It is trivial to see that EF implies EFX, and EFX implies EF1. For submodular valuations, EFX implies EFX⁰.

Some people actually mean EFX⁰ when they say EFX.

EFX was first defined in https://doi.org/10.1145/3355902 (Definition 4.5 in Section 4.2).

Dependency for:

1. MMS implies EFX for two agents (goods)

Info:

• Depth: 4
• Number of transitive dependencies: 5

Transitive dependencies:

1. /sets-and-relations/countable-set
2. σ-algebra
3. Set function
4. Fair division
5. Submodular function