EF1

Dependencies:

1. Fair division
2. Envy-freeness

$\newcommand{\defeq}{:=}$ Let $([n], M, V, w)$ be a fair division instance for indivisible items (where each agent $i$ has entitlement $w_i$). An allocation $A$ is said to be EF1-fair to agent $i$ iff for every agent $j \in [n] \setminus \{i\}$, either $i$ doesn't envy $j$, or for some item $t \in A_i \cup A_j$, we have \[ \frac{v_i(A_i \setminus \{t\})}{w_i} ≥ \frac{v_i(A_j \setminus \{t\})}{w_j}. \] If the above condition is not satisfied for some $j \in [n] \setminus \{i\}$, we say that $i$ EF1-envies $j$.

Dependency for:

1. MXS implies EF1 for n=2
2. EF1 implies PROP1
3. EFX implies EF1
4. Additive chores and binary marginals
5. Additive goods and binary marginals
6. PROP1+M1S allocation doesn't exist
7. MMS+APS doesn't imply PROP1 for chores
8. PROP1 doesn't imply M1S for unit marginals and n=2
9. M1S doesn't imply PROP1
10. PROP doesn't imply M1S for unit-demand valuations
11. MEFS+PROP doesn't imply EEF1 for chores
12. Share vs envy for identical valuations (chores)
13. EF1 doesn't imply PROPx or MXS
14. PROPx doesn't imply M1S
15. EEF doesn't imply EF1
16. Share vs envy for identical valuations (goods)

Info:

• Depth: 5
• Number of transitive dependencies: 5

Transitive dependencies:

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