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

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