Maximin share allocations

Dependencies:

  1. Fair division
  2. Maximin share of a set function

Consider a fair division instance with $n$ agents, equal entitlements, and a set $M$ of items. $\MMS_{v_i}^n(M)$ is called agent $i$'s maximin share. An allocation $A$ is MMS-fair to agent $i$ if $v_i(A_i) ≥ \MMS_{v_i}^n(M)$. For $\alpha \in [0, 1]$, $A$ is $\alpha$-MMS-fair to agent $i$ if $v_i(A_i) ≥ \alpha\MMS_{v_i}^n(M)$. Often, for brevity, we write $\MMS_i$ instead of $\MMS_{v_i}^n(M)$.

For non-equal entitlements, there are two variants: weighted MMS (WMMS) and pessimistic share (pessShare).

Let $\Pi^n(M)$ be the set of all $n$-partitions of $M$. (If the fair division instance is constrained, as in contiguous cake cutting, then we require each part to be feasible.) Agent $i$'s weighted maximin share is \[ \mathrm{WMMS}_i := w_i \sup_{X \in \Pi^n(M)} \min_{j=1}^n \frac{v_i(X_j)}{w_j}. \] Allocation $A$ is WMMS-fair to agent $i$ if $v_i(A_i) \ge \mathrm{WMMS}_i$. For discrete fair division, \[ \arg\max_{X \in \Pi^n(M)} \min_{j=1}^n \frac{v_i(X_j)}{w_j} \] is called the WMMS partition.

Let $1 ≤ \ell ≤ d$. Let $\Pi^d(M)$ be the set of all $d$-partitions of $M$. Then agent $i$'s $\ell$-out-of-$d$ share is defined as \[ \textrm{$\ell$-out-of-$d$-share}_i := \sup_{X \in \Pi^d(M): v_i(X_j) \le v_i(X_{j+1}) \forall j \in [d-1]} \sum_{j=1}^{\ell} v_i(X_j). \] Then agent $i$'s pessimistic share is defined as \[ \mathrm{pessShare}_i := \sup_{1 ≤ \ell ≤ d: \ell / d ≤ w_i} \textrm{$\ell$-out-of-$d$-share}_i. \] Allocation $A$ is pessShare-fair to agent $i$ if $v_i(A_i) \ge \mathrm{pessShare}_i$.

For equal entitlements, it's trivial to show that $\mathrm{WMMS}_i = \MMS_i$. One can also show that $\mathrm{pessShare}_i = \MMS_i$ for equal entitlements.

Proof

For equal entitlements, we have $w_i = 1/n$. The $1$-out-of-$n$-share is the same as MMS, so $\mathrm{pessShare}_i \ge \MMS_i$.

Now pick $d$ such that $\ell/d \le 1/n$, i.e., $d ≥ \ell n$. For any $X \in \Pi^d(M)$ such that $v_i(X_j) \le v_i(X_{j+1})$ for all $j \in [d-1]$. Now create $Y \in \Pi^n(M)$ where $Y_k = \bigcup_{j=(k-1)n + 1}^{kn} X_j$ for $k \in [n-1]$ and $Y_n = M \setminus \bigcup_{j=1}^{n-1} Y_j$. By definition of MMS, we get $\sum_{j=1}^{\ell} v_i(X_j) = v_i(Y_1) \le \MMS_i$. Since this is true for all such $X$, we get that $\ell$-out-of-$d$-share$_i \le \MMS_i$ whenever $\ell / d \le 1/n$. Hence, $\mathrm{pessShare}_i \le \MMS_i$.

Dependency for:

  1. EFX doesn't imply MMS
  2. EF doesn't imply PROP for supermodular valuations
  3. APS and MMS don't imply PROPm
  4. Share vs envy for identical valuations (goods)
  5. GMMS doesn't imply APS
  6. Share vs envy for identical valuations (chores)
  7. MMS+APS doesn't imply PROP1 for chores
  8. APS can be > MMS
  9. MMS is largest bundle value at most PROP when n=2
  10. WMMS-sat and envious of everyone implies EFX-sat
  11. Additive goods and binary marginals
  12. Additive chores and binary marginals
  13. PROP1+M1S allocation doesn't exist
  14. PROPm doesn't exist for mixed manna
  15. APS = MMS for n=2
  16. PROP implies WMMS and pessShare
  17. APS implies pessShare
  18. WMMS implies EFX for two agents
  19. MMS implies EEFX
  20. Leximin implies GMMS for idval
  21. MMS implies MXS

Info:

Transitive dependencies:

  1. /analysis/sup-inf
  2. /sets-and-relations/countable-set
  3. σ-algebra
  4. Set function
  5. Fair division
  6. Maximin share of a set function