Article Gists

This website contains summaries of research articles and categorizes them by topics.

  1. Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System [deuermeyer1982scheduling]
    by Bryan L. Deuermeyer, Donald K. Friesen, and Michael A. Langston in SIAM Journal on Algebraic Discrete Methods 1982 doi:10.1137/0603019 ❞
    Topics: scheduling: idMachines maxmin lpt fairDivision: indiv goods idVal additive mms

    Considers the problem of scheduling jobs on $m$ identical machines. Analyzes the approximation ratio of the LPT (longest processing time) algorithm for maximizing the MCT (minimum completion time).

    1. Proves that LPT's MCT is at least $3/4$ times the maximum MCT.
    2. Gives an example for which LPT's MCT is $(3m-1)/(4m-2)$ times the maximum MCT.
  2. The exact LPT-bound for maximizing the minimum completion time [csirik1992exact]
    by János Csirik, Hans Kellerer, and Gerhard Woeginger in Operations Research Letters 1992 doi:10.1016/0167-6377(92)90004-M ❞
    Topics: scheduling: idMachines maxmin lpt fairDivision: indiv goods idVal additive mms

    Analyzes the LPT (longest processing time) algorithm for scheduling jobs on $m$ identical machines. Proves that LPT's MCT (minimum completion time) is at least $(3m-1)/(4m-2)$ times the maximum MCT.

  3. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes [budish2011combinatorial]
    by Eric Budish in Journal of Political Economy 2011 doi:10.1086/664613 ❞
    gist status: incomplete
    Topics: fairDivision: indiv goods ceei mms ef1 marketEquilibrium: ceei
    1. Defines envy-freeness up to one good (EF1).
    2. Defines maximin share (MMS).
  4. Fair Enough: Guaranteeing Approximate Maximin Shares [procaccia2014fair]
    by Ariel D. Procaccia and Junxing Wang in EC 2014 doi:10.1145/2600057.2602835 ❞
    Superseded by [kurokawa2018fair]
    Topics: fairDivision: indiv goods additive mms

    Fair division of $m$ indivisible goods among $n$ agents with additive valuations.

    1. Theorem 2.1: For each $n ≥ 3$, there is an instance where an MMS allocation doesn't exist. $m$ may be exponential in $n$ in this instance.
    2. Introduced approximate MMS.
    3. Section 3: Algorithm for $ρ(1-ε)$-MMS, where $ε ≥ 0$ is a parameter to the algorithm, $ρ = 2n'/(3n'-1)$ $= (2/3)(1 + 1/(3n'-1))$, and $n'$ is the largest odd number such that $n' ≤ n$. The algorithm runs in polynomial time when $n$ and $ε$ are constants and $ε > 0$.
    4. Corollary of Section 3: When $n$ is constant, we can pick $ε = 1/(3n')$ to get $2/3$-MMS in polytime. When $n ∈ \{3, 4\}$, $3/4$-MMS exists.
  5. Approximation Algorithms for Computing Maximin Share Allocations [amanatidis2015approximation]
    by Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi in ICALP 2015 doi:10.1007/978-3-662-47672-7_4 ❞
    Superseded by [amanatidis2017approximation]
    Topics: fairDivision: indiv goods additive mms

    Fair division of $m$ indivisible goods among $n$ agents with additive valuations.

    1. Theorem 3: A simple round-robin-based $O(mn^2 + m^2)$-time algorithm for $1/2$-MMS.
    2. Theorem 4: PTAS for $2/3$-MMS.
    3. Theorem 6: PTAS for $6/7$-MMS for $n=3$.
    4. Theorem 7 and Corollary 1: Let valuations be IID uniform in $[0, 1]$. The Greedy Round Robin algorithm outputs a proportional allocation with probability $1-O(1/n)$ if $m > 2n$ and $n$ is large, and with probability $1-O(\log^2 m / m)$ if $m$ is large.
  6. When Can the Maximin Share Guarantee Be Guaranteed? [kurokawa2016can]
    by David Kurokawa, Ariel Procaccia, and Junxing Wang in AAAI 2016 doi:10.1609/aaai.v30i1.10041 ❞
    Topics: fairDivision: indiv goods additive mms

    Fair division of $m$ indivisible goods among $n$ agents with additive valuations.

    1. Theorem 2.1: $∀n≥3$, there is an example with $≤3n+4$ goods for which an MMS allocation doesn't exist.
    2. Theorem 3.1: Let $c > 0$ be a constant. For each agent $i$, let $D_i$ be a probability distribution supported over $[0, 1]$ such that $\Var(D_i) ≥ c$. Suppose $v_i(g)$ is independently randomly sampled from $D_i$ for each agent $i$ and good $g$. Then $∀ ε>0$, $∃ K$, such that if $\max(n, m) ≥ K$, then an MMS allocation exists with probability $1-ε$ ($K$ depends on $ε$ and $c$).
  7. Characterizing conflicts in fair division of indivisible goods using a scale of criteria [bouveret2016characterizing]
    by Sylvain Bouveret and Michel Lemaître in AAMAS 2016 doi:10.1007/s10458-015-9287-3 ❞
    Topics: fairDivision: indiv goods additive mms prop envyFree ceei minMaxShare egal

    Gives a scale of criteria for fair division of $m$ indivisible goods among $n$ agents with additive valuations.

    1. Propositions 2, 4, 6, 7: MMS ⟹ PROP ⟹ MinMaxShare ⟹ EnvyFree ⟹ CEEI
    2. Proposition 1, 3: The following problems are NP-hard: 1. computing an agent's MMS share. 2. finding an MMS allocation. 3. checking if a PROP allocation exists.
    3. Proposition 10: For sum-normalized valuations, PROP ⟹ Egalitarian.
    4. Proposition 11: For binary valuations, the round-robin algorithm gives an MMS allocation in $O(m^2)$ time.
    5. Proposition 12: For identical valuations, MMS, PROP, envy-freeness, CEEI, and equitability are the same.
    6. Proposition 13: If $n-1$ agents have identical valuations, an MMS allocation exists.
    7. Proposition 14: An MMS allocation exists if the corresponding ordered instance also has an MMS allocation.
    8. Propositions 18, 19, 20: If $m ≤ n+3$, then an MMS allocation exists.
    9. Experiments: Thousands of ordered fair division instances were randomly generated using IID (uniform and gaussion) valuations. MMS allocations were found to always exist.
  8. Approximation Algorithms for Computing Maximin Share Allocations [amanatidis2017approximation]
    by Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi in TALG 2017 doi:10.1145/3147173 arXiv:1503.00941v3 ❞
    Supersedes [amanatidis2015approximation]
    Topics: fairDivision: indiv goods additive mms

    Fair division of $m$ indivisible goods among $n$ agents with additive valuations.

    1. Theorem 3.5: A simple round-robin-based $O(mn^2 + m^2)$-time algorithm for $1/2$-MMS.
    2. Theorem 4.1: PTAS for $2/3$-MMS.
    3. Theorem 5.1: PTAS for $7/8$-MMS for $n=3$.
    4. Theorem 5.5: Algorithm to find an MMS allocation in $O(mn\log m)$ time when valuations are in $\{0, 1, 2\}$.
    5. Theorem 5.6 (without full proof): Reducing the problem of finding an $α$-MMS allocation to the special case of ordered instances.
    6. Theorem 6.2 and Corollary 6.4: Let valuations be IID uniform in $[0, 1]$. The Greedy Round Robin algorithm outputs a proportional allocation with probability $1-O(1/n)$ if $m > 2n$ and $n$ is large, and with probability $1-O(1/m)$ if $m$ is large.
  9. Approximation Algorithms for Maximin Fair Division [barman2017approximation]
    by Siddharth Barman and Sanath Kumar Krishna Murthy in EC 2017 doi:10.1145/3033274.3085136 ❞
    Superseded by [barman2020approximation]
    Topics: fairDivision: indiv goods additive submodular mms efx

    Fair (MMS) division of indivisible goods among n agents.

    1. Theorem 2.1: For non-negative additive valuations, $2n/(3n-1)$-MMS allocations can be found in polynomial time. The algorithm for this first reduces the problem to an ordered instance, and then applies a version of the Envy Cycle Elimination (ECE) algorithm.
    2. Corollary 2.3: For non-negative additive valuations, we can reduce the problem of finding an α-MMS allocation to the special case of an ordered instance using Bouveret and Lemaître's reduction.
    3. Lemma 2.5: For additive and ordered instances of goods, a version of the ECE algorithm outputs an EFX allocation.
    4. Theorem 3.1: For non-negative submodular valuations, we can compute a 1/10-MMS allocation in polynomial time using a simple round-robin algorithm.
  10. Algorithms for Max-Min Share Fair Allocation of Indivisible Chores [aziz2017algorithms]
    by Haris Aziz, Gerhard Rauchecker, Guido Schryen, and Toby Walsh in AAAI 2017 doi:10.1609/aaai.v31i1.10582 ❞
    gist status: abstractOnly
    Topics: fairDivision: indiv chores additive mms

    Fair division of indivisible chores among $n$ agents with additive valuations.

    1. MMS allocations may not exist for 3 agents.
    2. Computing an MMS allocation for chores, if it exists, is strongly NP-hard.
    3. Polynomial-time algorithm for 2-MMS.
    4. New fairness concept: optimal MMS.
    5. PTAS for optimal MMS for constant number of agents.
    6. Efficient heuristic algorithm.
  11. Fair Enough: Guaranteeing Approximate Maximin Shares [kurokawa2018fair]
    by David Kurokawa, Ariel D. Procaccia, and Junxing Wang in JACM 2018 doi:10.1145/3140756 ❞
    Supersedes [procaccia2014fair]
    Topics: fairDivision: indiv goods additive mms

    Fair division of $m$ indivisible goods among $n$ agents with additive valuations.

    1. Theorem 2.1: For each $n ≥ 3$, there is an instance with $m ≤ 3n+4$ where an MMS allocation doesn't exist.
    2. Introduced approximate MMS.
    3. Section 3: Algorithm for $ρ(1-ε)$-MMS, where $ε ≥ 0$ is a parameter to the algorithm, $ρ = 2n'/(3n'-1)$ $= (2/3)(1 + 1/(3n'-1))$, and $n'$ is the largest odd number such that $n' ≤ n$. The algorithm runs in polynomial time when $ε$ is a positive constant.
    4. Corollary of Section 3: When $n$ is constant, we can pick $ε = 1/(3n')$ to get $2/3$-MMS in polytime. When $n ∈ \{3, 4\}$, $3/4$-MMS exists.
  12. Fair Allocation of Indivisible Goods: Improvements and Generalizations [ghodsi2018fair]
    by Mohammad Ghodsi, MohammadTaghi HajiAghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami in EC 2018 doi:10.1145/3219166.3219238 arXiv:1704.00222 ❞
    Topics: fairDivision: indiv goods additive submodular xos subadditive mms

    Fair division of $m$ indivisible goods among $n$ agents, using MMS as the notion of fairness.

    1. Theorem 1.1: additive valuations: PTAS for $3/4$-MMS.
    2. Theorem 4.8: submodular valuations: $1/3$-MMS in polytime.
    3. Theorem 4.1: submodular valuations: For any $n≥2$, there is an instance with $n$ agents and $2n$ goods, where the first $n-1$ agents have the same valuation function and no allocation is better than $3/4$-MMS.
    4. Theorem 1.2: xos valuations: A $1/5$-MMS allocation always exists.
    5. Theorem 1.3: xos valuations: $1/8$-MMS in polytime.
    6. Theorem 4.2: xos valuations: For any $n≥2$, there is an instance with $n$ agents and $2n$ goods, where the first $n-1$ agents have the same valuation function and no allocation is better than $1/2$-MMS.
    7. Theorem 1.5: subadditive valuations: A $(10⌈\log m⌉)^{-1}$-MMS allocation always exists.
    8. Theorem A.6: additive valuations: A $4/5$-MMS allocation always exists for $n=4$.
  13. Comparing Approximate Relaxations of Envy-Freeness [amanatidis2018comparing]
    by Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis in IJCAI 2018 doi:10.24963/ijcai.2018/6 arXiv:1806.03114 ❞
    Topics: fairDivision: indiv goods additive ef1 efx mms pmms

    Relations between fairness notions for division of $m$ indivisible goods among $n$ agents with additive valuations.

    1. Proposiiton 3.1: $∀n≥2$, $∀α∈(0,1]$, $α$-EFX $\implies$ $α$-EF1, and EF1 doesn't imply $α$-EFX, even for identical valuations.
    2. Proposition 3.3: $∀n∈\{2,3\}$, EFX $\implies$ $2/3$-MMS. This is tight, even for identical valuations.
    3. Proposition 3.4: $∀n≥4$, EFX $\implies$ $\frac{4n}{7n-2}$-MMS. EFX doesn't guarantee better than $8/13$-MMS for $n≥4$ and doesn't guarantee better than $301/509$-MMS (≈ 0.5914-MMS) for $n≥1631721$, even for identical valuations.
    4. Proposition 3.5: $∀n≥2$, $∀α∈(0,1)$, $α$-EFX $\implies$ $\frac{αn}{α+2n-2}$-MMS, but is not better than $\frac{2α}{2+α}$-MMS, and not better than $\max(\frac{α}{1+α}, \frac{8α}{11+2α})$-MMS for $n≥4$, even for identical valuations.
    5. Proposition 3.6: $∀n≥2$, $∀α∈(0,1]$, $α$-EF1 $\implies$ $\frac{α}{n-1+α}$-MMS, and this is tight, even for identical valuations.
    6. Proposition 3.7: $∀n≥2$, $∀α∈(0,1]$, $α$-EFX $\implies$ $\frac{2α}{2+α}$-PMMS, and this is tight, even for identical valuations.
    7. Proposition 3.8: $∀n≥3$, $∀α∈(0,1]$, $α$-EF1 $\implies$ $\frac{α}{1+α}$-PMMS, and this is tight.
    8. Corollary 4.2 and Proposition 4.3: $∀n≥4$, PMMS $\implies$ $\frac{4n}{7n-2}$-MMS. PMMS doesn't guarantee better than $8/13$-MMS for $n≥4$ and doesn't guarantee better than $301/509$-MMS (≈ 0.5914-MMS) for $n≥1631721$, even for identical valuations.
    9. Proposition 4.4: $∀n≥3$, $∀α∈(0,1)$, $α$-PMMS $\implies$ $\frac{α}{2(n-1)-α(n-2)}$-MMS, but is not better than $\frac{α}{n-1-α(n-2)}$-MMS, even for identical valuations.
    10. Propositions 4.5 and 4.7: $∀n≥3$, $∀β∈(0,1]$, an MMS allocation is not guaranteed to be $β$-PMMS or $β$-EF1.
    11. Proposition 4.6: $∀n≥2$, $∀α∈(0,1)$, $α$-PMMS $\implies$ $\frac{α}{2-α}$-EF1, and this is tight, even for identical valuations.
    12. Proposition 4.8: $∀n≥2$, $∀α,β∈(0,1)$, $α$-PMMS doesn't guarantee $β$-EFX, even for identical valuations.
  14. On Maximin Share Allocations in Matroids [gourves2019maximin]
    by Laurent Gourvès and Jérôme Monnot in TCS 2019 doi:10.1016/j.tcs.2018.05.018 ❞
    gist status: incomplete
    Topics: fairDivision: indiv goods additive mms matroids

    Fair division of $m$ indivisible goods among $n$ agents with additive valuations and matroid constraints: Polytime algorithm for $1/2$-MMS, PTAS for MMS for $n=2$, PTAS for $8/9$-MMS for $n=3$.

  15. The Unreasonable Fairness of Maximum Nash Welfare [caragiannis2019unreasonable]
    by Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang in TEAC 2019 doi:10.1145/3355902 ❞
    Topics: fairDivision: indiv goods additive nashOpt PO EF1 mms pmms EFX

    Fair division of $m$ indivisible goods among $n$ agents with additive valuations.

    1. Theorem 3.2: A NashOpt allocation is also EF1+PO.
    2. Theorem 4.1: A NashOpt allocation is $π_n$-MMS, where $π_n = 2/(1+\sqrt{4n-3})$. For any $ε > 0$, no NashOpt allocation is $(π_n+ε)$-MMS.
    3. Pairwise maximin share (PMMS):
      1. Definition 4.3: α-PMMS.
      2. Example 4.4 (part 1): An instance with 3 agents and 5 identical goods, where some MMS allocation is not PMMS.
      3. Example 4.4 (part 2): An instance with 3 agents, 7 goods, and identical valuations where some PMMS allocation is not MMS.
      4. Theorem 4.6: An envy-free allocation is PMMS. A PMMS allocation is EFX + $1/2$-MMS.
      5. Corollary 4.7: A NashOpt allocation is $π_2$-PMMS, where $π_2 = (\sqrt{5}-1)/2 ≈ 0.618$. For any $ε > 0$, no NashOpt allocation is $(π_2+ε)$-PMMS.
    4. Appendix B: The elusive combination of EF1 and PO:
      1. Example B.1: Instance with 3 agents and 31 goods where rounding any divisible MNW allocation violates EF1.
      2. Example B.2 (part 1): Instance with 2 agents, 3 goods, and valuations normalized to sum to 1, where the unique max social welfare allocation is not EF1.
      3. Example B.2 (part 2): Instance with 3 agents, 4 goods, and valuations normalized to sum to 1, where the unique max egalitarian allocation is not EF1.
      4. Example B.3 (part 1): Instance with 4 agents, 10 goods, and valuations normalized to sum to 1, where the unique max social welfare allocation subject to EF1 is not PO.
      5. Example B.3 (part 2): Instance with 3 agents, 3 goods, and valuations normalized to sum to 1, where there is an allocation that is both max egal welfare and EF1, but not PO.
      6. Theorem B.5: Every EF1+PO allocation is $1/n$-MMS. For each $n≥1$, there exists an instance with $n$ agents and $2n-1$ goods for which some EF1+PO allocation gives some agent exactly $1/n$ of her MMS.
    5. Appendix C: General valuations:
      1. Theorem 3.3 (part 1): There is an instance with 2 agents, 4 goods, and identical subadditive valuations for which no allocation is EF1+PO.
      2. Theorem 3.3 (part 2): There is an instance with 2 agents, 4 goods, and identical superadditive (and hence supermodular) valuations for which no allocation is EF1+PO.
      3. Example C.3: An instance with 2 agents, 4 goods, and (non-identical) submodular valuations for which the unique MNW allocation is not EF1.
      4. Definition 3.4 and Theorem 3.5: For submodular valuations, every MNW allocation is MEF1+PO.
    6. Appendix D: Spectrum of Fair and Efficient Solutions
  16. Approximation Algorithms for Maximin Fair Division [barman2020approximation]
    by Siddharth Barman and Sanath Kumar KrishnaMurthy in TEAC 2020 doi:10.1145/3381525 ❞
    Supersedes [barman2017approximation]
    Topics: fairDivision: indiv goods chores additive submodular mms efx

    Fair (MMS) division of indivisible goods or chores among $n$ agents.

    1. Theorem 3.1: For non-negative additive valuations, $2n/(3n-1)$-MMS allocations can be found in polynomial time. The algorithm for this first reduces the problem to an ordered instance, and then applies a version of the Envy Cycle Elimination (ECE) algorithm.
    2. Corollary 3.3: For additive valuations (for either goods or chores), we can reduce the problem of finding an α-MMS allocation to the special case of an ordered instance using Bouveret and Lemaître's reduction.
    3. Lemma 3.5: For additive and ordered instances of goods, a version of the ECE algorithm outputs an EFX allocation.
    4. Theorem 4.1: For non-negative submodular valuations, we can compute a $\frac{1}{3}(1-\frac{1}{e})$-MMS allocation (≈ 0.2107-MMS) in polynomial time using a simple round-robin algorithm.
    5. Theorem A.2: For non-positive additive valuations, $(4n-1)/3n$-MMS allocations can be found in polynomial time. The algorithm for this first reduces the problem to an ordered instance, and then applies a version of the Envy Cycle Elimination (ECE) algorithm.
    6. Section B.1: Consider a fair division instance with $n$ agents, $2n-1$ goods, and additive identical valuations, where $n-1$ goods have value $n$ and $n$ goods have value 1. Then there is an EF1 allocation that is not better than $1/n$-MMS.
    7. Section B.2: There is a fair division instance with 2 agents, 4 goods, and submodular valuations, for which no allocation is better than $3/4$-MMS.
  17. Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination [amanatidis2020multiple]
    by Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos in TCS 2020 doi:10.1016/j.tcs.2020.07.006 arXiv:1909.07650 ❞
    Topics: fairDivision: indiv goods additive GMMS EF1 EFX PMMS

    Fair division of $m$ indivisible goods among $n$ agents with additive valuations. Let $ϕ = (\sqrt{5}+1)/2$.

    1. Algorithm 3: EF1 + $(ϕ-1)$-EFX (≈ 0.6180-EFX) + $\frac{2}{ϕ+2}$-GMMS (≈ 0.5529-GMMS) + $2/3$-PMMS in polytime.
    2. Theorem 4.7: EF1 + $3/5$-EFX + $4/7$-GMMS (≈ 0.5714-GMMS) + $2/3$-PMMS in polytime.
    3. Theorem 4.10: $\frac{2}{2ϕ-1}$-EF1 (≈ 0.894-EF1) + $(ϕ-1)$-EFX + $\frac{2}{ϕ+2}$-GMMS + $\frac{4ϕ-2}{2ϕ+3}$-PMMS (≈ 0.7171-PMMS) in polytime.
    4. Theorem 5.1: For $m ≤ n+2$, a GMMS allocation always exists and can be computed in polytime.
    5. Proposition 5.5: For any integers $n ≥ 2$ and $k ≥ 1$ and real numbers $α, β ∈ (0, 1)$, there is an instance with $n$ agents and $n + 4k$ goods, for which some allocation is $α$-GMMS but not $β$-EFX and not better than $\frac{α}{2-α}$-EF1 or $α$-PMMS.
  18. An Algorithmic Framework for Approximating Maximin Share Allocation of Chores [huang2021algorithmic]
    by Xin Huang and Pinyan Lu in EC 2021 doi:10.1145/3465456.3467555 arXiv:1907.04505v4 ❞
    Topics: fairDivision: indiv chores additive mms

    Fair division of indivisible chores among $n$ agents with additive valuations.

    1. Section 4: PTAS for 11/9-MMS.
    2. Example 4.1: Example with 4 agents, 14 chores, and identical valuations showing that their algorithm cannot give better than 20/17-MMS even for identical valuations.
    3. Section 5: 5/4-MMS in $O(mn\log m + n^2)$ time.
    4. Section 6: 11/9-MMS in $O(m\log m + n)$ time for identical valuations.
  19. Fair-Share Allocations for Agents with Arbitrary Entitlements [babaioff2021fair]
    by Moshe Babaioff, Tomer Ezra, and Uriel Feige in EC 2021 doi:10.1145/3465456.3467559 arXiv:2103.04304v4 ❞
    Topics: fairDivision: indiv goods chores mixedManna additive unequalEntitlements aps tps pessShare mms wmms

    For fair division of $m$ indivisible goods among $n$ agents with possibly unequal entitlements and additive valuations, this paper proposes a new notion of fairness called AnyPrice Share (APS), and shows how to compute an approximate APS allocation. Agent $i$ has entitlement $b_i$, where $\sum_{i=1}^n b_i = 1$.

    1. Definitions
      1. Definition 1.1: AnyPrice Share (APS), defined as a price-and-choose guarantee. The definition works even for non-additive valuations.
      2. Definition 3.1: AnyPrice Share, defined as a linear programming relaxation of MMS. The definition works even for non-additive valuations.
      3. Proposition 3.2: The two definitions of APS are equivalent.
      4. Section 1: Coined the term PessShare for a notion defined elsewhere.
    2. Theorem 1.3: Polytime algorithm for $\max(\frac{3}{5}, \frac{1}{2-b_i})$-APS.
    3. greedyEFX
      1. Theorem 1.4: Polytime algorithm (called greedyEFX) for $\frac{2}{3}(1 + \frac{1}{3n-1})$-APS (same algorithm as [barman2020approximation]: reduce to ordered instance and then use Envy Cycle Elimination).
      2. Proposition 5.5: For every $ε > 0$, there is an example with equal entitlements where greedyEFX outputs an allocation that is not $(2/3+ε)$-MMS.
      3. Theorem E.5: For equal entitlements and identical valuations, greedyEFX outputs a $3/4$-APS allocation.
      4. Proposition E.9: Example with $m = 3n-1$, equal entitlements, and identical valuations, where greedyEFX's output is not better than $\frac{3}{4}(1 + \frac{5}{24n-9})$-MMS.
    4. Relationships among fairness notions
      1. Observation 3.4: A CE (competitive equilibrium) allocation is an APS allocation.
      2. Proposition 3.7: Prop ≥ APS ≥ PessShare ≥ APS/2. For each inequality, there is an example where it holds as equality. For each inequality, there is an example with equal entitlements where it holds as a strict inequality.
      3. Lemma C.1: There is an example with $n=3$, $m=15$, equal entitlements, and identical valuations, where APS = 97 and MMS ≤ 96.
      4. Unproven claim: For equal entitlements, PessShare = MMS.
      5. Observation 3.8: For 2 agents with equal entitlements, APS = MMS. (Hence, computing APS is NP-hard.)
      6. Remark C.3: Example with $n=2$, $m=6$, equal entitlements, and submodular valuations, for which MMS = 5 and APS = 6. Another similar example with subadditive valuations instead, for which MMS = 3 and APS = 6.
      7. Corollary 5.4: For equal entitlements, APS ≤ (4/3)MMS.
      8. Proposition 4.2: TPS ≥ APS.
    5. Observation 3.9: APS allocation exists for $n=2$.
    6. Proposition 3.10: Algorithm for computing an agent's APS in pseudopolynomial time.
    7. Section 1: Why Weighted MMS (WMMS) is a bad notion of fairness.
    8. Section 1: Maximizing weighted NSW can give a bad output, even for $n = m = 3$.
    9. Observation 3.3: There is an optimal solution for APS' LP where the support has size at most $m$.
    10. Chores and Mixed Manna
      1. Definition F.1: APS for mixed manna defined as LP.
      2. Proposition F.2: $v([m]) ≥ 0$ implies APS ≥ 0 for mixed manna, even for non-additive valuations.
      3. Remark F.3: APS is a quasiconcave function of the entitlement for mixed manna.
      4. Proposition F.4: For chores, APS ≤ $\min_c v(c)$.
      5. Proposition F.5: For mixed manna, APS ≤ PROP.
      6. Proposition F.6: 2-APS allocation exists for chores.
      7. Definition F.7: Price-and-choose definition of APS for chores.
      8. Unproven claim: For chores, the two definitions of APS are equivalent.
  20. A Little Charity Guarantees Almost Envy-Freeness [chaudhury2021little]
    by Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa in SJoC 2021 doi:10.1137/20M1359134 ❞
    Topics: fairDivision: indiv goods efx charity mms gmms nashWelfare

    Fair division of a set $M$ of $m$ indivisible goods among $n$ agents (general monotone valuations).

    1. Section 1.2: Example with 3 agents, 4 goods, and additive valuations for which bundle-splitting is necessary.
    2. Algorithm 2.1: Takes as input any partial EFX allocation $Y$ (default value of $Y$ is the empty allocation) and outputs another partial allocation $X$ and a set $P$ of unallocated goods such that all of these hold:
      1. $X$ is EFX.
      2. $|P| < n$.
      3. $v_i(X_i) ≥ v_i(P)$ for each agent $i$.
      4. $v_i(X_i) ≥ v_i(Y_i)$ for each agent $i$.
      5. The algorithm runs in at most $m + mnV/Δ$ iterations, and each iteration uses at most $mn$ value queries, where $V = \max_i v_i(M)$ and $Δ = \min_i\min_{S,T: v_i(S)≠v_i(T)} |v_i(S)-v_i(T)|$.
      6. Proposition 3.1: When valuations are additive, $v_i(X_i) ≥ \frac{\MMS_i(M, n)}{2-|P|/n}$ for each agent $i$.
      7. Theorem 3.5: When valuations are additive, $(X_1 ∪ P, X_2, …, X_n)$ is $4/7$-GMMS and $1/2$-EFX.
    3. An algorithm parametrized by $ε > 0$ that outputs a partial allocation $X$ and a set $P$ of unallocated goods such that all of these hold:
      1. $X$ is $(1+ε)^{-1}$-EFX.
      2. $|P| < n$.
      3. $v_i(X_i) ≥ v_i(P)/(1+ε)$ for each agent $i$.
      4. The algorithm runs in $O((mn/ε)\log(V/Δ))$ iterations, and each iteration uses at most $mn$ value queries, where $V = \max_i v_i(M)$ and $Δ = \min_i\min_{S,T: v_i(S)≠v_i(T)} |v_i(S)-v_i(T)|$.
    4. For additive valuations, by picking $Y$ appropriately in Algorithm 2.1, its output $X$ satisfies $v_i(X_i) ≥ v_i(X^*)/2$, where $X^*$ is the maximum Nash welfare allocation.
  21. A Tight Negative Example for MMS Fair Allocations [feige2022tight]
    by Uriel Feige, Ariel Sapir, and Laliv Tauber in WINE 2021 doi:10.1007/978-3-030-94676-0_20 arXiv:2104.04977 ❞
    Topics: fairDivision: indiv goods chores additive mms

    Fair division of $m$ indivisible goods (or chores) among $n$ agents with additive valuations, using MMS as the notion of fairness.

    1. Theorem 1: An example with 3 agents and 9 goods where no allocation is better than 39/40-MMS.
    2. Theorem 2: For at most $n+5$ goods, an MMS allocation exists.
    3. Theorem 3: For at most 9 goods, some allocation is 39/40-MMS or better.
    4. Theorem 4: For each $n ≥ 4$, there is an instance with at most $3n+1+2(n\%2)$ goods for which no allocation is better than $(1-(⌈\frac{n}{2}⌉+1)^{-4})$-MMS. Furthermore, the instance has these properties:
      1. There are 2 kinds of valuation functions.
      2. There is a set $S$ of at most 11 positive integers such that $v_i(g) ∈ S$ for all $i$ and $g$.
      3. There is a set $S$ of goods such that $|S| ≤ 2⌈\frac{n}{2}⌉ + 3$, every good outside $S$ has the same value for each agent, and for each good $g ∈ S$ and every pair $(i,j)$ of agents, $|v_i(g) - v_j(g)| ≤ 1$.
      4. Each agent has an MMS partition where each bundle has total value $f(⌈\frac{n}{2}⌉+2)$, where $f(x) = x^2(x-2)^2+x ∈ ((x-2)^4, (x-1)^4)$.
    5. Theorem 5: Example with 3 agents and 9 chores for which no allocation is better than 44/43-MMS.
    6. Unproven claim: For at most 8 chores, an MMS allocation exists.
    7. Unproven claim: For at most 9 chores, some allocation is 44/43-MMS or better.
  22. Ordinal Maximin Share Approximation for Chores [hosseini2022ordinal]
    by Hadi Hosseini, Andrew Searns, and Erel Segal-Halevi in AAMAS 2022 arXiv:2201.07424 https://www.ifaamas.org/Proceedings/aamas2022/pdfs/p597.pdf ❞
    Topics: fairDivision: indiv chores additive mms

    Fair division of indivisible chores to $n$ agents. Fairness notion: 1-out-of-$d$ MMS.

    1. Strongly polynomial-time algorithm for 1-out-of-$\lfloor 2n/3 \rfloor$ MMS.
    2. 1-out-of-$\lfloor 3n/4 \rfloor$ MMS allocations always exist.
    3. Polynomial-time algorithm for 1-out-of-$\lfloor 3n/4 - O(\log n) \rfloor$ MMS.
  23. On Best-of-Both-Worlds Fair-Share Allocations [babaioff2022best]
    by Moshe Babaioff, Tomer Ezra, and Uriel Fiege in WINE 2022 doi:10.1007/978-3-031-22832-2_14 arXiv:2102.04909 ❞
    Topics: fairDivision: indiv goods additive exAnte PROP MMS fPO PO PROP1 TPS

    Fair and efficient division of $m$ indivisible goods among $n$ agents with additive valuations.

    1. An example with $m=2n-1$ for which [aziz2023best]'s algorithms give some agent at most $(2+ε)/n$ times her MMS.
    2. New fairness notion: TPS:
      1. ProportionalShare ≥ TPS ≥ MMS ≥ $\frac{n}{2n-1}$TPS. Every inequality holds as an equality for some instance and strict inequality for some instance.
      2. Every half-fair allocation is $n/(2n-1)$-TPS.
      3. The Envy-Cycle Elimination algorithm's output is half-fair.
      4. EFX allocations are half-fair.
      5. For $2n-1$ identical goods, in every allocation, some agent gets $n/(2n-1)$ times her TPS.
    3. Theorem 7: A polytime algorithm whose output is a distribution of at most $n$ allocations that is ex ante PROP + ex post 1/2-TPS + ex post PROP1.
    4. Proposition 8: For every $n ≥ 2$ and $ε > 0$, there is a fair division instance such that for any ex ante fPO distribution of allocations, every allocation in that distribution gives some agent at most $(1+ε)/n$ times her MMS.
    5. Corollary 9: There is a randomized allocation of support at most $n$ that is ex ante PROP + ex post 1/2-TPS + ex post PO.
    6. Appendix D: For 2 agents, the output of the cut-and-choose protocol with a random cutter is ex ante EF + ex post MMS + ex post EFX + ex post $2/3$-TPS.
    7. Theorem 22: Randomized polytime algorithm whose output is ex ante $\frac{n}{2n-1}$-PROP, ex post $\frac{n}{2n-1}$-TPS, and ex post EF1.
  24. Fair Shares: Feasibility, Domination and Incentive [babaioff2022fair]
    by Moshe Babaioff and Uriel Feige in EC 2022 doi:10.1145/3490486.3538286 arXiv:2205.07519 ❞
    Topics: fairDivision: indiv goods additive shares mms

    Considers fair division of $m$ indivisible goods among $n$ agents. This paper initiates a systematic study of feasible shares.

    1. Section 1.1: Definitions: Fix a class of valuations and the number $n$ of agents. The definitions also work for mixed-manna.
      1. For a valuation function $v: 2^{[m]} → ℝ$, a share $s$ maps the pair $(v, n)$ to a number in interval $[α, β]$, where $α$ is the value of the minimum-value bundle and $β$ is the value of the maximum-value bundle. For a set $S$ of shares and a real number $ρ$, define $ρS = \{ρs: s ∈ S\}$.
      2. For a share, defines feasibility, legibility (polytime computability), and self-maximizability. Let $S_F$, $S_M$, $S_C$ be the set of feasible, self-maximizing, and polytime computable shares, respectively.
      3. For shares $s_1$ and $s_2$, $s_1$ dominates $s_2$ (denoted as $s_1 ⪰ s_2$) iff for every valuation function $v$, we have $s_1(v, n) ≥ s_2(v, n)$. Share $s$ dominates a set $S$ of shares (denoted as $s ⪰ S$) iff $s ⪰ s'$ for all $s' ∈ S$.
      4. Two examples of feasibile, polytime-computable, and self-maximizing shares, where one dominates the other.
    2. Proposition 4: MMS $⪰ S_F$. Moreover, if the MMS is feasible, then it is the unique dominator of $S_F$, and the unique dominator of $S_F ∩ S_M$.
    3. Theorem 1: Let C be a class of valuations containing additive valuations. For C, there is no feasible share dominating $S_F ∩ S_M$.
    4. Theorem 2: Every feasible share is dominated by some feasible self-maximizing share.
    5. Proposition 6:
      1. $s ⪰ ρ$MMS $⟺ s ⪰ ρS_F ⟺ s ⪰ ρ(S_F ∩ S_M)$.
      2. For additive valuations, $s ⪰ ρ(S_F ∩ S_M ∩ S_C) ⟺ s ⪰ ρ$MMS.
    6. Theorem 3: For additive valuations, there is a share in $S_F ∩ S_M ∩ S_C$ that dominates $ρS_F$, where $ρ = 2n/(3n-1)$, and $ρ = 4/5$ for $n ≤ 4$. For any $ε > 0$, there is a share in $S_F ∩ S_M ∩ S_C$ that dominates $(1-ε)S_F$ for $n=2$.
    7. $F$-maximin shares (additive valuations only):
      1. Definition 5: Let $F$ be a family of partitions of $[m]$.
        1. The $F$-maximin share for valuation $v$ is $\max_{P ∈ F} \min_{j=1}^n v'(P_j)$, where $v'$ is the ordered valuation for $v$.
        2. The $F$-maximin partition for ordered valuation $v$ is $\arg\max_{P ∈ F} \min_{j=1}^n v(P_j)$.
        3. An allocation that gives every agent their $F$-maximin share is called an $F$-maximin allocation.
      2. Observation 17: For $n=2$, every $F$-maximin share is feasible, and if an $F$-maximin partition can be computed in polynomial time, then an $F$-maximin allocation can also be computed in polynomial time.
      3. Proposition 7: For additive valuations, every $F$-maximin share is self-maximizing.
    8. Nested share (additive valuations only):
      1. Section 6.3: The nested share for $n$ agents, parametrized by $q ∈ \{0, 1, …, n\}$, is denoted as $\NestShare_{n,q}$ ($\NestShare_q$ when $n$ is clear from context). It is defined as an $F$-maximin share. Let $ρ(n,q) := \inf_v \frac{\NestShare_{n,q}(v)}{\MMS^n(v)}$ (hence, $\NestShare_{n,q} \succeq ρ(n,q)\MMS^n(v)$).
      2. $\NestShare_n(v) ≥ \NestShare_{n-1}(v) ≥ … ≥ \NestShare_1(v) = \NestShare_0(v)$ for all $v$. Hence, $ρ(n,n) ≥ … ≥ ρ(n, 1) = ρ(n, 0)$.
      3. Example 1: For $n=4$ and goods of (additive) values [3, 3, 2, 2, 2, 2, 2, 2, 1, 1], MMS is 5 but $\NestShare_q$ is 4 for all $q$.
      4. Theorem 6: $\NestShare_3 ∈ S_F ∩ S_M ∩ S_C$, and an $\NestShare_3$-allocation can be computed in polynomial time. Furthermore, $\NestShare_3 \succeq \frac{2n}{3n-1}$MMS, and for $n≤4$, $\NestShare_3 \succeq (4/5)$MMS.
      5. Lemma 18: $\NestShare_q$ can be computed in $O(m^4\log m)$ time using dynamic programming.
      6. Lemma 19: $ρ(n,1) ≥ \frac{2n}{3n-1}$ (and hence $\NestShare_1 \succeq \frac{2n}{3n-1}$MMS).
      7. Proposition 26 (adapted from [babaioff2021fair]): $∀ ε>0, ∀ q≥1, ∃ n, ∃$ additive $v$, such that $\NestShare_{n,q}(v) ≤ (2/3+ε)\MMS^n(v)$.
      8. Lemma 9: An $\NestShare_{q,q}$ allocation exists implies that an $\NestShare_{n,q}$ allocation exists for all $n ≥ q$. Furthermore, if we can compute an $\NestShare_{q,q}$ allocation in $T(m,q)$ time, we can compute an $\NestShare_{n,q}$ allocation in $T(m-n+q,q) + O(mn)$ time (assuming $\NestShare_{n,q}$ for the entire set of goods has already been computed for each agent).
      9. Lemmas 10 and 11: For $n=3$, given every agent's $\NestShare_3$ partition, an $\NestShare_3$ allocation can be computed in $O(m)$ time.
      10. Lemmas 20, 21, 23, 24: $ρ(2,1) = 4/5$, $ρ(2,2) = 5/6$, $ρ(3,2) = 4/5$, $ρ(4,3) = 4/5$.
      11. Proposition 27: $ρ(3,3) ≤ 5/6$, $ρ(3,1) ≤ 0.7693$. For $n ≥ 4$, $ρ(n, n-2) ≤ 3/4$ and $ρ(n,n) ≤ 4/5$.
  25. Improved maximin fair allocation of indivisible items to three agents [feige2022improved]
    by Uriel Feige and Alexey Norkin 2022 arXiv:2205.05363 ❞
    gist status: abstractOnly paper status: unpublished
    Topics: fairDivision: indiv goods chores additive mms

    Fair division of $m$ indivisible items among 3 agents with additive valuations.

    1. An allocation of goods exists where agent 1 gets at least her proportional share and the other agents get at least 11/12 of their maximin share.
    2. An allocation of chores exists where agent 1 gets at most her proportional share and the other agents get at most 19/18 of their maximin share.
  26. EFX Allocations: Simplifications and Improvements [akrami2023efx]
    by Hannaneh Akrami, Chaudhury Bhaskar Ray, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta in EC 2023 arXiv:2205.07638 ❞
    gist status: abstractOnly paper status: toBePublished
    Topics: fairDivision: indiv goods EFX charity nashWelfare

    Fair division of $m$ indivisible goods among $n$ agents with general monotone valuations.

    1. Definition 2: A new class of valuations, called MMS-feasible valuations, that generalize additive and nice-cancelable valuations.
    2. Theorem 2: EFX allocations exist when $n=3$ and at least one agent has an MMS-feasible valuation function.
    3. Theorem 4: A polytime algorithm to find a partial $(1-ε)$-EFX allocation $X$ where no agent envies the charity bundle and the number of unallocated goods is $\widetilde{O}(\sqrt{n/ε})$. Furthermore, $X$ is $1/2$-MNW.
  27. Best of Both Worlds: Ex Ante and Ex Post Fairness in Resource Allocation [aziz2023best]
    by Haris Aziz, Rupert Freeman, Nisarg Shah, and Rohit Vaish in Operations Research 2023 doi:10.1287/opre.2022.2432 ❞
    Topics: fairDivision: indiv goods additive exAnte EF EF1 PO fPO PROP1 EF1MaL nashOpt

    Fair and efficient division of $m$ indivisible goods among $n$ agents with additive valuations.

    1. Defines (with citation) the following notions of fairness and efficiency:
      1. SD-EF and SD-EF1, which are stronger notions than EF and EF1, respectively.
      2. SD-Efficient (aka ordinally efficient), which is a weaker notion than fPO.
      3. PROP1 and EF1MaL.
    2. Proposition 1: An ex ante fPO allocation is also ex post fPO.
    3. Theorem 3: Algorithm to find a distribution of allocations that is ex ante SD-EF + ex post SD-EF1 + ex ante SD-Efficient in $O((m+n)^{9/2})$ time and having support at most $(m+n-1)^2 + 1$.
    4. An ex ante NashOpt allocation is also ex ante Group Fair, which implies ex ante EF + ex ante fPO.
    5. Theorem 8: Strongly polytime algorithm to find a distribution of allocations that is ex ante NashOpt + ex post PROP1 + ex post EF1MaL.
    6. Impossibility results:
      1. Theorem 4: Example with $n=2$ and $m=4$ for which no allocation is ex ante SD-EF + ex post EF1 + ex post PO.
      2. Theorem 5: Example with $n=m=2$ for which no allocation is ex ante PROP + ex post EF1 + ex post fPO.
      3. Theorem 6: Example with $n=m=2$ for which no allocation is ex ante SD-EF + ex ante fPO.