PaperlayerView exact revision on arXiv

Source-linked AI summary

Maximin Share Allocations Beyond Weakly Lexicographic Valuations

Nicholas Teh

arXiv:2610.00159v1cs.GT

TL;DR

Exact maximin-share allocations need not exist for general additive valuations, so the paper asks which structured valuation domains guarantee them. It gives an algorithm for agents with a few-valued lower part and arbitrarily many higher classes that dominate lower goods. The algorithm computes an exact MMS allocation in O(nm log^2(2 + m)) time.

  • Problem

    Exact MMS allocations need not exist for general additive valuations, motivating the search for valuation domains where the full guarantee can be attained.

    Source: §1 · p. 1

  • Method

    The algorithm repeatedly selects a rightmost acceptable bundle by lexicographically maximizing its increasing rank vector and relies on target-partition preservation across added higher classes.

    Source: §1.1 · p. 2, §3 · p. 5

  • Results

    O(nm log^2(2 + m)) time computes an exact MMS allocation when each agent’s lower values come from one of three specified families and higher classes meet the dominance condition.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    The result permits additive tradeoffs among lower goods alongside arbitrarily many agent-specific higher classes, extending exact-MMS guarantees beyond weakly lexicographic valuations.

    Source: §6 · p. 9

    The higher-class condition cannot generally be weakened to requiring each class value to be merely (1 − ε) times the total lower value; the example limits the algorithm’s guarantee, not MMS existence.

    Source: §6 · p. 9

Abstract

from arXiv · show

We study the fair division of indivisible goods among agents with nonnegative additive valuations. An agent's maximin share (MMS) is the value she can guarantee by partitioning the goods into as many bundles as there are agents and receiving a least-valued bundle. We prove the existence of exact MMS allocations for a valuation domain that generalizes several few-valued domains as well as weakly lexicographic valuations. For each agent, the lower-valued goods, after a positive rescaling, may take values in $\{0,1,d,d+1\}$, $\{0,1,2,2e\}$, or $\{0,1,2,3,4\}$, where $d,e\ge 2$ are integers. Above these goods, the valuation may contain arbitrarily many value classes, subject to the condition that a single good in each class is worth at least the total value of all strictly lower-valued goods. The value classes, scaling factors, and parameters may vary across agents. We give an algorithm that computes an MMS allocation in $O(nm\log^2(2+m))$ time, where $n$ is the number of agents and $m$ is the number of goods.

1 Introduction

The paper asks whether exact MMS fairness is possible when agents retain additive tradeoffs among lower-valued goods but higher classes dominate all lower goods. It answers yes for three lower-value families, with arbitrarily many agent-specific higher classes, and gives a polynomial-time algorithm.

1.2 Related Work

1.1 Our Results

  • After positive scaling, the lower-part values may belong to one of three families: {0, 1, d, d + 1}, {0, 1, 2, 2e}, or {0, 1, 2, 3, 4}, for integers d, e ≥ 2.Source: §1.1 · p. 2
  • Each higher value class may be added when one good in it is worth at least the total value of all strictly lower-valued goods.The number of higher classes is unrestricted, and the condition permits equality.Source: §1.1 · p. 2
  • O(nm log^2(2 + m)) time suffices to compute an exact MMS allocation for instances in which every agent has the specified valuation structure.The lower family, scaling, integer parameter, higher classes, and class boundaries may vary across agents.Source: §1.1 · p. 2
  • The four-positive-value lower family permits additive substitutions, such as replacing a good worth four with goods worth three and two, while higher classes remain dominant.The result includes guarantees for {0, 1, 2} valuations, personalized bivalued valuations with integer ratios, and weakly lexicographic valuations.Source: §1.1 · p. 2
  • The algorithm selects an acceptable bundle by maximizing its increasing rank vector lexicographically, then assigns it to an agent who accepts it.It first finds the smallest spaced-rank prefix meeting some agent’s target, then moves selected ranks as far right as possible, prioritizing earlier ranks.Source: §1.1 · p. 2

1.2 Related Work

  • The algorithm extends the exact-MMS valuation domain but does not claim Pareto optimality or envy-freeness up to any good.Those additional guarantees are reported for weakly lexicographic valuations [Ebadian et al., 2022, Aziz et al., 2023, Hosseini et al., 2024].Source: §1.2 · p. 3
  • The rightmost-bundle rule generalizes earlier rank-selection approaches by choosing the whole rank vector lexicographically for arbitrary bundle sizes.Prior work includes spaced bundles [Ebadian et al., 2022], two-class choices [Feige, 2022], and rightward rank choices in approximation algorithms [Heidari et al., 2026, Huang and Zhou, 2025].Source: §1.2 · p. 3

2 Preliminaries

The preliminaries define additive valuations, maximin share, and the valuation structure used in the paper. They also establish fixed-target and ordered-instance conventions for the algorithm.

2 Preliminaries

  • An instance consists of agents, indivisible goods, and nonnegative additive valuations; an allocation partitions the goods, and an agent’s MMS is the best minimum bundle value over partitions into k bundles.An MMS-fair allocation gives every agent at least her MMS.Source: §2 · p. 4
  • A lexicographic extension has higher-value classes whose individual good value is at least the total value of all strictly lower-valued goods.The classes may be empty as a list, and the sum counts every lower-valued good with multiplicity; equality is allowed.Source: §2 · p. 4
  • Each agent’s lower part uses a positive scaling of one of the three specified value families, and deleting goods preserves the domain condition.Agents need not agree on their lower parts or value classes.Source: §2 · p. 4
  • The algorithm uses fixed targets no greater than each agent’s MMS; for exact MMS, targets equal the original MMS and are not recomputed.After sorting singleton values separately, auxiliary ranks give agents a common order while preserving their singleton-value multisets and MMS.Source: §2 · pp. 4–5

3 The Algorithm

The algorithm allocates goods one bundle at a time by choosing an acceptable bundle whose increasing rank vector is lexicographically largest. Theorem 3.1 guarantees exact MMS and also allows any fixed targets within each agent’s MMS.

3 The Algorithm

  • Among acceptable bundles of size q satisfying the rank bounds, the algorithm chooses the lexicographically largest increasing rank vector, maximizing each rank in order.The bounds ensure that a selected bundle uses at most ⌈X/k⌉ goods from any prefix of length X.Source: §3 · p. 5
  • With k agents remaining, the algorithm selects the smallest q for which the spaced bundle {u1, uk+1, …, u(q−1)k+1} meets an agent’s target.It then gives the selected bundle to an agent who accepts it, removes that agent and bundle, and transfers the rank allocation to the original goods.Source: §3 · p. 5
  • The spaced search exists when every remaining agent has a target partition, since the full spaced sequence is worth at least vi(U)/k to each agent.The first acceptable bundle contains no good worth zero to its recipient, because deleting such a good would contradict the minimal choice of q.Source: §3 · p. 5
  • Theorem 3.1 guarantees an exact MMS allocation in O(nm log^2(2 + m)) time and meets any fixed targets 0 ≤ ti ≤ μi.It also permits any choice of accepting recipient.Source: §3 · p. 5
  • For two identical agents with goods worth 13, 13, 13, 13, 3, 3, 2, 2, 2, changing only the final rank can leave 31 against an MMS of 32.The algorithm selects ranks (3, 4, 7, 8, 9), worth 32, and leaves 32; the whole rank-vector choice, not a final-rank change alone, secures the guarantee.Source: §3 · p. 6

4 Preserving MMS Across Value Classes

The proof preserves target partitions as higher value classes are added to lower valuations. The two partition properties needed by the allocation algorithm hold for the specified lower-value families and are preserved under the stated class-extension condition.

4 Preserving MMS Across Value Classes

  • Properties (i) and (ii) support allocation by preserving target partitions after selected goods are removed, including an additional high-ranked good when needed.Property (i) leaves a (k−1)-partition after a qualifying bundle is removed; property (ii) leaves a (k−2)-partition after removing Sqv and u2.Source: §4 · p. 6
  • Adding any finite sequence of higher classes preserves both partition properties when each class value is at least the total value of existing goods.The bound on the number of upper classes is therefore unnecessary, but the extension assumptions matter: property (ii) need not hold for arbitrary additive valuations.Source: §4 · p. 6

4.1 MMS after Adding a Higher Value Class

  • If a higher class has a goods worth H, with H at least the total value of lower goods, MMS equals ℓH plus the (k−r)-MMS of the lower goods when a = kℓ + r.Repeated application reduces MMS computation across value classes to the lower part.Source: §4.1 · pp. 6–7

4.2 Proof Idea for the Extension Theorem

  • When upper goods are divisible into k equal groups, leftover upper goods can replace lower target bundles lost through removals; when none remain, the rightmost choice preserves the lower target partition.The extension proof uses the two partition properties to retain all k−1 remaining target bundles.Source: §4.2 · p. 7

4.3 The Two Properties for the Lower Valuations

  • Every positive scaling of the lower families {0, 1, d, d + 1}, {0, 1, 2, 2e}, and {0, 1, 2, 3, 4} satisfies properties (i) and (ii).Their partition conditions account for both total value and the availability of goods needed to complete bundles.Source: §4.3 · p. 7

4.4 Completing the Proof of Theorem 3.1

  • Theorem 3.1’s proof applies the preserved properties inductively: removing a selected bundle leaves each remaining agent a target partition, and the final transfer meets the original targets.For stronger targets, the proof also shows that the selected bundle continues to satisfy property (i) at each agent’s MMS.Source: §4.4 · p. 8

5 Efficient Implementation

The implementation avoids enumerating candidate bundles by maximizing their ranks coordinate by coordinate with binary search. Data structures support fast acceptability tests, yielding the stated time and space bounds.

5 Efficient Implementation

  • For a fixed rank prefix, the earliest possible completion is acceptable exactly when any completion is acceptable, so binary search finds the largest admissible next rank.Its ranks are rℓ = max{(ℓ−1)k + 1, r + ℓ−j} for ℓ = j, …, q; as r increases, its value to every agent weakly decreases.Source: §5 · p. 8
  • A binary indexed tree supplies interval sums and deletions in logarithmic time, while stored spaced-sequence sums evaluate a proposed completion using one interval query and one suffix sum.The same section computes initial targets by sorting and grouping values, testing at most five lower-part positions per agent, and applying one step per upper class.Source: §5 · pp. 8–9
  • O(nm log^2(2 + m)) operations suffice for all coordinate searches, with O(nm log(2 + m)) additional work and O(nm) total space.The stated operation bounds count arithmetic operations and comparisons.Source: §5 · pp. 8–9

6 Discussion

The discussion explains why the theorem works for lower-valued goods with additive tradeoffs and upper classes, and shows that weakening the upper-value condition can defeat the algorithm’s guarantee without defeating MMS existence. It also identifies open questions about other lower-value families and combining MMS with EFX.

6 Discussion

  • An extra upper good can replace a lower target bundle, while lower valuations bound target bundles lost under removals, preserving the whole target partition.The proof preserves the partition itself, not merely enough total value for it.Source: §6 · p. 9
  • For two identical agents, relaxing the upper-good threshold to any fixed (1−ε) fraction of the lower total does not retain the algorithm’s guarantee, although exact MMS still exists.The displayed partition is an exact MMS allocation.Source: §6 · p. 9
  • Open questions include which other lower valuations satisfy the two partition properties and whether exact MMS can be combined with EFX in this larger domain.The latter question is posed for envy-freeness up to any good.Source: §6 · p. 9

Declaration of generative AI use

  • The author reports using GPT-6 to explore proof ideas and revise the exposition, while taking responsibility for checking the arguments and the paper’s contents.Source: Declaration of generative AI use · p. 9

A Target Partitions and MMS Formulas for the Lower Valuations

This appendix establishes necessary and sufficient conditions for target partitions of the lower-valued goods and derives MMS formulas for three value families. Its arguments use balancing and deficit bounds to handle indivisible goods.

A Target Partitions and MMS Formulas for the Lower Valuations

A.1 Values {0, 1, d, d + 1}

  • For {0, 1, d, d + 1}, a target is feasible exactly when total-value and two additional inequalities hold, with automatic cases when the relevant residues are zero.The inequalities are dx + a + c ≥ kt, ρx + a + c ≥ kρ(λ + 1), and σx + c ≥ kσ(η + 1).Source: §A.1 · p. 13
  • For {0, 1, d, d + 1}, the minimum number of unit goods required is max{kt − dx − a, ρ[k(λ + 1) − x] − a, σ[k(η + 1) − x], 0}.The target partition exists when this number is at most c.Source: §A.1 · p. 14

A.2 Values {0, 1, 2, 2e}

  • For values {0, 1, 2, 2e}, MMS is the minimum of the total-value bound and three bounds based on balanced counts.The formula is given explicitly in terms of the counts a, b, c and the balanced-count parameters.Source: §A.2 · pp. 14–15

A.3 Values {0, 1, 2, 3, 4}

  • For {0, 1, 2, 3, 4}, a target partition requires total value plus at most three additional inequalities, with applicable rows determined by t’s parity and residues modulo three and four.The conditions are necessary and sufficient.Source: §A.3 · p. 15
  • For values {0, 1, 2, 3, 4}, MMS is the minimum of the total-value bound and six bounds derived from residue weights.The six weights are P + Y, P + A, P + Z + A, P, P + Z, and P + Z + Y.Source: §A.3 · p. 17

B.1 Proof of Lemma 4.3: Property (i)

The proof establishes property (i) for lower valuations by analyzing a lexicographically maximal bundle and using rank-based exchange or Lemma B.2 to derive removal or a contradiction, then checking the partition conditions family by family, including the inequality argument for values {0, 1, 2, 3, 4}.

B.1.1 An exchange for consecutive ranks

  • Removing Rq−1 from a k-partition into bundles worth at least t leaves k −1 bundles worth at least t.The exchange matches goods of Rq−1 with at least-as-valuable goods in one original bundle, then redistributes that bundle’s remainder.Source: §B.1.1 · p. 18

Values {0, 1, d, d + 1}

  • After the allocation, the second partition inequality holds with k−1 replacing k; Lemma A.1 then partitions the remaining goods into k−1 bundles, each worth at least t.Source: Values {0, 1, d, d + 1} · p. 19

Values {0, 1, 2, 2e}

  • For {0, 1, 2, 2e}, count bounds handle targets reached by high goods, twos, or ones and preserve every inequality of Lemma A.3.The proof divides into those three target cases and verifies the corresponding weighted inequalities.Source: Values {0, 1, 2, 2e} · p. 20

Values {0, 1, 2, 3, 4}

  • For {0, 1, 2, 3, 4}, ceiling-rounded cumulative rank counts support contradictions in the parity and several modulus-three and modulus-four remainder cases.The passages establish the modulus-four remainder-one, modulus-three remainder-one, modulus-four remainder-two, and modulus-four remainder-three cases.Source: Values {0, 1, 2, 3, 4} · pp. 21–22
  • For values {0, 1, 2, 3, 4}, the remaining count conditions force a contradiction, and every inequality of Lemma A.5 is preserved.The argument derives q = J and then makes R_{J−1} acceptable, contradicting its rejection.Source: Values {0, 1, 2, 3, 4} · p. 23

B.1.3 Why the rightmost choice permits removal

  • A lexicographically maximal bundle either allows removal via Lemma B.1 or B.2, or must be analyzed as an over-target bundle with a rejected consecutive rank reduction.The proof uses coordinatewise comparison with R_{q−1}; selected zero- or one-valued goods can be excluded, and rightward replacements preserve membership while maintaining the lexicographic comparison.Source: §B.1.3 · p. 23
  • For values {0, 1, d, d+1}, any over-target bundle yields an acceptable rank reduction, so Lemma B.2 proves the claim.The last spaced value must be d; either the consecutive bundle is at least as valuable as B, or the rank reduction has no more d-goods than B and is at least as valuable.Source: §B.1.3 · p. 23
  • For values {0, 1, 2, 2e}, rounding the target up to the next even integer makes the over-target bundle meet that target, allowing Lemma B.2 to apply.The proof first rules out a last spaced value of 2e and shows there are no remaining ones; feasibility and acceptance are unchanged by rounding.Source: §B.1.3 · p. 23
  • For values {0, 1, 2, 3, 4}, the cases with a last spaced value of 3 or selected threes are contradictory; otherwise rounding to an even target lets Lemma B.2 apply.The proof rules out the three-valued cases by counting positive goods and value classes; in the remaining cases, positive values are only two and four.Source: §B.1.3 · p. 24

B.2 Proof of Lemma 4.3: Property (ii)

This section proves property (ii) by bounding the weight removed with a spaced bundle and one extra good. The bound covers most partition inequalities at once, leaving only small targets to check for each valuation family.

B.2 Proof of Lemma 4.3: Property (ii)

  • The analysis considers the bundle B∗ formed from the first acceptable spaced bundle and one additional good, with k ≥3.It writes q=qv and z=v(u2) for the spaced-bundle size and the value of the additional good.Source: §B.2 · p. 24

B.2.1 A bound on the removed weight

  • A bound on removed weight preserves most partition inequalities at once, after which the proof checks the remaining small targets family by family.The bound concerns nonnegative nondecreasing singleton weights with zero weight at value zero, under a target at least twice the maximum used singleton weight.Source: §B.2.1 · p. 24
  • The proof expresses the singleton weight as a nonnegative combination of nested value-prefix indicators and bounds the goods taken from each prefix.A spaced sequence takes at most ⌈X/k⌉ goods from a prefix of size X; the additional good has weight at most the maximum used weight.Source: §B.2.1 · p. 25

B.2.2 Proof of property (ii)

The proof establishes property (ii) by showing that removing the chosen spaced bundle and one extra good preserves the required target partitions. It handles total value and partition inequalities across each of the three lower-valuation families.

B.2.2 Proof of property (ii)

  • When q=1, removing at most two goods destroys at most two original partition parts; for q≥2, the proof bounds the total value removed.For q≥3, it uses a bound involving the last spaced value; a two-good spaced target may need special treatment.Source: §B.2.2 · p. 25

Values {0, 1, 2, 3, 4}

  • For values {0, 1, 2, 3, 4}, every applicable partition inequality survives removal, proving property (ii) for this family.The proof checks total value and several count-weight rows, including exceptional small targets.Source: Values {0, 1, 2, 3, 4} · pp. 25–26

Values {0, 1, d, d + 1}

  • For values {0, 1, d, d + 1}, all criteria survive removal, and the total-value criterion is preserved.The proof separates the total-value case from the W1 and W2 criteria, including exceptional small-target cases.Source: Values {0, 1, d, d + 1} · pp. 26–27

Values {0, 1, 2, 2e}

  • For values {0, 1, 2, 2e}, all four inequalities are preserved, completing the proof of property (ii) for this family.The proof treats total value and the W1, W2, and W3 criteria, with separate checks for exceptional targets.Source: Values {0, 1, 2, 2e} · pp. 27–28

C Proof of Theorem 4.1

The proof derives a removal rule for goods beyond the first acceptable spaced bundle. Rank and prefix-count bounds let it retain target partitions after additional goods are removed.

C.1 Additional Removals

  • Lemma C.1 allows additional removals while preserving target partitions, subject to bounds on total removals and removals from every rank prefix.For a prefix of length X, the bound is |B ∩ {u1, . . . , uX}| ≤ ⌈X/k⌉ + d, with |B| ≤ qv + d.Source: §C.1 · p. 29
  • For d=1, the rank bounds make the removed goods componentwise no earlier than the first acceptable spaced bundle plus one good.The complement therefore has at least the same remaining values at corresponding positions, so a target partition transfers to it.Source: §C.1 · p. 29
  • For d>1, removing the first d−1 members of B reduces the remaining case to d=1 and leaves at least k−d−1 target bundles.If B has fewer than d−1 goods, deleting it directly destroys at most d−1 original partition parts.Source: §C.1 · p. 29

C.2 Proof of the Extension Theorem

The proof extends the allocation properties to added value classes by combining spare upper goods with lower-valued partitions. Its cases show that the argument remains valid after deletions and can be iterated across finitely many classes.

C.2 Proof of the Extension Theorem

  • For t ≤ ℓH, deleting at most q0 goods leaves enough upper goods for k − 1 targets; deleting at most q0 + d also leaves enough for k − d − 1 targets.Here q0 = ⌈t/H⌉ ≤ ℓ.Source: §C.2 · p. 29
  • For t > ℓH, the proof separates the upper contribution ℓH from a lower target s, with distinct target-size cases when r is positive or zero.When ℓ = 0, discarding partition parts containing removed goods establishes both properties.Source: §C.2 · p. 29
  • For property (i), spare upper goods cover residual bundles directly or combine with surviving lower partition parts in the r > 0 and r = 0 cases.When r = 0 and no upper goods remain spare, the lexicographic comparison reduces the claim to property (i) for the lower valuation.Source: §C.2 · pp. 29–30
  • For the additional-removal conclusion, the r > 0 case uses spare upper goods and deletes at most c affected lower parts; the r = 0 case applies Lemma C.1 with adjusted d′.The z spare upper goods cover residual bundles after the lower partition leaves h − z targets.Source: §C.2 · p. 30
  • The extension argument iterates across any finite number of classes because the defining condition survives deletions.Constructed lower bundles receive ℓ upper goods, while upper-only bundles receive at least ℓ + 1.Source: §C.2 · p. 30

D Running-Time Bounds in Theorem 3.1

The running-time analysis recognizes each agent’s valuation, computes exact MMS targets, and searches for acceptable bundles using rank-based data structures. Together these steps yield the stated O(nm log^2(2 + m)) allocation time.

D.1 Finding a Lower Part

  • Lower-part recognition tests at most five candidate prefixes and checks the defining condition on higher classes in linear time.Membership in the scaled lower-value families is checked with a constant number of tests, giving O(nm log(2 + m)) total recognition time after sorting.Source: §D.1 · p. 31

D.2 Computing Exact MMS Values

  • Exact MMS values are computed by processing higher classes in decreasing order, then evaluating the lower-part formula; this takes O(nm) operations after sorting.At each higher class, add ⌊a/k⌋H and replace k by k − (a mod k).Source: §D.2 · p. 31

D.3 Finding the Rightmost Acceptable Bundle

  • Fenwick trees provide logarithmic interval-sum queries over unallocated ranks, while stored spaced-suffix sums let the search evaluate candidate bundles.The candidate bundle value combines a fixed prefix, an interval sum, and a spaced-suffix sum.Source: §D.3 · pp. 31–32
  • Binary search selects the largest acceptable rank at each coordinate, checking all remaining agents rather than choosing a recipient in advance.The procedure returns the bundle specified by Algorithm 1 and leaves recipient choice unrestricted.Source: §D.3 · pp. 31–32
  • Coordinate searches and tree updates give total allocation time O(nm log^2(2 + m)); final transfers and stored arrays, trees, and lists use O(nm) time and space, respectively.Each allocated bundle contains q actual goods, so the total of kq across iterations is at most nm.Source: §D.3 · p. 32
Loading 2610.00159v1…